Struct CircularList 

pub struct CircularList<T> { /* private fields */ }

A circular doubly linked list with owned nodes. It is similar to the standard library LinkedList (the API is almost the same) exept it is circular (i.e. the last element is linked to the first).

Implementations

impl<T> CircularList<T>

pub fn new() -> Self

Create an empty CircularList.

Examples

use cdll::CircularList;

let list: CircularList<i32> = CircularList::new();

pub fn clear(&mut self)

Removes all elements from the CircularList.

This operation should compute in O(n) time.

Examples

use cdll::CircularList;

let mut cl = CircularList::new();

cl.push_front(2);
cl.push_front(1);
assert_eq!(cl.len(), 2);
assert_eq!(cl.front(), Some(&1));

cl.clear();
assert_eq!(cl.len(), 0);
assert_eq!(cl.front(), None);

pub fn len(&self) -> usize

Returns the length of the CircularList.

Examples

use cdll::CircularList;

let mut cl = CircularList::new();

cl.push_front(2);
assert_eq!(cl.len(), 1);

cl.push_front(1);
assert_eq!(cl.len(), 2);

cl.push_back(3);
assert_eq!(cl.len(), 3);

pub fn is_empty(&self) -> bool

Returns true if the CircularList is empty.

This operation should compute in O(1) time.

Examples

use cdll::CircularList;

let mut cl = CircularList::new();
assert!(cl.is_empty());

cl.push_front("foo");
assert!(!cl.is_empty());

pub fn front(&self) -> Option<&T>

Provides a reference to the front element, or None if the list is empty.

This operation should compute in O(1) time.

Examples

use cdll::CircularList;

let mut cl = CircularList::new();
assert_eq!(cl.front(), None);

cl.push_front(1);
assert_eq!(cl.front(), Some(&1));

pub fn front_mut(&mut self) -> Option<&mut T>

Provides a mutable reference to the front element, or None if the list is empty.

This operation should compute in O(1) time.

Examples

use cdll::CircularList;

let mut cl = CircularList::new();
assert_eq!(cl.front(), None);

cl.push_front(1);
assert_eq!(cl.front(), Some(&1));

match cl.front_mut() {
    None => {},
    Some(x) => *x = 5,
}
assert_eq!(cl.front(), Some(&5));

pub fn back(&self) -> Option<&T>

Provides a reference to the back element, or None if the list is empty.

This operation should compute in O(1) time.

Examples

use cdll::CircularList;

let mut cl = CircularList::new();
assert_eq!(cl.back(), None);

cl.push_back(1);
assert_eq!(cl.back(), Some(&1));

pub fn back_mut(&mut self) -> Option<&mut T>

Provides a mutable reference to the back element, or None if the list is empty.

This operation should compute in O(1) time.

Examples

use cdll::CircularList;

let mut cl = CircularList::new();
assert_eq!(cl.back(), None);

cl.push_back(1);
assert_eq!(cl.back(), Some(&1));

match cl.back_mut() {
    None => {},
    Some(x) => *x = 5,
}
assert_eq!(cl.back(), Some(&5));

pub fn push_back(&mut self, val: T)

Adds an element to the back of the list.

This operation should compute in O(1) time.

Examples

use cdll::CircularList;

let mut c = CircularList::new();
c.push_back(1);
c.push_back(3);
assert_eq!(3, *c.back().unwrap());

pub fn push_front(&mut self, val: T)

Adds an element to the front of the list.

This operation should compute in O(1) time.

Examples

use cdll::CircularList;

let mut cl = CircularList::new();

cl.push_front(2);
assert_eq!(cl.front().unwrap(), &2);

cl.push_front(1);
assert_eq!(cl.front().unwrap(), &1);

pub fn pop_front(&mut self) -> Option<T>

Removes the first element and returns it, or None if the list is empty.

This operation should compute in O(1) time.

Examples

use cdll::CircularList;

let mut c = CircularList::new();
assert_eq!(c.pop_front(), None);

c.push_front(1);
c.push_front(3);
assert_eq!(c.pop_front(), Some(3));
assert_eq!(c.pop_front(), Some(1));
assert_eq!(c.pop_front(), None);

pub fn pop_back(&mut self) -> Option<T>

Adds an element to the back of the list.

This operation should compute in O(1) time.

Examples

use cdll::CircularList;

let mut c = CircularList::new();
c.push_back(1);
c.push_back(3);
assert_eq!(3, *c.back().unwrap());

pub fn iter(&self) -> Iter<'_, T>

Provides a forward iterator.

Examples

use cdll::CircularList;

let mut list: CircularList<u32> = CircularList::new();

list.push_back(0);
list.push_back(1);
list.push_back(2);

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), None);

pub fn iter_mut(&mut self) -> IterMut<'_, T>

Provides a forward iterator with mutable references.

