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}