Data.Stack.Circular

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

Boxed circular stacks

data CStack v a

Circular stacks with fxed maximum size are just normal vectors with a pointer to the last element.

Construction of CStacks is done with empty and subsequent pushes, or the provided type conversion functions so that the index and bounds are updated and checked consistently. The data constructor CStack is exported only to enable creation of orphan instances such as Arbitrary (QuickCheck).

When denoting the efficiency of the functions m refers to the current size of the stack, and n to the maximum size.

Constructors

CStack

Fields

• stack :: v a
• index :: !Int
• curSize :: !Int

Instances

(Eq (v a), Vector v a) => Eq (CStack v a)

Defined in Data.Stack.Circular

Methods

(==) :: CStack v a -> CStack v a -> Bool

(/=) :: CStack v a -> CStack v a -> Bool

(Show (v a), Vector v a) => Show (CStack v a)

Defined in Data.Stack.Circular

Methods

showsPrec :: Int -> CStack v a -> ShowS

show :: CStack v a -> String

showList :: [CStack v a] -> ShowS

(ToJSON a, ToJSON (v a), Vector v a) => ToJSON (CStack v a)

We have c /= FromJSON $ ToJSON c, but the elements on the stack and their order are correctly saved and restored.

Defined in Data.Stack.Circular

Methods

toJSON :: CStack v a -> Value

toEncoding :: CStack v a -> Encoding

toJSONList :: [CStack v a] -> Value

toEncodingList :: [CStack v a] -> Encoding

(FromJSON a, FromJSON (v a), Vector v a) => FromJSON (CStack v a)

Defined in Data.Stack.Circular

Methods

parseJSON :: Value -> Parser (CStack v a)

parseJSONList :: Value -> Parser [CStack v a]

Construction

empty :: Vector v a => Int -> CStack v a

A circular stack without an element but of a given maximum size. At this state, it is not very useful :). O(n).

Conversion

toVector :: Vector v a => CStack v a -> v a

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.

This is a relatively expensive operation. O(m).

toVectorN :: Vector v a => Int -> CStack v a -> v a

Convert the last N 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 N.

This is a relatively expensive operation. O(N).

fromVector :: Vector v a => v a -> CStack v a

Convert a vector to a circular stack. 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. O(n).

The vector must be non-empty.

Accessors

get :: Vector v a => CStack v a -> a

Get the last element without changing the stack. O(1).

pop :: Vector v a => CStack v a -> (a, CStack v a)

Get the last element and remove it from the stack. O(1).

The stack must be non-empty.

push :: Vector v a => a -> CStack v a -> CStack v a

Push an element on the stack. O(n).

unsafePush :: Vector v a => a -> CStack v a -> CStack v a

Push an element on the stack. O(1).

Be careful; the internal vector is mutated! The immutable circular stack may not be used after this operation.

Queries

isFull :: Vector v a => CStack v a -> Bool

Check if the stack is full.

Folding

foldl1' :: Vector v a => (a -> a -> a) -> CStack v a -> a

Compute summary statistics of the elements on the stack using a custom commutative mappend function.

sum :: (Num a, Vector v a) => CStack v a -> a

Compute the sum of the elements on the stack.

mean :: (Real a, Vector v a, Fractional b) => CStack v a -> b

Compute the mean of the elements on the stack.

product :: (Num a, Vector v a) => CStack v a -> a

Compute the product of the elements on the stack.

For reasons of efficiency, commutativity of the combining function is assumed. That is, the order of elements of the stack must not matter.