Struct cyclic_data_types::stack::Stack

source · 
pub struct Stack<const SIZE: usize, T, const WRITE_OVER: bool>(_);
Expand description

Stack is the struct used to define the state of a stack using cyclic List.

NOTE: It is recommended to use Vec over Stack for most applications. As Vec has better - if not similar performance to the Stack. It is therefore, Stack should only be used when the stack should strictly be limited to a given size and or convince of life features provided by the Stack.

Generics

List types are derived using 3 generics.

  1. const SIZE: usize

SIZE is a generic constant 1 that defines the maximum size of the stack

  1. T: Sized

T is the type of element stored in the stack

  1. const WRITE_OVER: bool>

Creating Stacks

Stacks can be created in a couple of ways.

  1. Empty Stack

Empty Stack are created using the Default trait implementation for Queue.

let stack: Stack<SIZE, i64, false> = Stack::default();
 
assert_eq!(stack.len(), 0);
Run
  1. From Array

Stack can also be derived from arrays. The maximum size of the stack is the same size as the array. This is done using the [From<[SIZE; T]] trait implementation for List.

let stack: Stack<SIZE, i64, false> = [1i64,2i64,3i64,4i64,5i64].into();
Run
  1. From Vectors, Linked Lists and Iterators

Since collections (Vectors, Linked Lists and Iterators) cannot guarantee a size at compile time - the conversion is not always guaranteed to succeed. This occurs when collection is larger than the stack variant. As a result, the new stack cannot be created without resulting in a Error::Overflow. This can be resolved by either making sure the collection is at max the same size as the stack variant or the cyclic list variant permits WRITE_OVER.

Therefore, the TryFrom trait implementation of stack must be used.

Example of a successful conversion

const SIZE: usize = 5;
let stack: Stack<SIZE, i64, false> = Stack::try_from(vec![1i64,2i64,3i64,4i64,5i64])
    .unwrap();
Run
const SIZE: usize = 5;
let stack: Stack<SIZE, i64, true> = vec![1i64,2i64,3i64,4i64,5i64,6i64].try_into()
    .unwrap();
Run

Example of a failed conversion

const SIZE: usize = 5;
let stack: Result<Stack<SIZE, i64, false>, Error> = Stack::try_from(vec![1i64,2i64,3i64,4i64,5i64,6i64]);
 
assert_eq!(stack, Err(Error::Overflow))
Run

WRITE_OVER is a generic constant 1 that is used to determine if elements should be over written on overflow [note]: Generic Constraints

  1.  ↩

Implementations§

Returns the number of elements in the stack.

let mut stack: Stack<SIZE, i64, false> = Stack::default();
 
assert_eq!(stack.len(), 0);
 
assert!(stack.push(1).is_ok());
 
assert_eq!(stack.len(), 1);
Run

Pushes an element to the end of the stack.

 
let mut stack: Stack<SIZE, i64, false> = Stack::default();
 
assert!(stack.push(1).is_ok());
 
assert!(stack.push(2).is_ok());
Run

Returns a reference to the top most element of the stack.

 
let mut stack: Stack<SIZE, i64, false> = vec![1,2,3].try_into().unwrap();
 
assert_eq!(stack.peek(), Some(&3));
Run

Returns the top most element of the stack - after removing said element from the stack.

 
let mut stack: Stack<SIZE, i64, false> = vec![1,2,3].try_into().unwrap();
 
assert_eq!(stack.pop(), Some(3));
Run

Returns a reference to an element in the stack using an index (relative to the top of the stack).

 
let mut stack: Stack<SIZE, i64, false> = vec![1,2].try_into().unwrap();
 
assert_eq!(stack.read(0).unwrap(), &2);
assert_eq!(stack.read(1).unwrap(), &1);
Run
Return

read returns Error if the index is out range of the stack. Otherwise the method returns a reference of element at index.

Methods from Deref<Target = List<STACK_SIZE, T, WRITE_OVER>>§

Returns the number of elements in the list

let mut list: List<SIZE, i64, false>  = List::default();
 
assert_eq!(list.len(), 0);
 
assert!(list.push_back(1).is_ok());
 
assert_eq!(list.len(), 1);
Run

Pushes a new element to the back of the list. This operation is done in O(1).

let mut list : List<SIZE, i64, false> = List::default();
 
assert!(list.push_back(1).is_ok());
Run

If the list is full - the list has two options based on the WRITE_OVER flag.

  1. WRITE_OVER = true

The first element is written over and dropped. Meaning the first element is no longer in the list.

let mut list : List<SIZE, i64, true> = [1,2,3,4,5].into();
 
assert!(list.push_back(6).is_ok());
 
assert_eq!(list, [2,3,4,5,6].into());
Run
  1. WRITE_OVER = false

The new element isn’t added to the list. Resulting in no change to the state of the list.

let mut list : List<SIZE, i64, false> = [1,2,3,4,5].into();
 
assert!(list.push_back(6).is_err());
 
assert_eq!(list, [1,2,3,4,5].into());
Run
Returns
  • Self if the push was successful
  • Error if List is full and the WRITE_OVER flag is set to false

Pushes a new element to the front of the list. This operation is done in O(1).

let mut list : List<SIZE, i64, false> = List::default();
 
assert!(list.push_front(1).is_ok());
Run

If the list is full - the list has two options based on the WRITE_OVER flag.

  1. WRITE_OVER = true

The last element is written over and dropped. Meaning the last element is no longer in the list.

let mut list : List<SIZE, i64, true> = [1,2,3,4,5].into();
 
assert!(list.push_front(0).is_ok());
 
assert_eq!(list, [0,1,2,3,4].into());
Run
  1. WRITE_OVER = false

