Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.Extra.Seq

Contents

Seq
Constructors
Merge/split
Read/write
Products
Applications
Insert/delete
Bisection methods
- C++-like
- Splits
Conversions

Description

Dynamic sequence of monoid values with monoid actions on them through the SegAct instance.

Example

Expand

Create a Seq storage of length $10$ :

>>> import AtCoder.Extra.Monoid.RangeAdd qualified as RangeAdd
>>> import AtCoder.Extra.Seq qualified as Seq
>>> import AtCoder.LazySegTree (SegAct (..))
>>> import Data.Semigroup (Sum (..))
>>> import Data.Vector.Unboxed qualified as VU
>>> seq <- Seq.new @_ @(RangeAdd.RangeAdd (Sum Int)) @(Sum Int) 10

Allocate a sequence of $0, 1, 2, 3$ :

>>> handle <- Seq.newSeq seq (VU.fromList [0, 1, 2, 3])

Get monoid products:

>>> Seq.prodAll seq handle
Sum {getSum = 6}

>>> Seq.prod seq handle 1 3
Sum {getSum = 3}

read, write, modify and exchange are available:

>>> -- [0, 1, 2, 3] -> [0, 10, 2, 30]
>>> Seq.write seq handle 3 30
>>> Seq.modify seq handle (* 10) 1

Actions can be performed with SegAct instances:

>>> -- [0, 10, 2, 30] -> [0, 20, 12, 40]
>>> Seq.applyIn seq handle 1 4 (RangeAdd.new 10)
>>> Seq.prod seq handle 1 4
Sum {getSum = 72}

The sequence can be reversed if the action type is commutative:

>>> Seq.reverse seq handle 0 4
>>> VU.map getSum <$> Seq.freeze seq handle
[40,12,20,0]

The sequence is dynamic and new elements can be inserted or deleted:

>>> -- [40, 12, 20, 0] -> [40, 33, 12, 20, 0]
>>> Seq.insert seq handle 1 (Sum 33)
>>> -- [40, 33, 12, 20, 0] -> [40, 33, 12, 0]
>>> Seq.delete seq handle 3
Sum {getSum = 20}

>>> VU.map getSum <$> Seq.freeze seq handle
[40,33,12,0]

The Seq storage can store multiple sequences:

>>> handle2 <- Seq.newSeq seq (VU.generate 2 Sum)
>>> VU.map getSum <$> Seq.freeze seq handle2
[0,1]

Merge/split operations are available. merge functions mutate the given handle to be the merged sequence handle:

>>> Seq.merge seq handle handle2
>>> VU.map getSum <$> Seq.freeze seq handle
[40,33,12,0,0,1]

split functions mutate the given handle to be the leftmost one and returns right sequence handles:

>>> (handleM, handleR) <- Seq.split3 seq handle 2 4
>>> VU.map getSum <$> Seq.freeze seq handle
[40,33]

>>> VU.map getSum <$> Seq.freeze seq handleM
[12,0]

>>> VU.map getSum <$> Seq.freeze seq handleR
[0,1]

Bisection methods are available for monoid values and their products:

>>> Seq.reset seq
>>> handle <- Seq.newSeq seq $ VU.generate 10 Sum
>>> Seq.ilowerBound seq handle (\_ x -> x < 5)
5

>>> Seq.ilowerBoundProd seq handle (\_ x -> x < 5)
3

Since: 1.2.0.0

Synopsis

