| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.SplaySeq.Raw
Description
A mutable splay tree-based sequence.
Synopsis
- type SplayIndex = PoolIndex
- undefSI :: SplayIndex
- nullSI :: SplayIndex -> Bool
- data RawSplaySeq s v a = RawSplaySeq {
- capacityRSS :: !Int
- freeRSS :: !(Pool s ())
- lRSS :: !(MVector s SplayIndex)
- rRSS :: !(MVector s SplayIndex)
- pRSS :: !(MVector s SplayIndex)
- sRSS :: !(MVector s SplayIndex)
- vRSS :: !(MVector s v)
- aggRSS :: !(MVector s v)
- revRSS :: !(MVector s Bit)
- actRSS :: !(MVector s a)
- newRSS :: (Unbox v, Unbox a, PrimMonad m) => Int -> m (RawSplaySeq (PrimState m) v a)
- sizeRSS :: PrimMonad m => RawSplaySeq (PrimState m) v a -> m Int
- seqSizeRSS :: (HasCallStack, PrimMonad m) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m Int
- allocNodeRSS :: (HasCallStack, PrimMonad m, Unbox v, Monoid a, Unbox a) => RawSplaySeq (PrimState m) v a -> v -> m SplayIndex
- allocSeqRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a) => RawSplaySeq (PrimState m) v a -> Vector v -> m SplayIndex
- freeNodeRSS :: (HasCallStack, PrimMonad m) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m ()
- freeSubtreeRSS :: (HasCallStack, PrimMonad m) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m ()
- assertRootRSS :: (HasCallStack, PrimMonad m) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m ()
- readRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> Int -> SplayIndex -> m (v, SplayIndex)
- writeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> Int -> v -> SplayIndex -> m SplayIndex
- modifyRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> (v -> v) -> Int -> SplayIndex -> m SplayIndex
- exchangeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> Int -> v -> SplayIndex -> m (v, SplayIndex)
- foldRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> Int -> Int -> SplayIndex -> m (v, SplayIndex)
- foldAllRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m v
- sactRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> Int -> Int -> a -> SplayIndex -> m SplayIndex
- reverseRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> Int -> Int -> SplayIndex -> m SplayIndex
- insertRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> Int -> v -> SplayIndex -> m SplayIndex
- deleteRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> Int -> SplayIndex -> m SplayIndex
- bisectLRSS :: (Show v, HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> (v -> Bool) -> SplayIndex -> m (Maybe SplayIndex, SplayIndex)
- rotateRSS :: (HasCallStack, PrimMonad m) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m ()
- splayRSS :: (HasCallStack, PrimMonad m, Unbox v, Monoid v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> Bool -> m ()
- splayKthRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> Int -> m SplayIndex
- updateNodeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m ()
- writeNodeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> v -> m ()
- modifyNodeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a) => RawSplaySeq (PrimState m) v a -> (v -> v) -> SplayIndex -> m ()
- exchangeNodeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> v -> m v
- swapLrNodeRSS :: (HasCallStack, PrimMonad m) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m ()
- reverseNodeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m ()
- propNodeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m ()
- propNodeFromRootRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m ()
- sactNodeRSS :: (HasCallStack, PrimMonad m, Unbox v, Monoid a, Unbox a, SegmentAction a v) => RawSplaySeq (PrimState m) v a -> SplayIndex -> a -> m ()
- mergeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> SplayIndex -> m SplayIndex
- merge3RSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> SplayIndex -> SplayIndex -> m SplayIndex
- splitAtRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> Int -> m (SplayIndex, SplayIndex)
- split3RSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> Int -> Int -> m (SplayIndex, SplayIndex, SplayIndex)
- captureRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> Int -> Int -> m SplayIndex
Documentation
type SplayIndex = PoolIndex #
Index of a SplayNode stored in a SplayMap.
undefSI :: SplayIndex #
nullSI :: SplayIndex -> Bool #
data RawSplaySeq s v a #
Mutable, splay tree-based sequences.
Invariants
- The sequence order is kept in the tree before and after the splaying operation. Left children have smaller indices and right children have bigger indices.
I don't need lazily propagated actions
Well, use `RawSplaySeq s v v`. It allocates an unused vector, but doesn't duplicate the source code anyways.
Constructors
| RawSplaySeq | |
Fields
| |
newRSS :: (Unbox v, Unbox a, PrimMonad m) => Int -> m (RawSplaySeq (PrimState m) v a) #
\(O(N)\) Creates a new RawSplaySeq of capacity n with lazily propagated values.
sizeRSS :: PrimMonad m => RawSplaySeq (PrimState m) v a -> m Int #
\(O(1)\) Returns the number of elements stored. Requires monad for tracking the state.
seqSizeRSS :: (HasCallStack, PrimMonad m) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m Int #
\(O(1)\) Returns the number of elements in a sequence.
Allocation
allocNodeRSS :: (HasCallStack, PrimMonad m, Unbox v, Monoid a, Unbox a) => RawSplaySeq (PrimState m) v a -> v -> m SplayIndex #
\(O(1)\) Allocates a new node as a single element sequence.
allocSeqRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a) => RawSplaySeq (PrimState m) v a -> Vector v -> m SplayIndex #
\(O(N)\) Allocates a new sequence, internally as a binary tree from the bottom to the top.
freeNodeRSS :: (HasCallStack, PrimMonad m) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m () #
\(O(1)\) Frees a node.
freeSubtreeRSS :: (HasCallStack, PrimMonad m) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m () #
\(O(N)\) Frees a subtree.
assertRootRSS :: (HasCallStack, PrimMonad m) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m () #
\(O(1)\) Asserts the node is the root.
API
readRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> Int -> SplayIndex -> m (v, SplayIndex) #
Amortized \(O(\log N)\). Reads a kth node's value.
writeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> Int -> v -> SplayIndex -> m SplayIndex #
Amortized \(O(\log N)\). Writes a kth node's value.
modifyRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> (v -> v) -> Int -> SplayIndex -> m SplayIndex #
Amortized \(O(\log N)\). Modifies a kth node's value.
exchangeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> Int -> v -> SplayIndex -> m (v, SplayIndex) #
Amortized \(O(\log N)\). Exchanges a kth node's value.
foldRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> Int -> Int -> SplayIndex -> m (v, SplayIndex) #
Amortized \(O(\log N)\). Folds an interval [l, r].
foldAllRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m v #
Amortized \(O(\log N)\). Folds the whole sequence.
sactRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> Int -> Int -> a -> SplayIndex -> m SplayIndex #
Amortized \(O(\log N)\).
reverseRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> Int -> Int -> SplayIndex -> m SplayIndex #
Amortised \(O(\log N)\). Reverses the order of nodes in given range [l, r]. Requires the
monoid and the action to be commutative.
insertRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> Int -> v -> SplayIndex -> m SplayIndex #
Amortized \(O(\log N)\). Inserts a node at k.
deleteRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> Int -> SplayIndex -> m SplayIndex #
Amortized \(O(\log N)\). Deletes a node at k.
bisectLRSS :: (Show v, HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> (v -> Bool) -> SplayIndex -> m (Maybe SplayIndex, 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.
Self-balancing methods (internals)
rotateRSS :: (HasCallStack, PrimMonad m) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m () #
Amortized \(O(\log N)\). Rotates the node. Propagation and updates are done outside of the
function (see propFromRootRSS).
splayRSS :: (HasCallStack, PrimMonad m, Unbox v, Monoid v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> Bool -> m () #
Amortized \(O(\log N)\). Moves a node to the root, performing self-balancing heuristic called rotations.
Prerequisites
Parents are already propagated.
After call
The node is updated and propagated.
splayKthRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> Int -> m SplayIndex #
Amortized \(O(\log N)\). Finds k th node from the left and splays it.
Returns the new root.
Node operations (internals)
updateNodeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m () #
\(O(1)\) Recomputes the node size and the monoid aggregation.
writeNodeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> v -> m () #
\(O(1)\) Writes the monoid.
Prerequisties
The node is a root (it's splayed).
modifyNodeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a) => RawSplaySeq (PrimState m) v a -> (v -> v) -> SplayIndex -> m () #
\(O(1)\) Modifies the monoid.
Prerequisties
The node is a root (it's splayed).
exchangeNodeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> v -> m v #
\(O(1)\) Modifies the monoid.
Prerequisties
The node is a root (it's splayed).
swapLrNodeRSS :: (HasCallStack, PrimMonad m) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m () #
\(O(1)\) Reverses left and right children.
reverseNodeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m () #
\(O(1)\) Reverses left and right children, recursively and lazily.
propNodeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m () #
Amortized \(O(\log N)\). Propgates at a node.
propNodeFromRootRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> m () #
Amortized \(O(\log N)\). Propagetes from the root to the given node.
sactNodeRSS :: (HasCallStack, PrimMonad m, Unbox v, Monoid a, Unbox a, SegmentAction a v) => RawSplaySeq (PrimState m) v a -> SplayIndex -> a -> m () #
Amortized \(O(\log N)\). Propgates at a node.
Split / merge
mergeRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> SplayIndex -> m SplayIndex #
Amortized \(O(\log N)\). Merges two nodes. It's implemented a reverse operation of splitRSS.
merge3RSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> SplayIndex -> SplayIndex -> m SplayIndex #
Amortized \(O(\log N)\). Folds three nodes from left to right.
splitAtRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> Int -> m (SplayIndex, SplayIndex) #
Amortized \(O(\log N)\). Splits a sequneces into two nodes. It's implemented a reverse
operation of splitRSS.
split3RSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> Int -> Int -> m (SplayIndex, SplayIndex, SplayIndex) #
Amortized \(O(\log N)\). Splits into three sequences from right to left.
captureRSS :: (HasCallStack, PrimMonad m, Monoid v, Unbox v, Monoid a, Unbox a, SegmentAction a v, Eq a) => RawSplaySeq (PrimState m) v a -> SplayIndex -> Int -> Int -> m SplayIndex #
Amortized \(O(\log N)\). Captures a subtree of [l, r). Be sure that it's half-open interval! Splay the new root after call.