| Copyright | (c) Dylan Simon 2015 |
|---|---|
| License | MIT |
| Safe Haskell | Safe |
| Language | Haskell2010 |
Data.RangeSet.IntMap
Description
This is simply a specialization of Data.RangeSet.Map to Int.
The implementation of RIntSet is based on Data.IntMap.Strict.
Synopsis
- data RIntSet
- (\\) :: RIntSet -> RIntSet -> RIntSet
- null :: RIntSet -> Bool
- isFull :: RIntSet -> Bool
- size :: RIntSet -> Int
- member :: Int -> RIntSet -> Bool
- notMember :: Int -> RIntSet -> Bool
- lookupLT :: Int -> RIntSet -> Maybe Int
- lookupGT :: Int -> RIntSet -> Maybe Int
- lookupLE :: Int -> RIntSet -> Maybe Int
- lookupGE :: Int -> RIntSet -> Maybe Int
- containsRange :: (Int, Int) -> RIntSet -> Bool
- isSubsetOf :: RIntSet -> RIntSet -> Bool
- valid :: RIntSet -> Bool
- empty :: RIntSet
- full :: RIntSet
- singleton :: Int -> RIntSet
- singletonRange :: (Int, Int) -> RIntSet
- insert :: Int -> RIntSet -> RIntSet
- insertRange :: (Int, Int) -> RIntSet -> RIntSet
- delete :: Int -> RIntSet -> RIntSet
- deleteRange :: (Int, Int) -> RIntSet -> RIntSet
- union :: RIntSet -> RIntSet -> RIntSet
- difference :: RIntSet -> RIntSet -> RIntSet
- intersection :: RIntSet -> RIntSet -> RIntSet
- split :: Int -> RIntSet -> (RIntSet, RIntSet)
- splitMember :: Int -> RIntSet -> (RIntSet, Bool, RIntSet)
- findMin :: RIntSet -> Int
- findMax :: RIntSet -> Int
- complement :: RIntSet -> RIntSet
- elems :: RIntSet -> [Int]
- toList :: RIntSet -> [Int]
- fromList :: [Int] -> RIntSet
- fromAscList :: [Int] -> RIntSet
- toAscList :: RIntSet -> [Int]
- toRangeList :: RIntSet -> [(Int, Int)]
- fromRangeList :: [(Int, Int)] -> RIntSet
- fromRList :: RSet Int -> RIntSet
- toRList :: RIntSet -> RSet Int
- fromNormalizedRangeList :: [(Int, Int)] -> RIntSet
Range set type
Internally set is represented as sorted list of distinct inclusive ranges.
Operators
Query
lookupLT :: Int -> RIntSet -> Maybe Int Source #
O(log n). Find largest element smaller than the given one.
lookupGT :: Int -> RIntSet -> Maybe Int Source #
O(log n). Find smallest element greater than the given one.
lookupLE :: Int -> RIntSet -> Maybe Int Source #
O(log n). Find largest element smaller or equal to than the given one.
lookupGE :: Int -> RIntSet -> Maybe Int Source #
O(log n). Find smallest element greater or equal to than the given one.
containsRange :: (Int, Int) -> RIntSet -> Bool Source #
O(log n). Is the entire range contained within the set?
isSubsetOf :: RIntSet -> RIntSet -> Bool Source #
O(n+m). Is this a subset?
(s1 tells whether isSubsetOf s2)s1 is a subset of s2.
valid :: RIntSet -> Bool Source #
O(n). Ensure that a set is valid. All functions should return valid sets
except those with unchecked preconditions: fromAscList,
fromNormalizedRangeList
Construction
Combine
Filter
split :: Int -> RIntSet -> (RIntSet, RIntSet) Source #
O(log n). The expression (split x set(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) Source #
O(log n). Performs a split but also returns whether the pivot
element was found in the original set.
Min/Max
Complement
complement :: RIntSet -> RIntSet Source #
O(n). Complement of the set.
Conversion
elems :: RIntSet -> [Int] Source #
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] Source #
O(n*r). Convert the set to a list of elements (in arbitrary order). r is the size of longest range.
fromList :: [Int] -> RIntSet Source #
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 Source #
fromRangeList :: [(Int, Int)] -> RIntSet Source #
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.
fromNormalizedRangeList :: [(Int, Int)] -> RIntSet Source #
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.