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