Examples

use cdll::CircularList;

let mut list: CircularList<u32> = CircularList::new();

list.push_back(0);
list.push_back(1);
list.push_back(2);

for element in list.iter_mut() {
    *element += 10;
}

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&10));
assert_eq!(iter.next(), Some(&11));
assert_eq!(iter.next(), Some(&12));
assert_eq!(iter.next(), None);

pub fn rev_iter(&self) -> Rev<'_, T>

Provides a backward iterator.

Examples

use cdll::CircularList;

let mut list: CircularList<u32> = CircularList::new();

list.push_back(0);
list.push_back(1);
list.push_back(2);

let mut iter = list.rev_iter();
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), None);

pub fn cursor(&self) -> Option<Cursor<'_, T>>

Provides a Cursor at the front element.

If the list is empty, returns None.

pub fn cursor_mut(&mut self) -> Option<CursorMut<'_, T>>

Provides a CursorMut at the front element.

If the list is empty, returns None.

pub fn split_half(&mut self) -> Option<Self>

Extracts one half of the list and returns it as a new list.

If the list is empty, this returns None.

The extracted list is the greater half if the length is odd.

This operation is O(n).

Examples

use cdll::list;

let mut list = list![1, 2, 3];
let half = list.split_half();
assert_eq!(half, Some(list![2, 3]));

pub fn rotate(&mut self, mid: isize)

If mid is positive, rotates the list in-place such that the first mid elements of the list move to the end while the last self.len() - mid elements move to the front.

If mid is negative, rotates the list in-place such that the first self.len() + mid elements of the list move to the end while the last -mid elements move to the front.

Only the Euclid remainder of mid modulo self.len() is used.

Examples

use cdll::list;
let mut a = list!['a', 'b', 'c', 'd', 'e', 'f'];
a.rotate(2);
assert_eq!(a, list!['c', 'd', 'e', 'f', 'a', 'b']);

use cdll::list;
let mut a = list!['a', 'b', 'c', 'd', 'e', 'f'];
a.rotate(-2);
assert_eq!(a, list!['e', 'f', 'a', 'b', 'c', 'd']);

pub fn append(&mut self, other: &mut Self)

Moves all elements from other to the end of the list.

This reuses all the nodes from other and moves them into self. After this operation, other becomes empty.

This operation should compute in O(1) time and O(1) memory.

Examples

use cdll::CircularList;

let mut list1 = CircularList::new();
list1.push_back('a');

let mut list2 = CircularList::new();
list2.push_back('b');
list2.push_back('c');

list1.append(&mut list2);

let mut iter = list1.iter();
assert_eq!(iter.next(), Some(&'a'));
assert_eq!(iter.next(), Some(&'b'));
assert_eq!(iter.next(), Some(&'c'));
assert!(iter.next().is_none());

assert!(list2.is_empty());

impl<T: PartialEq> CircularList<T>

pub fn contains(&self, elem: &T) -> bool

Returns true if the list contains an element with the given value.

This operation is O(n).

Examples

use cdll::list;

let l = list![10, 40, 30];
assert!(l.contains(&30));
assert!(!l.contains(&50));

pub fn dedup(&mut self)

Removes consecutive repeated elements in the list according to the PartialEq trait implementation.

If the list is sorted, this removes all duplicates.

Examples

use cdll::list;

let mut list = list![1, 2, 2, 3, 2];

list.dedup();

assert_eq!(list, list![1, 2, 3, 2]);

impl<T: PartialOrd> CircularList<T>

pub fn merge(&mut self, other: &mut Self)

Moves all elements from other to the list keeping it ordered if it is the case.

This reuses all the nodes from other and moves them into self. After this operation, other becomes empty.

This operation should compute in O(n) time and O(1) memory.

Examples

use cdll::{CircularList, list};

let mut list1 = CircularList::new();
list1.push_back('a');
list1.push_back('c');

let mut list2 = CircularList::new();
list2.push_back('b');
list2.push_back('d');

list1.merge(&mut list2);

assert_eq!(list1, list!['a', 'b', 'c', 'd']);
assert!(list2.is_empty());

Trait Implementations

impl<T: Clone> Clone for CircularList<T>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for CircularList<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Default for CircularList<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T> Drop for CircularList<T>

fn drop(&mut self)

Executes the destructor for this type.

fn pin_drop(self: Pin<&mut Self>)

🔬This is a nightly-only experimental API. (pin_ergonomics)

Execute the destructor for this type, but different to Drop::drop, it requires self to be pinned.

impl<T: Eq> Eq for CircularList<T>

impl<T> Extend<T> for CircularList<T>

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T> FromIterator<T> for CircularList<T>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<T> IntoIterator for CircularList<T>

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

type Item = T

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PartialEq> PartialEq for CircularList<T>

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.