nodes::tree Class Reference
A dynamically linked tree with an arbitrary number of branches. More...
#include <tree.h>
Classes | |
| class | iterator |
Public Types | |
| enum | traversal_directions { prefix, infix, postfix, to_branches, reverse_branches } |
| enum | elevator_directions { TOWARD_ROOT, AWAY_FROM_ROOT } |
Public Member Functions | |
| tree () | |
| constructs a new tree with a root and zero branches. | |
| virtual | ~tree () |
| destroys the tree by recursively destroying all child tree nodes. | |
| DEFINE_CLASS_NAME ("tree") | |
| virtual tree * | branch (int branch_number) const |
| Returns the specified branch of this tree. | |
| virtual int | which (tree *branch_to_find) const |
| Returns the branch number for a particular branch in this tree. | |
| virtual int | branches () const |
| Returns the number of branches currently connected to this tree. | |
| virtual tree * | parent () const |
| Returns the tree node that is the immediate ancestor of this one. | |
| virtual tree * | root () const |
| Locates and returns the absolute root of the tree containing this tree. | |
| virtual int | depth () const |
| Returns the distance of "this" from the root. The root's depth is 0. | |
| virtual void | attach (tree *new_branch) |
| Attaches the specified branch to the current tree. | |
| virtual void | insert (int branch_place, tree *new_branch) |
| inserts "new_branch" before the branches starting at "branch_place". | |
| virtual basis::outcome | prune (tree *branch_to_cut) |
| Removes the specified branch from this tree. | |
| virtual basis::outcome | prune_index (int branch_to_cut) |
| Removes the branch at the specified index from this tree. | |
| iterator | start (traversal_directions direction) const |
| Returns a fresh iterator positioned at this tree node. | |
| virtual bool | generate_path (path &to_follow) const |
| Returns the path to "this" path_tree from its root. | |
Detailed Description
A dynamically linked tree with an arbitrary number of branches.
A tree is defined as a node with n branch nodes, where n is dynamic. Each branch is also a tree. Branch numbers range from 0 through n-1 in the methods below. Trees can be self-cleaning, meaning that the tree will destroy all of its children when it is destroyed.
NOTE: the node indices are not numbered completely obviously; it is better to use the tree functions for manipulating the node rather than muddling with it directly. the branch to the tree node's parent is stored as node zero, in actuality, rather than node zero being the first branch.
Definition at line 39 of file tree.h.
Member Enumeration Documentation
Constructor & Destructor Documentation
| nodes::tree::tree | ( | ) |
constructs a new tree with a root and zero branches.
Definition at line 271 of file tree.cpp.
References nodes::BACKWARDS_BRANCH, NIL, and nodes::node::set_link().
| nodes::tree::~tree | ( | ) | [virtual] |
Member Function Documentation
| void nodes::tree::attach | ( | tree * | new_branch | ) | [virtual] |
Attaches the specified branch to the current tree.
Definition at line 311 of file tree.cpp.
References nodes::BACKWARDS_BRANCH, nodes::node::insert_link(), nodes::node::links(), and nodes::node::set_link().
Referenced by nodes::symbol_tree::add(), filesystem::directory_tree::add_path(), bookmark_tree::find_parent(), filesystem::filename_tree::pack(), bookmark_tree::process_category(), and nodes::packable_tree::recursive_unpack().
| tree * nodes::tree::branch | ( | int | branch_number | ) | const [virtual] |
Returns the specified branch of this tree.
NIL is returned if the "branch_number" refers to a branch that does not exist.
Reimplemented in nodes::symbol_tree.
Definition at line 291 of file tree.cpp.
References bounds_return, branches(), nodes::node::get_link(), and NIL.
Referenced by filesystem::directory_tree::jump_to(), filesystem::directory_tree::seek(), and ~tree().
| int nodes::tree::branches | ( | ) | const [virtual] |
Returns the number of branches currently connected to this tree.
Definition at line 289 of file tree.cpp.
References nodes::node::links().
Referenced by branch(), filesystem::directory_tree::children(), filesystem::directory_tree::jump_to(), bookmark_tree::process_category(), prune_index(), filesystem::directory_tree::seek(), nodes::symbol_tree::sort(), nodes::symbol_tree::text_form(), and ~tree().
| nodes::tree::DEFINE_CLASS_NAME | ( | "tree" | ) |
| int nodes::tree::depth | ( | ) | const [virtual] |
Returns the distance of "this" from the root. The root's depth is 0.
Definition at line 347 of file tree.cpp.
References parent(), and root().
Referenced by nodes::symbol_tree::text_form().
| bool nodes::tree::generate_path | ( | path & | to_follow | ) | const [virtual] |
Returns the path to "this" path_tree from its root.
Definition at line 361 of file tree.cpp.
References nodes::path::size().
| void nodes::tree::insert | ( | int | branch_place, | |
| tree * | new_branch | |||
| ) | [virtual] |
inserts "new_branch" before the branches starting at "branch_place".
Places a branch at a particular index and pushes the branches at that index (and after it) over by one branch.
Definition at line 318 of file tree.cpp.
References nodes::BACKWARDS_BRANCH, nodes::node::get_link(), nodes::node::insert_link(), nodes::node::links(), NIL, and nodes::node::set_link().
Referenced by nodes::symbol_tree::sort().
| tree * nodes::tree::parent | ( | ) | const [virtual] |
Returns the tree node that is the immediate ancestor of this one.
if this is the root node, then NIL is returned.
Definition at line 287 of file tree.cpp.
References nodes::BACKWARDS_BRANCH, and nodes::node::get_link().
Referenced by depth(), filesystem::directory_tree::remove_path(), nodes::tree::iterator::whack(), and ~tree().
Removes the specified branch from this tree.
note that the pruning does not affect the branch being removed; it just detaches that branch from the tree. if one wants to get rid of the branch, it should be deleted. if this cannot find the tree specified in the available branches then the branches of this tree are not touched and common::NOT_FOUND is returned.
Reimplemented in nodes::symbol_tree.
Definition at line 330 of file tree.cpp.
References prune_index(), and which().
Referenced by nodes::tree::iterator::whack(), and ~tree().
| outcome nodes::tree::prune_index | ( | int | branch_to_cut | ) | [virtual] |
Removes the branch at the specified index from this tree.
if this is given an invalid branch number, then the available branches then the branches of this tree are not touched and common::NOT_FOUND is returned.
Definition at line 337 of file tree.cpp.
References nodes::BACKWARDS_BRANCH, bounds_return, branches(), nodes::node::get_link(), NIL, nodes::node::set_link(), and nodes::node::zap_link().
Referenced by prune(), and nodes::symbol_tree::sort().
| tree * nodes::tree::root | ( | ) | const [virtual] |
Locates and returns the absolute root of the tree containing this tree.
If this tree IS the absolute root, then "this" is returned.
Definition at line 301 of file tree.cpp.
References nodes::BACKWARDS_BRANCH, and nodes::node::get_link().
Referenced by depth().
| tree::iterator nodes::tree::start | ( | traversal_directions | direction | ) | const |
Returns a fresh iterator positioned at this tree node.
Definition at line 387 of file tree.cpp.
Referenced by nodes::packable_tree::recursive_pack(), nodes::packable_tree::recursive_packed_size(), and nodes::symbol_tree::text_form().
| int nodes::tree::which | ( | tree * | branch_to_find | ) | const [virtual] |
Returns the branch number for a particular branch in this tree.
common::NOT_FOUND if the branch is not one of the child nodes.
Definition at line 298 of file tree.cpp.
Referenced by prune(), and nodes::symbol_tree::prune().
The documentation for this class was generated from the following files:
