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