rklaehn / intervalset

Efficient immutable interval sets

GitHub

intervalsets

Efficient immutable interval sets for spire.

Two of these data structures have since been included into spire-extras.

Build Status codecov.io Maven Central Scaladoc

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.

ScalaWorld presentation

Presentation at ScalaWorld 2017