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<>(); 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 @Override 057 public boolean acceptsMember(RelationMember m) { 058 return "address".equals(m.getRole()) || "house".equals(m.getRole()); 059 } 060 061 @Override 062 public List<RelationMember> sortMembers(List<RelationMember> list) { 063 Collections.sort(list, new Comparator<RelationMember>() { 064 @Override 065 public int compare(RelationMember a, RelationMember b) { 066 final int houseNumber = AlphanumComparator.getInstance().compare( 067 a.getMember().get("addr:housenumber"), 068 b.getMember().get("addr:housenumber")); 069 if (houseNumber != 0) { 070 return houseNumber; 071 } 072 final String aDisplayName = a.getMember().getDisplayName(DefaultNameFormatter.getInstance()); 073 final String bDisplayName = b.getMember().getDisplayName(DefaultNameFormatter.getInstance()); 074 return AlphanumComparator.getInstance().compare(aDisplayName, bDisplayName); 075 } 076 }); 077 return list; 078 } 079 } 080 081 /** 082 * Sort a collection of relation members by the way they are linked. 083 * 084 * @param relationMembers collection of relation members 085 * @return sorted collection of relation members 086 */ 087 public List<RelationMember> sortMembers(List<RelationMember> relationMembers) { 088 List<RelationMember> newMembers = new ArrayList<>(); 089 090 // Sort members with custom mechanisms (relation-dependent) 091 List<RelationMember> defaultMembers = new ArrayList<>(relationMembers.size()); 092 // Maps sorter to assigned members for sorting. Use LinkedHashMap to retain order. 093 Map<AdditionalSorter, List<RelationMember>> customMap = new LinkedHashMap<>(); 094 095 // Dispatch members to the first adequate sorter 096 for (RelationMember m : relationMembers) { 097 boolean wasAdded = false; 098 for (AdditionalSorter sorter : additionalSorters) { 099 if (sorter.acceptsMember(m)) { 100 List<RelationMember> list; 101 list = customMap.get(sorter); 102 if (list == null) { 103 customMap.put(sorter, list = new LinkedList<>()); 104 } 105 list.add(m); 106 wasAdded = true; 107 break; 108 } 109 } 110 if (!wasAdded) { 111 defaultMembers.add(m); 112 } 113 } 114 115 // Sort members and add them to result 116 for (Entry<AdditionalSorter, List<RelationMember>> entry : customMap.entrySet()) { 117 newMembers.addAll(entry.getKey().sortMembers(entry.getValue())); 118 } 119 newMembers.addAll(sortMembersByConnectivity(defaultMembers)); 120 return newMembers; 121 } 122 123 public static List<RelationMember> sortMembersByConnectivity(List<RelationMember> defaultMembers) { 124 125 List<RelationMember> newMembers = new ArrayList<>(); 126 127 RelationNodeMap map = new RelationNodeMap(defaultMembers); 128 // List of groups of linked members 129 // 130 List<LinkedList<Integer>> allGroups = new ArrayList<>(); 131 132 // current group of members that are linked among each other 133 // Two successive members are always linked i.e. have a common node. 134 // 135 LinkedList<Integer> group; 136 137 Integer first; 138 while ((first = map.pop()) != null) { 139 group = new LinkedList<>(); 140 group.add(first); 141 142 allGroups.add(group); 143 144 Integer next = first; 145 while ((next = map.popAdjacent(next)) != null) { 146 group.addLast(next); 147 } 148 149 // The first element need not be in front of the list. 150 // So the search goes in both directions 151 // 152 next = first; 153 while ((next = map.popAdjacent(next)) != null) { 154 group.addFirst(next); 155 } 156 } 157 158 for (LinkedList<Integer> tmpGroup : allGroups) { 159 for (Integer p : tmpGroup) { 160 newMembers.add(defaultMembers.get(p)); 161 } 162 } 163 164 // Finally, add members that have not been sorted at all 165 for (Integer i : map.getNotSortableMembers()) { 166 newMembers.add(defaultMembers.get(i)); 167 } 168 169 return newMembers; 170 } 171 172}