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).

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

See empty; do no check that length is strictly positive.

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).

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

See toVectorN but do not check that N is positive.

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.

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

See fromVector but do not check for empty vector.

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. Slow! If possible, use unsafePush. 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.

reset :: CStack v a -> CStack v a

Reset the stack. O(1).

Queries

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

Check if the stack is full.

Folding

foldl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> CStack v b -> a

Left fold. O(m).

foldl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> CStack v b -> a

Left fold with strict accumulator. O(m).

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

Left fold on non-empty vectors with strict accumulator. O(m).

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

Compute the sum of the elements on the stack. O(m).

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

Compute the product of the elements on the stack. O(m).