Efficient immutable interval sets for spire.
Two of these data structures have since been included into spire-extras.
This repository contains two data structures for sets of non-overlapping intervals. Boundaries are either inclusive or exclusive, so (0..2] is different to [1..2].
IntervalTrie is based on a binary TRIE and requires the element type to be convertable to a long while preserving order. This is the case for all primitive types.
IntervalSeq is based on sorted sequences of boundary values and works for any element type for which an Order instance is available.
IntervalMap is a generalization of IntervalSeq to more complex values. This is the most generic data structure. It requires an Order[K] for the keys, and something like a Bool[V] or a Monoid[V] for the values.
An utility to merge two sorted arrays with a close to optimal number of comparisons. This is what operations in IntervalSeq and IntervalMap are based on.