#include <tree.h>
Inheritance diagram for nodes::tree:
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. | |
| IMPLEMENT_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 outcome | prune (tree *branch_to_cut) |
| Removes the specified branch from this tree. | |
| virtual 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. | |
Classes | |
| class | iterator |
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.
| nodes::tree::tree | ( | ) |
constructs a new tree with a root and zero branches.
Definition at line 266 of file tree.cpp.
References nodes::BACKWARDS_BRANCH, NIL, and nodes::node::set_link().
| nodes::tree::~tree | ( | ) | [virtual] |
| nodes::tree::IMPLEMENT_CLASS_NAME | ( | "tree" | ) |
| 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 286 of file tree.cpp.
References bounds_return, branches(), nodes::node::get_link(), and NIL.
Referenced by nodes::symbol_tree::branch(), directory_tree::seek(), and ~tree().
| 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 293 of file tree.cpp.
References nodes::node::which().
Referenced by prune(), and nodes::symbol_tree::prune().
| int nodes::tree::branches | ( | ) | const [virtual] |
Returns the number of branches currently connected to this tree.
Definition at line 284 of file tree.cpp.
References nodes::node::links().
Referenced by branch(), directory_tree::children(), nodes::symbol_tree::find(), bookmark_tree::process_category(), prune_index(), directory_tree::seek(), nodes::symbol_tree::sort(), nodes::symbol_tree::text_form(), and ~tree().
| 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 282 of file tree.cpp.
References nodes::BACKWARDS_BRANCH, and nodes::node::get_link().
Referenced by depth(), nodes::symbol_tree::find(), directory_tree::remove_path(), nodes::tree::iterator::whack(), and ~tree().
| 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 296 of file tree.cpp.
References nodes::BACKWARDS_BRANCH, and nodes::node::get_link().
Referenced by depth().
| int nodes::tree::depth | ( | ) | const [virtual] |
Returns the distance of "this" from the root. The root's depth is 0.
Definition at line 342 of file tree.cpp.
References parent(), and root().
Referenced by nodes::symbol_tree::text_form().
| void nodes::tree::attach | ( | tree * | new_branch | ) | [virtual] |
Attaches the specified branch to the current tree.
Definition at line 306 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(), directory_tree::add_path(), bookmark_tree::find_parent(), bookmark_tree::process_category(), and nodes::packable_tree::recursive_unpack().
| 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 313 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().
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 325 of file tree.cpp.
References common::NOT_FOUND, prune_index(), and which().
Referenced by nodes::symbol_tree::prune(), 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 332 of file tree.cpp.
References nodes::BACKWARDS_BRANCH, bounds_return, branches(), nodes::node::get_link(), NIL, common::NOT_FOUND, common::OKAY, nodes::node::set_link(), and nodes::node::zap_link().
Referenced by prune(), and nodes::symbol_tree::sort().
| tree::iterator nodes::tree::start | ( | traversal_directions | direction | ) | const |
Returns a fresh iterator positioned at this tree node.
Definition at line 382 of file tree.cpp.
Referenced by nodes::packable_tree::recursive_pack(), and 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 356 of file tree.cpp.
References nodes::path::size().
1.5.1