Query and Entry API changes

[JohnDowson]

After pondering this for a while, I've come to realisation that what we call Entry is a distraction, and in fact, Query is the closest we have to HashMap's Entry. This is because while HashMap returns Entry in response to it's key, we query using Areas and return Query in response. It would make sense therefore to make Query an enum with an Empty variant.

Another question is if changes to how we store data are needed. One thought i've had is that SlotMap<Handle, V> and an associated SecondaryMap<Handle, Area> might be a good solution.

[ambuc]

Query is a bit "lazy" at the moment - it implements Iterator, but it's not possible to know whether or not that iterator is empty without consuming it. This means that creating a Query has no cost, and walking it has some cost. I don't see a way to make this change without consuming the potential list of Entrys up-front - which isn't necessarily a problem, but it is a change. What's the problem we're trying to solve here again?

I don't know much about SlotMap beyond what's in the first page of that doc - but I support any backing store change which shows benefits during performance testing!

[JohnDowson]

I suppose, query should be checking QTInners in the Area and collecting a set of their contained values. Then it can either return Query::Empty or lazily yield Entries.

On Thu, Nov 30, 2023, 3:16 AM James Adam Buckland @.***> wrote:

Query https://docs.rs/quadtree_rs/latest/quadtree_rs/iter/struct.Query.html is a bit "lazy" at the moment - it implements Iterator, but it's not possible to know whether or not that iterator is empty without consuming it. This means that creating a Query has no cost, and walking it has some cost. I don't see a way to make this change without consuming the potential list of Entry https://docs.rs/quadtree_rs/latest/quadtree_rs/entry/struct.Entry.htmls up-front - which isn't necessarily a problem, but it is a change. What's the problem we're trying to solve here again?

I don't know much about SlotMap https://docs.rs/slotmap/latest/slotmap/ beyond what's in the first page of that doc - but I support any backing store change which shows benefits during performance testing!

— Reply to this email directly, view it on GitHub https://github.com/ambuc/quadtree/issues/25#issuecomment-1832901711, or unsubscribe https://github.com/notifications/unsubscribe-auth/AJRGM3RWMDO4XILMACEAJDDYG7F4ZAVCNFSM6AAAAABAADD3RSVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTQMZSHEYDCNZRGE . You are receiving this because you authored the thread.Message ID: @.***>

[ambuc]

It is already possible to construct a Query and simply .collect() all the Entry s from its Iterator. I don't see what the benefit is of forcing every user of Query to collect all of their entries on the spot. Maybe you can speak a bit more about your use case?

[JohnDowson]

Okay, I might have under-explained what I'm doing. Let's back up.

My usecase is as follows: I have a square grid, and rectangular widgets that need to be placed in that grid. For that I need an easy way to ask if given area in the tree is free.

[ambuc]

You can use query for this already.

Here is an example:

let mut qt = Quadtree::<u32, u8>::new(4);
//   0  1  2  3  4  5  6
// 0 +--+--+--+--+--+--+
//   |  |  |  |  |  |  |
// 1 +--+--+--+--+--+--+
//   |  |  |  |  |  |  |
// 2 +--+--o o o o--+--+  o @ (2, 2)->(2x2) #10
//   |  |   o o o   |  |  x @ (3, 3)->(2x2) #55
// 3 +--+--o oxoxox x--+
//   |  |   o oxox x   |
// 4 +--+--o oxoxox x--+
//   |  |  |   x x x   |
// 5 +--+--+--x x x x--+
//   |  |  |  |  |  |  |
// 6 +--+--+--+--+--+--+
assert!(qt.insert(((2, 2), (2, 2)), 10,).is_some());
assert!(qt.insert(((3, 3), (2, 2)), 55,).is_some());

let empty_region = qt.query(((0, 0), (2, 2)));
debug_assert!(empty_region.collect::<Vec<_>>().is_empty());

let nonempty_region = qt.query(((0, 0), (3, 3)));
debug_assert!(!nonempty_region.collect::<Vec<_>>().is_empty());

[JohnDowson]

Hm, yes, but it's not very pretty.

On Thu, Nov 30, 2023, 7:24 PM James Adam Buckland @.***> wrote:

You can use query for this already.

Here is an example:

let mut qt = Quadtree::<u32, u8>::new(4);// 0 1 2 3 4 5 6// 0 +--+--+--+--+--+--+// | | | | | | |// 1 +--+--+--+--+--+--+// | | | | | | |// 2 +--+--o o o o--+--+ o @ (2, 2)->(2x2) #10// | | o o o | | x @ (3, 3)->(2x2) #55// 3 +--+--o oxoxox x--+// | | o oxox x |// 4 +--+--o oxoxox x--+// | | | x x x |// 5 +--+--+--x x x x--+// | | | | | | |// 6 +--+--+--+--+--+--+assert!(qt.insert(((2, 2), (2, 2)), 10,).is_some());assert!(qt.insert(((3, 3), (2, 2)), 55,).is_some()); let empty_region = qt.query(((0, 0), (2, 2)));debug_assert!(empty_region.collect::<Vec<>>().is_empty()); let nonempty_region = qt.query(((0, 0), (3, 3)));debug_assert!(!nonempty_region.collect::<Vec<>>().is_empty());

— Reply to this email directly, view it on GitHub https://github.com/ambuc/quadtree/issues/25#issuecomment-1834103824, or unsubscribe https://github.com/notifications/unsubscribe-auth/AJRGM3UTQD5G3VPIAVTHDSDYHCXLTAVCNFSM6AAAAABAADD3RSVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTQMZUGEYDGOBSGQ . You are receiving this because you authored the thread.Message ID: @.***>

[JohnDowson]

Perhaps a separate interface specifically for checking if area contains anything?

Maybe along with an API for nonoverlapping insertion which does the check for you.

Then it could be as simple as

let mut widget = Some(widget);
while let Some(w) = widget {
    widget = tree.insert.nonoverlapping(area, w);
    area = next_area_to_try;
}

[ambuc]

This sounds pretty similar to the non-overlapping mode we discussed in https://github.com/ambuc/quadtree/issues/16. I would be happy to review PRs which add that mode. Perhaps Quadtree::insert fails in non-overlapping mode if the new region would overlap with an existing region?

[JohnDowson]

Yes, this is the same conversation, continued.

I'm not entirely sure a mode is a good idea. I would like to either make it type-safe, or leave it as an alternative insertion method.

[JohnDowson]

I don't know much about SlotMap beyond what's in the first page of that doc - but I support any backing store change which shows benefits during performance testing!

Do you have any ideas for how to benchmark changes? Coming up with performance tests is always tricky.

[ambuc]

Yes, this is the same conversation, continued.

I'm not entirely sure a mode is a good idea. I would like to either make it type-safe, or leave it as an alternative insertion method.

I leave the decision entirely in your hands -- but I suspect it will be much simpler to write an alternative insertion method.