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