Changeset 2421 in josm
- Timestamp:
- 2009-11-09T17:02:00+01:00 (15 years ago)
- Location:
- trunk/src/org/openstreetmap/josm/gui/dialogs/relation
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/src/org/openstreetmap/josm/gui/dialogs/relation/MemberTableModel.java
-
Property svn:eol-style
set to
native
r2394 r2421 1 // License: GPL. For details, see LICENSE file. 1 2 package org.openstreetmap.josm.gui.dialogs.relation; 2 3 … … 569 570 } 570 571 572 /** 573 * Sort the relation members by the way they are linked. 574 */ 571 575 void sort() { 572 576 RelationNodeMap map = new RelationNodeMap(members); 573 Vector<LinkedList<Integer>> segments; 574 LinkedList<Integer> segment; 575 Node startSearchNode; 576 Node endSearchNode; 577 boolean something_done; 578 579 /* 580 * sort any 2 or more connected elements together may be slow with many unconnected members 581 */ 582 583 if (map.isEmpty()) 584 // empty relation or incomplete members 585 return; 586 segments = new Vector<LinkedList<Integer>>(); 587 588 while (!map.isEmpty()) { 589 // find an element for the next segment 590 // try first element in relation if we just started 591 // otherwise, or if first element is another relation, just fetch some element from the 592 // map 593 Integer next; 594 if ((segments.size() == 0) && map.remove(0, members.get(0))) { 595 next = 0; 596 } else { 597 next = map.pop(); 598 if (next == null) { 599 break; 600 } 601 } 602 603 segment = new LinkedList<Integer>(); 604 segment.add(next); 605 segments.add(segment); 606 607 do { 608 something_done = false; 609 startSearchNode = null; 610 endSearchNode = null; 611 if (segment.size() == 1) { 612 // only one element in segment, so try to link against each linkable node of element 613 RelationMember m = members.get(segment.getFirst()); 614 if (m.isWay()) { 615 Way w = m.getWay(); 616 endSearchNode = w.lastNode(); 617 if (w.lastNode() != w.firstNode()) 618 { 619 startSearchNode = w.firstNode(); 620 } 621 } else if (m.isNode()) { 622 Node n = m.getNode(); 623 endSearchNode = n; 624 } 625 } else { 626 // add unused node of first element and unused node of last element 627 // start with the first element (compared to next element) 628 startSearchNode = getUnusedNode(members.get(segment.getFirst()), members.get(segment.get(1))); 629 630 // now the same for the last element (compared to previous element) 631 endSearchNode = getUnusedNode(members.get(segment.getLast()), members.get(segment.get(segment.size() - 2))); 632 } 633 634 // let's see if we can find connected elements for endSearchNode and startSearchNode 635 if (startSearchNode != null) { 636 Integer m2 = map.find(startSearchNode, segment.getFirst()); 637 if (m2 != null) { 638 segment.add(0, m2); 639 map.remove(m2, members.get(m2)); 640 something_done = true; 641 } 642 } 643 if (endSearchNode != null) { 644 Integer m2 = map.find(endSearchNode, segment.getLast()); 645 if (m2 != null) { 646 segment.add(segment.size(), m2); 647 map.remove(m2, members.get(m2)); 648 something_done = true; 649 } 650 } 651 } while (something_done); 652 653 } 654 655 if (segments.size() > 0) { 656 // append map.remaining() to segments list (as a single segment) 657 segment = new LinkedList<Integer>(); 658 segment.addAll(map.getRemaining()); 659 segments.add(segment); 660 661 // now we need to actually re-order the relation members 662 ArrayList<RelationMember> newmembers = new ArrayList<RelationMember>(); 663 for (LinkedList<Integer> segment2 : segments) { 664 for (Integer p : segment2) { 665 newmembers.add(members.get(p)); 666 } 667 } 668 members.clear(); 669 members.addAll(newmembers); 670 671 fireTableDataChanged(); 672 } 577 578 // List of groups of linked members 579 // 580 ArrayList<LinkedList<Integer>> allGroups = new ArrayList<LinkedList<Integer>>(); 581 582 // current group of members that are linked among each other 583 // Two successive members are always linked i.e. have a common node. 584 // 585 LinkedList<Integer> group; 586 587 Integer first; 588 while ((first = map.pop()) != null) { 589 group = new LinkedList<Integer>(); 590 group.add(first); 591 592 allGroups.add(group); 593 594 Integer next = first; 595 while ((next = map.popAdjacent(next)) != null) { 596 group.addLast(next); 597 } 598 599 // The first element need not be in front of the list. 600 // So the search goes in both directions 601 // 602 next = first; 603 while ((next = map.popAdjacent(next)) != null) { 604 group.addFirst(next); 605 } 606 607 } 608 609 group = new LinkedList<Integer>(); 610 group.addAll(map.getNotSortableMembers()); 611 allGroups.add(group); 612 613 ArrayList<RelationMember> newMembers = new ArrayList<RelationMember>(); 614 for (LinkedList<Integer> tmpGroup : allGroups) { 615 for (Integer p : tmpGroup) { 616 newMembers.add(members.get(p)); 617 } 618 } 619 620 if (members.size() != newMembers.size()) throw new AssertionError(); 621 622 members.clear(); 623 members.addAll(newMembers); 624 fireTableDataChanged(); 673 625 } 674 626 … … 679 631 * 680 632 * If both ways are not linked in any way, NONE is returned. 681 * 633 * 682 634 * Else the direction is given as follows: 683 635 * Let the relation be a route of oneway streets, and someone travels them in the given order. … … 711 663 /** the list of nodes the way k can dock to */ 712 664 List<Node> refNodes= new ArrayList<Node>(); 713 665 714 666 switch (ref_direction) { 715 case FORWARD: 667 case FORWARD: 716 668 refNodes.add(way_ref.lastNode()); 717 669 break; … … 728 680 return NONE; 729 681 } 730 682 731 683 for (Node n : refNodes) { 732 684 if (n == null) continue; … … 752 704 * determine, if the way i is a roundabout and if yes, what type of roundabout 753 705 */ 754 private Direction roundaboutType(int i) { 706 private Direction roundaboutType(int i) { //FIXME 755 707 RelationMember m = members.get(i); 756 708 if (m == null || !m.isWay()) return NONE; 757 709 Way w = m.getWay(); 758 if (w != null && 759 "roundabout".equals(w.get("junction")) && 710 return roundaboutType(w); 711 } 712 static Direction roundaboutType(Way w) { 713 if (w != null && 714 "roundabout".equals(w.get("junction")) && 760 715 w.getNodesCount() < 200 && 761 716 w.getNodesCount() > 2 && 762 w.getNode(0) != null && 717 w.getNode(0) != null && 763 718 w.getNode(1) != null && 764 719 w.getNode(2) != null && … … 775 730 return NONE; 776 731 } 777 732 778 733 private WayConnectionType wayConnection(int i) { 779 734 if (connectionType == null) { -
Property svn:eol-style
set to
-
trunk/src/org/openstreetmap/josm/gui/dialogs/relation/RelationNodeMap.java
-
Property svn:eol-style
set to
native
r2365 r2421 1 // License: GPL. For details, see LICENSE file. 1 2 package org.openstreetmap.josm.gui.dialogs.relation; 2 3 3 4 import java.util.ArrayList; 5 import java.util.Iterator; 6 import java.util.List; 7 import java.util.Map; 8 import java.util.TreeMap; 4 9 import java.util.TreeSet; 5 10 … … 8 13 import org.openstreetmap.josm.data.osm.Way; 9 14 15 import static org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction.*; 16 10 17 /** 11 * A mapping from Node positions to elements in a Relation (currently Nodes and Ways only) 18 * Auxiliary class for relation sorting. 19 * 20 * Constructs two mappings: One that maps each way to its nodes and the inverse mapping that 21 * maps each node to all ways that have this node. 22 * After construction both maps are consistent, but later on objects that are no longer needed 23 * are removed from the value sets. 24 * However the corresponding keys are not deleted even if they map to an empty set. 25 * Note that normal ways have 2 nodes (beginning and end) but roundabouts can have less or more 26 * (that are shared by other members). 12 27 * 13 28 * @author Christiaan Welvaart <cjw@time4t.net> 14 * 29 * 15 30 */ 16 31 public class RelationNodeMap { 32 /* 33 * read only list of all relation members 34 */ 35 private final List<RelationMember> members; 36 /* 37 * the maps. (Need TreeMap for efficiency.) 38 */ 39 private TreeMap<Node, TreeSet<Integer>> nodesMap; 40 private TreeMap<Integer, TreeSet<Node>> waysMap; 41 /* 42 * Used to keep track of what members are done. 43 */ 44 private TreeSet<Integer> remaining; 45 17 46 /** 18 * For each way endpoint, list all ways that share this node47 * All members that are incomplete or not a way 19 48 */ 20 private java.util.HashMap<Node, TreeSet<Integer>> points; 21 /** 22 * Singleton nodes 23 */ 24 private java.util.HashMap<Node, Integer> nodes; 25 private java.util.Vector<Integer> remaining; 26 /** 27 * read only list 28 */ 29 private final ArrayList<RelationMember> members; 49 private List<Integer> notSortable = new ArrayList<Integer>(); 30 50 31 51 RelationNodeMap(ArrayList<RelationMember> members) { 32 int i;52 this.members = members; 33 53 34 this.members = members; 35 points = new java.util.HashMap<Node, TreeSet<Integer>>(); 36 nodes = new java.util.HashMap<Node, Integer>(); 37 remaining = new java.util.Vector<Integer>(); 54 nodesMap = new TreeMap<Node, TreeSet<Integer>>(); 55 waysMap = new TreeMap<Integer, TreeSet<Node>>(); 38 56 39 for (i = 0; i < members.size(); ++i) {57 for (int i = 0; i < members.size(); ++i) { 40 58 RelationMember m = members.get(i); 41 if (m.getMember().incomplete )59 if (m.getMember().incomplete || !m.isWay()) 42 60 { 43 remaining.add(Integer.valueOf(i));61 notSortable.add(i); 44 62 } 45 else 46 { 47 add(i, m); 48 } 49 } 50 } 51 52 Integer find(Node node, int current) { 53 Integer result = null; 54 55 try { 56 result = nodes.get(node); 57 if (result == null) { 58 result = points.get(node).first(); 59 if (members.get(current).getMember() == members.get(result).getMember()) { 60 result = points.get(node).last(); 61 } 62 } 63 } catch (NullPointerException f) { 64 } catch (java.util.NoSuchElementException e) { 65 } 66 67 return result; 68 } 69 70 void add(int n, RelationMember m) { 71 if (m.isWay()) { 72 Way w = m.getWay(); 73 if (w.lastNode() == w.firstNode()) 74 { 75 nodes.put(w.firstNode(), n); 76 } 77 else 78 { 79 if (!points.containsKey(w.firstNode())) { 80 points.put(w.firstNode(), new TreeSet<Integer>()); 81 } 82 points.get(w.firstNode()).add(n); 83 84 if (!points.containsKey(w.lastNode())) { 85 points.put(w.lastNode(), new TreeSet<Integer>()); 86 } 87 points.get(w.lastNode()).add(n); 88 } 89 } else if (m.isNode()) { 90 Node node = m.getNode(); 91 nodes.put(node, n); 92 } else { 93 remaining.add(n); 94 } 95 } 96 97 boolean remove(int n, RelationMember a) { 98 boolean result; 99 if (a.isWay()) { 100 Way w = a.getWay(); 101 if (w.firstNode() == w.lastNode()) 102 { 103 result = (nodes.remove(w.firstNode()) != null); 104 } 105 else 106 { 107 result = points.get(w.firstNode()).remove(n); 108 result &= points.get(w.lastNode()).remove(n); 109 } 110 } else { 111 result = (nodes.remove(a.getMember()) != null); 112 } 113 return result; 114 } 115 116 // no node-mapped entries left 117 boolean isEmpty() { 118 return points.isEmpty() && nodes.isEmpty(); 119 } 120 121 java.util.Vector<Integer> getRemaining() { 122 return remaining; 123 } 124 125 Integer pop() { 126 Node node = null; 127 Integer result = null; 128 129 if (!nodes.isEmpty()) { 130 node = nodes.keySet().iterator().next(); 131 result = nodes.get(node); 132 nodes.remove(node); 133 } else if (!points.isEmpty()) { 134 for (TreeSet<Integer> set : points.values()) { 135 if (!set.isEmpty()) { 136 result = set.first(); 137 Way w = members.get(result).getWay(); 138 points.get(w.firstNode()).remove(result); 139 points.get(w.lastNode()).remove(result); 140 break; 63 else { 64 Way w = m.getWay(); 65 if (MemberTableModel.roundaboutType(w) != NONE) { 66 for (Node nd : w.getNodes()) { 67 addPair(nd, i); 68 } 69 } else { 70 addPair(w.firstNode(), i); 71 addPair(w.lastNode(), i); 141 72 } 142 73 } 143 74 } 144 75 145 return result; 76 remaining = new TreeSet<Integer>(); 77 for (Integer k : waysMap.keySet()) { 78 remaining.add(k); 79 } 80 81 /* 82 * Clean up the maps, i.e. remove nodes from roundabouts and dead ends that 83 * cannot be used in future. (only for performance) 84 */ 85 Iterator<Map.Entry<Node,TreeSet<Integer>>> it = nodesMap.entrySet().iterator(); 86 while (it.hasNext()) { 87 Map.Entry<Node,TreeSet<Integer>> nodeLinks = it.next(); 88 89 if (nodeLinks.getValue().size() < 2) { 90 // System.err.println("DELETE: "+nodeLinks.getKey()+" "+nodeLinks.getValue()); 91 if (nodeLinks.getValue().size() != 1) throw new AssertionError(); 92 93 Integer d_way = nodeLinks.getValue().iterator().next(); 94 TreeSet<Node> d_way_nodes = waysMap.get(d_way); 95 d_way_nodes.remove(nodeLinks.getKey()); 96 97 it.remove(); 98 continue; 99 } 100 // System.err.println(nodeLinks.getKey()+" "+nodeLinks.getValue()); 101 102 } 103 // System.err.println(""); 104 // System.err.println(remaining); 105 // System.err.println(""); 106 // System.err.println(nodesMap); 107 // System.err.println(""); 108 // System.err.println(waysMap); 109 110 } 111 112 private void addPair(Node n, int i) { 113 TreeSet<Integer> ts = nodesMap.get(n); 114 if (ts == null) { 115 ts = new TreeSet<Integer>(); 116 nodesMap.put(n, ts); 117 } 118 ts.add(i); 119 120 TreeSet<Node> ts2 = waysMap.get(i); 121 if (ts2 == null) { 122 ts2 = new TreeSet<Node>(); 123 waysMap.put(i, ts2); 124 } 125 ts2.add(n); 126 } 127 128 /** 129 * Return a relation member that is linked to the 130 * member 'i', but has not been popped jet. 131 * Return null if there is no such member left. 132 */ 133 public Integer popAdjacent(Integer i) { 134 // System.err.print("Adjacent["+i+"]:"); 135 TreeSet<Node> nodes = waysMap.get(i); 136 // System.err.print(nodes); 137 for (Node n : nodes) { 138 // System.err.print(" {"+n.getId()+"} "); 139 TreeSet<Integer> adj = nodesMap.get(n); 140 if (!adj.isEmpty()) { 141 Integer j = adj.iterator().next(); 142 done(j); 143 waysMap.get(j).remove(n); 144 // System.err.println(j); 145 return j; 146 } 147 } 148 return null; 149 } 150 151 /** 152 * Returns some remaining member or null if 153 * every sortable member has been processed. 154 */ 155 public Integer pop() { 156 if (remaining.isEmpty()) return null; 157 Integer i = remaining.iterator().next(); 158 done(i); 159 return i; 160 } 161 162 /** 163 * This relation member has been processed. 164 * Remove references in the nodesMap. 165 */ 166 private void done(Integer i) { 167 remaining.remove(i); 168 TreeSet<Node> nodes = waysMap.get(i); 169 for (Node n : nodes) { 170 boolean result = nodesMap.get(n).remove(i); 171 if (!result) throw new AssertionError(); 172 } 173 } 174 175 public List<Integer> getNotSortableMembers() { 176 return notSortable; 146 177 } 147 178 } -
Property svn:eol-style
set to
Note:
See TracChangeset
for help on using the changeset viewer.