Struct cyclic_data_types::queue::Queue

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

Queue is the struct used to define the state of a queue using cyclic List. As a result, the queue inherits the O(1) insertion and deletion for enqueuing & dequeuing.

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 queue

  1. T: Sized

T is the type of element stored in the queue

  1. const WRITE_OVER: bool>

Creating Queue

Queue can be created in a couple of ways.

  1. Empty Queue

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

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

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

let mut queue: Queue<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 queue variant. As a result, the new queue 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 queue variant or the cyclic list variant permits WRITE_OVER.

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

Example of a successful conversion

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

Example of a failed conversion

const SIZE: usize = 5;
let queue: Result<Queue<SIZE, i64, false>, Error> = Queue::try_from(vec![1i64,2i64,3i64,4i64,5i64,6i64]);
 
assert_eq!(queue, 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 queue.

let mut queue: Queue<SIZE, i64, false> = Queue::default();
 
assert_eq!(queue.len(), 0);
 
assert!(queue.enqueue(1).is_ok());
 
assert_eq!(queue.len(), 1);
Run

Pushes an element to the end of the queue.

 
let mut queue: Queue<SIZE, i64, false> = Queue::default();
 
assert!(queue.enqueue(1).is_ok());
 
assert!(queue.enqueue(2).is_ok());
Run

Returns a reference to the first element in the queue.

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

Returns the first element of the queue - after removing said element from the queue.

 
let mut queue: Queue<SIZE, i64, false> = vec![1,2,3].try_into().unwrap();
 
assert_eq!(queue.dequeue(), Some(1));
assert_eq!(queue.dequeue(), Some(2));
assert_eq!(queue.dequeue(), Some(3));
assert_eq!(queue.dequeue(), None);
Run

Methods from Deref<Target = List<QUEUE_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.