[josm-dev] QuadBuckets in Dataset

[Karl Guggisberg]

Hi,

I'd also like to see a kind of spatial index but I agree with Jiri that
QuadBucket is currently only used in validator.

And I fully agree with the steps Jiri proposes. Even if QuadBucket was
disabled for a short time we would gain a lot with Jiris moves. The major
goal is still to turn DataSet in a properly managed and consistent object
storage which allows for efficient traversal from childs to parents.

-- Karl 


-----Ursprüngliche Nachricht-----
Von: josm-dev-bounces at openstreetmap.org
[mailto:josm-dev-bounces at openstreetmap.org] Im Auftrag von Jiri Klement
Gesendet: Samstag, 31. Oktober 2009 16:28
An: josm-dev
Betreff: [josm-dev] QuadBuckets in Dataset

Hi,

QuadBuckets is used for some time as storage for nodes and ways in Dataset
but I think it doesn't bring any benefit for JOSM in current state. Ability
to do fast search for bounding box will be usefull in future, but right now
it can't be used because it's not sure that QuadBuckets will be reindexed
after change of node coordinates.

In any case, I don't think QuadBuckets or any other concreate storage class
should be exposed as public field in Dataset. There should be only
unmodifiable collection, all changes should go through
addPrimitive/removePrimitive and possibly other methods. So the first
suggestion is replace QuadBuckets with Collection again.

Another thing is what class should be used internally as a storage for nodes
and ways. The most common operation is simply iterarating over all elements
- that's the task where QuadBuckects is more than three times slower than
ArrayList. and two times slower than Storage class.
Another operation is looking for element based on id. That's currently used
in methods like Way.load(), but it will be also useful in other places, like
in currently hot selection code.

I think selection should be id based - when Dataset.setSelected(Node) is
called then node that exist in the Dataset and has the same id as argument
should be selected, not neccessary the same instance of Node passed as an
argument. That will preserve backwards compatibility with old code, that
relies on the fact that OsmPrimitive.cloneFrom preserved selection flag and
it will be also useful for replacing OsmPrimitive with PrimitiveData
classes.

To summarize, I would like to do following:
1) Replace public QuadBuckets<Node> nodes in Dataset with Collection<Node>
getNodes(), that will return Collections.unmodifiableCollection of nodes
2) Replace for now QuadBuckets in Dataset with class more suitable for
iterating and looking for ids - Storage* class from josm-ng looks like a
good candidate. QuadBuckets can be used again when it makes sense (maybe
both Storage and QuadBuckets can be used at the same time, as each class is
useful for differrent type of operations)

Are there any complains?

* Storage class is basically memory effective hash map implementation.
--
Jiri

_______________________________________________
josm-dev mailing list
josm-dev at openstreetmap.org
http://lists.openstreetmap.org/listinfo/josm-dev