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