Struct Node

pub struct Node<C> {
    pub cargo: C,
    pub children: Vec<Node<C>>,
}

The easiest way to construct a Node is by using its associated function Node::new, immediately passing its cargo. As a tree consists of only Nodes, this first Node is a tree having one Node.

Afterwards, other Nodes can be added to the tree, either by passing a cargo, or else by creating another Node (with or without subnodes) and adding it as a child to the first or any other node of the tree :

use tree_by_path::{Node, TraverseAction};

// Creating a first node.
let mut n = Node::new('a');

// n is a one-node tree now. Let's add a child node by passing a cargo.
let root_path = n.get_first_path();
n.add_cargo_under_path(&root_path, 'b').expect(
    "It should always be possible to add a node under the root node");

// Let's create another small tree having cargoes of the same type.
let mut n2 = Node::new('c');
n2.add_cargo_under_path(&root_path, 'd').expect(
    "It should always be possible to add a node under the root node");

// Now we add the second tree's root node as a child to the first tree's root node :
n.add_node_under_path(&root_path, n2).expect(
    "It should always be possible to add a node under the root node");

// Concatenating all of the tree's nodes' cargoes :
let concatenated = n.traverse(
    String::new(),
    |accum, current_node, _path| {
        accum.push(current_node.cargo);
        TraverseAction::Continue
    }
);

assert_eq!("abcd".to_string(), concatenated);
 

Fields

cargo: C

children: Vec<Node<C>>

Implementations

impl<C> Node<C>

pub fn new(cargo: C) -> Node<C>

Creates a new node and immediately also a new tree having a single (root) node.

The cargo has to be passed immediately. If you need a tree with optional cargoes in the nodes, create a node having an Option<Whatever> as cargo.

Any node, with its subnodes, can always be attached as a child to a node of a tree having nodes of the same cargo type. (See the add_node_* methods.)

pub fn get_first_path(&self) -> Vec<usize>

Returns Vec::<usize>::new(), as this is always the root node’s path.

pub fn get_last_path(&self) -> Vec<usize>

Returns the path or address of the last subnode of the node on which this method is called.

pub fn get_next_path(&self, path: &[usize]) -> Result<Vec<usize>, PathError>

Returns the path or address of the next child node after the child node having the path passed as an argument.

This next child node can be its first child, or its next sibling if it hasn’t any children, or its parent’s next sibling if it’s the last child of its parent node, or even its grandparent, etc.

If there is no next node (when the path passed as argument is the path of the tree’s last node), a PathError::RequestedPathNotAvailable is returned.

Note that Node.traverse internally uses this method.

Example :

use tree_by_path::Node;

let mut n = Node::new("Brussels".to_string());
let root_path = Vec::<usize>::new();

let ghent_path = n.add_cargo_under_path(&root_path, "Ghent".to_string()).expect(
    "Error adding node under root node");

let antwerp_path = n.add_cargo_under_path(&root_path, "Antwerp".to_string()).expect(
    "Error adding node under root node");

assert_eq!(Ok(antwerp_path.clone()), n.get_next_path(&ghent_path));

pub fn get_previous_path( &self, path: &Vec<usize>, ) -> Result<Vec<usize>, PathError>

Returns the path or address of the previous child node before the child node having the path passed as an argument.

If there is no previous node (when the path passed as argument is the path of the tree’s first node), a PathError::RequestedPathNotAvailable is returned.

Note that Node.traverse_back internally uses this method.

pub fn add_cargo_under_path( &mut self, path: &Vec<usize>, cargo: C, ) -> Result<Vec<usize>, (PathError, C)>

Looks for the tree’s child node having the given path,
adds a new child node under it having the given cargo,
and returns a Result being either
Ok(path_of_added_node)
or else
Err((PathError, cargo_not_having_been_moved_into_tree)).

Example :

use tree_by_path::{Node, PathError};

let mut n = Node::new(0u8);
let mut result: Result<Vec<usize>, (PathError, u8)>;

result = n.add_cargo_under_path(&vec![], 1);
assert!(result.is_ok());
assert_eq!(vec![0], result.unwrap());

result = n.add_cargo_under_path(&vec![], 2);
assert!(result.is_ok());
assert_eq!(vec![1], result.unwrap());
assert_eq!(&2, n.borrow_cargo(&vec![1]).unwrap());

result = n.add_cargo_under_path(&vec![0], 3);
assert!(result.is_ok());
assert_eq!(vec![0, 0], result.unwrap());

