A dynamically linked tree with an arbitrary number of branches. More...

#include <tree.h>

Inheritance diagram for nodes::tree:

[legend]

Collaboration diagram for nodes::tree:

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. More...

virtual	~tree ()
	destroys the tree by recursively destroying all child tree nodes. More...

	DEFINE_CLASS_NAME ("tree")

virtual tree *	branch (int branch_number) const
	Returns the specified branch of this tree. More...

virtual int	which (tree *branch_to_find) const
	Returns the branch number for a particular branch in this tree. More...

virtual int	branches () const
	Returns the number of branches currently connected to this tree. More...

virtual tree *	parent () const
	Returns the tree node that is the immediate ancestor of this one. More...

virtual tree *	root () const
	Locates and returns the absolute root of the tree containing this tree. More...

virtual int	depth () const
	Returns the distance of "this" from the root. The root's depth is 0. More...

virtual void	attach (tree *new_branch)
	Attaches the specified branch to the current tree. More...

virtual void	insert (int branch_place, tree *new_branch)
	inserts "new_branch" before the branches starting at "branch_place". More...

virtual basis::outcome	prune (tree *branch_to_cut)
	Removes the specified branch from this tree. More...

virtual basis::outcome	prune_index (int branch_to_cut)
	Removes the branch at the specified index from this tree. More...

iterator	start (traversal_directions direction) const
	Returns a fresh iterator positioned at this tree node. More...

virtual bool	generate_path (path &to_follow) const
	Returns the path to "this" path_tree from its root. More...

Public Member Functions inherited from nodes::node
	node (int number_of_links=0)
	the constructor provides for "number_of_links" links initially. More...

virtual	~node ()
	the destructor simply invalidates the node. More...

int	links () const
	Returns the number of links the node currently holds. More...

void	set_link (int link_number, node *new_link)
	Connects the node "new_link" to this node. More...

node *	get_link (int link_number) const
	Returns the node that is connected to the specified "link_number". More...

void	zap_link (int link_number)
	the specified link is removed from the node. More...

void	insert_link (int where, node *to_add=NULL_POINTER)
	adds a new link prior to the position specified in "where". More...

int	which (node *to_find) const
	locates the index where "to_find" lives in our list of links. More...

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

◆ elevator_directions

enum nodes::tree::elevator_directions

Enumerator
TOWARD_ROOT
AWAY_FROM_ROOT

Definition at line 114 of file tree.h.

◆ traversal_directions

enum nodes::tree::traversal_directions

Enumerator
prefix
infix
postfix
to_branches
reverse_branches

Definition at line 94 of file tree.h.

Constructor & Destructor Documentation

◆ tree()

nodes::tree::tree ( )

constructs a new tree with a root and zero branches.

Definition at line 275 of file tree.cpp.

References nodes::BACKWARDS_BRANCH, NULL_POINTER, and nodes::node::set_link().

◆ ~tree()

nodes::tree::~tree ( )

virtual

destroys the tree by recursively destroying all child tree nodes.

Definition at line 279 of file tree.cpp.

References structures::stack< contents >::acquire_pop(), branch(), branches(), FUNCDEF, LOG, NULL_POINTER, parent(), prune(), structures::stack< contents >::push(), structures::stack< contents >::size(), and basis::WHACK().

Member Function Documentation

◆ attach()

void nodes::tree::attach ( tree * new_branch )

virtual

Attaches the specified branch to the current tree.

Definition at line 453 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(), bookmark_tree::process_category(), and nodes::packable_tree::recursive_unpack().

◆ branch()

tree * nodes::tree::branch ( int branch_number ) const

virtual

Returns the specified branch of this tree.

NULL_POINTER is returned if the "branch_number" refers to a branch that does not exist.

Reimplemented in nodes::symbol_tree.

Definition at line 433 of file tree.cpp.

References bounds_return, branches(), nodes::node::get_link(), and NULL_POINTER.

Referenced by nodes::symbol_tree::branch(), filesystem::directory_tree::jump_to(), filesystem::directory_tree::seek(), and ~tree().

◆ branches()

int nodes::tree::branches ( ) const

virtual

Returns the number of branches currently connected to this tree.

Definition at line 431 of file tree.cpp.

References nodes::node::links().

Referenced by branch(), filesystem::directory_tree::children(), nodes::symbol_tree::find(), 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().

◆ DEFINE_CLASS_NAME()

nodes::tree::DEFINE_CLASS_NAME ( "tree" )

◆ depth()

int nodes::tree::depth ( ) const

virtual

Returns the distance of "this" from the root. The root's depth is 0.

Definition at line 502 of file tree.cpp.

References parent(), and root().

Referenced by nodes::symbol_tree::text_form().

◆ generate_path()

bool nodes::tree::generate_path ( path & to_follow ) const

virtual

Returns the path to "this" path_tree from its root.

Definition at line 516 of file tree.cpp.

References nodes::path::size().

◆ insert()

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 460 of file tree.cpp.

References nodes::BACKWARDS_BRANCH, nodes::node::get_link(), nodes::node::insert_link(), nodes::node::links(), NULL_POINTER, and nodes::node::set_link().

Referenced by nodes::symbol_tree::sort().

◆ parent()

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 NULL_POINTER is returned.

Definition at line 429 of file tree.cpp.

References nodes::BACKWARDS_BRANCH, and nodes::node::get_link().

Referenced by depth(), nodes::symbol_tree::find(), filesystem::directory_tree::remove_path(), nodes::tree::iterator::whack(), and ~tree().

◆ prune()

outcome nodes::tree::prune ( tree * branch_to_cut )

virtual

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 472 of file tree.cpp.

References prune_index(), and which().

Referenced by nodes::symbol_tree::prune(), filesystem::directory_tree::remove_path(), nodes::tree::iterator::whack(), and ~tree().

◆ prune_index()

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 479 of file tree.cpp.

References nodes::BACKWARDS_BRANCH, bounds_return, branches(), FUNCDEF, nodes::node::get_link(), LOG, NULL_POINTER, nodes::node::set_link(), and nodes::node::zap_link().

Referenced by prune(), and nodes::symbol_tree::sort().

◆ root()

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 443 of file tree.cpp.

References nodes::BACKWARDS_BRANCH, and nodes::node::get_link().

Referenced by depth().

◆ start()

tree::iterator nodes::tree::start ( traversal_directions direction ) const

Returns a fresh iterator positioned at this tree node.

Definition at line 542 of file tree.cpp.

Referenced by nodes::packable_tree::recursive_pack(), nodes::packable_tree::recursive_packed_size(), and nodes::symbol_tree::text_form().

◆ which()

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 440 of file tree.cpp.

References nodes::node::which().

Referenced by prune(), and nodes::symbol_tree::prune().

The documentation for this class was generated from the following files:

/opt/feistymeow.org/feisty_meow/nucleus/library/nodes/tree.h
/opt/feistymeow.org/feisty_meow/nucleus/library/nodes/tree.cpp

Classes

Public Types

Public Member Functions

Detailed Description

Member Enumeration Documentation

◆ elevator_directions

◆ traversal_directions

Constructor & Destructor Documentation

◆ tree()

◆ ~tree()

Member Function Documentation

◆ attach()

◆ branch()

◆ branches()

◆ DEFINE_CLASS_NAME()

◆ depth()

◆ generate_path()

◆ insert()

◆ parent()

◆ prune()

◆ prune_index()

◆ root()

◆ start()

◆ which()