| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.IntervalMap
Description
IntervalMap is a sparse map that manages non-overlapping (l, r, x) value pairs.
Typically used with StateT.
Typical problems
Synopsis
- newtype IntervalMap a = IntervalMap {}
- emptyIM :: IntervalMap a
- fromVecMIM :: (Vector v a, Eq a, Monad m) => v a -> (Int -> Int -> a -> m ()) -> m (IntervalMap a)
- fromVecIM :: (Vector v a, Eq a) => v a -> IntervalMap a
- lookupIM :: Int -> Int -> IntervalMap a -> Maybe (Int, Int, a)
- readMayIM :: Int -> Int -> IntervalMap a -> Maybe a
- readIM :: HasCallStack => Int -> Int -> IntervalMap a -> a
- intersectsIM :: Int -> Int -> IntervalMap a -> Bool
- containsIM :: Int -> IntervalMap a -> Bool
- insertMIM :: (Monad m, Eq a) => Int -> Int -> a -> (Int -> Int -> a -> m ()) -> (Int -> Int -> a -> m ()) -> IntervalMap a -> m (IntervalMap a)
- insertIM :: Eq a => Int -> Int -> a -> IntervalMap a -> IntervalMap a
- deleteMIM :: Monad m => Int -> Int -> (Int -> Int -> a -> m ()) -> IntervalMap a -> m (IntervalMap a)
- deleteIM :: Int -> Int -> IntervalMap a -> IntervalMap a
- mexIM :: IntervalMap a -> Int
Documentation
newtype IntervalMap a #
IntervalMap is a sparse map that manages non-overlapping (l, r, x) value pairs.
Constructors
| IntervalMap | |
Instances
| Show a => Show (IntervalMap a) # | |
Defined in Data.IntervalMap Methods showsPrec :: Int -> IntervalMap a -> ShowS # show :: IntervalMap a -> String # showList :: [IntervalMap a] -> ShowS # | |
| Eq a => Eq (IntervalMap a) # | |
Defined in Data.IntervalMap Methods (==) :: IntervalMap a -> IntervalMap a -> Bool # (/=) :: IntervalMap a -> IntervalMap a -> Bool # | |
emptyIM :: IntervalMap a #
\(O(1)\) Creates an empty IntervalMap.
fromVecMIM :: (Vector v a, Eq a, Monad m) => v a -> (Int -> Int -> a -> m ()) -> m (IntervalMap a) #
\(O(NW)\) Creates an interval map combining successive equal values into one.
fromVecIM :: (Vector v a, Eq a) => v a -> IntervalMap a #
\(O(NW)\) Pure variant of fromVecMIM
lookupIM :: Int -> Int -> IntervalMap a -> Maybe (Int, Int, a) #
\(O(\min(n, W))\) Looks up an interval that contains [l, r].
readMayIM :: Int -> Int -> IntervalMap a -> Maybe a #
\(O(\min(n, W))\) Looks up an interval that contains [l, r] reads out the value.
readIM :: HasCallStack => Int -> Int -> IntervalMap a -> a #
\(O(\min(n, W))\) Looks up an interval that contains [l, r] reads out the value.
intersectsIM :: Int -> Int -> IntervalMap a -> Bool #
\(O(\min(n, W))\) Boolean variant of lookupIM.
containsIM :: Int -> IntervalMap a -> Bool #
\(O(\min(n, W))\) Point variant of intersectsIM.
insertMIM :: (Monad m, Eq a) => Int -> Int -> a -> (Int -> Int -> a -> m ()) -> (Int -> Int -> a -> m ()) -> IntervalMap a -> m (IntervalMap a) #
Amortized \(O(\min(\log n, W))\) interval insertion with side effects. Old overlapping intervals are overwritten.
insertIM :: Eq a => Int -> Int -> a -> IntervalMap a -> IntervalMap a #
Amortized \(O(\min(\log n, W))\) interval insertion. Old overlapping intervals are overwritten.
deleteMIM :: Monad m => Int -> Int -> (Int -> Int -> a -> m ()) -> IntervalMap a -> m (IntervalMap a) #
Amortized \(O(\min(\log n, W))\) interval deletion with side effects.
deleteIM :: Int -> Int -> IntervalMap a -> IntervalMap a #
Amortized \(O(\min(\log n, W))\) interval deletion.
mexIM :: IntervalMap a -> Int #
\(O(\min(\log n, W))\) Mex retrieval. REMARK: The interval map has to be like a set. Use
maxIS when possible.