Struct TrailTree 

pub struct TrailTree<K, T>
where
    K: Clone + Ord,
{ /* private fields */ }

A hierarchical search tree structure for efficiently searching paths. Operates over locally-unique, searchable keys K with associated data T.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
let leaf = con.insert(&[10, 12, 2]);
 
assert_eq!(&con.path(leaf), &[10, 12, 2]);

Implementations

impl<K, T> TrailTree<K, T>

where K: Clone + Ord,

pub fn search(&self, path: &[K]) -> Option<usize>

Returns the id of the element following a path from the root.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
let leaf = con.insert(&[1, 2, 3, 4]);
 
assert_eq!(con.search(&[1, 2, 3, 4]), Some(leaf));
assert_eq!(con.search(&[2, 4, 6]), None);

See also TrailTree::search_from.

pub fn search_from(&self, id: usize, path: &[K]) -> Option<usize>

Returns the id of the element following a path from the specified element.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
let leaf = con.insert(&[1, 2, 3, 4]);
 
let mid = con.search(&[1, 2]);
assert!(mid.is_some());
 
assert_eq!(con.search_from(mid.unwrap(), &[3, 4]), Some(leaf));

See also TrailTree::search.

pub fn key(&self, id: usize) -> Option<K>

Returns the key of the specified element.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
let leaf = con.insert(&[1, 2]);
 
assert_eq!(con.key(leaf), Some(2));

pub fn keys(&self) -> Vec<K>

Returns an ordered list of keys available from the root.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
con.insert(&[10]);
con.insert(&[2]);
con.insert(&[12]);
 
assert_eq!(&con.keys(), &[2, 10, 12]);

pub fn keys_from(&self, id: usize) -> Vec<K>

Returns an ordered list of keys available from the specified element.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
con.insert(&[1, 10]);
con.insert(&[1, 2]);
con.insert(&[1, 12]);
 
let mid = con.search(&[1]);
assert!(mid.is_some());
 
assert_eq!(&con.keys_from(mid.unwrap()), &[2, 10, 12]);

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

Returns a reference to the data associated with the specified element.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,u32>::new();
 
let leaf = con.insert(&[100, 50]);
 
con.set(leaf, 9001);
 
assert_eq!(con.get(leaf), Some(9001).as_ref());

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

Returns a mutable reference to the data associated with the specified element.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,u32>::new();
 
let leaf = con.insert(&[100, 50]);
 
con.set(leaf, 9001);
if let Some(data) = con.get_mut(leaf) {
    *data = 1009;
}
 
assert_eq!(con.get(leaf), Some(1009).as_ref());

pub fn path(&self, id: usize) -> Vec<K>

Returns the key path to the specified element.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
let leaf = con.insert(&[10, 12, 2]);
 
assert_eq!(&con.path(leaf), &[10, 12, 2]);

impl<K, T> TrailTree<K, T>

where K: Clone + Ord,

pub fn capacity(&self) -> usize

Returns the allocated memory capacity.

impl<K, T> TrailTree<K, T>

where K: Clone + Ord,

pub fn prev(&self, id: usize) -> Option<usize>

Returns the previous sequential node in the layer.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
let a = con.insert(&[5, 10]);
let b = con.insert(&[5, 20]);
 
assert_eq!(con.prev(b), Some(a));
assert_eq!(con.prev(a), None);

See also TrailTree::next.

pub fn next(&self, id: usize) -> Option<usize>

Returns the next sequential node in the layer.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
let a = con.insert(&[5, 10]);
let b = con.insert(&[5, 20]);
 
assert_eq!(con.next(a), Some(b));
assert_eq!(con.next(b), None);

See also TrailTree::prev.

pub fn parent(&self, id: usize) -> Option<usize>

Returns the parent of the specified element or None if a root.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
let leaf = con.insert(&[1, 2]);
 
let mid = con.search(&[1]);
assert!(mid.is_some());
 
assert_eq!(mid, con.parent(leaf));
assert_eq!(None, con.parent(mid.unwrap()));

See also TrailTree::first, TrailTree::last.

pub fn first(&self, id: Option<usize>) -> Option<usize>

Returns the first element in the specified element’s subtree. If no element is specified, the first root element is returned.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
assert_eq!(con.first(None), None);
 