result = n.add_cargo_under_path(&vec![0], 4);
assert!(result.is_ok());
assert_eq!(vec![0, 1], result.unwrap());

let borrowed = n.borrow_cargo(&vec![0, 1]);
assert!(borrowed.is_ok());
assert_eq!(&4, borrowed.unwrap());

result = n.add_cargo_under_path(&vec![50], 99);
assert!(result.is_err());
assert_eq!((PathError::InputPathNotFound,99), result.unwrap_err());

result = n.add_cargo_under_path(&vec![0, 1, 1], 99);
assert!(result.is_err());
assert_eq!((PathError::InputPathNotFound,99), result.unwrap_err());

pub fn add_cargo_after_path( &mut self, path: &Vec<usize>, cargo: C, ) -> Result<Vec<usize>, (PathError, C)>

Looks for the tree’s child node having the given path,
adds a new child node after it,
and returns a Result being either
Ok(path_of_added_node)
or else
Err((PathError, cargo_not_having_been_moved_into_tree)).

Note that trying to add a node after the root node cannot but result in
Err((PathError::InputPathNotFitForOperation, cargo_not_having_been_moved_into_tree)),
as a tree’s root node can’t have siblings.

pub fn add_cargo_before_path( &mut self, path: &Vec<usize>, cargo: C, ) -> Result<Vec<usize>, (PathError, C)>

Looks for the tree’s child node having the given path,
adds a new child node before it,
and returns a Result being either
Ok(path_of_added_node)
or else
Err((PathError, cargo_not_having_been_moved_into_tree)).

Note that trying to add a node before the root node cannot but result in
Err((PathError::InputPathNotFitForOperation, cargo_not_having_been_moved_into_tree)),
as a tree’s root node can’t have siblings.

pub fn extract_node(&mut self, path: &Vec<usize>) -> Result<Node<C>, PathError>

Looks for the tree’s child node having the given path,
tries and removes it
and returns either
Ok(removed_node_with_all_its_children)
or
Err(PathError).

Trying and removing the root node amounts to trying and removing a node from itself, which cannot but result in an Err(PathError::InputPathNotFitForOperation):

use tree_by_path::{Node, PathError};

let mut n = Node::new(("Jane Kirby", "CEO"));
let root_path = n.get_first_path();

let cfo_path = n.add_cargo_under_path(
    &root_path,
    ("Rob Delsing", "CFO")
).unwrap();

let account_path = n.add_cargo_under_path(
    &cfo_path,
    ("Pierre Lévèque", "Head of Accounting")
).unwrap();

let cio_path = n.add_cargo_under_path(
    &root_path,
    ("Dilshat Ahmetova", "CFO")
).unwrap();

let mut result = n.extract_node(&root_path);
assert_eq!(Err(PathError::InputPathNotFitForOperation), result);

result = n.extract_node(&cfo_path);
match result {
    Err(_) => panic!("Failed to extract an existing child node."),
    Ok(cfo_tree) => {
        assert_eq!("Pierre Lévèque", cfo_tree.borrow_cargo(&vec![0]).unwrap().0)
    },
}

assert_eq!("Dilshat Ahmetova", n.borrow_cargo(&vec![0]).unwrap().0)

pub fn add_node_under_path( &mut self, path: &Vec<usize>, node: Node<C>, ) -> Result<Vec<usize>, (PathError, Node<C>)>

Looks for the tree’s child node having the given path,
adds the given node under it,
and returns a Result being either
Ok(path_of_added_node)
or else
Err((PathError, node_not_having_been_moved_into_tree)).

Example :

use tree_by_path::{Node, PathError};

let mut n = Node::new(0u8);
let mut result: Result<Vec<usize>, (PathError, Node<u8>)>;

result = n.add_node_under_path(&vec![], Node::new(1));
assert!(result.is_ok());
assert_eq!(vec![0], result.unwrap());

result = n.add_node_under_path(&vec![], Node::new(2));
assert!(result.is_ok());
assert_eq!(vec![1], result.unwrap());
assert_eq!(&2, n.borrow_cargo(&vec![1]).unwrap());

result = n.add_node_under_path(&vec![0], Node::new(3));
assert!(result.is_ok());
assert_eq!(vec![0, 0], result.unwrap());

result = n.add_node_under_path(&vec![0], Node::new(4));
assert!(result.is_ok());
assert_eq!(vec![0, 1], result.unwrap());

