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.Collections;
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;
014
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.gui.DefaultNameFormatter;
019import org.openstreetmap.josm.tools.AlphanumComparator;
020import org.openstreetmap.josm.tools.Utils;
021
022public class RelationSorter {
023
024    private interface AdditionalSorter {
025        boolean acceptsMember(RelationMember m);
026
027        List<RelationMember> sortMembers(List<RelationMember> list);
028    }
029
030    private static final Collection<AdditionalSorter> additionalSorters = new ArrayList<>();
031    static {
032        // first adequate sorter is used, so order matters
033        additionalSorters.add(new AssociatedStreetRoleStreetSorter());
034        additionalSorters.add(new AssociatedStreetRoleAddressHouseSorter());
035        additionalSorters.add(new PublicTransportRoleStopPlatformSorter());
036    }
037
038    /**
039     * Class that sorts the {@code street} members of
040     * {@code type=associatedStreet} and {@code type=street} relations.
041     */
042    private static class AssociatedStreetRoleStreetSorter implements AdditionalSorter {
043
044        @Override
045        public boolean acceptsMember(RelationMember m) {
046            return "street".equals(m.getRole());
047        }
048
049        @Override
050        public List<RelationMember> sortMembers(List<RelationMember> list) {
051            return sortMembersByConnectivity(list);
052        }
053    }
054
055    /**
056     * Class that sorts the {@code address} and {@code house} members of
057     * {@code type=associatedStreet} and {@code type=street} relations.
058     */
059    private static class AssociatedStreetRoleAddressHouseSorter implements AdditionalSorter {
060
061        @Override
062        public boolean acceptsMember(RelationMember m) {
063            return "address".equals(m.getRole()) || "house".equals(m.getRole());
064        }
065
066        @Override
067        public List<RelationMember> sortMembers(List<RelationMember> list) {
068            Collections.sort(list, new Comparator<RelationMember>() {
069                @Override
070                public int compare(RelationMember a, RelationMember 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            });
082            return list;
083        }
084    }
085
086    /**
087     * Class that sorts the {@code platform} and {@code stop} members of
088     * {@code type=public_transport} relations.
089     */
090    private static class PublicTransportRoleStopPlatformSorter implements AdditionalSorter {
091
092        @Override
093        public boolean acceptsMember(RelationMember m) {
094            return m.getRole() != null && (m.getRole().startsWith("platform") || m.getRole().startsWith("stop"));
095        }
096
097        private static String getStopName(OsmPrimitive p) {
098            for (Relation ref : Utils.filteredCollection(p.getReferrers(), Relation.class)) {
099                if (ref.hasTag("type", "public_transport") && ref.hasTag("public_transport", "stop_area") && ref.getName() != null) {
100                    return ref.getName();
101                }
102            }
103            return 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 : additionalSorters) {
152                if (sorter.acceptsMember(m)) {
153                    List<RelationMember> list;
154                    list = customMap.get(sorter);
155                    if (list == null) {
156                        list = new LinkedList<>();
157                        customMap.put(sorter, list);
158                    }
159                    list.add(m);
160                    wasAdded = true;
161                    break;
162                }
163            }
164            if (!wasAdded) {
165                defaultMembers.add(m);
166            }
167        }
168
169        // Sort members and add them to result
170        for (Entry<AdditionalSorter, List<RelationMember>> entry : customMap.entrySet()) {
171            newMembers.addAll(entry.getKey().sortMembers(entry.getValue()));
172        }
173        newMembers.addAll(sortMembersByConnectivity(defaultMembers));
174        return newMembers;
175    }
176
177    public static List<RelationMember> sortMembersByConnectivity(List<RelationMember> defaultMembers) {
178
179        List<RelationMember> newMembers = new ArrayList<>();
180
181        RelationNodeMap map = new RelationNodeMap(defaultMembers);
182        // List of groups of linked members
183        //
184        List<LinkedList<Integer>> allGroups = new ArrayList<>();
185
186        // current group of members that are linked among each other
187        // Two successive members are always linked i.e. have a common node.
188        //
189        LinkedList<Integer> group;
190
191        Integer first;
192        while ((first = map.pop()) != null) {
193            group = new LinkedList<>();
194            group.add(first);
195
196            allGroups.add(group);
197
198            Integer next = first;
199            while ((next = map.popAdjacent(next)) != null) {
200                group.addLast(next);
201            }
202
203            // The first element need not be in front of the list.
204            // So the search goes in both directions
205            //
206            next = first;
207            while ((next = map.popAdjacent(next)) != null) {
208                group.addFirst(next);
209            }
210        }
211
212        for (List<Integer> tmpGroup : allGroups) {
213            for (Integer p : tmpGroup) {
214                newMembers.add(defaultMembers.get(p));
215            }
216        }
217
218        // Finally, add members that have not been sorted at all
219        for (Integer i : map.getNotSortableMembers()) {
220            newMembers.add(defaultMembers.get(i));
221        }
222
223        return newMembers;
224    }
225
226}