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

Copyright(c) Dylan Simon 2015
LicenseMIT
Safe HaskellSafe
LanguageHaskell2010

Data.RangeSet.IntMap

Contents

Description

This is simply a specialization of Data.RangeSet.Map to Int.

The implementation of RIntSet is based on Data.IntMap.Strict.

Synopsis

Range set type

data RIntSet #

Internally set is represented as sorted list of distinct inclusive ranges.

Instances

Operators

(\\) :: RIntSet -> RIntSet -> RIntSet infixl 9 #

O(n+m). See difference.

Query

null :: RIntSet -> Bool #

O(1). Is this the empty set?

isFull :: RIntSet -> Bool #

O(1). Is this the empty set?

size :: RIntSet -> Int #

O(n). The number of the elements in the set.

member :: Int -> RIntSet -> Bool #

O(log n). Is the element in the set?

notMember :: Int -> RIntSet -> Bool #

O(log n). Is the element not in the set?

lookupLT :: Int -> RIntSet -> Maybe Int #

O(log n). Find largest element smaller than the given one.

lookupGT :: Int -> RIntSet -> Maybe Int #

O(log n). Find smallest element greater than the given one.

lookupLE :: Int -> RIntSet -> Maybe Int #

O(log n). Find largest element smaller or equal to than the given one.

lookupGE :: Int -> RIntSet -> Maybe Int #

O(log n). Find smallest element greater or equal to than the given one.

containsRange :: (Int, Int) -> RIntSet -> Bool #

O(log n). Is the entire range contained within the set?

isSubsetOf :: RIntSet -> RIntSet -> Bool #

O(n+m). Is this a subset? (s1 isSubsetOf s2) tells whether s1 is a subset of s2.

valid :: RIntSet -> Bool #

O(n). Ensure that a set is valid. All functions should return valid sets except those with unchecked preconditions: fromAscList, fromNormalizedRangeList

Construction

empty :: RIntSet #

O(1). The empty set.

full :: RIntSet #

O(1). The full set.

singleton :: Int -> RIntSet #

O(1). Create a singleton set.

singletonRange :: (Int, Int) -> RIntSet #

O(1). Create a continuos range set.

insert :: Int -> RIntSet -> RIntSet #

O(n). Insert an element in a set.

insertRange :: (Int, Int) -> RIntSet -> RIntSet #

O(n). Insert a continuos range in a set.

delete :: Int -> RIntSet -> RIntSet #

/O(n). Delete an element from a set.

deleteRange :: (Int, Int) -> RIntSet -> RIntSet #

/O(n). Delete a continuos range from a set.

Combine

union :: RIntSet -> RIntSet -> RIntSet #

O(n*m). The union of two sets.

difference :: RIntSet -> RIntSet -> RIntSet #

O(n*m). Difference of two sets.

intersection :: RIntSet -> RIntSet -> RIntSet #

O(n*m). The intersection of two sets.

Filter

split :: Int -> RIntSet -> (RIntSet, RIntSet) #

O(log n). The expression (split x set) is a pair (set1,set2) where set1 comprises the elements of set less than x and set2 comprises the elements of set greater than x.

splitMember :: Int -> RIntSet -> (RIntSet, Bool, RIntSet) #

O(log n). Performs a split but also returns whether the pivot element was found in the original set.

Min/Max

findMin :: RIntSet -> Int #

O(log n). The minimal element of a set.

findMax :: RIntSet -> Int #

O(log n). The maximal element of a set.

Complement

complement :: RIntSet -> RIntSet #

O(n). Complement of the set.

Conversion

elems :: RIntSet -> [Int] #

O(n*r). An alias of toAscList. The elements of a set in ascending order. r is the size of longest range.

toList :: RIntSet -> [Int] #

O(n*r). Convert the set to a list of elements (in arbitrary order). r is the size of longest range.

fromList :: [Int] -> RIntSet #

O(n*log n). Create a set from a list of elements.

Note that unlike Data.Set and other binary trees, this always requires a full sort and traversal to create distinct, disjoint ranges before constructing the tree.

fromAscList :: [Int] -> RIntSet #

O(n). Create a set from a list of ascending elements.

The precondition is not checked. You may use valid to check the result. Note that unlike Data.Set and other binary trees, this always requires a full traversal to create distinct, disjoint ranges before constructing the tree.

toAscList :: RIntSet -> [Int] #

O(n*r). Convert the set to an ascending list of elements.

toRangeList :: RIntSet -> [(Int, Int)] #

O(n). Convert the set to a list of range pairs.

fromRangeList :: [(Int, Int)] -> RIntSet #

O(n*log n). Create a set from a list of range pairs.

Note that unlike Data.Set and other binary trees, this always requires a full sort and traversal to create distinct, disjoint ranges before constructing the tree.

fromRList :: RSet Int -> RIntSet #

O(n). Convert a list-based RSet to a map-based RIntSet.

toRList :: RIntSet -> RSet Int #

O(n). Convert a map-based RIntSet to a list-based RSet.

fromNormalizedRangeList :: [(Int, Int)] -> RIntSet #

O(n). Convert a normalized, non-adjacent, ascending list of ranges to a set.

The precondition is not checked. In general you should only use this function on the result of toRangeList or ensure valid on the result.