Crate tree_by_path

source ·
Expand description
pub struct Node<C> {
    pub cargo: C,
    pub children: Vec<Node<C>>,
}

tree_by_path trees consist of a Node<C> root node that may or may not have Node<C> children, who in turn may or may not have other Node<C> children etc.

Every node carries a useful cargo of generic type C (“cargo”). (Nullability of the cargo can be obtained by instantiating a tree having Node<Option<YourType>> nodes.)

Child nodes are directly owned by parent nodes as elements of their children vector : Vec<Node<C>>.

Child nodes hold no reference to their parent. This parent, however, can always be retrieved by removing the last element of the indexes array the node has been addressed with - see below.

This design has been chosen so as to avoid the use of RefCell or other inner mutability mechanisms, which defer borrow checking from compilation to runtime.

Address paths

Except for the root node, all nodes in the tree are an n-th element in their parent node’s children collection.

This means that every node can be addressed using a Vec<usize> series of indexes :

  • the root node’s address is an empty series of indexes : [];
  • any direct child node under the root node has one index in its address, starting with [0];
  • other nodes have a longer address, e.g.:
  []
   |
  [0]-----------------[1]-----------------[2]
   |                   |
  [0,0]---[0,1]       [1,0]---[1,1]
           |                   |
          [0,1,0]             [1,1,0]---[1,1,1]---[1,1,2]

These addresses are the paths meant in the crate’s name.

Use of these addresses, which are &Vec<usize> objects accepted and returned by nearly all methods of struct Node<C>, allow code using this crate to hold only one mutable reference to a root node, without needing any other references, thus avoiding the need of holding on to multiple mutable references of nodes of the same tree, which would be prohibited by Rust’s borrow checker.

So, instead of references to nodes, instances of Vec<usize> paths can be kept in variables.

And even if these path addresses can become obsolete after insertion or removal of nodes, specific nodes can be retrieved by lookups on the nodes’ cargo using the traverse* methods if needed - see the section Node identifiers.

Cloning

Node<C> is clonable if type C is clonable :

use tree_by_path::Node;
let n = Node::new(20u8);
let mut nc = n.clone();
let root_path = n.get_first_path();
let cloned_cargo = nc.borrow_mut_cargo(&root_path).unwrap();
*cloned_cargo = 21u8;
assert_eq!(&20u8, n.borrow_cargo(&root_path).unwrap());
assert_eq!(&21u8, nc.borrow_cargo(&root_path).unwrap());

Cloning a Node<C> instance having a non-clonable cargo, however, will cause a compilation error :

ⓘ
use tree_by_path::Node;

#[derive(Debug)]
struct NoClone {}

let mut n = Node::new(NoClone{});
n.add_cargo_under_path(&Vec::<usize>::new(), NoClone{}).unwrap();

// The below statement doesn't even compile :
let nc = n.clone();

Cyclic parent-child node ownership

No way has been found to force a node to have one of its parent nodes as a child node in its children vector, and that’s for the better.

The below code fails to compile:

ⓘ
use tree_by_path::Node;

let mut root = Node::new(0u32);
let mut last_path = root.add_cargo_under_path(&vec![], 1).unwrap();
last_path = root.add_cargo_under_path(&last_path, 2).unwrap();
let last_node = root.borrow_mut_node(&last_path).unwrap();

let result = last_node.add_node_under_path(&vec![], root);

// error[E0505]: cannot move out of `root` because it is borrowed
// 
// let mut root = Node::new(0u32);
//     -------- binding `root` declared here
// 
// let last_node = root.borrow_mut_node(&last_path).unwrap();
//                 ---- borrow of `root` occurs here
// let result = last_node.add_node_under_path(&vec![], root);
//                        -------------------          ^^^^ move out of `root` occurs here
//                        |
//                        borrow later used by call

Examples

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

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

// Adding a node with specified cargo after a node which doesn't exist yet :
result = n.add_cargo_after_path(&vec![0], 1);
assert!(result.is_err());
assert_eq!((PathError::RequestedPathNotAvailable, 1), result.unwrap_err());

// Now we create a node that will have address [0] :
result = n.add_cargo_under_path(&vec![], 1);
assert!(result.is_ok());
result_path = result.unwrap();
assert_eq!(vec![0], result_path);

// So now we can add a node after the one having address [0] :
result = n.add_cargo_after_path(&vec![0], 2);
assert!(result.is_ok());
result_path = result.unwrap();
assert_eq!(vec![1], result_path);
assert_eq!(&2, n.borrow_cargo(&result_path).unwrap());

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

// Traversing the cargoes of all nodes can be done using the iter() method :
let mut sum = n.iter().fold(
    0i8,
    |mut accum, &crg| {
        accum += crg;
        accum
    }
);

assert_eq!(6i8, sum);

// However, the traverse* methods runs somewhat faster.
// Moreover, traverse_mut offers mutable access to the nodes :
n.traverse_mut(
    0i8,
    |_acc, nd, _path| {
        nd.cargo *= 2i8;
        TraverseAction::Continue
    }
);

assert_eq!(&4, n.borrow_cargo(&vec![2]).unwrap());

