Efficient immutable data structure for small multi-sets of integer ranges?
Background
I'm currently writing some Elixir algorithms that are quite computationally expensive. The most-used datastructure is a multi-set of (finite) integer ranges. Modifying this data structure takes up around 80% of the execution time in insert and remove, so it's time to see if there's something better out there. I'm spending around 1400 clock cycles per insert or remove, so there should be some margin for improvement.
Current implementation
The current model, called Domain, is a fully persistent immutable ordered linked-list of [low, high) pairs, normalized so that for any time two ranges overlap, the first one is the longest. Touching ranges are also joined. 864
Most domains consist of less than 100 ranges, but some consist of up to 10k ranges. The current data structure is chosen because it was easy to work with, avoiding premature optimization.
The Domain datastructure represents a multiset of integers. Internally representing ranges as [low, high) pairs is just an optimization. Since some domains cover many million of numbers, I don't think a multiset would be fast enough to be viable.
A range is a set of b-a unique integers x, a <= x < b, distinct from every previously defined range, with b-a as large as possible.
The operations
The operations supported right now are
* insert(a,b) union of two domains, keeping duplicates
* remove(a,b) a minus b
* intersection(a,b)
* ncov(a,n) a with n-1 copies of each present integer removed.
* after(a,n) domain of everything in a equal to or greater than n
* before(a,n) domain of everything in a equal to or smaller than n
* minlen(a,l) domain of all ranges in a with a cardinality of at least l.
* trunc_start(a,l) a with the l smallest integers removed from each range.
* trunc_end(a,l) a with the l largest integers removed from each range.
Queries:
* contains?(a,p) does the domain a contain a specified integer p?
* covers?(a,b) is domain b a subset of domain a?
* lowest(a) what's the lowest integer in the domain?
* highest(a) what's the highest integer in the domain?
Behaviour
The most common use-case is to modify the structure a small bit at a time, from smallest value to biggest. Since inserts might modify the whole structure, the lists are almost always rebuilt completely right now. Changing the access pattern to bulk inserts and deletions is not feasible.
The second most common use-case is intersection between multiple (3+) domains, currently implemented as repeatedly calling the binary intersection function.
Questions
* Is there a standard name of this data structure?
* Is there a more efficient format? If so, which one(s)?
* Would a tree be faster than a linked-list? With or without rebalancing? 242