A symbol table that supports scope nesting and/or trees of symbol tables. More...

#include <symbol_tree.h>

Inheritance diagram for nodes::symbol_tree:

[legend]

Collaboration diagram for nodes::symbol_tree:

[legend]

Public Types
enum	find_methods { just_branches , recurse_downward , recurse_upward }

Public Types inherited from nodes::tree
enum	traversal_directions { prefix , infix , postfix , to_branches , reverse_branches }

enum	elevator_directions { TOWARD_ROOT , AWAY_FROM_ROOT }

Public Member Functions
	symbol_tree (const basis::astring &node_name, int estimated_elements=100)
	creates a symbol_tree node with the "node_name". More...

virtual	~symbol_tree ()
	all child nodes will be deleted too. More...

	DEFINE_CLASS_NAME ("symbol_tree")

int	children () const
	returns the number of children of this node. More...

const basis::astring &	name () const
	returns the name of this node. More...

int	estimated_elements () const
	returns the number of bits in this node's table. More...

symbol_tree *	branch (int index) const
	returns the "index"th branch. More...

void	rehash (int estimated_elements)
	resizes the underlying symbol_table for this node. More...

void	hash_appropriately (int estimated_elements)
	resizes the hashing parameter to limit bucket sizes. More...

bool	add (symbol_tree *to_add)
	adds a child to this symbol_tree. More...

virtual basis::outcome	prune (tree *to_zap)
	removes a sub-tree "to_zap". More...

symbol_tree *	find (const basis::astring &to_find, find_methods how, basis::string_comparator_function *comp=NULL_POINTER)
	returns the node specified by "to_find" or NULL_POINTER. More...

void	sort ()
	sorts the sub-nodes of this symbol_tree. More...

basis::astring	text_form () const
	traverses the tree to build a textual list of the nodes. More...

Public Member Functions inherited from nodes::tree
	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 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_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 symbol table that supports scope nesting and/or trees of symbol tables.

Note: although the symbol_tree is a tree, proper functioning is only guaranteed if you stick to its own add / find methods rather than calling on the base class's methods... but the tree's iterator support should be used for traversing the symbol_tree and prune should work as expected.

Definition at line 36 of file symbol_tree.h.

Member Enumeration Documentation

◆ find_methods

enum nodes::symbol_tree::find_methods

Enumerator
just_branches
recurse_downward
recurse_upward

Definition at line 79 of file symbol_tree.h.

Constructor & Destructor Documentation

◆ symbol_tree()

nodes::symbol_tree::symbol_tree	(	const basis::astring &	node_name,
		int	estimated_elements = `100`
	)

creates a symbol_tree node with the "node_name".

presumably this could be a child of another symbol tree also. the "estimated_elements" is used to choose a size for the table holding the names.

Definition at line 52 of file symbol_tree.cpp.

References FUNCDEF.

◆ ~symbol_tree()

nodes::symbol_tree::~symbol_tree ( )

virtual

all child nodes will be deleted too.

if the automatic child node deletion is not good for your purposes, be sure to unhook the children before deletion of the tree and manage them separately.

Definition at line 60 of file symbol_tree.cpp.

References FUNCDEF, LOG, and basis::WHACK().

Member Function Documentation

◆ add()

bool nodes::symbol_tree::add ( symbol_tree * to_add )

adds a child to this symbol_tree.

Definition at line 87 of file symbol_tree.cpp.

References nodes::tree::attach(), FUNCDEF, LOG, and name().

◆ branch()

symbol_tree * nodes::symbol_tree::branch ( int index ) const

virtual

returns the "index"th branch.

Reimplemented from nodes::tree.

Definition at line 134 of file symbol_tree.cpp.

References nodes::tree::branch().

Referenced by find(), bookmark_tree::process_category(), and sort().

◆ children()

int nodes::symbol_tree::children ( ) const

returns the number of children of this node.

Definition at line 76 of file symbol_tree.cpp.

◆ DEFINE_CLASS_NAME()

nodes::symbol_tree::DEFINE_CLASS_NAME ( "symbol_tree" )

