Struct bittree::BitTree

pub struct BitTree<K: GetBytes, V: GetBytes> { /* fields omitted */ }

This is the main data structure that the crate contains. It consists of a tree of bits that is specifically meant for an O(1) find function. It has slow indexing, pushes, and removals, however, and so is mainly useful for seldom changed datasets that are searched consistently.

Example usage:

use bittree::BitTree;
let mut btree = BitTree::new();
btree.add(&0usize, Some(0usize));
assert_eq!(btree.find(&0usize), Some(0usize));
 
btree.remove(&0usize);
assert_eq!(btree.find(&0usize), None);

Implementations

impl<K: GetBytes, V: GetBytes> BitTree<K, V>

pub fn new() -> BitTree<K, V>

This creates a new BitTree.

pub fn add(&mut self, key: &K, value: Option<V>)

To add to the bittree, this function gets all of the bits of the input data and creates new entries for each non-existent part of the path of bits until it completes the bitpath. It adds a new value at the last entry.

pub fn remove(&mut self, key: &K)

To remove from the tree of bits, this function gets the second to last entry for the input data and removes the child entry used for the data.

pub fn find(&mut self, value: &V) -> Option<K>

To search through the data and find a value, this function checks if all of the required bit entries specified in the bitpath exist in the values-to-keys bitpath, which solely depends on the size of the data being searched for (a constant, hence constant time) rather than the size of the dataset.

Trait Implementations

impl<K: Clone + GetBytes, V: Clone + GetBytes> Clone for BitTree<K, V>

fn clone(&self) -> BitTree<K, V>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K: Debug + GetBytes, V: Debug + GetBytes> Debug for BitTree<K, V>

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

Formats the value using the given formatter.

impl<K: GetBytes, V: GetBytes> Default for BitTree<K, V>

fn default() -> Self

Returns the "default value" for a type.

impl<K: GetBytes, V: GetBytes> GetBytes for BitTree<K, V>

fn get_bytes(&self) -> &[u8]

impl<K: GetBytes, V: GetBytes> Index<&'_ K> for BitTree<K, V>

type Output = Option<V>

The returned type after indexing.

fn index(&self, index: &K) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<K: GetBytes, V: GetBytes> IndexMut<&'_ K> for BitTree<K, V>

fn index_mut(&mut self, index: &K) -> &mut Option<V>

Performs the mutable indexing (container[index]) operation.