Struct cyclic_data_types::queue::Queue
source · 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.
const SIZE: usize
SIZE is a generic constant 1 that defines the maximum size of the queue
T: Sized
T is the type of element stored in the queue
const WRITE_OVER: bool>
Creating Queue
Queue can be created in a couple of ways.
- 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- 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- 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();
Runconst SIZE: usize = 5;
let queue: Queue<SIZE, i64, true> = vec![1i64,2i64,3i64,4i64,5i64,6i64].try_into()
.unwrap();
RunExample 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))
RunWRITE_OVER is a generic constant 1 that is used to determine if elements should be over written on overflow [note]: Generic Constraints
Implementations§
source§impl<const SIZE: usize, T, const WRITE_OVER: bool> Queue<SIZE, T, WRITE_OVER>
impl<const SIZE: usize, T, const WRITE_OVER: bool> Queue<SIZE, T, WRITE_OVER>
sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
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);
Runsourcepub fn enqueue(&mut self, elem: T) -> Result<&mut Self, Error>
pub fn enqueue(&mut self, elem: T) -> Result<&mut Self, Error>
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());
Runsourcepub fn peek(&mut self) -> Option<&T>
pub fn peek(&mut self) -> Option<&T>
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));
Runsourcepub fn dequeue(&mut self) -> Option<T>
pub fn dequeue(&mut self) -> Option<T>
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);
RunMethods from Deref<Target = List<QUEUE_SIZE, T, WRITE_OVER>>§
sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
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);
Runsourcepub fn push_back(&mut self, elem: T) -> Result<&mut Self, Error>
pub fn push_back(&mut self, elem: T) -> Result<&mut Self, Error>
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());
RunIf the list is full - the list has two options based on the WRITE_OVER
flag.
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());
RunWRITE_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());
RunReturns
- Self if the push was successful
- Error if List is full and the
WRITE_OVER
flag is set tofalse
sourcepub fn push_front(&mut self, elem: T) -> Result<&mut Self, Error>
pub fn push_front(&mut self, elem: T) -> Result<&mut Self, Error>
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());
RunIf the list is full - the list has two options based on the WRITE_OVER
flag.
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());
RunWRITE_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());
RunReturns
- Self if the push was successful
- Error if List is full and the
WRITE_OVER
flag is set tofalse
sourcepub fn get(&self, index: isize) -> Option<&T>
pub fn get(&self, index: isize) -> Option<&T>
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();
RunThe 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));
RunThe 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));
RunReturn
None
if the list is emptySome(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)
).
sourcepub unsafe fn get_unchecked(&self, index: usize) -> Option<&T>
pub unsafe fn get_unchecked(&self, index: usize) -> Option<&T>
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.
sourcepub fn get_mut(&mut self, index: isize) -> Option<&mut T>
pub fn get_mut(&mut self, index: isize) -> Option<&mut T>
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();
RunThe 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));
RunThe 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));
RunThe following can be used to update an element
*list.get_mut(0).unwrap() = 6;
assert_eq!(list.get(0), Some(&6));
RunReturn
None
if the list is emptySome(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)
).
sourcepub unsafe fn get_unchecked_mut(&mut self, index: usize) -> Option<&mut T>
pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> Option<&mut T>
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.
sourcepub fn remove_back(&mut self) -> Option<T>
pub fn remove_back(&mut self) -> Option<T>
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());
RunReturn
Some(last element in list)
iflist.len()
> 0None
iflist.len()
= 0
sourcepub fn remove_front(&mut self) -> Option<T>
pub fn remove_front(&mut self) -> Option<T>
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());
RunReturn
Some(last element in list)
iflist.len()
> 0None
iflist.len()
= 0