Deque¶

1

import "std/data/deque";

Deque<T> struct¶

A deque in Spice is a commonly used data structure that allows insertion and removal of elements from both ends: front and back.

Time complexity:
Insert at front: O(1)
Insert at back: O(1)
Delete from front: O(1)
Delete from back: O(1)
Search: O(n)

Deques pre-allocate space using an initial size and a resize factor to not have to re-allocate with every item pushed. This implementation uses a ring buffer, that wraps around when one of the indices reach the start or end of the allocated heap space.

Constructors¶

ctor¶

1

public p Deque.ctor(unsigned long initAllocItems, const T& defaultValue)

Construct a deque pre-filled with a number of copies of a default value

Parameters

ctor¶

1

public p Deque.ctor(unsigned int initAllocItems)

Construct a deque, pre-allocating space for the given number of items

Parameters

ctor¶

1

public p Deque.ctor(unsigned long initAllocItems = INITIAL_ALLOC_COUNT)

Construct a deque, pre-allocating space for the given number of items

Parameters

ctor¶

1

public p Deque.ctor(const Deque<T>& original)

Construct a deque as a deep copy of another deque

Parameters

Methods¶

pushBack¶

1

public p Deque.pushBack(const T& item)

Add an item at the back of the deque

Parameters

pushFront¶

1

public p Deque.pushFront(const T& item)

Add an item at the front of the deque

Parameters

popFront¶

1

public f<T&> Deque.popFront()

Retrieve the first item and remove it

Returns: T& — First item

popBack¶

1

public f<T&> Deque.popBack()

Retrieve the last item and remove it

Returns: T& — Last item

front¶

1

public f<T&> Deque.front()

Retrieve the first item without removing it from the deque

Returns: T& — First item

back¶

1

public f<T&> Deque.back()

Retrieve the last item without removing it from the deque

Returns: T& — Last item

getSize¶

1

public f<long> Deque.getSize()

Retrieve the current size of the deque

Returns: long — Current size of the deque

getCapacity¶

1

public f<long> Deque.getCapacity()

Retrieve the current capacity of the deque

Returns: long — Current capacity of the deque

isEmpty¶

1

public f<bool> Deque.isEmpty()

Checks if the deque contains any items at the moment

Returns: bool — Empty or not empty

isFull¶

1

public f<bool> Deque.isFull()

Checks if the deque exhausts its capacity and needs to resize at the next call of push

Returns: bool — Full or not full

reserve¶

1

public p Deque.reserve(unsigned long itemCount)

Reserves itemCount items

Parameters

pack¶

1

public p Deque.pack()

Frees allocated memory that is not used by the deque

Operators¶

operator=¶

1

public p operator=<T>(Deque<T>& this, const Deque<T>& newValue)

Copy-assign the contents of another deque into this one

Parameters

operator==¶

1

public f<bool> operator==<T>(const Deque<T>& lhs, const Deque<T>& rhs)

Check if two deques are equal, i.e. they have the same size and equal contents in order

Parameters

Returns: bool — Equal or not equal

operator!=¶

1

public f<bool> operator!=<T>(const Deque<T>& lhs, const Deque<T>& rhs)

Check if two deques are not equal

Parameters

Returns: bool — Not equal or equal