# intervalsets

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

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

IntervalSeq is based on sorted sequences of boundary values and works for any element type for which an Order instance is available.

## IntervalMap

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.

## QuickArrayMerge

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.