Struct CountTree

pub struct CountTree<T>(/* private fields */);

Counting tree.

A balanced binary tree which keeps track of total number of child nodes in each node, so that elements can be inserted and deleted using its in-order index. The algorithm used internally is a variation of AVL Tree. Time complexities mentioned below are that of worst case scenario (and are of the same order as that of an AVL tree).

Examples

let mut ct: CountTree<i32> = CountTree::new();
ct.push_front(20);
ct.push_front(10);
assert_eq!(ct.pop_back().unwrap(), 20);

You can also use collect to create one from an iterator. This has a time complexity of O(n), which is much more efficient than inserting iteratively.

let mut ct: CountTree<i32> = (0..100).collect();
assert_eq!(ct.remove(32), 32);

Implementations

impl<T> CountTree<T>

pub fn new() -> CountTree<T>

Returns an empty CountTree

pub fn is_empty(&self) -> bool

Returns true if the tree contains no elements.

pub fn len(&self) -> usize

Returns the number elements in the tree. Time complexity: O(1)

pub fn clear(&mut self)

Clears the tree, dropping all elements iteratively.

pub fn get(&self, index: usize) -> Option<&T>

Returns the element at the given index, or None if index is out of bounds. Time complexity: O(log(n))

pub fn get_mut(&mut self, index: usize) -> Option<&mut T>

Returns a mutable reference to the element at the given index, or None if out of bounds. Time complexity: O(log(n))

pub fn insert(&mut self, index: usize, value: T)

Inserts an element at the given index. Time complexity: O(log(n))

Panics

Panics if index is greater than self.len()

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

Prepends an element at the beginning.

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

Appends an element at the end.

pub fn remove(&mut self, index: usize) -> T

Removes the element at the given index. Time complexity: O(log(n))

Panics

Panics if index is out of bounds.

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

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

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

Removes and returns the last element, or None if empty.

Trait Implementations

impl<T> BinaryTree for CountTree<T>

type Node = CountNode<T>

fn root(&self) -> Option<&Self::Node>

impl<T> Debug for CountTree<T>

where T: Debug,

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

Formats the value using the given formatter.

impl<T> Drop for CountTree<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<T> FromIterator<T> for CountTree<T>

fn from_iter<I>(iterable: I) -> Self

where I: IntoIterator<Item = T>,

Time complexity: Θ(n + log²(n))

impl<'a, T> IntoIterator for &'a CountTree<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for CountTree<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.