tree_iterators_rs::prelude

Trait MutBorrowedTreeNode

Source 
pub trait MutBorrowedTreeNode<'a>
where
    Self: Sized + 'a,
{
    type MutBorrowedValue: Sized;
    type MutBorrowedChildren: IntoIterator<Item = &'a mut Self, IntoIter: FusedIterator>;

    // Required method
    fn get_value_and_children_iter_mut(
        &'a mut self,
    ) -> (Self::MutBorrowedValue, Self::MutBorrowedChildren);

    // Provided methods
    fn at_path_mut(&'a mut self, path: &[usize]) -> Option<&'a mut Self> { ... }
    fn bfs_iter_mut(&'a mut self) -> MutBorrowedBFSIterator<'a, Self> ⓘ { ... }
    fn dfs_preorder_iter_mut(
        &'a mut self,
    ) -> MutBorrowedDFSPreorderIterator<'a, Self> ⓘ { ... }
    fn dfs_postorder_iter_mut(
        &'a mut self,
    ) -> MutBorrowedDFSPostorderIterator<'a, Self> ⓘ { ... }
    fn into_pipeline_mut(
        &'a mut self,
    ) -> impl TreeIterator<Self::MutBorrowedValue, Self::MutBorrowedChildren> { ... }
    fn prune_mut<F>(&'a mut self, f: F) -> Option<Tree<Self::MutBorrowedValue>>
       where F: FnMut(&Self::MutBorrowedValue) -> bool { ... }
    fn prune_path_mut<F>(
        &'a mut self,
        f: F,
    ) -> Option<Tree<Self::MutBorrowedValue>>
       where F: FnMut(&[usize], &Self::MutBorrowedValue) -> bool { ... }
    fn prune_depth_mut(
        &'a mut self,
        max_depth: usize,
    ) -> Tree<Self::MutBorrowedValue> { ... }
    fn map_mut<Output, F>(&'a mut self, f: F) -> Tree<Output>
       where F: FnMut(Self::MutBorrowedValue) -> Output { ... }
    fn fold_mut<Output, F>(&'a mut self, f: F) -> Output
       where F: FnMut(Vec<Output>, Self::MutBorrowedValue) -> Output { ... }
}
Expand description

A tree node where getting its children mutably borrows its value.

Required Associated Types§

Source

type MutBorrowedValue: Sized

A mutable reference to the value of each node in the tree.

Source

type MutBorrowedChildren: IntoIterator<Item = &'a mut Self, IntoIter: FusedIterator>

The type of iterator that can be used to iterate over each node’s children collection.

Required Methods§

Source

fn get_value_and_children_iter_mut( &'a mut self, ) -> (Self::MutBorrowedValue, Self::MutBorrowedChildren)

This method gets the value and children from this node. The other methods of this trait assume that the ‘Children’ list does not contain any circular references. If there are, an infinite loop will result.

Provided Methods§

Source

fn at_path_mut(&'a mut self, path: &[usize]) -> Option<&'a mut Self>

Given a path (list of indexes - see TreeContext::path for more information) down the nodes of tree, at_path will walk the list of indexes and fetch the node at the given path.

§Example Usage
use tree_iterators_rs::prelude::{Tree, OwnedTreeNode};

let tree = Tree {
    value: 0,
    children: vec![
        Tree {
            value: 1,
            children: vec![
                Tree {
                    value: 2,
                    children: vec![],
                },
                Tree {
                    value: 3,
                    children: vec![],
                }
            ]
        }
    ]
};

assert_eq!(Some(3), tree.at_path(&[0, 1]).map(|tree| tree.value));
Source

fn bfs_iter_mut(&'a mut self) -> MutBorrowedBFSIterator<'a, Self> ⓘ

This method retrieves an iterator that can be used to perform Breadth First (VecDeque-based) searches of a tree.

A Breadth First Search (BFS) is defined as:

A tree traversal that involves breadth-first searching a tree from the top down. Given a tree of the following shape, this traversal type would traverse the elements in the order 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

In this traversal, we scan each level of the tree from left to right before going down to the next level.

       0
      / \
     1   2
    / \ / \
   3  4 5  6
          /
         7
          \
           8
          /
         9
          \
          10
Source

fn dfs_preorder_iter_mut( &'a mut self, ) -> MutBorrowedDFSPreorderIterator<'a, Self> ⓘ

This method retrieves an iterator that can be used to perform Depth First Preorder searches of a tree.

A Depth First Preorder search is defined as:

A tree traversal that involves depth-first searching a tree from the top down. Given a tree of the following shape, this traversal type would traverse the elements in the order 0, 1, 3, 4, 2, 5, 6, 7, 8, 9, 10.

In this traversal, each node will only be traversed before any of its children have been traversed.

       0
      / \
     1   2
    / \ / \
   3  4 5  6
          /
         7
          \
           8
          /
         9
          \
          10
Source

fn dfs_postorder_iter_mut( &'a mut self, ) -> MutBorrowedDFSPostorderIterator<'a, Self> ⓘ

This method retrieves an iterator that can be used to perform Depth First Postorder searches of a tree.

A Depth First Postorder search (referred to as DFS Postorder) is defined as:

A tree traversal that involves depth-first searching a tree from the bottom up. Given a tree of the following shape, this traversal type would traverse the elements in the order 3, 4, 1, 5, 10, 9, 8, 7, 6, 2, 0.

In this traversal, each node will only be traversed after all of its children have been traversed.

       0
      / \
     1   2
    / \ / \
   3  4 5  6
          /
         7
          \
           8
          /
         9
          \
          10

This traversal type guarantees that getChildren() will only be called once per node of the tree.

Source

fn into_pipeline_mut( &'a mut self, ) -> impl TreeIterator<Self::MutBorrowedValue, Self::MutBorrowedChildren>

This method converts the current TreeNode into a TreeIterator.

TreeIterators have 2 purposes:

  1. they serve as the internal piping of tree_iterators_rs
  2. they can efficiently chain the prune, map, and fold operations on a tree.

If you are only applying a single prune, map, or fold operation, just call the associated method.

If you are chaining many operations together, use into_pipeline. This will be much more efficient in memory since it only maintains a single ancestor stack of the tree at a time.

§Example Usage:
use tree_iterators_rs::{
    examples::create_example_tree,
    prelude::{Tree, MutBorrowedTreeNode, TreeIteratorBase, TreeIterator}
};

let mut tree = create_example_tree();
let result = tree.into_pipeline_mut()
    .prune_depth(2)
    .map_tree(|value| *value + 200)
    .collect_tree()
    .expect("all non-prune methods to collect into a Some()");

assert_eq!(
    Tree {
       value: 200,
       children: vec![
           Tree {
               value: 201,
               children: vec![
                   Tree {
                       value: 203,
                       children: vec![],
                   },
                   Tree {
                       value: 204,
                       children: vec![],
                   },
               ],
           },
           Tree {
               value: 202,
               children: vec![
                   Tree {
                       value: 205,
                       children: vec![],
                   },
                   Tree {
                       value: 206,
                       children: vec![],
                   },
               ],
           },
       ],
    },
    result);
Source

fn prune_mut<F>(&'a mut self, f: F) -> Option<Tree<Self::MutBorrowedValue>>
where F: FnMut(&Self::MutBorrowedValue) -> bool,

Prune is a tree-based analog to filter.

Uses the given closure to determine if each subtree in this tree should be pruned.

Given an element the closure must return true or false. Any nodes in the tree for which this evaluates to true will be pruned out of the resulting tree. If the root node is pruned, this will return None.

The closure is called on the nodes in a depth first preorder traversal order (see dfs_preorder for more details). If a node is determined to be pruned, its entire subtree will be pruned without calling the closure on its descendent nodes.

§Basic usage:
use tree_iterators_rs::prelude::{MutBorrowedTreeNode, Tree};

let mut tree = Tree {
    value: 0,
    children: vec![
        Tree {
            value: 1,
            children: vec![Tree {
                value: 3,
                children: Vec::new(),
            }],
        },
        Tree {
            value: 2,
            children: Vec::new()
        },
    ],
};

assert_eq!(
    Some(
        Tree {
            value: &mut 0,
            children: vec![
                Tree {
                    value: &mut 2,
                    children: Vec::new(),
                }
            ],
        },
    ),
    tree.prune_mut(|value| {
        /// The output for this code would be the following. A couple notes about
        /// this output:
        /// 1. the node with a value of '1' has been removed
        /// 2. the closure is never called on the node with a value of '3' since
        ///    it is already determined to be pruned once '1' has been evaluated.
        /// ```
        /// 0
        /// 1
        /// 2
        /// ```
        println!("{value:?}");
        **value == 1
    })
);
Source

fn prune_path_mut<F>(&'a mut self, f: F) -> Option<Tree<Self::MutBorrowedValue>>
where F: FnMut(&[usize], &Self::MutBorrowedValue) -> bool,

Prune is a tree-based analog to filter.

Uses the given closure to determine if each subtree in this tree should be pruned.

Given the path of an element and the element’s value, the closure must return true or false. Any nodes in the tree for which this evaluates to true will be pruned out of the resulting tree. If the root node is pruned, this will return None.

The closure is called on the nodes in a depth first preorder traversal order (see dfs_preorder for more details). If a node is determined to be pruned, its entire subtree will be pruned without calling the closure on its descendent nodes.

§Basic usage:
use tree_iterators_rs::prelude::{MutBorrowedTreeNode, Tree};

let mut tree = Tree {
    value: 0,
    children: vec![
        Tree {
            value: 1,
            children: vec![Tree {
                value: 3,
                children: Vec::new(),
            }],
        },
        Tree {
            value: 2,
            children: Vec::new()
        },
    ],
};

assert_eq!(
    Some(
        Tree {
            value: &mut 0,
            children: vec![
                Tree {
                    value: &mut 2,
                    children: Vec::new(),
                }
            ],
        },
    ),
    tree.prune_path_mut(|path, value| {
        /// The output for this code would be the following. A couple notes about
        /// this output:
        /// 1. the node with a value of '1' has been removed
        /// 2. the closure is never called on the node with a value of '3' since
        ///    it is already determined to be pruned once '1' has been evaluated.
        /// ```
        /// 0
        /// 1
        /// 2
        /// ```
        println!("{value:?}");
        matches!(path.get(0), Some(0))
    })
);
Source

fn prune_depth_mut( &'a mut self, max_depth: usize, ) -> Tree<Self::MutBorrowedValue>

Prune is a tree-based analog to filter.

Uses the depth of each subtree to determine if the subtree should be pruned. Any node with a depth that is strictly greater than the max_depth parameter will be pruned from the tree.

Depth is zero-based, so the root node is considered to be at depth zero.

Ex. given a tree like the following, the depths would be as labeled.

       0       <- depth: 0
      / \
     1   2     <- depth: 1
    / \ / \
   3  4 5  6   <- depth: 2
          /
         7     <- depth: 3
          \
           8   <- depth: 4
          /
         9     <- depth: 5
          \
          10   <- depth: 6
§Basic usage:
use tree_iterators_rs::prelude::{Tree, MutBorrowedTreeNode};

let mut tree = Tree {
    value: 0,
    children: vec![
        Tree {
            value: 1,
            children: vec![Tree {
                value: 3,
                children: vec![],
            }],
        },
        Tree {
            value: 2,
            children: vec![],
        },
    ],
};

assert_eq!(
    Tree {
        value: &mut 0,
        children: vec![],
    },
    tree.prune_depth_mut(0)
);
Source

fn map_mut<Output, F>(&'a mut self, f: F) -> Tree<Output>
where F: FnMut(Self::MutBorrowedValue) -> Output,

map is a tree-based analog to map.

Takes a closure and applies that closure to each node’s value in the tree.

map() transforms one tree into another, by means of its argument: something that implements FnMut. It produces a new tree which calls this closure on each node of the original tree.

If you are good at thinking in types, you can think of map() like this: If you have a tree that has elements of some type A, and you want a tree of some other type B, you can use map(), passing a closure that takes an A and returns a B.

§Example Usage
use tree_iterators_rs::{
    examples::create_example_binary_tree,
    prelude::{Tree, MutBorrowedTreeNode}
};

let mut tree = Tree {
    value: "0-0",
    children: vec![
        Tree {
            value: "1-1",
            children: vec![],
        },
        Tree {
            value: "2-2",
            children: vec![],
        }
    ],
};

let result = tree.map_mut(|value: &mut &'static str| {
    value.split("-").nth(1).unwrap().to_string()
});

assert_eq!(
    Tree {
        value: "0".to_string(),
        children: vec![
            Tree {
                value: "1".to_string(),
                children: vec![],
            },
            Tree {
                value: "2".to_string(),
                children: vec![],
            },
        ],
    },
    result);
Source

fn fold_mut<Output, F>(&'a mut self, f: F) -> Output
where F: FnMut(Vec<Output>, Self::MutBorrowedValue) -> Output,

fold is a tree-based analog to fold.

Folds every element into an accumulation by applying an operation, returning the final result.

fold() takes one argument: a closure with two arguments: the result of accumulating all children of the current tree node, and an element. The closure returns the value that the accumulator should have for the parent node’s accumulation.

After applying this closure to every node of the tree, fold() returns the accumulation.

This operation is sometimes called ‘reduce’ or ‘inject’.

Folding is useful whenever you have a tree of something, and want to produce a single value from it.

§Example Usage
use tree_iterators_rs::{
    examples::create_example_tree,
    prelude::MutBorrowedTreeNode
};

let mut tree = create_example_tree();
let accumulation = tree.fold_mut(|child_accumulations: Vec<usize>, value| {
    child_accumulations
        .into_iter()
        .sum::<usize>()
    + *value
});

assert_eq!(55, accumulation);

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors§