Data.RangeSet.IntMap

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

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

Range set type

data RIntSet

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

Instances

Eq RIntSet

Ord RIntSet

Show RIntSet

Monoid RIntSet

NFData RIntSet

Semigroup RIntSet

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.