nodes::symbol_tree Class Reference

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]

List of all members.

Public Types
enum	find_methods { just_branches, recurse_downward, recurse_upward }
Public Member Functions
	symbol_tree (const basis::astring &node_name, int estimated_elements=100)
	creates a symbol_tree node with the "node_name".
virtual	~symbol_tree ()
	all child nodes will be deleted too.
	DEFINE_CLASS_NAME ("symbol_tree")
int	children () const
	returns the number of children of this node.
const basis::astring &	name () const
	returns the name of this node.
int	estimated_elements () const
	returns the number of bits in this node's table.
symbol_tree *	branch (int index) const
	returns the "index"th branch.
void	rehash (int estimated_elements)
	resizes the underlying symbol_table for this node.
void	hash_appropriately (int estimated_elements)
	resizes the hashing parameter to limit bucket sizes.
bool	add (symbol_tree *to_add)
	adds a child to this symbol_tree.
virtual basis::outcome	prune (tree *to_zap)
	removes a sub-tree "to_zap".
symbol_tree *	find (const basis::astring &to_find, find_methods how, basis::string_comparator_function *comp=NIL)
	returns the node specified by "to_find" or NIL.
void	sort ()
	sorts the sub-nodes of this symbol_tree.
basis::astring	text_form () const
	traverses the tree to build a textual list of the nodes.

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

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

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 43 of file symbol_tree.cpp.

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 50 of file symbol_tree.cpp.

References basis::WHACK().

Member Function Documentation

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

adds a child to this symbol_tree.

Definition at line 67 of file symbol_tree.cpp.

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

symbol_tree * nodes::symbol_tree::branch ( int index ) const [virtual]

returns the "index"th branch.

Reimplemented from nodes::tree.

Definition at line 103 of file symbol_tree.cpp.

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

int nodes::symbol_tree::children ( ) const

returns the number of children of this node.

Definition at line 56 of file symbol_tree.cpp.

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

int nodes::symbol_tree::estimated_elements ( ) const

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

Definition at line 60 of file symbol_tree.cpp.

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

returns the node specified by "to_find" or NIL.

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

Parameters:

comp

= just_branches,

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

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 64 of file symbol_tree.cpp.

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

returns the name of this node.

Definition at line 58 of file symbol_tree.cpp.

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

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.

Reimplemented from nodes::tree.

Definition at line 78 of file symbol_tree.cpp.

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

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

resizes the underlying symbol_table for this node.

Definition at line 62 of file symbol_tree.cpp.

void nodes::symbol_tree::sort ( )

sorts the sub-nodes of this symbol_tree.

Definition at line 107 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().

astring nodes::symbol_tree::text_form ( ) const