Struct patricia_tree::node::Node

pub struct Node<V> { /* fields omitted */ }

A node which represents a subtree of a patricia tree.

Note that this is a low level building block. Usually it is recommended to use more high level data structures (e.g., PatriciaTree).

Methods

impl<V> Node<V>

pub fn root() -> Self

Makes a new node which represents an empty tree.

Examples

use patricia_tree::node::Node;

let node = Node::<()>::root();
assert!(node.label().is_empty());
assert!(node.value().is_none());
assert!(node.child().is_none());
assert!(node.sibling().is_none());

pub fn new(
    label: &[u8],
    value: Option<V>,
    child: Option<Self>,
    sibling: Option<Self>
) -> Self

Makes a new node.

Examples

use patricia_tree::node::Node;

let node0 = Node::new("foo".as_ref(), Some(3), None, None);
assert_eq!(node0.label(), b"foo");
assert_eq!(node0.value(), Some(&3));
assert_eq!(node0.child().map(|n| n.label()), None);
assert_eq!(node0.sibling().map(|n| n.label()), None);

let node1 = Node::new("bar".as_ref(), None, None, Some(node0));
assert_eq!(node1.label(), b"bar");
assert_eq!(node1.value(), None);
assert_eq!(node1.child().map(|n| n.label()), None);
assert_eq!(node1.sibling().map(|n| n.label()), Some(&b"foo"[..]));

// If the length of a label name is longer than 255, it will be splitted to two nodes.
let node2 = Node::new([b'a'; 256].as_ref(), Some(4), Some(node1), None);
assert_eq!(node2.label(), [b'a'; 255].as_ref());
assert_eq!(node2.value(), None);
assert_eq!(node2.child().map(|n| n.label()), Some(&b"a"[..]));
assert_eq!(node2.sibling().map(|n| n.label()), None);

assert_eq!(node2.child().unwrap().value(), Some(&4));
assert_eq!(node2.child().unwrap().child().unwrap().label(), b"bar");

pub fn label(&self) -> &[u8]

Returns the label of this node.

pub fn value(&self) -> Option<&V>

Returns the reference to the value of this node.

pub fn value_mut(&mut self) -> Option<&mut V>

Returns the mutable reference to the value of this node.

pub fn child(&self) -> Option<&Self>

Returns the reference to the child of this node.

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

Returns the mutable reference to the child of this node.

pub fn sibling(&self) -> Option<&Self>

Returns the reference to the sibling of this node.

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

Returns the mutable reference to the sibling of this node.

pub fn take_value(&mut self) -> Option<V>

Takes the value out of this node.

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

Takes the child out of this node.

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

Takes the sibling out of this node.

pub fn set_value(&mut self, value: V)

Sets the value of this node.

pub fn set_child(&mut self, child: Self)

Sets the child of this node.

pub fn set_sibling(&mut self, sibling: Self)

Sets the sibling of this node.

Important traits for Iter<'a, V>

impl<'a, V: 'a> Iterator for Iter<'a, V> type Item = (usize, &'a Node<V>);

pub fn iter(&self) -> Iter<V>

Gets an iterator which traverses the nodes in this tree, in depth first order.

Examples

use patricia_tree::PatriciaSet;
use patricia_tree::node::Node;

let mut set = PatriciaSet::new();
set.insert("foo");
set.insert("bar");
set.insert("baz");

let node = Node::from(set);
let nodes = node.iter().map(|(level, node)| (level, node.label())).collect::<Vec<_>>();
assert_eq!(nodes,
           [
               (0, "".as_ref()),
               (1, "ba".as_ref()),
               (2, "r".as_ref()),
               (2, "z".as_ref()),
               (1, "foo".as_ref())
           ]);

Trait Implementations

impl<V> From<Node<V>> for PatriciaMap<V>

fn from(f: Node<V>) -> Self

Performs the conversion.

impl<V> From<PatriciaMap<V>> for Node<V>

fn from(f: PatriciaMap<V>) -> Self

Performs the conversion.

impl<V> AsRef<Node<V>> for PatriciaMap<V>

fn as_ref(&self) -> &Node<V>

Performs the conversion.

impl<V: Debug> Debug for Node<V>

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

Formats the value using the given formatter.

impl<V> Send for Node<V>

impl<V> Drop for Node<V>

fn drop(&mut self)

Executes the destructor for this type.

impl<V: Clone> Clone for Node<V>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<V> IntoIterator for Node<V>

type Item = (usize, Node<V>)

The type of the elements being iterated over.

type IntoIter = IntoIter<V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl From<Node<()>> for PatriciaSet

fn from(f: Node<()>) -> Self

Performs the conversion.

impl From<PatriciaSet> for Node<()>

fn from(f: PatriciaSet) -> Self

Performs the conversion.

impl AsRef<Node<()>> for PatriciaSet

fn as_ref(&self) -> &Node<()>

Performs the conversion.