| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.SplaySeq
Contents
Description
A mutable splay tree-based sequence.
Typical Problems
Synopsis
- data SplaySeq s v a = SplaySeq {
- rawSS :: !(RawSplaySeq s v a)
- rootSS :: !(MVector s SplayIndex)
- newLazySS :: (Unbox v, Unbox a, PrimMonad m) => Int -> m (SplaySeq (PrimState m) v a)
- newSS :: (Unbox v, PrimMonad m) => Int -> m (SplaySeq (PrimState m) v v)
- capacitySS :: SplaySeq s v a -> Int
- sizeSS :: PrimMonad m => SplaySeq (PrimState m) v a -> m Int
- seqSizeSS :: (HasCallStack, PrimMonad m) => SplaySeq (PrimState m) v a -> m Int
- allocSeqSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a) => SplaySeq (PrimState m) v a -> Vector v -> m ()
- freeSS :: (HasCallStack, PrimMonad m) => SplaySeq (PrimState m) v a -> m ()
- readSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> Int -> m v
- writeSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> Int -> v -> m ()
- modifySS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> (v -> v) -> Int -> m ()
- exchangeSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> Int -> v -> m v
- foldSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> Int -> Int -> m v
- foldAllSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> m v
- sactSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> Int -> Int -> a -> m ()
- reverseSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> Int -> Int -> m ()
- insertSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> Int -> v -> m ()
- deleteSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> Int -> m ()
- bisectLSS :: (Show v, HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> (v -> Bool) -> m (Maybe SplayIndex)
Documentation
Mutable, splay tree-based sequences.
Internally, it's RawSplaySeq with automatic root index update.
Constructors
| SplaySeq | |
Fields
| |
newLazySS :: (Unbox v, Unbox a, PrimMonad m) => Int -> m (SplaySeq (PrimState m) v a) #
\(O(N)\) Allocates a SplaySeq with lazily propagated values.
newSS :: (Unbox v, PrimMonad m) => Int -> m (SplaySeq (PrimState m) v v) #
\(O(N)\) Allocates a SplaySeq without lazily propagated values. It still allocates needless
vector, but I failed to fix it.
capacitySS :: SplaySeq s v a -> Int #
\(O(1)\) Returns the maximum number of elements.
sizeSS :: PrimMonad m => SplaySeq (PrimState m) v a -> m Int #
\(O(1)\) Returns the number of elements stored. Requires monad for tracking the state.
seqSizeSS :: (HasCallStack, PrimMonad m) => SplaySeq (PrimState m) v a -> m Int #
\(O(1)\) Returns the number of elements in a sequence.
Allocation
allocSeqSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a) => SplaySeq (PrimState m) v a -> Vector v -> m () #
\(O(N)\) Allocates a new sequence, internally as a binary tree from the bottom to the top.
API
readSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> Int -> m v #
Amortized \(O(\log N)\). Reads a kth node's value.
writeSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> Int -> v -> m () #
Amortized \(O(\log N)\). Writes a kth node's value.
modifySS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> (v -> v) -> Int -> m () #
Amortized \(O(\log N)\). Modifies a kth node's value.
exchangeSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> Int -> v -> m v #
Amortized \(O(\log N)\). Exchanges a kth node's value.
foldSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> Int -> Int -> m v #
Amortized \(O(\log N)\). Folds an interval [l, r].
foldAllSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> m v #
Amortized \(O(\log N)\). Folds the whole sequence.
sactSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> Int -> Int -> a -> m () #
Amortized \(O(\log N)\).
reverseSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> Int -> Int -> m () #
Amortised \(O(\log N)\). Reverses the order of nodes in given range [l, r]. Requires the
monoid and the action to be commutative.
insertSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> Int -> v -> m () #
Amortized \(O(\log N)\). Inserts a node at k.
deleteSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> Int -> m () #
Amortized \(O(\log N)\). Deletes a node at k.
bisectLSS :: (Show v, HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => SplaySeq (PrimState m) v a -> (v -> Bool) -> m (Maybe SplayIndex) #
Amortized \(O(\log N)\). Bisection method over the sequence. Partition point. Note that The user function is run over each node, not fold of an interval.