This PR is a major change. It turns HexSet into HexMap<Value>. Think of it as a dictionary of Hex → Value, but one that understands the hierarchical nature of H3. You can query a small hex for a value, but possibly get returned the value for a 'complete' parent hex. If all you wanted was a Hex → Value dictionary, a regular HashMap<H3Cell, V> would do.

What about sets?

With this change, what we HexSet is represented as a HexMap<()>, where we're using the unit (()) type for values. Unfortunately, this does not optimize into the equivalent of the previous HexSet type and imposes fairly large performance penalties. The performance hits are in the neighborhood of 130% on my 2013 Mac Pro. But keep in mind that means that calls to .contains() now take ~40 ns when they used to take ~17 ns. 40 ns is still pretty damn fast.

EDIT: I switched to criterion for proper benchmarking and the performance difference is negligible

Remaining work

• [x] decide if pluggable compactor is part of the map or only provided with .insert_and_compact()
• [ ] ability to reduce a hex?
• [x] update documentation to reflect this major change
• [ ] ~make HexSet its own type to avoid Value = () perf hit?~ out of scope
• [x] rename this repo hexmap right before/after merging

The first point about where the compactor should live has major implications for serialization, the namability of types, etc. For example, what if the user wants to use a closure for compaction? That's currently supported. But if the compactor was a generic member of the HexMap type itself, how do you name it? Hint: you can't name the type of closure.

On the second point about reduction: what if, instead of getting the value for a Hex, the user wants to perform a reduction/fold on all children for a particular hex? Reduction could be very useful when you want to say, summarize all data for all hexes in a region. That would be hard to do without exposing the internal Node type.

Set/maps should implement .iter[_mut]() which returns an iterator over all cells.

Note to potential implementor: Nodes do not store their keys (cells). It's not necessary, since the structure mimics the semantics of H3. We'll need to reconstruct cell values as part of the tree walk. I suspect this could be a pretty big bottleneck, but it's better than the larger performance hit we'd incur if nodes did store a copy of their cell.

This was originally a PR against @Vagabond's adt/refactor branch. After a bunch of messy rebases, it has a bit more than speedup code, but this project is churning so YOLO

it looks like parse_h3cell is the biggest bottleneck. This patch makes the test cases almost 3x faster on my machine.

Additionally, I added a .len() method. With it, I discovered that the - 1 was making an HTree with only 836 leaves instead of the 42383 contained in the source region.

Major goal: it would be awesome it we could both construct a compacted tree and drain it to a vec faster than calling libh3's compact() function. My gut feeling is the bottle neck currently lays non-deterministic alloction of behavior of a hexset. I do have a PR that improves things, but it probably needs some work. See https://github.com/JayKickliter/HexSet/pull/4

This is an experimental PR to improve HexSet creation. It appears to halve the time to build up very large sets at the expense of up about slowing down contains() by about 20%. I originally thought this approach could take advance of cache locality to also improve contains, so this PR may be dead in the water.