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