[josm-dev] QuadBuckets in Dataset

[Dave Hansen]

On Sat, 2009-10-31 at 18:26 +0100, Jiri Klement wrote:
> > One suggestion was to use the UndoRedoHandler code to catch
> > modifications and reindex the primitives.  How about something like
> > this?
> ....
> I'm not sure if the code will work for one moved node. You first call
> reIndexPrimitives(modified) that might move node to different bucket
> and then try to get ways, that still think the node is in the old
> buckets. Anyway after some modifications it should work, at least as a
> temporary solution.

Yeah, you're right.

One thought I have is that we can have a Map<Node, Coor>.  Before the
executeCommand() happens, we run through all the modified data in
UndoRedoHandler and record all the nodes and their existing coordinates.

After the executeCommand(), we run through the modified nodes again and
compare their coordinates to the ones in the old map.  If changed, we
look up any ways using the node, but with the *old* coordinate from the
map.

Another option would be to just give both Nodes and Ways another class
variable that records where they were stuck in the QuadBuckets.  If we
ever try to find an existing object, we just use that variable.  When we
insert things, we set that variable in the object.

We could either record an old set of coordinates, or we could even put a
pointer directly to the QBLevel object that stores the Way or Node.

remove() in QuadBuckets then becomes a very quick operation that won't
ever fail because an object got moved:

class QuadBuckets {
	...
	boolean remove(T o) {
		QBLevel qb = n.qblevel;
		return qb.remove(t);
	}
	class QBLevel {
		...
	        boolean add_content(T o)
	        {
	            boolean ret = false;
	            if (content == null)
	                content = new LinkedList<T>();
	            ret = content.add(o);
	            if (debug && !this.isLeaf())
        	        pout("added "+o.getClass().getName()+" to non-leaf with size: " + content.size());
+		    o.qblevel = this;
	            return ret;
	        }
	}
}

The only downside is that it costs an extra pointer.

-- Dave