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 customMap.put(sorter, list = new LinkedList<>()); 157 } 158 list.add(m); 159 wasAdded = true; 160 break; 161 } 162 } 163 if (!wasAdded) { 164 defaultMembers.add(m); 165 } 166 } 167 168 // Sort members and add them to result 169 for (Entry<AdditionalSorter, List<RelationMember>> entry : customMap.entrySet()) { 170 newMembers.addAll(entry.getKey().sortMembers(entry.getValue())); 171 } 172 newMembers.addAll(sortMembersByConnectivity(defaultMembers)); 173 return newMembers; 174 } 175 176 public static List<RelationMember> sortMembersByConnectivity(List<RelationMember> defaultMembers) { 177 178 List<RelationMember> newMembers = new ArrayList<>(); 179 180 RelationNodeMap map = new RelationNodeMap(defaultMembers); 181 // List of groups of linked members 182 // 183 List<LinkedList<Integer>> allGroups = new ArrayList<>(); 184 185 // current group of members that are linked among each other 186 // Two successive members are always linked i.e. have a common node. 187 // 188 LinkedList<Integer> group; 189 190 Integer first; 191 while ((first = map.pop()) != null) { 192 group = new LinkedList<>(); 193 group.add(first); 194 195 allGroups.add(group); 196 197 Integer next = first; 198 while ((next = map.popAdjacent(next)) != null) { 199 group.addLast(next); 200 } 201 202 // The first element need not be in front of the list. 203 // So the search goes in both directions 204 // 205 next = first; 206 while ((next = map.popAdjacent(next)) != null) { 207 group.addFirst(next); 208 } 209 } 210 211 for (List<Integer> tmpGroup : allGroups) { 212 for (Integer p : tmpGroup) { 213 newMembers.add(defaultMembers.get(p)); 214 } 215 } 216 217 // Finally, add members that have not been sorted at all 218 for (Integer i : map.getNotSortableMembers()) { 219 newMembers.add(defaultMembers.get(i)); 220 } 221 222 return newMembers; 223 } 224 225}