The new element isn’t added to the list. Resulting in no change to the state of the list.

let mut list : List<SIZE, i64, false> = [1,2,3,4,5].into();
 
assert!(list.push_front(0).is_err());
 
assert_eq!(list, [1,2,3,4,5].into());
Run
Returns
  • Self if the push was successful
  • Error if List is full and the WRITE_OVER flag is set to false

returns a reference to an element in the list at provided index.

The get element retrieval works similarly to a cyclic list and python lists. Where, the list loop backs to the beginning of the list when the index is greater than the size of the list; and the list can be accessed from the end of the list using negative integers.

Therefore, let the following be a cyclic list.

let mut list : List<SIZE, i64, false> = [1,2,3,4,5].into();
Run

The following is equivalent in retrieving the last element

assert_eq!(list.get(4), Some(&5));
assert_eq!(list.get(4), list.get(9));
assert_eq!(list.get(4), list.get(-1));
Run

The following is equivalent in retrieving the first element

assert_eq!(list.get(0), Some(&1));
assert_eq!(list.get(0), list.get(5));
assert_eq!(list.get(0), list.get(-5));
Run
Return
  • None if the list is empty
  • Some(T) if the list has at least one element
Note

If certain constraints on the index is met. Then the following element retrievals are recommended over .get(index).

If, i ∈ [0, list.len()) then, list.get(i) = list[i as usize] If, i ∈ [-1 * list.len(), list.len()) then, list.get(i) = list[i as isize]

This is because the Index<usize> and Index<isize> are defined with let checks - with the assumption that certain guarantees on the index are provided on run time.

Such that, im(Self::Index<usize>) ⊆ im(Self::Index<isize>) ⊆ im(Self::get(&self, isize)).

returns a reference to an element in the list at provided index of the underlying array. get_unchecked is faster than all the other retrieval methods - however, provides less safety & features in exchange.

Returns

The method returns None if the underlying array has not value at the given index. Otherwise, the method returns a reference to the items at the array index.

returns a mutable reference to an element in the list at provided index.

The get_mut element retrieval works similarly to a cyclic list and python lists. Where, the list loop backs to the beginning of the list when the index is greater than the size of the list; and the list can be accessed from the end of the list using negative integers.

Therefore, let the following be a cyclic list.

let mut list : List<SIZE, i64, false> = [1,2,3,4,5].into();
Run

The following is equivalent in retrieving last element

assert_eq!(list.get_mut(4), Some(&mut 5));
assert_eq!(list.get_mut(9), Some(&mut 5));
assert_eq!(list.get_mut(-1), Some(&mut 5));
Run

The following is equivalent in the retrieving first element

assert_eq!(list.get_mut(0), Some(&mut 1));
assert_eq!(list.get_mut(5), Some(&mut 1));
assert_eq!(list.get_mut(-5), Some(&mut 1));
Run

The following can be used to update an element

*list.get_mut(0).unwrap() = 6;
 
assert_eq!(list.get(0), Some(&6));
Run
Return
  • None if the list is empty
  • Some(T) if the list has at least one element
Note

If certain constraints on the index is met. Then the following element retrievals are recommended over .get(index).

If, i ∈ [0, list.len()) then, list.get(i) = list[i as usize] If, i ∈ [-1 * list.len(), list.len()) then, list.get(i) = list[i as isize]

This is because the Index<usize> and Index<isize> are defined with let checks - with the assumption that certain guarantees on the index are provided on run time.

Such that, im(Self::Index<usize>) ⊆ im(Self::Index<isize>) ⊆ im(Self::get_mut(&self, isize)).

returns a reference to an element in the list at provided index of the underlying array. get_unchecked is faster than all the other retrieval methods - however, provides less safety & features in exchange.

Returns

The method returns None if the underlying array has not value at the given index. Otherwise, the method returns a reference to the items at the array index.

Removes the last element from the list and returns removed element. This occurs in O(1)

let mut list : List<SIZE, i64, false> = [1,2,3,4,5].into();
 
assert_eq!(list.remove_back(), Some(5));
 
assert_eq!(list.len(), 4);
assert_eq!(list, vec![1,2,3,4].try_into().unwrap());
Run
Return
  • Some(last element in list) if list.len() > 0
  • None if list.len() = 0

Removes the first element from the list and returns removed element. This occurs in O(1)

let mut list : List<SIZE, i64, false> = [1,2,3,4,5].into();
 
assert_eq!(list.remove_front(), Some(1));
 
assert_eq!(list.len(), 4);
assert_eq!(list, vec![2,3,4,5].try_into().unwrap());
Run
Return
  • Some(last element in list) if list.len() > 0
  • None if list.len() = 0

Creates an iterator object that iterates over the elements in the list

Trait Implementations§

Formats the value using the given formatter. Read more
Returns the “default value” for a type. Read more
The resulting type after dereferencing.
Dereferences the value.
Mutably dereferences the value.
Formats the value using the given formatter. Read more
Converts to this type from the input type.
Converts to this type from the input type.
Converts to this type from the input type.
Converts to this type from the input type.
Creates a value from an iterator. Read more
This method tests for self and other values to be equal, and is used by ==.
This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
The type returned in the event of a conversion error.
Performs the conversion.
The type returned in the event of a conversion error.
Performs the conversion.
The type returned in the event of a conversion error.
Performs the conversion.

Auto Trait Implementations§

Blanket Implementations§

Gets the TypeId of self. Read more
Immutably borrows from an owned value. Read more
Mutably borrows from an owned value. Read more

Returns the argument unchanged.

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Converts the given value to a String. Read more
The type returned in the event of a conversion error.
Performs the conversion.
The type returned in the event of a conversion error.
Performs the conversion.