range-set-list: Memory efficient sets with ranges of elements.

[ data, library, mit ] [ Propose Tags ]

Memory efficient sets with continuous ranges of discrete, bounded elements. List- and map-based implementations. Interface mimics Data.Set where possible.


[Skip to Readme]
Versions 0.0.1, 0.0.2, 0.0.3, 0.0.4, 0.0.5, 0.0.6, 0.0.7, 0.1.0.0, 0.1.1.0, 0.1.2.0, 0.1.2.1, 0.1.3
Change log CHANGELOG.md
Dependencies base (>=4.5 && <4.13), containers (>=0.5.3 && <0.7), deepseq (>=1.3.0.0 && <1.5), hashable (>=1.2.3.3 && <1.3), semigroups (>=0.16.2.2 && <0.19) [details]
License MIT
Author Oleg Grenrus <oleg.grenrus@iki.fi>
Maintainer Oleg Grenrus <oleg.grenrus@iki.fi>
Revised Revision 1 made by phadej at Tue Sep 25 08:43:32 UTC 2018
Category Data
Home page https://github.com/phadej/range-set-list#readme
Bug tracker https://github.com/phadej/range-set-list/issues
Source repo head: git clone https://github.com/phadej/range-set-list
Uploaded by phadej at Mon May 21 16:54:58 UTC 2018
Distributions LTSHaskell:0.1.3, NixOS:0.1.3, Stackage:0.1.3
Downloads 3632 total (53 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2018-05-21 [all 1 reports]
Hackage Matrix CI

Modules

[Index]

Downloads

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

For package maintainers and hackage trustees


Readme for range-set-list-0.1.3

[back to package description]

range-set-list

Build Status Hackage Stackage LTS 2 Stackage LTS 3 Stackage Nightly

A few trivial implementations of range sets.

You can find the package (and its documentation) on hackage.

This module is intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.,

import Data.RangeSet.List (RSet)
import qualified Data.RangeSet.List as RSet

This package contains two implementations of exactly the same interface, plus one specialization, all of which provide exactly the same behavior:

  • "Data.RangeSet.List" implements the simplest RSet based on list. Set construction and manipulation is most efficient for this version, but lookups may require a full list traversal.
  • "Data.RangeSet.Map" implements a slightly less simple RSet based on map. Construction and manipulation have more overhead in this version, but lookups are significantly faster, especially for large sets.
  • "Data.RangeSet.IntMap" is simply a specialization of "Data.RangeSet.Map" to Ints based on IntMap.

Compared to Data.Set, this module also imposes an Enum constraint for many functions. We must be able to identify consecutive elements to be able to glue and split ranges properly.

The implementation assumes that

x < succ x
pred x < x

and there aren't elements in between (not true for Float and Double). Also succ and pred are never called for largest or smallest value respectively.