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.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.RelationMember;
015import org.openstreetmap.josm.gui.DefaultNameFormatter;
016import org.openstreetmap.josm.tools.AlphanumComparator;
017
018public class RelationSorter {
019
020    private static interface AdditionalSorter {
021        public boolean acceptsMember(RelationMember m);
022        public List<RelationMember> sortMembers(List<RelationMember> list);
023    }
024
025    private static final Collection<AdditionalSorter> additionalSorters = new ArrayList<AdditionalSorter>();
026
027    static {
028        // first adequate sorter is used, so order matters
029        additionalSorters.add(new AssociatedStreetRoleStreetSorter());
030        additionalSorters.add(new AssociatedStreetRoleAddressHouseSorter());
031    }
032
033    /**
034     * Class that sorts the {@code street} members of
035     * {@code type=associatedStreet} and {@code type=street} relations.
036     */
037    private static class AssociatedStreetRoleStreetSorter implements AdditionalSorter {
038
039        @Override
040        public boolean acceptsMember(RelationMember m) {
041            return "street".equals(m.getRole());
042        }
043
044        @Override
045        public List<RelationMember> sortMembers(List<RelationMember> list) {
046            return sortMembersByConnectivity(list);
047        }
048    }
049
050    /**
051     * Class that sorts the {@code address} and {@code house} members of
052     * {@code type=associatedStreet} and {@code type=street} relations.
053     */
054    private static class AssociatedStreetRoleAddressHouseSorter implements AdditionalSorter {
055
056        public static final AlphanumComparator ALPHANUM_COMPARATOR = new AlphanumComparator();
057
058        @Override
059        public boolean acceptsMember(RelationMember m) {
060            return "address".equals(m.getRole()) || "house".equals(m.getRole());
061        }
062
063        @Override
064        public List<RelationMember> sortMembers(List<RelationMember> list) {
065            Collections.sort(list, new Comparator<RelationMember>() {
066                @Override
067                public int compare(RelationMember a, RelationMember b) {
068                    final int houseNumber = ALPHANUM_COMPARATOR.compare(
069                            a.getMember().get("addr:housenumber"),
070                            b.getMember().get("addr:housenumber"));
071                    if (houseNumber != 0) {
072                        return houseNumber;
073                    }
074                    final String aDisplayName = a.getMember().getDisplayName(DefaultNameFormatter.getInstance());
075                    final String bDisplayName = b.getMember().getDisplayName(DefaultNameFormatter.getInstance());
076                    return ALPHANUM_COMPARATOR.compare(aDisplayName, bDisplayName);
077                }
078            });
079            return list;
080        }
081    }
082
083    /**
084     * Sort a collection of relation members by the way they are linked.
085     *
086     * @param relationMembers collection of relation members
087     * @return sorted collection of relation members
088     */
089    public List<RelationMember> sortMembers(List<RelationMember> relationMembers) {
090        List<RelationMember> newMembers = new ArrayList<RelationMember>();
091
092        // Sort members with custom mechanisms (relation-dependent)
093        List<RelationMember> defaultMembers = new ArrayList<RelationMember>(relationMembers.size());
094        // Maps sorter to assigned members for sorting. Use LinkedHashMap to retain order.
095        Map<AdditionalSorter, List<RelationMember>> customMap = new LinkedHashMap<AdditionalSorter, List<RelationMember>>();
096
097        // Dispatch members to the first adequate sorter
098        for (RelationMember m : relationMembers) {
099            boolean wasAdded = false;
100            for (AdditionalSorter sorter : additionalSorters) {
101                if (sorter.acceptsMember(m)) {
102                    List<RelationMember> list;
103                    list = customMap.get(sorter);
104                    if (list == null) {
105                        customMap.put(sorter, list = new LinkedList<RelationMember>());
106                    }
107                    list.add(m);
108                    wasAdded = true;
109                    break;
110                }
111            }
112            if (!wasAdded) {
113                defaultMembers.add(m);
114            }
115        }
116
117        // Sort members and add them to result
118        for (Entry<AdditionalSorter, List<RelationMember>> entry : customMap.entrySet()) {
119            newMembers.addAll(entry.getKey().sortMembers(entry.getValue()));
120        }
121        newMembers.addAll(sortMembersByConnectivity(defaultMembers));
122        return newMembers;
123    }
124
125    public static List<RelationMember> sortMembersByConnectivity(List<RelationMember> defaultMembers) {
126
127        List<RelationMember> newMembers = new ArrayList<RelationMember>();
128
129        RelationNodeMap map = new RelationNodeMap(defaultMembers);
130        // List of groups of linked members
131        //
132        List<LinkedList<Integer>> allGroups = new ArrayList<LinkedList<Integer>>();
133
134        // current group of members that are linked among each other
135        // Two successive members are always linked i.e. have a common node.
136        //
137        LinkedList<Integer> group;
138
139        Integer first;
140        while ((first = map.pop()) != null) {
141            group = new LinkedList<Integer>();
142            group.add(first);
143
144            allGroups.add(group);
145
146            Integer next = first;
147            while ((next = map.popAdjacent(next)) != null) {
148                group.addLast(next);
149            }
150
151            // The first element need not be in front of the list.
152            // So the search goes in both directions
153            //
154            next = first;
155            while ((next = map.popAdjacent(next)) != null) {
156                group.addFirst(next);
157            }
158        }
159
160        for (LinkedList<Integer> tmpGroup : allGroups) {
161            for (Integer p : tmpGroup) {
162                newMembers.add(defaultMembers.get(p));
163            }
164        }
165
166        // Finally, add members that have not been sorted at all
167        for (Integer i : map.getNotSortableMembers()) {
168            newMembers.add(defaultMembers.get(i));
169        }
170
171        return newMembers;
172    }
173
174}