[josm-dev] Reverse lookups

[Dave Hansen]

I've been using this code for a while to speed up JOSM validator tests:

	http://www.mail-archive.com/josm-dev@openstreetmap.org/msg00265.html

What I do is just destroy the entire reverse lookup table each time the
DataSet changes.  It works for batched operations, but reverts to
sucking each time that the data is modified.

I just experimented with replacing the explicit HashMap<Node,List<Way>>
with something that uses the QuadBuckets search functionality instead.
It's pretty simple:

   public List<Way> waysUsingNode(Node n)
    {
        QuadBuckets<Way> qb = (QuadBuckets<Way>)ds.ways;
        List<Way> possible_ways = qb.search(n.getCoor(), 0.000001);
        List<Way> result = new ArrayList<Way>();
        for (Way w : possible_ways) {
            if (!w.containsNode(n))
                continue;
            result.add(w);
        }
        return result;
    }

It works because I calculate a bounding box for each node and all of its
nodes are guaranteed to be contained inside the box.  

It is way faster than iterating through the data set.  It's also much
more space efficient than keeping an explicit map.  

BTW, here's the patch for using QuadBuckets for way storage:

	http://josm.openstreetmap.de/ticket/3671

This could also potentially make click processing much faster.  We can
also optimize redraw() operations when zoomed in on a large data set by
doing a search instead of iterating across the entire data set.

-- Dave