let borrowed = n.borrow_cargo(&vec![0, 1]);
assert!(borrowed.is_ok());
assert_eq!(&4, borrowed.unwrap());

result = n.add_node_under_path(&vec![50], Node::new(99));
assert!(result.is_err());
assert_eq!((PathError::InputPathNotFound, Node::new(99)), result.unwrap_err());

result = n.add_node_under_path(&vec![0, 1, 1], Node::new(99));
assert!(result.is_err());
assert_eq!((PathError::InputPathNotFound, Node::new(99)), result.unwrap_err());

pub fn add_node_after_path( &mut self, path: &Vec<usize>, node: Node<C>, ) -> Result<Vec<usize>, (PathError, Node<C>)>

Looks for the tree’s child node having the given path,
adds the given node after it,
and returns a Result being either
Ok(path_of_added_node)
or else
Err((PathError, node_not_having_been_moved_into_tree)).

Note that trying to add a node after the root node cannot but result in
Err((PathError::InputPathNotFitForOperation, node_not_having_been_moved_into_tree)),
as a tree’s root node can’t have siblings.

pub fn add_node_before_path( &mut self, path: &Vec<usize>, node: Node<C>, ) -> Result<Vec<usize>, (PathError, Node<C>)>

Looks for the tree’s child node having the given path,
adds the given node before it,
and returns a Result being either
Ok(path_of_added_node)
or else
Err((PathError, node_not_having_been_moved_into_tree)).

Note that trying to add a node before the root node cannot but result in
Err((PathError::InputPathNotFitForOperation, node_not_having_been_moved_into_tree)),
as a tree’s root node can’t have siblings.

pub fn swap_node( &mut self, path: &Vec<usize>, node: Node<C>, ) -> Result<Node<C>, (PathError, Node<C>)>

