This question is related to my previous question:
Looking for a set implementation with small memory footprint
I'm looking for information about combined data structures, which can efficiently represent a set S of non-intersecting sub-intervals of the given integer interval
[0, MAX) with the single operation:
- testAndInsert(min, max) - test if the interval
[min, max]intersects with any of already existing intervals in the
S; if no intersections are found, then insert the interval
[min, max]into the set
S, potentially merging it with one or two neighbor intervals; return success, if and only if the insertion was done.
I'm asking about combined data structures, because it looks like we have two evident choices - linked data structures (for example, various binary trees) and array-based data structures (bitmaps). However, both of them have their own shortages:
Balanced binary trees will have O(log(n)) time complexity and look good, when number of intervals in the
Sis much less than the
MAX. However each node of the tree will take at least 16 bytes (for links) on 64-bit machine. For example, if we represent all odd integers in the interval [0, 1000), then we'll need 8000 bytes only for links.
Bitmaps will have O(1) time complexity, but take constant memory, which depends only on the
MAX. Representation of all the odd integers in the interval [0, 1000) needs only 125 bytes. However, when the
MAXis large and the number of existing intervals is much less than the
MAX, then most of the memory, taken by the bitmap, will be wasted.
I'm not actually focused on the time complexity - something between O(1) and O(log(n)) is acceptable, but in real situations the memory footprint of the data structure plays a very important role. If machine begins swapping because of lack of memory, then even O(1) data structure will work for ages.
Are there any data structures, which could automatically adapt themselves to the size of the
S in this problem? For example, when we start with the empty
S (no intervals at all), the data structure is linked, then it becomes array-based (piece by piece?), then it probably switches to storage of the
S complement (free space is small) and becomes linked again?
P.S.: I know about the Boost ICL interval set and use it now, but I'm interested in other possible approaches.
MAX? Do you have an upper bound on the number of intervals you expect to have in the tree? Since you're asking about optimization down to the individual bit/byte value, knowing concrete numbers can sometimes help, if you know what they will be in your application. That said, if you don't know or want a generic solution because those values will vary greatly, that's an acceptable answer too. $\endgroup$
MAXyet. It should be large enough to justify usage of any new data structure. Number of intervals can grow from 0 to
MAX/2(worst case with all odd points) and then decrease to 1 (full "universe" interval). $\endgroup$