| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.IntervalSet
Description
IntervalSet is a sparse set that manages non-overlapping (l, r) value pairs.
Typically used with StateT.
Typical problems
Synopsis
- type IntervalSet = IntervalMap ()
- emptyIS :: IntervalSet
- lookupIS :: Int -> Int -> IntervalSet -> Maybe (Int, Int)
- intersectsIS :: Int -> Int -> IntervalSet -> Bool
- containsIS :: Int -> IntervalSet -> Bool
- insertMIS :: Monad m => Int -> Int -> (Int -> Int -> m ()) -> (Int -> Int -> m ()) -> IntervalSet -> m IntervalSet
- insertIS :: Int -> Int -> IntervalSet -> IntervalSet
- deleteMIS :: Monad m => Int -> Int -> (Int -> Int -> m ()) -> IntervalSet -> m IntervalSet
- deleteIS :: Int -> Int -> IntervalSet -> IntervalSet
- mexIS :: IntervalSet -> Int
Documentation
type IntervalSet = IntervalMap () #
IntervalSet is a sparse set that manages non-overlapping (l, r) value pairs.
emptyIS :: IntervalSet #
\(O(1)\) Creates an empty IntervalSet.
lookupIS :: Int -> Int -> IntervalSet -> Maybe (Int, Int) #
\(O(\min(n, W))\) Looks up an interval that contains [l, r].
intersectsIS :: Int -> Int -> IntervalSet -> Bool #
\(O(\min(n, W))\) Boolean variant of lookupIM.
containsIS :: Int -> IntervalSet -> Bool #
\(O(\min(n, W))\) Point variant of intersectsIM.
insertMIS :: Monad m => Int -> Int -> (Int -> Int -> m ()) -> (Int -> Int -> m ()) -> IntervalSet -> m IntervalSet #
Amortized \(O(\min(\log n, W))\) interval insertion with side effects. Old overlapping intervals are overwritten.
insertIS :: Int -> Int -> IntervalSet -> IntervalSet #
Amortized \(O(\min(\log n, W))\) interval insertion. Old overlapping intervals are overwritten.
deleteMIS :: Monad m => Int -> Int -> (Int -> Int -> m ()) -> IntervalSet -> m IntervalSet #
Amortized \(O(\min(\log n, W))\) interval deletion with side effects.
deleteIS :: Int -> Int -> IntervalSet -> IntervalSet #
Amortized \(O(\min(\log n, W))\) interval deletion.
mexIS :: IntervalSet -> Int #
\(O(\min(\log n, W))\) Mex retrieval.