Looks for the node having the given path,
replaces it (with all its child nodes !) by the given node (with all its child nodes),
and returns either
Ok(node_that_was_replaced)
or else
Err((PathError, node_not_having_been_moved_into_tree).

Note that trying and replacing the root node will result in a
Err((PathError::InputPathNotFitForOperation, node)).

But even if replacing a tree’s child node is not possible, it is possible to replace its cargo.

pub fn borrow_cargo(&self, path: &Vec<usize>) -> Result<&C, PathError>

Returns a Result having either

• a non-mutable reference to the cargo of the child node having the given path
  or else
• a PathError.

Example:

use tree_by_path::Node;

let mut n = Node::new("Athens");
let root_path = Vec::<usize>::new();
let mut added_path: Vec<usize>;

added_path = n.add_cargo_under_path(&root_path, "Thessaloniki").unwrap();
added_path = n.add_cargo_under_path(&added_path, "Kilkis").unwrap();

added_path = n.add_cargo_under_path(&root_path, "Kavala").unwrap();
added_path = n.add_cargo_under_path(&added_path, "Moustheni").unwrap();

let borrow_result = n.borrow_cargo(&vec![1, 0]);

assert!(borrow_result.is_ok());
assert_eq!(&"Moustheni", borrow_result.unwrap());

pub fn borrow_mut_cargo( &mut self, path: &Vec<usize>, ) -> Result<&mut C, PathError>

Returns a Result having either

• a mutable reference to the cargo of the child node having the given path
  or else
• a PathError.

Note : an easier way to change a (child) node’s cargo is the set_cargo method.

Example:

use tree_by_path::Node;

let mut n = Node::new("Greece");
let root_path = Vec::<usize>::new();
let mut added_path: Vec<usize>;

added_path = n.add_cargo_under_path(&root_path, "Thessaloniki").unwrap();
added_path = n.add_cargo_under_path(&added_path, "Kilkis").unwrap();

added_path = n.add_cargo_under_path(&root_path, "Kavala").unwrap();
added_path = n.add_cargo_under_path(&added_path, "Moustheni").unwrap();

let mut borrow_result = n.borrow_mut_cargo(&vec![1, 0]);
assert!(borrow_result.is_ok());
let borrowed = borrow_result.unwrap();

*borrowed = "Kokkinochori";
 
borrow_result = n.borrow_mut_cargo(&vec![1, 0]);
assert!(borrow_result.is_ok());
assert_eq!(&"Kokkinochori", borrow_result.unwrap());

pub fn set_cargo( &mut self, path: &Vec<usize>, cargo: C, ) -> Result<(), (PathError, C)>

Returns a Result having either

• ()
  or else
• a tuple (PathError, cargo_not_having_been_moved_into_the_tree).

Note that the cargo previously held by the targeted node is lost after a call to set_cargo. In order to retrieve the previously held cargo, use the swap_cargo method which, however, is a more expensive operation.

Example:

use tree_by_path::Node;

let mut n = Node::new('a');
n.add_cargo_under_path(&vec![], 'b').unwrap();
n.add_cargo_under_path(&vec![], 'c').unwrap();

let result = n.set_cargo(&vec![1], 'z');

assert!(result.is_ok());
assert_eq!(&'z', n.borrow_cargo(&vec![1]).unwrap());

pub fn swap_cargo( tree_root: Node<C>, path: &Vec<usize>, cargo: C, ) -> CargoSwapResult<C>

Unlike method swap_node, swap_cargo

• is an associated function, to be called as Node::swap_cargo(...);
• takes a Node<C> as a parameter, instead of a mutable reference;
• allows one to swap the cargo on a root node, instead of only on subnodes.

The latter is also the reason why swap_cargo needs the target node to be moved into its first parameter: swapping the cargo on a root node involves replacing that node with another one.

This also means that, if you want to swap the cargo on a node, you’ll have to retrieve it from the function’s return value afterwards, or it will be dropped :

use tree_by_path::{Node, PathError, TraverseAction};

#[derive(Debug)]
struct NoCopy {
    value: u8,
}
 
let mut n = Node::new(NoCopy{value: 10});
let added_path = n.add_cargo_under_path(&vec![], NoCopy{value: 1}).unwrap();
n.add_cargo_under_path(&vec![], NoCopy{value: 7}).unwrap();

n.add_cargo_under_path(&added_path, NoCopy{value: 2}).unwrap();
n.add_cargo_under_path(&added_path, NoCopy{value: 3}).unwrap();

let mut total = n.traverse(
    0u8,
    |accum, nd, _path| {
        *accum += nd.cargo.value;
        TraverseAction::Continue
    }
);

assert_eq!(23u8, total);

// Moving our root node n into swap_cargo's first parameter.
let swap_result = Node::swap_cargo(n, &vec![], NoCopy{value: 30u8});

assert!(swap_result.is_ok());

let old_cargo: NoCopy;

// Getting our tree with root node n back.
(n, old_cargo) = swap_result.unwrap();

assert_eq!(10, old_cargo.value);

total = n.traverse(
    0u8,
    |accum, nd, _path| {
        *accum += nd.cargo.value;
        TraverseAction::Continue
    }
);

assert_eq!(43u8, total);

If ever the swap operation would fail, the node passed as first parameter is not lost and can be retrieved from the Err(...) result :

use tree_by_path::{Node, PathError};

let mut n = Node::new('g');
n.add_cargo_under_path(&vec![], 'o').unwrap();

// Moving root node n into swap_cargo's first parameter ...
let result = Node::swap_cargo(n, &vec![5], 'a');

assert!(result.is_err());
 
// ... and getting it back from the function's return value.
let (err, n, new_cargo) = result.unwrap_err();
assert_eq!(&'g', n.borrow_cargo(&vec![]).unwrap());

assert_eq!(PathError::InputPathNotFound, err);

// Besides, neither the new cargo not having been swapped is lost.
assert_eq!('a', new_cargo);

pub fn has_path(&self, path: &Vec<usize>) -> bool

Checks if a node has a subnode having the given path.

You’ll rarely want to call this method: all other methods accepting an input path return a Result::Err(...) which will return cargo and nodes not inserted or swapped if the given path is nonexistent or not fit for the operation.

In most cases, if you use this method to prevent a subsequent method call to fail, you’ll just be doubling the processing involved in retrieving the node the path points at.

pub fn iter(&self) -> NodeIterator<'_, C>

Returns a NodeIterator<'it, C> : std::iter::Iterator which allows iteration over immutable references to a tree’s cargoes.

Note that use of the methods traverse and traverse_back is usually faster and more flexible.

pub fn traverse<Accum, CallBack>( &self, init: Accum, call_back: CallBack, ) -> Accum

where CallBack: FnMut(&mut Accum, &Node<C>, &Vec<usize>) -> TraverseAction,

traverse receives two arguments :

• an initial value for an accumulator;
• a callback function or closure. traverse passes a node and all of its child nodes to this callback closure or function.

The callback closure receives three parameters :

• a mutable reference to the accumulated value;
• an immutable reference to the node passed to it;
• an immutable reference to the passed node’s address or path.

Unlike std::iter::Iterator.fold, the callback closure doesn’t return the accumulated value, but a TraverseAction variant.

(As the accumulated value is mutable, it can be manipulated by the callback closure.)

Example : totalizing the numerical cargo of all nodes until the total reaches a certain value:

use tree_by_path::{Node, TraverseAction};

let mut n = Node::new(0);
n.add_cargo_under_path(&vec![], 1).unwrap();
n.add_cargo_under_path(&vec![], 2).unwrap();
n.add_cargo_under_path(&vec![1], 3).unwrap();
n.add_cargo_under_path(&vec![1], 4).unwrap();
n.add_cargo_under_path(&vec![], 5).unwrap();

let outcome = n.traverse(
    0,
    |acc, nd, _path| {
        *acc += nd.cargo;

        if *acc <= 5 { TraverseAction::Continue } else { TraverseAction::Stop }
    }
);

assert_eq!(6, outcome);

pub fn traverse_mut<Accum, CallBack>( &mut self, init: Accum, call_back: CallBack, ) -> Accum

where CallBack: FnMut(&mut Accum, &mut Node<C>, &Vec<usize>) -> TraverseAction,

traverse_mut receives two arguments :

• an initial value for an accumulator;
• a callback function or closure. ‘traverse_mut’ passes a node and all of its child nodes to this callback closure or function.

The callback closure receives three parameters :

• a mutable reference to the accumulated value;
• a mutable reference to the node passed to it;
• a reference to the passed node’s address or path.

Unlike std::iter::Iterator.fold, the callback closure doesn’t return the accumulated value, but a TraverseAction variant.

(As the accumulated value is mutable, it can be manipulated by the callback closure.)

Example : increasing the value of every node with 1:

use tree_by_path::{Node, TraverseAction};

let mut n = Node::new(0);
n.add_cargo_under_path(&vec![], 1).unwrap();
n.add_cargo_under_path(&vec![], 2).unwrap();
n.add_cargo_under_path(&vec![1], 3).unwrap();
n.add_cargo_under_path(&vec![1], 4).unwrap();
n.add_cargo_under_path(&vec![], 5).unwrap();

let changed_nodes = n.traverse_mut(
    0,
    |changed, nd, _path| {
        nd.cargo += 1;
        *changed += 1;

        TraverseAction::Continue
    }
);

assert_eq!(6, changed_nodes);

let outcome = n.traverse_mut(
    0,
    |acc, nd, _path| {
        *acc += nd.cargo;

        TraverseAction::Continue
    }
);

assert_eq!(21, outcome);

pub fn traverse_back<Accum, CallBack>( &self, init: Accum, call_back: CallBack, ) -> Accum

where CallBack: FnMut(&mut Accum, &Node<C>, &Vec<usize>) -> TraverseAction,

traverse_back acts in a similar way as the traverse method, except

• the nodes are visited in exactly the inverse order that traverse would visit them - this means that a node’s children are visited before their parent node, and the root node is visited last.
• TraverseAction::SkipChildren causes a node’s parent to be visited next, and preceding siblings to be skipped.

pub fn traverse_mut_back<Accum, CallBack>( &mut self, init: Accum, call_back: CallBack, ) -> Accum

where CallBack: FnMut(&mut Accum, &mut Node<C>, &Vec<usize>) -> TraverseAction,

traverse_mut_back acts in a similar way as the traverse_mut method, except

• the nodes are visited in exactly the inverse order that traverse_mut would visit them - this means that a node’s children are visited before their parent node, and the root node is visited last.
• TraverseAction::SkipChildren causes a node’s parent to be visited next, and preceding siblings to be skipped.

pub fn borrow_node(&self, path: &Vec<usize>) -> Result<&Node<C>, PathError>

pub fn borrow_mut_node( &mut self, path: &Vec<usize>, ) -> Result<&mut Node<C>, PathError>

Trait Implementations

impl<C> Clone for Node<C>

where C: Clone,

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<C: Debug> Debug for Node<C>

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

Formats the value using the given formatter.

impl<C: PartialEq> PartialEq for Node<C>

fn eq(&self, other: &Node<C>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<C> StructuralPartialEq for Node<C>