data Seq s f a = Seq {
- nSeq :: !Int
- poolSeq :: !(Pool s ())
- lSeq :: !(MVector s Index)
- rSeq :: !(MVector s Index)
- pSeq :: !(MVector s Index)
- sSeq :: !(MVector s Int)
- vSeq :: !(MVector s a)
- prodSeq :: !(MVector s a)
- revSeq :: !(MVector s Bit)
- lazySeq :: !(MVector s f)
}
newtype Handle s = Handle {
- unHandle :: MVector s Index
}
newHandle :: PrimMonad m => Index -> m (Handle (PrimState m))
nullHandle :: PrimMonad m => Handle (PrimState m) -> m Bool
invalidateHandle :: PrimMonad m => Handle (PrimState m) -> m ()
new :: (PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) => Int -> m (Seq (PrimState m) f a)
reset :: PrimMonad m => Seq (PrimState m) f a -> m ()
free :: (PrimMonad m, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> m ()
newNode :: (PrimMonad m, Monoid f, Unbox f, Unbox a) => Seq (PrimState m) f a -> a -> m (Handle (PrimState m))
newSeq :: (PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Vector a -> m (Handle (PrimState m))
merge :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Handle (PrimState m) -> m ()
merge3 :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Handle (PrimState m) -> Handle (PrimState m) -> m ()
merge4 :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Handle (PrimState m) -> Handle (PrimState m) -> Handle (PrimState m) -> m ()
split :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m (Handle (PrimState m))
split3 :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> m (Handle (PrimState m), Handle (PrimState m))
split4 :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> Int -> m (Handle (PrimState m), Handle (PrimState m), Handle (PrimState m))
splitLr :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> m (Handle (PrimState m), Handle (PrimState m))
read :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m a
readMaybe :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m (Maybe a)
write :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> a -> m ()
modify :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> (a -> a) -> Int -> m ()
exchange :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> a -> m a
prod :: (HasCallStack, Show a, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> m a
prodMaybe :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> m (Maybe a)
prodAll :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> m a
applyIn :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> f -> m ()
applyToRoot :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> f -> m ()
reverse :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> m ()
insert :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> a -> m ()
delete :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m a
delete_ :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m ()
detach :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m (Handle (PrimState m))
ilowerBound :: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> (Int -> a -> Bool) -> m Int
ilowerBoundM :: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> (Int -> a -> m Bool) -> m Int
ilowerBoundProd :: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> (Int -> a -> Bool) -> m Int
ilowerBoundProdM :: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> (Int -> a -> m Bool) -> m Int
isplitMaxRight :: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> (Int -> a -> Bool) -> m (Handle (PrimState m))
isplitMaxRightM :: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> (Int -> a -> m Bool) -> m (Handle (PrimState m))
isplitMaxRightProd :: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> (Int -> a -> Bool) -> m (Handle (PrimState m))
isplitMaxRightProdM :: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> (Int -> a -> m Bool) -> m (Handle (PrimState m))
freeze :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> m (Vector a)

Seq

data Seq s f a Source #

Storages of dynamic sequences of monoid values with monoid actions on them through the SegAct instance.

Since: 1.2.0.0

Constructors

Seq

Fields

nSeq :: !Int
The maximum number of elements.
Since: 1.2.0.0
poolSeq :: !(Pool s ())
Pool for free slot management.
Since: 1.2.0.0
lSeq :: !(MVector s Index)
Decomposed node data storage: left children.
Since: 1.2.0.0
rSeq :: !(MVector s Index)
Decomposed node data storage: right children.
Since: 1.2.0.0
pSeq :: !(MVector s Index)
Decomposed node data storage: parents.
Since: 1.2.0.0
sSeq :: !(MVector s Int)
Decomposed node data storage: subtree sizes.
Since: 1.2.0.0
vSeq :: !(MVector s a)
Decomposed node data storage: monoid values.
Since: 1.2.0.0
prodSeq :: !(MVector s a)
Decomposed node data storage: monoid products.
Since: 1.2.0.0
revSeq :: !(MVector s Bit)
Decomposed node data storage: reversed flag of children.
Since: 1.2.0.0
lazySeq :: !(MVector s f)
Decomposed node data storage: lazily propagated monoid action. Use () if you don't need monoid actions.
Since: 1.2.0.0

newtype Handle s Source #

Handle for a sequence in Seq. It internally stores the root node and updates it following splaying operations, as Seq utilizes a splay tree structure.

Since: 1.2.0.0

Constructors

Handle
Fields unHandle :: MVector s Index Since: 1.2.0.0

newHandle :: PrimMonad m => Index -> m (Handle (PrimState m)) Source #

$O(1)$ Creates a new sequence Handle from a root node index.

Since: 1.2.0.0

nullHandle :: PrimMonad m => Handle (PrimState m) -> m Bool Source #

$O(1)$ Returns whether the sequence is empty.

Since: 1.2.0.0

invalidateHandle :: PrimMonad m => Handle (PrimState m) -> m () Source #

$O(1)$ Invalidates a sequence handle. Note that it does not change or free the sequence.

Since: 1.2.0.0

Constructors

new :: (PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) => Int -> m (Seq (PrimState m) f a) Source #

$O(n)$ Creates a new Seq of length $n$ .

Since: 1.2.0.0

reset :: PrimMonad m => Seq (PrimState m) f a -> m () Source #

$O(1)$ Clears the sequence storage. All the handles must not be used again.

Since: 1.2.0.0

free :: (PrimMonad m, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> m () Source #

$O(n)$ Frees a sequence and invalidates the handle.

Since: 1.2.0.0

newNode :: (PrimMonad m, Monoid f, Unbox f, Unbox a) => Seq (PrimState m) f a -> a -> m (Handle (PrimState m)) Source #

$O(1)$ Allocates a new sequence of length $1$ .

Since: 1.2.0.0

newSeq :: (PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Vector a -> m (Handle (PrimState m)) Source #

$O(n)$ Allocates a new sequence.

Since: 1.2.0.0

Merge/split

merge :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Handle (PrimState m) -> m () Source #

Amortized $O(\log n)$ . Merges two sequences $l, r$ into one in the given order, ignoring empty sequences. The right sequence handle will be invalidated.

Since: 1.2.0.0

merge3 :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Handle (PrimState m) -> Handle (PrimState m) -> m () Source #

Amortized $O(\log n)$ . Merges three sequences $l, m, r$ into one in the given order, ignoring empty sequences. All handles, except for the leftmost one, will be invalidated.

Since: 1.2.0.0

merge4 :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Handle (PrimState m) -> Handle (PrimState m) -> Handle (PrimState m) -> m () Source #

Amortized $O(\log n)$ . Merges four sequences $a, b, c, d$ into one in the given order, ignoring empty sequences. All handles, except for the leftmost one, will be invalidated.

Constraints

The vertices must be roots.

Since: 1.2.0.0

split :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m (Handle (PrimState m)) Source #

Amortized $O(\log n)$ . Splits a sequences into two: $[0, k), [k, n)$ . The handle will point to the left sequence. Returns the right sequence handle.

Constraints

$0 \le k \le n$ .

Since: 1.2.0.0

split3 :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> m (Handle (PrimState m), Handle (PrimState m)) Source #

Amortized $O(\log n)$ . Splits a sequences into three: $[0, l), [l, r), [r, n)$ . The handle will point to the leftmost sequence. Returns the middle and the right sequence handles.

Constraints

$0 \le l \le r \le n$ .

Since: 1.2.0.0

split4 :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> Int -> m (Handle (PrimState m), Handle (PrimState m), Handle (PrimState m)) Source #

Amortized $O(\log n)$ . Splits a sequences into four: $[0, i), [i, j), [j, k), [k, n)$ . The handle will point to the leftmost sequence. Returns the non-leftmost sequence handles.

Constraints

$0 \le i \le j \le k \le n$ .

Since: 1.2.0.0

splitLr :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> m (Handle (PrimState m), Handle (PrimState m)) Source #

Amortized $O(\log n)$ . Splits a sequence into three: $[0, \mathrm{root}), \mathrm{root}, [\mathrm{root} + 1, n)$ .

Constraints

The sequence must be non-empty.

Since: 1.2.0.0

Read/write

read :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m a Source #

Amortized $O(\log n)$ . Reads the $k$ -th node's monoid value.

Constraints

$0 \le k \lt n$

Since: 1.2.0.0

readMaybe :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m (Maybe a) Source #

Amortized $O(\log n)$ . Reads the $k$ -th node's monoid value.

Since: 1.2.0.0

write :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> a -> m () Source #

Amortized $O(\log n)$ . Writes to the $k$ -th node's monoid value.

Constraints

$0 \le k \lt n$

Since: 1.2.0.0

modify :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> (a -> a) -> Int -> m () Source #

Amortized $O(\log n)$ . Modifies the $k$ -th node's monoid value.

Constraints

$0 \le k \lt n$

Since: 1.2.0.0

exchange :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> a -> m a Source #

Amortized $O(\log n)$ . Exchanges the $k$ -th node's monoid value.

Constraints

$0 \le k \lt n$

Since: 1.2.0.0

Products

prod :: (HasCallStack, Show a, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> m a Source #

Amortized $O(\log n)$ . Returns the monoid product in an interval $[l, r)$ .

Constraints

$0 \le l \le r \le n$

Since: 1.2.0.0

prodMaybe :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> m (Maybe a) Source #

Amortized $O(\log n)$ . Returns the monoid product in an interval $[l, r)$ . Returns Nothing if an invalid interval is given.

Since: 1.2.0.0

prodAll :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> m a Source #

Amortized $O(\log n)$ . Returns the monoid product of the whole sequence.

Since: 1.2.0.0

Applications

applyIn :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> f -> m () Source #

Amortized $O(\log n)$ . Given an interval $[l, r)$ , applies a monoid action $f$ .

Constraints

$0 \le l \le r \le n$

Since: 1.2.0.0

applyToRoot :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> f -> m () Source #

$O(1)$ Applies a monoid action $f$ to the root of a sequence.

Since: 1.2.0.0

reverse :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> Int -> m () Source #

Amortized $O(\log n)$ . Reverses the sequence in $[l, r)$ .

Constraints

The monoid action $f$ must be commutative.
The monoid value $v$ must be commutative.

Since: 1.2.0.0

Insert/delete

insert :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> a -> m () Source #

Amortized $O(\log n)$ . Inserts a new node at $k$ with initial monoid value $v$ . This function works for an empty sequence handle.

Constraints

$0 \le k \le n$

Since: 1.2.0.0

delete :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m a Source #

Amortized $O(\log n)$ . Frees the $k$ -th node and returns the monoid value of it.

Constraints

$0 \le k \lt n$

Since: 1.2.0.0

delete_ :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m () Source #

Amortized $O(\log n)$ . Frees the $k$ -th node.

Constraints

$0 \le k \lt n$

Since: 1.2.0.0

detach :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> Int -> m (Handle (PrimState m)) Source #

Amortized $O(\log n)$ . Detaches the $k$ -th node and returns a handle for it.

Constraints

$0 \le k \lt n$

Since: 1.2.0.0

Bisection methods

C++-like

ilowerBound Source #

Arguments

:: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)
=> Seq (PrimState m) f a	Sequence storage
-> Handle (PrimState m)	Sequence handle
-> (Int -> a -> Bool)	User predicate $f(i, v_i)$ that takes the index and the monoid value
-> m Int	Maximum $r$ , where $f(i, v_i)$ holds for $i \in [0, r)$

Amortized $O(\log n)$ .

Constraints

The sequence must be non-empty.

Since: 1.2.0.0

ilowerBoundM Source #

Arguments

:: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)
=> Seq (PrimState m) f a	Sequence storage
-> Handle (PrimState m)	Sequence handle
-> (Int -> a -> m Bool)	User predicate $f(i, v_i)$ that takes the index and the monoid value
-> m Int	Maximum $r$ , where $f(i, v_i)$ holds for $i \in [0, r)$

Amortized $O(\log n)$ .

Constraints

The sequence must be non-empty.

Since: 1.2.0.0

ilowerBoundProd Source #

Arguments

:: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)
=> Seq (PrimState m) f a	Sequence storage
-> Handle (PrimState m)	Sequence handle
-> (Int -> a -> Bool)	User predicate $f(i, v_0 \dots v_i)$ that takes the index and the monoid product
-> m Int	Maximum $r$ , where $f(i, v_0 \dots v_i)$ holds for $i \in [0, r)$

Amortized $O(\log n)$ .

Constraints

The sequence must be non-empty.

Since: 1.2.0.0

ilowerBoundProdM Source #

Arguments

:: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)
=> Seq (PrimState m) f a	Sequence storage
-> Handle (PrimState m)	Sequence handle
-> (Int -> a -> m Bool)	User predicate $f(i, v_0 \dots v_i)$ that takes the index and the monoid product
-> m Int	Maximum $r$ , where $f(i, v_0 \dots v_i)$ holds for $i \in [0, r)$

Amortized $O(\log n)$ .

Constraints

The sequence must be non-empty.

Since: 1.2.0.0

Splits

isplitMaxRight Source #

Arguments

:: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)
=> Seq (PrimState m) f a	Sequence storage
-> Handle (PrimState m)	Sequence handle
-> (Int -> a -> Bool)	User predicate $f(i, v_i)$ that takes the index and the monoid value
-> m (Handle (PrimState m))	Handle of the right sequence $[r, n)$ , where $r$ is the maximum $r$ such that $f(i, v_i)$ holds for $i \in [0, r)$

Amortized $O(\log n)$ . Splits a sequence into two with the user predicate and returns the right sequence handle.

Constraints

The sequence must be non-empty.

Since: 1.2.0.0

isplitMaxRightM Source #

Arguments

:: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)
=> Seq (PrimState m) f a	Sequence storage
-> Handle (PrimState m)	Sequence handle
-> (Int -> a -> m Bool)	User predicate $f(i, v_i)$ that takes the index and the monoid value
-> m (Handle (PrimState m))	Handle of the right sequence $[r, n)$ , where $r$ is the maximum $r$ such that $f(i, v_i)$ holds for $i \in [0, r)$

