1 /*****************************************************************************\
4 * Author : Chris Koeritz *
6 *******************************************************************************
7 * Copyright (c) 1992-$now By Author. This program is free software; you can *
8 * redistribute it and/or modify it under the terms of the GNU General Public *
9 * License as published by the Free Software Foundation; either version 2 of *
10 * the License or (at your option) any later version. This is online at: *
11 * http://www.fsf.org/copyleft/gpl.html *
12 * Please send any updates to: fred@gruntose.com *
13 \*****************************************************************************/
15 #include "symbol_tree.h"
17 #include <basis/functions.h>
18 #include <structures/symbol_table.h>
19 #include <textual/parser_bits.h>
20 #include <textual/string_manipulation.h>
22 #define DEBUG_SYMBOL_TREE
23 // uncomment for totally noisy version.
25 #include <loggers/program_wide_logger.h>
27 #define LOG(s) CLASS_EMERGENCY_LOG(program_wide_logger::get(), astring(s) + a_sprintf(" [obj=%p]", this))
28 using namespace loggers;
30 using namespace basis;
31 using namespace structures;
32 using namespace textual;
36 //hmmm: used for... explain please.
37 class symbol_tree_associations : public symbol_table<symbol_tree *>
40 symbol_tree_associations(int estimated_elements)
41 : symbol_table<symbol_tree *>(estimated_elements) {}
42 virtual ~symbol_tree_associations() {
44 //hmmm: below was really wrong and things are still wrong because we're letting the symtab destruct our trees?
45 // real thing would be to just toss any pointers referenced in the sym tab here.
46 // OR... not at all because sym tab stores objects, and expects objects, and since a pointer isn't an object it will not auto-delete?
49 //hmmm: why was this here? was it ever needed?
50 //hmmm: maybe it's the missing link?
52 //probably we don't actually want to whack here???
53 // for (int i = 0; i < symbols(); i++) {
61 symbol_tree::symbol_tree(const astring &node_name, int estimated_elements)
63 _associations(new symbol_tree_associations(estimated_elements)),
64 _name(new astring(node_name))
68 symbol_tree::~symbol_tree()
70 FUNCDEF("destructor");
71 LOG("symtree dtor: prior to whacks");
73 LOG("symtree dtor: after whacking associations");
75 LOG("symtree dtor: after all whacks");
78 int symbol_tree::children() const { return _associations->symbols(); }
80 const astring &symbol_tree::name() const { return *_name; }
82 int symbol_tree::estimated_elements() const { return _associations->estimated_elements(); }
84 void symbol_tree::rehash(int estimated_elements) { _associations->rehash(estimated_elements); }
86 void symbol_tree::hash_appropriately(int estimated_elements)
87 { _associations->hash_appropriately(estimated_elements); }
89 bool symbol_tree::add(symbol_tree *to_add)
91 #ifdef DEBUG_SYMBOL_TREE
93 LOG(astring("adding node for ") + to_add->name());
95 attach(to_add); // add to tree.
96 _associations->add(to_add->name(), to_add); // add to associations.
100 outcome symbol_tree::prune(tree *to_zap_in)
102 #ifdef DEBUG_SYMBOL_TREE
105 symbol_tree *to_zap = dynamic_cast<symbol_tree *>(to_zap_in);
107 #ifdef DEBUG_SYMBOL_TREE
108 LOG("about to barf due to null symtree after dynamic cast.");
110 throw("error: symbol_tree::prune: wrong type of node in prune");
112 #ifdef DEBUG_SYMBOL_TREE
113 LOG(astring("zapping node for ") + to_zap->name());
115 int found = which(to_zap); // find the node in the tree.
116 if (negative(found)) return common::NOT_FOUND; // not found.
117 #ifdef DEBUG_SYMBOL_TREE
118 int kids = _associations->symbols();
120 _associations->whack(to_zap->name()); // remove from associations.
121 #ifdef DEBUG_SYMBOL_TREE
122 if (kids - 1 != _associations->symbols())
123 throw("error: symbol_tree::prune: failed to crop kid in symtab");
125 tree::prune(to_zap); // remove from tree.
129 symbol_tree *symbol_tree::branch(int index) const
130 { return dynamic_cast<symbol_tree *>(tree::branch(index)); }
132 // implementation snagged from basis/shell_sort.
133 void symbol_tree::sort()
138 for (gap = n / 2; gap > 0; gap /= 2) {
139 for (i = gap; i < n; i++) {
140 for (j = i - gap; j >= 0 && branch(j)->name() > branch(j + gap)->name();
142 // swap the elements that are disordered.
143 temp = branch(j + gap);
144 prune_index(j + gap);
146 temp = branch(j + 1);
148 insert(j + gap, temp);
154 symbol_tree *symbol_tree::find(const astring &to_find, find_methods how,
155 string_comparator_function *comp)
157 #ifdef DEBUG_SYMBOL_TREE
160 if (comp == NULL_POINTER) comp = astring_comparator;
161 #ifdef DEBUG_SYMBOL_TREE
162 LOG(astring("finding node called ") + to_find);
164 // ensure that we compare the current node.
165 if (comp(name(), to_find)) return this;
167 // perform the upward recursion first, since it's pretty simple.
168 if (how == recurse_upward) {
169 symbol_tree *our_parent = dynamic_cast<symbol_tree *>(parent());
170 if (!our_parent) return NULL_POINTER; // done recursing.
171 return our_parent->find(to_find, how, comp);
174 // see if our branches match the search term.
175 symbol_tree **found = _associations->find(to_find, comp);
176 #ifdef DEBUG_SYMBOL_TREE
177 if (!found) LOG(to_find + " was not found.")
178 else LOG(to_find + " was found successfully.");
181 if (how == recurse_downward) {
182 // see if we can't find that name in a sub-node.
183 symbol_tree *answer = NULL_POINTER;
184 for (int i = 0; i < branches(); i++) {
185 // we will try each branch in turn and see if it has a child named
187 symbol_tree *curr = dynamic_cast<symbol_tree *>(branch(i));
188 #ifdef DEBUG_SYMBOL_TREE
189 LOG(astring("recursing to ") + curr->name());
192 answer = curr->find(to_find, how, comp);
202 //hmmm: is this useful elsewhere?
203 astring hier_prefix(int depth, int kids)
205 astring indent = string_manipulation::indentation( (depth - 1) * 2);
206 if (!depth) return "";
207 else if (!kids) return indent + "|--";
208 else return indent + "+--";
211 astring symbol_tree::text_form() const
213 #ifdef DEBUG_SYMBOL_TREE
214 FUNCDEF("text_form");
218 tree::iterator ted = start(prefix);
219 // create our iterator to do a prefix traversal.
221 tree *curr = (tree *)ted.next();
223 //hmmm: this cast assumes that the tree only contains trees. for more
224 // safety, we might want a dynamic cast here also.
226 // we have a good directory to show.
227 symbol_tree *curr_cast = dynamic_cast<symbol_tree *>(curr);
229 // something very bad with that...
230 #ifdef DEBUG_SYMBOL_TREE
231 LOG("logic error: unknown type in symbol tree.");
236 astring name_to_log = curr_cast->name();
237 if (!ted.size()) name_to_log = "";
238 #ifdef DEBUG_SYMBOL_TREE
239 LOG(a_sprintf("depth %d kids %d name %s", ted.size(), curr_cast->branches(),
242 to_return += hier_prefix(curr->depth(), curr_cast->branches());
243 to_return += name_to_log;
244 to_return += parser_bits::platform_eol_to_chars();
246 curr = (tree *)ted.next();