001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.gui.dialogs.relation.sort;
003
004import java.util.ArrayList;
005import java.util.Collection;
006import java.util.HashMap;
007import java.util.LinkedHashMap;
008import java.util.LinkedList;
009import java.util.List;
010import java.util.Map;
011import java.util.Map.Entry;
012
013import org.openstreetmap.josm.data.osm.OsmPrimitive;
014import org.openstreetmap.josm.data.osm.Relation;
015import org.openstreetmap.josm.data.osm.RelationMember;
016import org.openstreetmap.josm.gui.DefaultNameFormatter;
017import org.openstreetmap.josm.tools.AlphanumComparator;
018import org.openstreetmap.josm.tools.Utils;
019
020public class RelationSorter {
021
022    private interface AdditionalSorter {
023        boolean acceptsMember(RelationMember m);
024
025        List<RelationMember> sortMembers(List<RelationMember> list);
026    }
027
028    private static final Collection<AdditionalSorter> additionalSorters = new ArrayList<>();
029    static {
030        // first adequate sorter is used, so order matters
031        additionalSorters.add(new AssociatedStreetRoleStreetSorter());
032        additionalSorters.add(new AssociatedStreetRoleAddressHouseSorter());
033        additionalSorters.add(new PublicTransportRoleStopPlatformSorter());
034    }
035
036    /**
037     * Class that sorts the {@code street} members of
038     * {@code type=associatedStreet} and {@code type=street} relations.
039     */
040    private static class AssociatedStreetRoleStreetSorter implements AdditionalSorter {
041
042        @Override
043        public boolean acceptsMember(RelationMember m) {
044            return "street".equals(m.getRole());
045        }
046
047        @Override
048        public List<RelationMember> sortMembers(List<RelationMember> list) {
049            return sortMembersByConnectivity(list);
050        }
051    }
052
053    /**
054     * Class that sorts the {@code address} and {@code house} members of
055     * {@code type=associatedStreet} and {@code type=street} relations.
056     */
057    private static class AssociatedStreetRoleAddressHouseSorter implements AdditionalSorter {
058
059        @Override
060        public boolean acceptsMember(RelationMember m) {
061            return "address".equals(m.getRole()) || "house".equals(m.getRole());
062        }
063
064        @Override
065        public List<RelationMember> sortMembers(List<RelationMember> list) {
066            list.sort((a, b) -> {
067                final int houseNumber = AlphanumComparator.getInstance().compare(
068                        a.getMember().get("addr:housenumber"),
069                        b.getMember().get("addr:housenumber"));
070                if (houseNumber != 0) {
071                    return houseNumber;
072                }
073                final String aDisplayName = a.getMember().getDisplayName(DefaultNameFormatter.getInstance());
074                final String bDisplayName = b.getMember().getDisplayName(DefaultNameFormatter.getInstance());
075                return AlphanumComparator.getInstance().compare(aDisplayName, bDisplayName);
076            });
077            return list;
078        }
079    }
080
081    /**
082     * Class that sorts the {@code platform} and {@code stop} members of
083     * {@code type=public_transport} relations.
084     */
085    private static class PublicTransportRoleStopPlatformSorter implements AdditionalSorter {
086
087        @Override
088        public boolean acceptsMember(RelationMember m) {
089            return m.getRole() != null && (m.getRole().startsWith("platform") || m.getRole().startsWith("stop"));
090        }
091
092        private static String getStopName(OsmPrimitive p) {
093            for (Relation ref : Utils.filteredCollection(p.getReferrers(), Relation.class)) {
094                if (ref.hasTag("type", "public_transport") && ref.hasTag("public_transport", "stop_area") && ref.getName() != null) {
095                    return ref.getName();
096                }
097            }
098            return p.getName();
099        }
100
101        @Override
102        public List<RelationMember> sortMembers(List<RelationMember> list) {
103            final Map<String, RelationMember> platformByName = new HashMap<>();
104            for (RelationMember i : list) {
105                if (i.getRole().startsWith("platform")) {
106                    final RelationMember old = platformByName.put(getStopName(i.getMember()), i);
107                    if (old != null) {
108                        // Platform with same name present. Stop to avoid damaging complicated relations.
109                        // This case can happily be handled differently.
110                        return list;
111                    }
112                }
113            }
114            final List<RelationMember> sorted = new ArrayList<>(list.size());
115            for (RelationMember i : list) {
116                if (i.getRole().startsWith("stop")) {
117                    sorted.add(i);
118                    final RelationMember platform = platformByName.remove(getStopName(i.getMember()));
119                    if (platform != null) {
120                        sorted.add(platform);
121                    }
122                }
123            }
124            sorted.addAll(platformByName.values());
125            return sorted;
126        }
127    }
128
129    /**
130     * Sort a collection of relation members by the way they are linked.
131     *
132     * @param relationMembers collection of relation members
133     * @return sorted collection of relation members
134     */
135    public List<RelationMember> sortMembers(List<RelationMember> relationMembers) {
136        List<RelationMember> newMembers = new ArrayList<>();
137
138        // Sort members with custom mechanisms (relation-dependent)
139        List<RelationMember> defaultMembers = new ArrayList<>(relationMembers.size());
140        // Maps sorter to assigned members for sorting. Use LinkedHashMap to retain order.
141        Map<AdditionalSorter, List<RelationMember>> customMap = new LinkedHashMap<>();
142
143        // Dispatch members to the first adequate sorter
144        for (RelationMember m : relationMembers) {
145            boolean wasAdded = false;
146            for (AdditionalSorter sorter : additionalSorters) {
147                if (sorter.acceptsMember(m)) {
148                    List<RelationMember> list;
149                    list = customMap.get(sorter);
150                    if (list == null) {
151                        list = new LinkedList<>();
152                        customMap.put(sorter, list);
153                    }
154                    list.add(m);
155                    wasAdded = true;
156                    break;
157                }
158            }
159            if (!wasAdded) {
160                defaultMembers.add(m);
161            }
162        }
163
164        // Sort members and add them to result
165        for (Entry<AdditionalSorter, List<RelationMember>> entry : customMap.entrySet()) {
166            newMembers.addAll(entry.getKey().sortMembers(entry.getValue()));
167        }
168        newMembers.addAll(sortMembersByConnectivity(defaultMembers));
169        return newMembers;
170    }
171
172    public static List<RelationMember> sortMembersByConnectivity(List<RelationMember> defaultMembers) {
173
174        List<RelationMember> newMembers = new ArrayList<>();
175
176        RelationNodeMap map = new RelationNodeMap(defaultMembers);
177        // List of groups of linked members
178        //
179        List<LinkedList<Integer>> allGroups = new ArrayList<>();
180
181        // current group of members that are linked among each other
182        // Two successive members are always linked i.e. have a common node.
183        //
184        LinkedList<Integer> group;
185
186        Integer first;
187        while ((first = map.pop()) != null) {
188            group = new LinkedList<>();
189            group.add(first);
190
191            allGroups.add(group);
192
193            Integer next = first;
194            while ((next = map.popAdjacent(next)) != null) {
195                group.addLast(next);
196            }
197
198            // The first element need not be in front of the list.
199            // So the search goes in both directions
200            //
201            next = first;
202            while ((next = map.popAdjacent(next)) != null) {
203                group.addFirst(next);
204            }
205        }
206
207        for (List<Integer> tmpGroup : allGroups) {
208            for (Integer p : tmpGroup) {
209                newMembers.add(defaultMembers.get(p));
210            }
211        }
212
213        // Finally, add members that have not been sorted at all
214        for (Integer i : map.getNotSortableMembers()) {
215            newMembers.add(defaultMembers.get(i));
216        }
217
218        return newMembers;
219    }
220
221}