Ignore:
Timestamp:
2009-11-09T17:02:00+01:00 (14 years ago)
Author:
bastiK
Message:

relation editor: respect roundabouts when sorting the relation

File:
1 edited

Legend:

Unmodified
Added
Removed

  • 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.
    12package org.openstreetmap.josm.gui.dialogs.relation;
    23
    34import java.util.ArrayList;
     5import java.util.Iterator;
     6import java.util.List;
     7import java.util.Map;
     8import java.util.TreeMap;
    49import java.util.TreeSet;
    510
    … …  
    813import org.openstreetmap.josm.data.osm.Way;
    914
     15import static org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction.*;
     16
    1017/**
    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).
    1227 *
    1328 * @author Christiaan Welvaart <cjw@time4t.net>
    14  *
     29 * 
    1530 */
    1631public 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
    1746    /**
    18      * For each way endpoint, list all ways that share this node
     47     * All members that are incomplete or not a way
    1948     */
    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>();
    3050
    3151    RelationNodeMap(ArrayList<RelationMember> members) {
    32         int i;
     52        this.members = members;
    3353
    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>>();
    3856
    39         for (i = 0; i < members.size(); ++i) {
     57        for (int i = 0; i < members.size(); ++i) {
    4058            RelationMember m = members.get(i);
    41             if (m.getMember().incomplete)
     59            if (m.getMember().incomplete || !m.isWay())
    4260            {
    43                 remaining.add(Integer.valueOf(i));
     61                notSortable.add(i);
    4462            }
    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);
    14172                }
    14273            }
    14374        }
    14475
    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;
    146177    }
    147178}
Note: See TracChangeset for help on using the changeset viewer.