#include <symbol_tree.h>
Inheritance diagram for nodes::symbol_tree:
Public Types | |
| enum | find_methods { just_branches, recurse_downward, recurse_upward } |
Public Member Functions | |
| symbol_tree (const istring &node_name, int max_bits=2) | |
| creates a symbol_tree node with the "node_name". | |
| virtual | ~symbol_tree () |
| all child nodes will be deleted too. | |
| IMPLEMENT_CLASS_NAME ("symbol_tree") | |
| int | children () const |
| returns the number of children of this node. | |
| const istring & | name () const |
| returns the name of this node. | |
| int | max_bits () 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 max_bits) |
| resizes the underlying symbol_table for this node. | |
| void | hash_appropriately (int max_per_bucket) |
| resizes the hashing parameter to limit bucket sizes. | |
| bool | add (symbol_tree *to_add) |
| adds a child to this symbol_tree. | |
| virtual outcome | prune (tree *to_zap) |
| removes a sub-tree "to_zap". | |
| symbol_tree * | find (const istring &to_find, find_methods how=just_branches, string_comparator_function *comp=NIL) |
| returns the node specified by "to_find" or NIL. | |
| void | sort () |
| sorts the sub-nodes of this symbol_tree. | |
| istring | text_form () const |
| traverses the tree to build a textual list of the nodes. | |
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 35 of file symbol_tree.h.
Definition at line 79 of file symbol_tree.h.
| nodes::symbol_tree::symbol_tree | ( | const istring & | node_name, | |
| int | max_bits = 2 | |||
| ) |
creates a symbol_tree node with the "node_name".
presumably this could be a child of another symbol tree also. the "max_bits" is used to choose a size for the table holding the names; the entries will be hashed into 2^max_bits slots.
Definition at line 45 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 52 of file symbol_tree.cpp.
References WHACK().
| nodes::symbol_tree::IMPLEMENT_CLASS_NAME | ( | "symbol_tree" | ) |
| int nodes::symbol_tree::children | ( | ) | const |
| const istring & nodes::symbol_tree::name | ( | ) | const |
returns the name of this node.
Definition at line 60 of file symbol_tree.cpp.
Referenced by add(), find(), bookmark_tree::process_category(), prune(), sort(), and text_form().
| int nodes::symbol_tree::max_bits | ( | ) | const |
| 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.
References nodes::tree::branch().
Referenced by find(), bookmark_tree::process_category(), and sort().
| void nodes::symbol_tree::rehash | ( | int | max_bits | ) |
| void nodes::symbol_tree::hash_appropriately | ( | int | max_per_bucket | ) |
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 66 of file symbol_tree.cpp.
| bool nodes::symbol_tree::add | ( | symbol_tree * | to_add | ) |
adds a child to this symbol_tree.
Definition at line 69 of file symbol_tree.cpp.
References nodes::tree::attach(), FUNCDEF, LOG, and name().
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 80 of file symbol_tree.cpp.
References deadly_error, FUNCDEF, LOG, name(), negative(), non_continuable_error, common::NOT_FOUND, common::OKAY, nodes::tree::prune(), static_class_name, and nodes::tree::which().
| symbol_tree * nodes::symbol_tree::find | ( | const istring & | to_find, | |
| find_methods | how = just_branches, |
|||
| 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.
Definition at line 128 of file symbol_tree.cpp.
References branch(), nodes::tree::branches(), find(), FUNCDEF, istring_comparator(), LOG, name(), NIL, nodes::tree::parent(), recurse_downward, and recurse_upward.
Referenced by find(), bookmark_tree::find_parent(), and bookmark_tree::process_category().
| 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().
| istring nodes::symbol_tree::text_form | ( | ) | const |
traverses the tree to build a textual list of the nodes.
Definition at line 183 of file symbol_tree.cpp.
References nodes::tree::branches(), nodes::tree::depth(), FUNCDEF, nodes::hier_prefix(), LOG, name(), nodes::tree::iterator::next(), log_base::platform_ending(), nodes::tree::prefix, istring::s(), nodes::path::size(), and nodes::tree::start().
1.5.1