Additional info: ranges never overlap but updates might move ranges

The second requirement is not very basic. I think you have to specify what that is further to understand what you want there. Also can ranges merge once you move them? If understand you never split the ranges to produce new ones.

I think that to calculate a diff you would still need to do the linear lookup through all of the nodes. And to lookup a range you'll need two indexes (two maps) so you'll have to do two lookups whatever way you look at it. And then you have to do the intersection of results :thinking_face:

if you're looking for an off-the-shelf solution, I think guava has some ImmutableRangeMap stuff which sounds a bit like the stuff you're describing.

So a tuple->data map, then x->tuple and y->tuple maps too to lookup that tuple. And then you have to maintain these two additional maps as you change the ranges. Edit: This is how I'd implement an "immutable range map". Maybe it exists already.

Y fast trie?

https://wikiless.org/wiki/X-fast_trie?lang=en

Looks very similar to Clojure's vectors

And a YFT is built on top of it https://wikiless.org/wiki/Y-fast_trie?lang=en

Maybe try a https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html it has log(N) lookup time complexity. Use the bottom of your range as the Key for each value. It supports floorEntry() that will find the highest key below the value that you are searching for. e.g. {1 :a 5 :b 10 :c }.floorEntry(7)=>[5 :b] To increase performance, you could add a clojure LRU cache on top for constant time lookup of recent values.

Aha, I need a tree bitmap (dealing with IPs)

Yeah tree bitmap potentially looks good. Advantage of Treemap is it's built into the language (so it's available and implementation is solid) and doesn't have much API to learn.

I think there should be a way to use TreeMap's .ceilingEntry and .floorEntry to encode ranges because if your node has [:end] then it could mean that the range is below the found node. i.e. you could save #{:end :end-inclusive :start-inclusive :start} set in the map and this would allow you to save ranges while retaining the numbers. Then you'd have a number, let's say 200 and you'd find two sets (floor+ceiling). Then you'd need to decide based on these sets whether it's in the range. That could probably work :thinking_face:

I can implement the tree map if I can understand the paper

https://blog.apnic.net/2021/06/04/storing-and-retrieving-ip-prefixes-efficiently/ rabbit hole

https://cseweb.ucsd.edu/~varghese/PAPERS/willpaper.pdf

zach tellman made > “An adaptation of Okasaki and Gill’s \“Fast Mergeable Integer Maps`\“, which can be found at http://ittc.ku.edu/~andygill/papers/IntMap98.pdf” https://github.com/clojure/data.int-map/blob/master/src/main/clojure/clojure/data/int_map.clj

Not sure if that hits your requirement (which i don’t understand) of t1 transformed efficiently into t2 but some prior art in the area

Thanks, I realized exactly what data structure I need and found there aren't many implementations of it

If you happen to find a reference implementation of Tree Bitmap for IP addresses which isn't written in Rust please lmk 🙂