Copyright | 2021 Dominik Schrempf |
---|---|
License | GPL-3.0-or-later |
Maintainer | dominik.schrempf@gmail.com |
Stability | unstable |
Portability | portable |
Safe Haskell | None |
Language | Haskell2010 |
Creation date: Thu Jun 18 10:00:28 2020.
Construction of mutable circular stacks is done with replicate
and subsequent
push
es, or with fromVector
.
When denoting the asymptotic runtime of functions, n
refers to the circular
stack size.
Synopsis
- data MStack v s a
- replicate :: (Vector v a, PrimMonad m) => Int -> a -> m (MStack v (PrimState m) a)
- fromVector :: (Vector v a, PrimMonad m) => v a -> m (MStack v (PrimState m) a)
- fromVectorWithIndex :: (Vector v a, PrimMonad m) => Int -> v a -> m (MStack v (PrimState m) a)
- toVector :: (Vector v a, PrimMonad m) => MStack v (PrimState m) a -> m (v a)
- take :: (Vector v a, PrimMonad m) => Int -> MStack v (PrimState m) a -> m (v a)
- size :: Vector v a => MStack v s a -> Int
- get :: (Vector v a, PrimMonad m) => MStack v (PrimState m) a -> m a
- pop :: (Vector v a, PrimMonad m) => MStack v (PrimState m) a -> m (a, MStack v (PrimState m) a)
- push :: (Vector v a, PrimMonad m) => a -> MStack v (PrimState m) a -> m (MStack v (PrimState m) a)
- foldM :: (Vector v b, PrimMonad m) => (a -> b -> a) -> a -> MStack v (PrimState m) b -> m a
- foldKM :: (Vector v b, PrimMonad m) => Int -> (a -> b -> a) -> a -> MStack v (PrimState m) b -> m a
- data Stack v a
- thaw :: (Vector v a, PrimMonad m) => Stack v a -> m (MStack v (PrimState m) a)
- freeze :: (Vector v a, PrimMonad m) => MStack v (PrimState m) a -> m (Stack v a)
Mutable circular stacks
Mutable circular stacks with fixed size are just mutable vectors with a pointer to the last element.
Construction and conversion
replicate :: (Vector v a, PrimMonad m) => Int -> a -> m (MStack v (PrimState m) a) Source #
A circular stack of given size with the same element replicated.
Call error
if the maximum size is zero or negative.
O(n).
fromVector :: (Vector v a, PrimMonad m) => v a -> m (MStack v (PrimState m) a) Source #
Convert a vector to a circular stack with size being equal to the length of the vector. The first element of the vector is the oldest element of the stack, the last element of the vector is the youngest element of the stack.
The vector must be non-empty.
O(n).
fromVectorWithIndex :: (Vector v a, PrimMonad m) => Int -> v a -> m (MStack v (PrimState m) a) Source #
Convert a vector to a circular stack with size being equal to the length of the vector. The element of the vector at the given index is the youngest element of the stack, the next element of the vector is the oldest element of the stack.
The vector must be non-empty.
O(n).
toVector :: (Vector v a, PrimMonad m) => MStack v (PrimState m) a -> m (v a) Source #
Convert a circular stack to a vector. The first element of the returned vector is the oldest element of the stack, the last element of the returned vector is the youngest element of the stack.
O(n).
take :: (Vector v a, PrimMonad m) => Int -> MStack v (PrimState m) a -> m (v a) Source #
Convert the last k elements of a circular stack to a vector. The first element of the returned vector is the oldest element of the stack, the last element of the returned vector is the youngest element of the stack.
The size of the stack must be larger than k.
O(k).
Accessors
get :: (Vector v a, PrimMonad m) => MStack v (PrimState m) a -> m a Source #
Get the last element without changing the stack.
O(1).
pop :: (Vector v a, PrimMonad m) => MStack v (PrimState m) a -> m (a, MStack v (PrimState m) a) Source #
Pop the youngest element from the stack and put the focus on the previous element.
Be careful:
The stack is always full! Popping returns the last element and moves the index to the second-last element, but the element is not truly removed from the stack. It is only put to the end of the queue.
Hence, pop
always succeeds, even if there are actually no more elements on
the stack (similar to walking backwards in a circle).
O(1).
push :: (Vector v a, PrimMonad m) => a -> MStack v (PrimState m) a -> m (MStack v (PrimState m) a) Source #
Push an element on the stack.
O(1).
Monadic folds
foldM :: (Vector v b, PrimMonad m) => (a -> b -> a) -> a -> MStack v (PrimState m) b -> m a Source #
Monadic fold from young to old over all elements of the stack.
Please also see the documentation of pop
.
O(n).
foldKM :: (Vector v b, PrimMonad m) => Int -> (a -> b -> a) -> a -> MStack v (PrimState m) b -> m a Source #
See foldM
but only over the k
youngest elements on the stack.
O(k).
Immutable circular stacks
Immutable circular stack; useful, for example, to save, or restore a mutable circular stack.