Struct GenTree

pub struct GenTree<T> { /* private fields */ }

Implementations

impl<T> GenTree<T>

pub fn new() -> GenTree<T>

Creates a new, zero-sized GenTree.

pub fn new_with_capacity(capacity: usize) -> GenTree<T>

Creates a new GenTree that pre-allocates to the given capacity.

pub fn root(&self) -> Position

Returns the Position to the tree’s root node.

pub fn mut_root(&mut self, data: T)

pub fn is_root(&self, position: &Position) -> bool

Indicates whether the given Position is the tree’s root.

pub fn is_some(&self, position: &Position) -> bool

Indicates whether the given Position contains data.

pub fn is_none(&self, position: &Position) -> bool

Indicates whether the given Position contains data.

pub fn is_empty(&self) -> bool

Indicates whether the tree is empty.

pub fn size(&self) -> usize

Returns the number of live nodes in the tree.

pub fn num_children(&self, position: &Position) -> usize

Returns the number of children for a Node at the given Position.

pub fn depth(&mut self, _node: &Position) -> usize

WARNING: Unimplemented

pub fn height(&mut self, _node: &Position) -> usize

WARNING: Unimplemented

pub fn get_data(&self, position: &Position) -> Option<&T>

Returns an immutable reference to the data at the given Position, if Some.

pub fn get_for_pos(&self, position: &Position) -> Option<&T>

Returns an immutable reference to the data at the given Position, if Some.

pub fn add_child(&mut self, position: &Position, data: T) -> Position

Adds a child to the given Position and returns its Position.

pub fn children(&self, position: &Position) -> &Vec<Position>

Returns a reference to the list of child Positions for the given Position.

pub fn remove(&mut self, position: Position) -> Option<T>

Removes a node at the given Position and returns its data. If the removed Position has a parent, all the deleted node’s children get pushed to the deleted Position’s parent. If the deleted Position has no parent (root) a new parent is designated as the first child of the deleted node, e.g. this is a tree, not a forest. Ordering for the designation of the new root is not guaranteed, and depends on when child Positions were added. For this reason, caution is advised when potentially deleting root nodes.

Runs in O(s + c) time where:

• s is the number of the deleted node’s siblings (i.e. the number of its parent’s children),
• c is the number of the deleted node’s children.

Precondition:

          3
       /    \
      5      9 (marked for deleteion)
    /  \    /  \
   8   12  11  14

Postcondition:

          3
       /  |  \
      5   11  14
    /  \    
   8   12  

Precondition:

          3 (marked for deletion)
       /  |  \
      5   11  14
    /  \    
   8   12  

Postcondition:

         5
    /  /   \  \
   8  12   11 14

Precondition:

          3 (marked for deletion)
       /    \
      9      5
    /  \    /  \
   8   12  11  14

Postcondition:

          9
       /  |  \
      8  12   5
             /  \
            11   14

pub fn parent(&mut self, position: &Position) -> Option<Position>

Returns the Position of a given Position’s parent, if Some.

Trait Implementations

impl<T: Debug> Debug for GenTree<T>

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

Formats the value using the given formatter.

impl<T> Default for GenTree<T>

fn default() -> Self

Returns the “default value” for a type.