AtCoder.Internal.GrowVec

Growable vector with some runtime overhead (by MutVar).

Example

>>> import AtCoder.Internal.GrowVec qualified as GV
>>> growVec <- GV.new @_ @Int 0
>>> GV.null growVec
True

>>> GV.pushBack growVec 10
>>> GV.pushBack growVec 11
>>> GV.pushBack growVec 12
>>> GV.freeze growVec
[10,11,12]

>>> GV.length growVec
3

>>> GV.capacity growVec
4

>>> GV.write growVec 1 20
>>> GV.read growVec 1
20

>>> GV.popBack growVec
Just 12

>>> GV.popBack growVec
Just 20

>>> GV.reserve growVec 20
>>> GV.capacity growVec
20

>>> GV.unsafeFreeze growVec
[10]

Since: 1.0.0.0

GrowVec

data GrowVec s a

Growable vector with some runtime overhead.

Since: 1.0.0.0

Constructors

new :: (PrimMonad m, Unbox a) => Int -> m (GrowVec (PrimState m) a)

\(O(n)\) Creates a GrowVec with initial capacity \(n\).

Since: 1.0.0.0

build :: (PrimMonad m, Unbox a) => Vector a -> m (GrowVec (PrimState m) a)

\(O(n)\) Creates a GrowVec with initial values.

Since: 1.0.0.0

reserve :: (HasCallStack, PrimMonad m, Unbox a) => GrowVec (PrimState m) a -> Int -> m ()

\(O(n)\) Reserves the internal storage capacity.

Since: 1.0.0.0

Metadata

length :: (PrimMonad m, Unbox a) => GrowVec (PrimState m) a -> m Int

\(O(1)\) Returns the number of elements in the vector.

Since: 1.0.0.0

capacity :: (PrimMonad m, Unbox a) => GrowVec (PrimState m) a -> m Int

\(O(1)\) Returns the capacity of the internal the vector.

Since: 1.0.0.0

null :: (PrimMonad m, Unbox a) => GrowVec (PrimState m) a -> m Bool

\(O(1)\) Returns True if the vector is empty.

Since: 1.0.0.0

Readings

read :: (HasCallStack, PrimMonad m, Unbox a) => GrowVec (PrimState m) a -> Int -> m a

\(O(1)\) Yields the element at the given position. Will throw an exception if the index is out of range.

Since: 1.0.0.0

Modifications

Writing

write :: (HasCallStack, PrimMonad m, Unbox a) => GrowVec (PrimState m) a -> Int -> a -> m ()

\(O(1)\) Writes to the element at the given position. Will throw an exception if the index is out of range.

Since: 1.0.0.0

Push/pop

pushBack :: (PrimMonad m, Unbox a) => GrowVec (PrimState m) a -> a -> m ()

Amortized \(O(1)\). Grow the capacity twice

Since: 1.0.0.0

popBack :: (PrimMonad m, Unbox a) => GrowVec (PrimState m) a -> m (Maybe a)

\(O(1)\) Removes the last element from the buffer and returns it, or Nothing if it is empty.

Since: 1.0.0.0

popBack_ :: (PrimMonad m, Unbox a) => GrowVec (PrimState m) a -> m ()

\(O(1)\) popBack with the return value discarded.

Since: 1.0.0.0

Conversion

freeze :: (PrimMonad m, Unbox a) => GrowVec (PrimState m) a -> m (Vector a)

\(O(n)\) Yields an immutable copy of the mutable vector.

Since: 1.0.0.0

unsafeFreeze :: (PrimMonad m, Unbox a) => GrowVec (PrimState m) a -> m (Vector a)

\(O(1)\) Unsafely converts a mutable vector to an immutable one without copying. The mutable vector may not be used after this operation.

Since: 1.0.0.0