◆ estimated_elements()

int nodes::symbol_tree::estimated_elements ( ) const

returns the number of bits in this node's table.

Definition at line 80 of file symbol_tree.cpp.

Referenced by hash_appropriately(), and rehash().

◆ find()

symbol_tree * nodes::symbol_tree::find	(	const basis::astring &	to_find,
		find_methods	how,
		basis::string_comparator_function *	comp = `NULL_POINTER`
	)

returns the node specified by "to_find" or NULL_POINTER.

this should be fairly quick due to the symbol table's hashing. the "how" method specifies the type of recursion to be used in searching if any. if "how" is passed as "just_branches", then only the branches are checked and no recursion upwards or downwards is performed. if "how" is "recurse_downward", then all sub-trees under the branches are checked also. if "how" is given as "recurse_upward", then "this" node and parent nodes are checked. the "comp" parameter will be used for comparing the strings if it's passed as non-null.

Parameters

comp	= just_branches,

Definition at line 159 of file symbol_tree.cpp.

References basis::astring_comparator(), branch(), nodes::tree::branches(), find(), FUNCDEF, LOG, name(), NULL_POINTER, nodes::tree::parent(), recurse_downward, and recurse_upward.

Referenced by find(), bookmark_tree::find_parent(), and bookmark_tree::process_category().

◆ hash_appropriately()

void nodes::symbol_tree::hash_appropriately ( int estimated_elements )

resizes the hashing parameter to limit bucket sizes.

rehashes the name table so that there will be no more (on average) than "max_per_bucket" items per hashing bucket. this is the max that will need to be crossed to find an item, so reducing the number per bucket speeds access but also requires more memory.

Definition at line 84 of file symbol_tree.cpp.

References estimated_elements().

◆ name()

const astring & nodes::symbol_tree::name ( ) const

returns the name of this node.

Definition at line 78 of file symbol_tree.cpp.

Referenced by add(), find(), bookmark_tree::process_category(), prune(), sort(), and text_form().

◆ prune()

outcome nodes::symbol_tree::prune ( tree * to_zap )

virtual

removes a sub-tree "to_zap".

the "to_zap" tree had better be a symbol_tree; we are just matching the lower-level virtual function prototype. note that the tree node "to_zap" is not destroyed; it is just plucked from the tree.

hmmm: how about not? throw("error: symbol_tree::prune: wrong type of node in prune");

Reimplemented from nodes::tree.

Definition at line 98 of file symbol_tree.cpp.

References FUNCDEF, LOG, name(), basis::negative(), nodes::tree::prune(), and nodes::tree::which().

◆ rehash()

void nodes::symbol_tree::rehash ( int estimated_elements )

resizes the underlying symbol_table for this node.

Definition at line 82 of file symbol_tree.cpp.

References estimated_elements().

◆ sort()

void nodes::symbol_tree::sort ( )

sorts the sub-nodes of this symbol_tree.

Definition at line 138 of file symbol_tree.cpp.

References branch(), nodes::tree::branches(), nodes::tree::insert(), name(), and nodes::tree::prune_index().

Referenced by bookmark_tree::find_parent(), and bookmark_tree::process_category().

◆ text_form()

astring nodes::symbol_tree::text_form ( ) const

traverses the tree to build a textual list of the nodes.

Definition at line 216 of file symbol_tree.cpp.

References nodes::tree::branches(), nodes::tree::depth(), FUNCDEF, nodes::hier_prefix(), LOG, name(), nodes::tree::iterator::next(), nodes::tree::prefix, basis::astring::s(), nodes::path::size(), and nodes::tree::start().

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

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

Public Types

Public Member Functions

Detailed Description

Member Enumeration Documentation

◆ find_methods

Constructor & Destructor Documentation

◆ symbol_tree()

◆ ~symbol_tree()

Member Function Documentation

◆ add()

◆ branch()

◆ children()

◆ DEFINE_CLASS_NAME()

◆ estimated_elements()

◆ find()

◆ hash_appropriately()

◆ name()

◆ prune()

◆ rehash()

◆ sort()

◆ text_form()