[josm-dev] [PATCH 1/2] QuadBuckets (using quad tiling) for node storage in JOSM

[Dave Hansen]

On Sat, 2009-09-12 at 21:04 +0200, Petr Nejedlý wrote:
> Dave Hansen napsal(a):
>  > Ooh, I forgot about josm-ng.  That one looks very usable.  If mine
>  > doesn't pan out, I'll certainly look at that one.
> 
> Well, the QTree in josm-ng is similar to yours in the way it distributes 
> the content, though I did pay quite some attention to memory usage 
> (hint: e.g. LinkedList is not the collection you'd like to use unless 
> you have specific reason to)

For the leaf nodes you mean?  I actually got better performance out of
it than I did ArrayList.  Honestly, I've been looking at performance a
lot more than pure memory usage, so I bet you're right.  But, when you
have an absolute ton of ArrayLists around that you're iterating over a
lot ArrayList.size() actually shows up in the profiles pretty high.

> and support also 2d entities (node is 
> zero-d). The problem with importing it directly into josm is that it 
> uses (in -ng) the projected (and integer) coordinates. While it doesn't 
> care whether the coordinates are projected or not, it hugely benefit 
> from their signed integer nature.

You just mean that they're cheaper to deal with than doubles/floats?

> Dave Hansen napsal(a):
>  > QuadBuckets also happen to implement Collection<Node>.  So, we can
>  > just plug it in for Collection like in the DataSet class.
> 
> I have not looked at the josm codebase for a while, but as long as
> Node has publicly mutable coordinates, you can't honestly do it.
> If anything moves a node, it has no way to automatically jump into the 
> new bucket. And it makes no sense to try patching all the places which 
> can move a node (MoveCommand is not the only one).

Just recently, Node/Way/Relation require access to be via accessor
functions.  That should help out quite a bit.  The one thing that we do
need is for a list of PrimitiveChangeListeners or something to call when
primitives do change.

You're right, though.  This can't simply be dropped in for the node list
and retain its searching abilities.

-- Dave