sum = n.traverse(
    0i8,
    |acc, nd, _path| {
        *acc += nd.cargo;
        TraverseAction::Continue
    }
);

assert_eq!(12i8, sum);

Node identifiers

Another way of keeping track of specific nodes could be having cargoes of a custom type that holds an identifier number or string together with other content, and looking for the nodes using one of the traverse* methods. E.g.:

use tree_by_path::{Node, TraverseAction};

// The example's custom cargo type needs an enum.
#[derive(Clone, Debug)]
enum HtmlPart {
    Main,
    Tag(String),
    SimpleAttribute(String),
    ValueAttribute(String, String),
    Data(String),
}

// The example's custom cargo type, having an identifier property.
#[derive(Clone, Debug)]
struct HtmlCargo {
    id: u32,
    content: HtmlPart,
}

impl HtmlCargo {
    // One could have the 'new' method automatically fill in a new id
    // by increasing a static std::sync::atomic::AtomicU32.
    fn new(id: u32, content: HtmlPart) -> Self {
        Self { id, content, }
    }
}

// Let's create a rough general HTML page tree,
// thereby keeping track of the id of the page title node and the
// main content section node:
let mut general_page = Node::new(HtmlCargo::new(0, HtmlPart::Main));
let main_path = general_page.get_first_path();
let err_txt = "Adding under unknown path";

let doctype_path = general_page.add_cargo_under_path(
    &main_path,
    HtmlCargo::new(1, HtmlPart::Tag("!doctype".to_string()))
).expect(err_txt);

general_page.add_cargo_under_path(
    &doctype_path,
    HtmlCargo::new(2, HtmlPart::SimpleAttribute("html".to_string()))
).expect(err_txt);

let html_path = general_page.add_cargo_under_path(
    &main_path,
    HtmlCargo::new(3, HtmlPart::Tag("html".to_string()))
).expect(err_txt);

let head_path = general_page.add_cargo_under_path(
    &html_path,
    HtmlCargo::new(4, HtmlPart::Tag("head".to_string()))
).expect(err_txt);

let title_tag_id = 5u32;
let title_content_id = 6u32;

let title_tag_path = general_page.add_cargo_under_path(
    &head_path,
    HtmlCargo::new(5, HtmlPart::Tag("title".to_string()))
).expect(err_txt);

let body_path = general_page.add_cargo_under_path(
    &html_path,
    HtmlCargo::new(7, HtmlPart::Tag("body".to_string()))
).expect(err_txt);

// Adding other things to body, like navigation, footer, etc.

// Adding the tag that will contain custom parts.
let custom_part_id = 8u32;

general_page.add_cargo_under_path(
    &body_path,
    HtmlCargo::new(custom_part_id, HtmlPart::Tag("section".to_string()))
).expect(err_txt);

// Let's clone the general page skeleton in order to make a custom page.
let mut custom_page_welcome = general_page.clone();

// Let's look for the node of the title tag by title_tag_id
// and add a title text if found.
let title_tag_found = custom_page_welcome.traverse_mut(
    false,
    |is_found, node, path| {
        if node.cargo.id == title_tag_id {
            *is_found = true;

            node.add_cargo_under_path(
                &vec![],
                HtmlCargo::new(title_content_id, HtmlPart::Data("Welcome !".to_string()))
            ).expect(err_txt);

            TraverseAction::Stop
        } else {
            TraverseAction::Continue
        }
    }
);

if !title_tag_found {
    println!("Couldn't add a title to the custom page HTML tree.");
}

// Let's look for the node of the custom_part by custom_part_id and add content if found.
let custom_part_tag_found = custom_page_welcome.traverse_mut(
    false,
    |is_found, node, path| {
        if node.cargo.id == custom_part_id {
            *is_found = true;

            let mut last_path = node.add_cargo_under_path(
                &vec![],
                HtmlCargo::new(1000, HtmlPart::Tag("h1".to_string()))
            ).expect(err_txt);

            node.add_cargo_under_path(
                &last_path,
                HtmlCargo::new(1001, HtmlPart::Data("Welcome !".to_string()))
            ).expect(err_txt);

            // Etcetera : adding further content.

            TraverseAction::Stop
        } else {
            TraverseAction::Continue
        }
    }
);

if !custom_part_tag_found {
    println!("Couldn't add custom content to the custom page HTML tree.");
}

// Using another custom_page_welcome.traverse call,
// the very HTML string for the custom page could be created.

Structs

  • Node
    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.
  • NodeIterator
    NodeIterator<'it, C> : std::iter::Iterator allows iteration over immutable references to a tree’s cargoes.

Enums

  • PathError
  • TraverseAction
    A TraverseAction variant is expected as the return value of the callback closure or function passed to Node’s traverse(_mut)(_back) methods.

Type Aliases

  • CargoSwapResult
    If Node<C>::swap_cargo succeeds, it returns
    Ok<(node_parameter_moved_back_out, previous_cargo)>.
    Otherwise, it returns
    Err<(PathError, node_parameter_moved_back_out, new_cargo_moved_back_out)>.