range-set-list-0.1.4: Memory efficient sets with ranges of elements.
Copyright(c) Dylan Simon 2015
LicenseMIT
Maintaineroleg.grenrus@iki.fi
Stabilityexperimental
Portabilitynon-portable (tested with GHC only)
Safe HaskellSafe
LanguageHaskell2010

Data.RangeSet.Internal

Description

Most functions in this module deal with normalized (closed, fst <= snd, non-overlapping, non-adjacent, ordered) ranges, but do not check this assumption. Most users should use a higher-level interface.

Synopsis

Documentation

rangeSize :: Enum a => a -> a -> Sum Int Source #

Determine the number of items in an Enum range as a Sum

rangeIsSubsetList :: Ord a => a -> a -> [(a, a)] -> Maybe [(a, a)] Source #

Determine if [x,y] is a subset of the list, returning the list right of y if so.

isSubsetRangeList :: Ord a => [(a, a)] -> [(a, a)] -> Bool Source #

Determine if the first list is a subset of the second.

insertRangeList :: (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)] Source #

Add [x,y].

There are three possibilities we consider, when inserting into non-empty set:

  • discretely after: continue
  • discretely before: prepend
  • overlapping: union and prepend

deleteRangeList :: (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)] Source #

Remove a range from a range list.

There are 6 possibilities we consider, when deleting from non-empty set:

  • more
  • less
  • strictly inside (splits)
  • overlapping less-edge
  • overlapping more-edge
  • stricly larger

unionRangeList :: (Ord a, Enum a) => [(a, a)] -> [(a, a)] -> [(a, a)] Source #

Union two range lists.

differenceRangeList :: (Ord a, Enum a) => [(a, a)] -> [(a, a)] -> [(a, a)] Source #

Compute the set difference, removing each range in the second list from the first.

intersectRangeList :: Ord a => [(a, a)] -> [(a, a)] -> [(a, a)] Source #

Compute the intersection.

complementRangeList :: (Ord a, Enum a, Bounded a) => [(a, a)] -> [(a, a)] Source #

Compute the complement.

fromAscElemList :: (Eq a, Enum a) => [a] -> [(a, a)] Source #

Normalize a sorted list of elements to a range list.

fromElemList :: (Ord a, Enum a) => [a] -> [(a, a)] Source #

Normalize an arbitrary list of elements to a range list.

normalizeRangeList :: (Ord a, Enum a) => [(a, a)] -> [(a, a)] Source #

Normalize an arbitrary list of ranges.

validRangeList :: (Ord a, Enum a, Bounded a) => [(a, a)] -> Bool Source #

Check if a list is normalized.