Amortized $O(\log n)$ . Splits a sequence into two with the user predicate and returns the right sequence handle.

Constraints

The sequence must be non-empty.

Since: 1.2.0.0

isplitMaxRightProd Source #

Arguments

:: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)
=> Seq (PrimState m) f a	Sequence storage
-> Handle (PrimState m)	Sequence handle
-> (Int -> a -> Bool)	User predicate $f(i, v_0 \dots v_i)$ that takes the index and the monoid value
-> m (Handle (PrimState m))	Handle of the right sequence $[r, n)$ , where $r$ is the maximum $r$ such that $f(i, v_0 \dots v_i)$ holds for $i \in [0, r)$

Amortized $O(\log n)$ . Splits a sequence into two with the user predicate and returns the right sequence handle.

Constraints

The sequence must be non-empty.

Since: 1.2.0.0

isplitMaxRightProdM Source #

Arguments

:: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)
=> Seq (PrimState m) f a	Sequence storage
-> Handle (PrimState m)	Sequence handle
-> (Int -> a -> m Bool)	User predicate $f(i, v_0 \dots v_i)$ that takes the index and the monoid value
-> m (Handle (PrimState m))	Handle of the right sequence $[r, n)$ , where $r$ is the maximum $r$ such that $f(i, v_0 \dots v_i)$ holds for $i \in [0, r)$

Amortized $O(\log n)$ . Splits a sequence into two with the user predicate and returns the right sequence handle.

Constraints

The sequence must be non-empty.

Since: 1.2.0.0

Conversions

freeze :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq (PrimState m) f a -> Handle (PrimState m) -> m (Vector a) Source #

Amortized $O(n)$ . Returns the sequence of monoid values.

Since: 1.2.0.0

Key	Shortcut
s	Open this search box
esc	Close this search box
↓,ctrl + j	Move down in search results
↑,ctrl + k	Move up in search results
↵	Go to active search result