pub trait VecPreOrderInsertionHelper<T> {
    // Required method
    fn insert_pre_order(&mut self, elem: &T, tree_root: &Node);
}
Expand description

Helper trait to insert an element into vector whose elements are maintained in tree order

Required Methods§

source

fn insert_pre_order(&mut self, elem: &T, tree_root: &Node)

Implementations on Foreign Types§

source§

impl<T> VecPreOrderInsertionHelper<T> for Vec<Dom<T>>where T: DerivedFrom<Node> + DomObject,

source§

fn insert_pre_order(&mut self, elem: &T, tree_root: &Node)

This algorithm relies on the following assumptions:

  • any elements inserted in this vector share the same tree root
  • any time an element is removed from the tree root, it is also removed from this array
  • any time an element is moved within the tree, it is removed from this array and re-inserted

Under these assumptions, an element’s tree-order position in this array can be determined by performing a preorder traversal of the tree root’s children, and increasing the destination index in the array every time a node in the array is encountered during the traversal.

Implementors§