Copyright | (c) Dominik Schrempf 2020 |
---|---|
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
. Use the data constructors for MStack
and
Stack
only if you know what you are doing.
When denoting the asymptotic runtime of functions, n
refers to the circular
stack size.
Synopsis
- data MStack v s a = MStack {}
- 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)
- 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)
- 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)
- foldl :: (Vector v b, PrimMonad m) => (a -> b -> a) -> a -> MStack v (PrimState m) b -> m a
- sum :: (Num a, Vector v a, PrimMonad m) => MStack v (PrimState m) a -> m a
- product :: (Num a, Vector v a, PrimMonad m) => MStack v (PrimState m) a -> m a
- data Stack v a = Stack {}
- 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 deepest (oldest) element of the stack, the last element of the vector is the current (newest) 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 deepest (oldest) element of the stack, the last element of the returned vector is the current (newest) 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 deepest (oldest) element of the stack, the last element of the returned vector is the current (newest) 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 current 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).
Folds
Commutativity of the combining function is assumed for fold-like functions provided in this module, that is, the order of elements of the stack must not matter!
foldl :: (Vector v b, PrimMonad m) => (a -> b -> a) -> a -> MStack v (PrimState m) b -> m a Source #
Immutable circular stacks
Immutable circular stack; useful, for example, to save, or restore a mutable circular stack.