I may need to restructure my basic data structure for the DHT node cache.
I need a data structure that is:
- sparsely populated (the namespace is 2^{256} elements large)
- allows efficient access to elements, inserting or removing them (like a dictionary/ map)
- allows to efficiently traverse the successors and predecessors of an element
- returns the next larger (or next smaller) element when looking up a non-existing element in the interval between those two
- works in a modular/ ring-like element space
Especially the last 2 requirements are rather tricky, but rather important, because on a ring node 5 can have node 2^{256}-10 as its direct successor.
I am currently using an ordered tree map as data structure because it supports looking up the next element < or > the given lookup index. But I have to mess around with the used comparison functions to make it somehow work, by comparing (a-b) \mod N and (b-a) \mod N when doing compare a b.
This requires some compromise of a node seemingly not having a predecessor when actually the predecessor is just more than \frac{N}{2} away.
I can imagine that this compromise might work, but either my test code is wrong or there are some undesirable further edge cases I do not understand yet.
So if you know another data structure supporting the requirements mentioned above, I welcome any recommendations.
Update:
Unfortunately, I have indeed found an edge case where a tree map does not work properly.
Let there be a Map with the keys [2^255+2^254+3, 2, 2^253], all keys are NodeIDs mod 2^256.
fromList [(NodeID {getNodeID = 86844066927987146567678238756515930889952488499230423029593188005934847229955},()),(NodeID {getNodeID = 2},()),(NodeID {getNodeID = 14474011154664524427946373126085988481658748083205070504932198000989141204992},())]
While (NodeID 2^255+2^254+3) > (NodeID 2^254 + 14) …
True
… and 2^255+2^254+3 is an element of the map…
True
… looking for an element larger than 2^254 + 14 doesn’t yield any.
Nothing
That’s the tree of the map:
NodeID {getNodeID = 2}:=()
±-NodeID {getNodeID = 86844066927987146567678238756515930889952488499230423029593188005934847229955}:=()
±-NodeID {getNodeID = 14474011154664524427946373126085988481658748083205070504932198000989141204992}:=()
So I obviously need to find another data structure 