let a = con.insert(&[1]);
let b = con.insert(&[1, 4]);
con.insert(&[1, 8]);
con.insert(&[2, 3]);
 
assert_eq!(con.first(None), Some(a));
assert_eq!(con.first(Some(a)), Some(b));

See also TrailTree::last, TrailTree::parent.

pub fn last(&self, id: Option<usize>) -> Option<usize>

Returns the last element in the specified element’s subtree. If no element is specified, the last root element is returned.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
assert_eq!(con.last(None), None);
 
let a = con.insert(&[1]);
con.insert(&[1, 4]);
let b = con.insert(&[1, 8]);
let c = con.insert(&[2]);
 
assert_eq!(con.last(None), Some(c));
assert_eq!(con.last(Some(a)), Some(b));

See also TrailTree::first, TrailTree::parent.

impl<K, T> TrailTree<K, T>

where K: Clone + Ord,

pub fn insert(&mut self, path: &[K]) -> usize

Inserts an index path into the tree, returning the ID of the last node in the path.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
let a = con.insert(&[5, 10]);
 
assert_eq!(con.search(&[5, 10]), Some(a));

See also TrailTree::extend.

pub fn extend(&mut self, id: usize, path: &[K]) -> usize

Extends an existing path in the tree with a new path, returning the ID of the last node in the extended path.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
let a = con.insert(&[5]);
let b = con.extend(a, &[10]);
 
assert_eq!(con.search(&[5, 10]), Some(b));
assert_eq!(con.parent(b), Some(a));

See also TrailTree::insert.

pub fn relocate(&mut self, id: usize, dst: usize) -> bool

Moves an element and its subtree to the prefix of a destination element. The operation fails if the key already exists in the destination.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
let a = con.insert(&[5]);
let b = con.extend(a, &[10]);
let c = con.insert(&[4]);
 
assert!(con.relocate(b, c));
assert_eq!(con.search_from(c, &[10]), Some(b));
assert_eq!(con.parent(b), Some(c));

See also TrailTree::relocate_with.

pub fn relocate_with(&mut self, id: usize, dst: usize, key: K) -> bool

Moves an element and its subtree to the prefix of a destination element with a new key. The operation fails if the key already exists in the destination.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
let a = con.insert(&[5]);
let b = con.extend(a, &[10]);
let c = con.insert(&[4]);
 
assert!(con.relocate_with(b, c, 9));
assert_eq!(con.search_from(c, &[9]), Some(b));
assert_eq!(con.parent(b), Some(c));

See also TrailTree::relocate.

pub fn remove(&mut self, id: usize)

Removes the subtree starting at the specified element.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
let a = con.insert(&[10]);
con.extend(a, &[20, 30]);
let b = con.insert(&[5, 2]);
con.insert(&[20]);
con.insert(&[15]);
 
con.remove(a);
 
assert_eq!(con.search(&[10]), None);
assert_eq!(con.search(&[5, 2]), Some(b));

pub fn clear(&mut self)

Removes all items from the tree, but does not release memory.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
 
con.insert(&[5, 10, 15]);
con.clear();
 
assert_eq!(con.first(None), None);

pub fn release(&mut self)

Releases all memory used by the tree.

pub fn set(&mut self, id: usize, data: T) -> Option<T>

Replaces data associated with the specified element and returns the old value.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,u32>::new();
 
let a = con.insert(&[5, 10]);
 
assert_eq!(con.set(a, 42), None);
assert_eq!(con.set(a, 43), Some(42));

pub fn unset(&mut self, id: usize) -> Option<T>

Removes data associated with the specified element and returns the old value.

Examples

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,u32>::new();
 
let a = con.insert(&[5, 10]);
 
con.set(a, 24);
 
assert_eq!(con.unset(a), Some(24));
assert_eq!(con.unset(a), None);

impl<K, T> TrailTree<K, T>

where K: Clone + Ord,

pub const fn new() -> Self

Constructs a new, empty structure.

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::new();
assert_eq!(con.capacity(), 0);

pub fn with_capacity(capacity: usize) -> Self

Constructs a new structure with the requested capacity of preallocated cells.

use trailtree::TrailTree;
 
let mut con = TrailTree::<u32,()>::with_capacity(10);
 
assert!(con.capacity() >= 10);