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.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.RelationMember; 015import org.openstreetmap.josm.gui.DefaultNameFormatter; 016import org.openstreetmap.josm.tools.AlphanumComparator; 017 018public class RelationSorter { 019 020 private static interface AdditionalSorter { 021 public boolean acceptsMember(RelationMember m); 022 public List<RelationMember> sortMembers(List<RelationMember> list); 023 } 024 025 private static final Collection<AdditionalSorter> additionalSorters = new ArrayList<AdditionalSorter>(); 026 027 static { 028 // first adequate sorter is used, so order matters 029 additionalSorters.add(new AssociatedStreetRoleStreetSorter()); 030 additionalSorters.add(new AssociatedStreetRoleAddressHouseSorter()); 031 } 032 033 /** 034 * Class that sorts the {@code street} members of 035 * {@code type=associatedStreet} and {@code type=street} relations. 036 */ 037 private static class AssociatedStreetRoleStreetSorter implements AdditionalSorter { 038 039 @Override 040 public boolean acceptsMember(RelationMember m) { 041 return "street".equals(m.getRole()); 042 } 043 044 @Override 045 public List<RelationMember> sortMembers(List<RelationMember> list) { 046 return sortMembersByConnectivity(list); 047 } 048 } 049 050 /** 051 * Class that sorts the {@code address} and {@code house} members of 052 * {@code type=associatedStreet} and {@code type=street} relations. 053 */ 054 private static class AssociatedStreetRoleAddressHouseSorter implements AdditionalSorter { 055 056 public static final AlphanumComparator ALPHANUM_COMPARATOR = new AlphanumComparator(); 057 058 @Override 059 public boolean acceptsMember(RelationMember m) { 060 return "address".equals(m.getRole()) || "house".equals(m.getRole()); 061 } 062 063 @Override 064 public List<RelationMember> sortMembers(List<RelationMember> list) { 065 Collections.sort(list, new Comparator<RelationMember>() { 066 @Override 067 public int compare(RelationMember a, RelationMember b) { 068 final int houseNumber = ALPHANUM_COMPARATOR.compare( 069 a.getMember().get("addr:housenumber"), 070 b.getMember().get("addr:housenumber")); 071 if (houseNumber != 0) { 072 return houseNumber; 073 } 074 final String aDisplayName = a.getMember().getDisplayName(DefaultNameFormatter.getInstance()); 075 final String bDisplayName = b.getMember().getDisplayName(DefaultNameFormatter.getInstance()); 076 return ALPHANUM_COMPARATOR.compare(aDisplayName, bDisplayName); 077 } 078 }); 079 return list; 080 } 081 } 082 083 /** 084 * Sort a collection of relation members by the way they are linked. 085 * 086 * @param relationMembers collection of relation members 087 * @return sorted collection of relation members 088 */ 089 public List<RelationMember> sortMembers(List<RelationMember> relationMembers) { 090 List<RelationMember> newMembers = new ArrayList<RelationMember>(); 091 092 // Sort members with custom mechanisms (relation-dependent) 093 List<RelationMember> defaultMembers = new ArrayList<RelationMember>(relationMembers.size()); 094 // Maps sorter to assigned members for sorting. Use LinkedHashMap to retain order. 095 Map<AdditionalSorter, List<RelationMember>> customMap = new LinkedHashMap<AdditionalSorter, List<RelationMember>>(); 096 097 // Dispatch members to the first adequate sorter 098 for (RelationMember m : relationMembers) { 099 boolean wasAdded = false; 100 for (AdditionalSorter sorter : additionalSorters) { 101 if (sorter.acceptsMember(m)) { 102 List<RelationMember> list; 103 list = customMap.get(sorter); 104 if (list == null) { 105 customMap.put(sorter, list = new LinkedList<RelationMember>()); 106 } 107 list.add(m); 108 wasAdded = true; 109 break; 110 } 111 } 112 if (!wasAdded) { 113 defaultMembers.add(m); 114 } 115 } 116 117 // Sort members and add them to result 118 for (Entry<AdditionalSorter, List<RelationMember>> entry : customMap.entrySet()) { 119 newMembers.addAll(entry.getKey().sortMembers(entry.getValue())); 120 } 121 newMembers.addAll(sortMembersByConnectivity(defaultMembers)); 122 return newMembers; 123 } 124 125 public static List<RelationMember> sortMembersByConnectivity(List<RelationMember> defaultMembers) { 126 127 List<RelationMember> newMembers = new ArrayList<RelationMember>(); 128 129 RelationNodeMap map = new RelationNodeMap(defaultMembers); 130 // List of groups of linked members 131 // 132 List<LinkedList<Integer>> allGroups = new ArrayList<LinkedList<Integer>>(); 133 134 // current group of members that are linked among each other 135 // Two successive members are always linked i.e. have a common node. 136 // 137 LinkedList<Integer> group; 138 139 Integer first; 140 while ((first = map.pop()) != null) { 141 group = new LinkedList<Integer>(); 142 group.add(first); 143 144 allGroups.add(group); 145 146 Integer next = first; 147 while ((next = map.popAdjacent(next)) != null) { 148 group.addLast(next); 149 } 150 151 // The first element need not be in front of the list. 152 // So the search goes in both directions 153 // 154 next = first; 155 while ((next = map.popAdjacent(next)) != null) { 156 group.addFirst(next); 157 } 158 } 159 160 for (LinkedList<Integer> tmpGroup : allGroups) { 161 for (Integer p : tmpGroup) { 162 newMembers.add(defaultMembers.get(p)); 163 } 164 } 165 166 // Finally, add members that have not been sorted at all 167 for (Integer i : map.getNotSortableMembers()) { 168 newMembers.add(defaultMembers.get(i)); 169 } 170 171 return newMembers; 172 } 173 174}