Struct xfast::Xfast

pub struct Xfast<T = String> { /* fields omitted */ }

A bitwise trie to store integers.

The values in a X-fast trie are stored at the leaves. An internal node is added to the trie only if it has leaves in its subtree.

Each level of the trie is modelled as a hash map storing the trie nodes at that level.

The range of integers need to be specified while initializing a trie.

Examples

    use xfast::Xfast;

    let mut test_trie: Xfast<&str> = Xfast::new(31);
    test_trie.insert_key(11, "eleven");
    test_trie.insert_key(1, "one");
    test_trie.insert_key(5, "five");
    assert_eq!(test_trie.len(), 3);
        
    let predecessor_3 = test_trie.find_predecessor(3);
    if predecessor_3.is_some() {
        let predecessor_value = predecessor_3.unwrap().value.unwrap();
        assert_eq!(predecessor_value, "one");
    }

Methods

impl<T> Xfast<T>

pub fn new(range: usize) -> Self

Creates a new Xfast Trie to store a given range of integers

Examples

    use xfast::Xfast;
     
    let mut test_trie: Xfast<&str> = Xfast::new(31);

pub fn len(&self) -> usize

Returns the count of values stored in the trie

Examples

    use xfast::Xfast;

    let mut test_trie: Xfast<&str> = Xfast::new(31);
    test_trie.insert_key(11, "eleven");
    test_trie.insert_key(1, "one");
    assert_eq!(test_trie.len(), 2);

pub fn find_successor(&self, key: usize) -> Option<&TrieNode<T>>

Returns the smallest node more than or eqaul to the node associated with key. In case of no such node it returns None. #Examples

Examples

    use xfast::Xfast;

    let mut test_trie: Xfast<&str> = Xfast::new(31);
    test_trie.insert_key(11, "eleven");
    test_trie.insert_key(1, "one");
    test_trie.insert_key(5, "five");
    assert_eq!(test_trie.len(), 3);
     
    if let Some(successor_3) = test_trie.find_successor(3) {
        let successor_value = successor_3.value.unwrap();
        assert_eq!(successor_value, "five");
    }
    let successor_14 = test_trie.find_successor(14);
        assert!(successor_14.is_none());

pub fn find_predecessor(&self, key: usize) -> Option<&TrieNode<T>>

Returns the largest node less that or eqaul to the node with key. In case of no such node it returns None. #Examples

Examples

    use xfast::Xfast;

    let mut test_trie: Xfast<&str> = Xfast::new(31);
    test_trie.insert_key(11, "eleven");
    test_trie.insert_key(1, "one");
    test_trie.insert_key(5, "five");
    assert_eq!(test_trie.len(), 3);
        
    if let Some(predecessor_3) = test_trie.find_predecessor(3) {
        let predecessor_value = predecessor_3.value.unwrap();
        assert_eq!(predecessor_value, "one");
    }

    let predecessor_0 = test_trie.find_predecessor(0);
        assert!(predecessor_0.is_none());

pub fn insert_key(&mut self, key: usize, value: T)

Insert key and value into the trie

Examples

    use xfast::Xfast;

    let mut test_trie: Xfast<&str> = Xfast::new(31);
    test_trie.insert_key(11, "eleven");

pub fn delete_key(&mut self, key: usize) -> Option<NonNull<TrieNode<T>>>

Delete a key from the trie. If the node doesn't exist it returns None else retuns the deleted TrieNode wrapped in a NonNull struct.

Examples

   use xfast::Xfast;

   let mut test_trie: Xfast<&str> = Xfast::new(31);
   test_trie.insert_key(11, "eleven");
   test_trie.insert_key(1, "one");
   test_trie.insert_key(5, "five");
   assert_eq!(test_trie.len(), 3);
       
   test_trie.delete_key(5);
   assert_eq!(test_trie.len(), 2);
   assert!(test_trie.delete_key(2).is_none());
   assert_eq!(test_trie.len(), 2);

pub fn find_key(&self, key: usize) -> Option<&TrieNode<T>>

Find a key in the trie

Examples

   use xfast::Xfast;

   let mut test_trie: Xfast<&str> = Xfast::new(31);
   test_trie.insert_key(11, "eleven");
   test_trie.insert_key(1, "one");
   if let Some(node_1) = test_trie.find_key(1) {
       // all the leaf nodes values have non trivial values and assert is_some. 
       // So unwrapping will not panic
       assert_eq!(node_1.value.unwrap(), "one");
   }

Important traits for XfastIter<'a, T>

impl<'a, T> Iterator for XfastIter<'a, T> type Item = (&'a usize, &'a TrieNode<T>);

pub fn iter(&self) -> XfastIter<T>

Returns an iterator around all the key-TrieNode pairs stored in the trie.

Examples

    use xfast::Xfast;

    let mut test_trie: Xfast<&str> = Xfast::new(31);
    test_trie.insert_key(11, "eleven");
    test_trie.insert_key(1, "one");
    test_trie.insert_key(19, "nineteen");
    for (key, node) in test_trie.iter() {
        println!("key: {} value: {:?}", key, node);
    }

Important traits for XfastIterMut<'a, T>

impl<'a, T> Iterator for XfastIterMut<'a, T> type Item = (&'a usize, &'a mut TrieNode<T>);

pub fn iter_mut(&mut self) -> XfastIterMut<T>

Returns a mutable iterator around all the key-TrieNode pairs stored in the trie.

Examples

    use xfast::Xfast;

    let mut test_trie: Xfast<&str> = Xfast::new(31);
    test_trie.insert_key(11, "eleven");
    test_trie.insert_key(1, "one");
    test_trie.insert_key(19, "nineteen");
    for (key, node) in test_trie.iter_mut() {
        if key % 2 == 1 {
            node.value = Some("updated_odd");    
        }
    }

    if let Some(node_1) = test_trie.find_key(1) {
        assert_eq!(node_1.value.unwrap(), "updated_odd");
    }

Trait Implementations

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

type Item = (&'a usize, &'a TrieNode<T>)

The type of the elements being iterated over.

type IntoIter = XfastIter<'a, T>

Which kind of iterator are we turning this into?

Important traits for XfastIter<'a, T>

impl<'a, T> Iterator for XfastIter<'a, T> type Item = (&'a usize, &'a TrieNode<T>);

fn into_iter(self) -> XfastIter<'a, T>

Creates an iterator from a value.

impl<T: Debug> Debug for Xfast<T>

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

Formats the value using the given formatter.