circular-0.4.0.2: Circular fixed-sized mutable vectors
Copyright(c) 2021 Dominik Schrempf
LicenseGPL-3.0-or-later
Maintainerdominik.schrempf@gmail.com
Stabilityunstable
Portabilityportable
Safe HaskellNone
LanguageHaskell2010

Data.Stack.Circular

Description

Creation date: Thu Jun 18 10:00:28 2020.

Construction of mutable circular stacks is done with replicate and subsequent pushes, or with fromVector.

When denoting the asymptotic runtime of functions, n refers to the circular stack size.

Synopsis

Mutable circular stacks

data MStack v s a Source #

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

size :: Vector v a => MStack v s a -> Int Source #

Size of the stack.

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

data Stack v a Source #

Immutable circular stack; useful, for example, to save, or restore a mutable circular stack.

Instances

Instances details
Eq (v a) => Eq (Stack v a) Source # 
Instance details

Defined in Data.Stack.Circular

Methods

(==) :: Stack v a -> Stack v a -> Bool #

(/=) :: Stack v a -> Stack v a -> Bool #

Read (v a) => Read (Stack v a) Source # 
Instance details

Defined in Data.Stack.Circular

Show (v a) => Show (Stack v a) Source # 
Instance details

Defined in Data.Stack.Circular

Methods

showsPrec :: Int -> Stack v a -> ShowS #

show :: Stack v a -> String #

showList :: [Stack v a] -> ShowS #

ToJSON (v a) => ToJSON (Stack v a) Source # 
Instance details

Defined in Data.Stack.Circular

Methods

toJSON :: Stack v a -> Value #

toEncoding :: Stack v a -> Encoding #

toJSONList :: [Stack v a] -> Value #

toEncodingList :: [Stack v a] -> Encoding #

FromJSON (v a) => FromJSON (Stack v a) Source # 
Instance details

Defined in Data.Stack.Circular

Methods

parseJSON :: Value -> Parser (Stack v a) #

parseJSONList :: Value -> Parser [Stack v a] #

thaw :: (Vector v a, PrimMonad m) => Stack v a -> m (MStack v (PrimState m) a) Source #

Conversion from immutable to mutable circular stack.

O(n).

freeze :: (Vector v a, PrimMonad m) => MStack v (PrimState m) a -> m (Stack v a) Source #

Conversion from mutable to immutable circular stack.

O(n).