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.HashMap; 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.DefaultNameFormatter; 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.tools.AlphanumComparator; 019 020/** 021 * This class sorts the relation members by connectivity. 022 * <p> 023 * Multiple {@link AdditionalSorter}s are implemented to handle special relation types. 024 */ 025public class RelationSorter { 026 027 private interface AdditionalSorter { 028 boolean acceptsMember(RelationMember m); 029 030 List<RelationMember> sortMembers(List<RelationMember> list); 031 } 032 033 private static final Collection<AdditionalSorter> ADDITIONAL_SORTERS = Arrays.asList( 034 // first adequate sorter is used, so order matters 035 new AssociatedStreetRoleStreetSorter(), 036 new AssociatedStreetRoleAddressHouseSorter(), 037 new PublicTransportRoleStopPlatformSorter() 038 ); 039 040 /** 041 * Class that sorts the {@code street} members of 042 * {@code type=associatedStreet} and {@code type=street} relations. 043 */ 044 private static class AssociatedStreetRoleStreetSorter implements AdditionalSorter { 045 046 @Override 047 public boolean acceptsMember(RelationMember m) { 048 return "street".equals(m.getRole()); 049 } 050 051 @Override 052 public List<RelationMember> sortMembers(List<RelationMember> list) { 053 return sortMembersByConnectivity(list); 054 } 055 } 056 057 /** 058 * Class that sorts the {@code address} and {@code house} members of 059 * {@code type=associatedStreet} and {@code type=street} relations. 060 */ 061 private static class AssociatedStreetRoleAddressHouseSorter implements AdditionalSorter { 062 063 @Override 064 public boolean acceptsMember(RelationMember m) { 065 return "address".equals(m.getRole()) || "house".equals(m.getRole()); 066 } 067 068 @Override 069 public List<RelationMember> sortMembers(List<RelationMember> list) { 070 list.sort((a, 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 return list; 082 } 083 } 084 085 /** 086 * Class that sorts the {@code platform} and {@code stop} members of 087 * {@code type=public_transport} relations. 088 */ 089 private static class PublicTransportRoleStopPlatformSorter implements AdditionalSorter { 090 091 @Override 092 public boolean acceptsMember(RelationMember m) { 093 return m.getRole() != null && (m.getRole().startsWith("platform") || m.getRole().startsWith("stop")); 094 } 095 096 private static String getStopName(OsmPrimitive p) { 097 return p.referrers(Relation.class) 098 .filter(ref -> ref.hasTag("type", "public_transport") 099 && ref.hasTag("public_transport", "stop_area") 100 && ref.getName() != null) 101 .map(Relation::getName) 102 .findFirst() 103 .orElse(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 : ADDITIONAL_SORTERS) { 152 if (sorter.acceptsMember(m)) { 153 wasAdded = customMap.computeIfAbsent(sorter, k -> new LinkedList<>()).add(m); 154 break; 155 } 156 } 157 if (!wasAdded) { 158 defaultMembers.add(m); 159 } 160 } 161 162 // Sort members and add them to result 163 for (Entry<AdditionalSorter, List<RelationMember>> entry : customMap.entrySet()) { 164 newMembers.addAll(entry.getKey().sortMembers(entry.getValue())); 165 } 166 newMembers.addAll(sortMembersByConnectivity(defaultMembers)); 167 return newMembers; 168 } 169 170 /** 171 * Sorts a list of members by connectivity 172 * @param defaultMembers The members to sort 173 * @return A sorted list of the same members 174 */ 175 public static List<RelationMember> sortMembersByConnectivity(List<RelationMember> defaultMembers) { 176 177 List<RelationMember> newMembers = new ArrayList<>(); 178 179 RelationNodeMap map = new RelationNodeMap(defaultMembers); 180 // List of groups of linked members 181 // 182 List<LinkedList<Integer>> allGroups = new ArrayList<>(); 183 184 // current group of members that are linked among each other 185 // Two successive members are always linked i.e. have a common node. 186 // 187 LinkedList<Integer> group; 188 189 Integer first; 190 while ((first = map.pop()) != null) { 191 group = new LinkedList<>(); 192 group.add(first); 193 194 allGroups.add(group); 195 196 Integer next = first; 197 while ((next = map.popAdjacent(next)) != null) { 198 group.addLast(next); 199 } 200 201 // The first element need not be in front of the list. 202 // So the search goes in both directions 203 // 204 next = first; 205 while ((next = map.popAdjacent(next)) != null) { 206 group.addFirst(next); 207 } 208 } 209 210 for (List<Integer> tmpGroup : allGroups) { 211 for (Integer p : tmpGroup) { 212 newMembers.add(defaultMembers.get(p)); 213 } 214 } 215 216 // Finally, add members that have not been sorted at all 217 for (Integer i : map.getNotSortableMembers()) { 218 newMembers.add(defaultMembers.get(i)); 219 } 220 221 return newMembers; 222 } 223 224}