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