Merge branch 'release-2.140.101'
[feisty_meow.git] / nucleus / library / nodes / symbol_tree.cpp
1 /*****************************************************************************\
2 *                                                                             *
3 *  Name   : symbol_tree                                                       *
4 *  Author : Chris Koeritz                                                     *
5 *                                                                             *
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 \*****************************************************************************/
14
15 #include "symbol_tree.h"
16
17 #include <basis/functions.h>
18 #include <structures/symbol_table.h>
19 #include <textual/parser_bits.h>
20 #include <textual/string_manipulation.h>
21
22 //#define DEBUG_SYMBOL_TREE
23   // uncomment for totally noisy version.
24
25 #include <loggers/program_wide_logger.h>
26 #undef LOG
27 #define LOG(s) CLASS_EMERGENCY_LOG(program_wide_logger::get(), s)
28 using namespace loggers;
29
30 using namespace basis;
31 using namespace structures;
32 using namespace textual;
33
34 namespace nodes {
35
36 class symbol_tree_associations : public symbol_table<symbol_tree *>
37 {
38 public:
39   symbol_tree_associations(int estimated_elements)
40       :  symbol_table<symbol_tree *>(estimated_elements) {}
41   virtual ~symbol_tree_associations() {
42 //    for (int i = 0; i < symbols(); i++) {
43 //      WHACK(use(i));
44 //    }
45   }
46 };
47
48 //////////////
49
50 symbol_tree::symbol_tree(const astring &node_name, int estimated_elements)
51 : tree(),
52   _associations(new symbol_tree_associations(estimated_elements)),
53   _name(new astring(node_name))
54 {
55 }
56
57 symbol_tree::~symbol_tree()
58 {
59   FUNCDEF("destructor");
60 LOG("prior to whacks");
61   WHACK(_associations);
62   WHACK(_name);
63 LOG("after whacks");
64 }
65
66 int symbol_tree::children() const { return _associations->symbols(); }
67
68 const astring &symbol_tree::name() const { return *_name; }
69
70 int symbol_tree::estimated_elements() const { return _associations->estimated_elements(); }
71
72 void symbol_tree::rehash(int estimated_elements) { _associations->rehash(estimated_elements); }
73
74 void symbol_tree::hash_appropriately(int estimated_elements)
75 { _associations->hash_appropriately(estimated_elements); }
76
77 bool symbol_tree::add(symbol_tree *to_add)
78 {
79 #ifdef DEBUG_SYMBOL_TREE
80   FUNCDEF("add");
81   LOG(astring("adding node for ") + to_add->name());
82 #endif
83   attach(to_add);  // add to tree.
84   _associations->add(to_add->name(), to_add);  // add to associations.
85   return true;
86 }
87
88 outcome symbol_tree::prune(tree *to_zap_in)
89 {
90 #ifdef DEBUG_SYMBOL_TREE
91   FUNCDEF("prune");
92 #endif
93   symbol_tree *to_zap = dynamic_cast<symbol_tree *>(to_zap_in);
94   if (!to_zap)
95     throw("error: symbol_tree::prune: wrong type of node in prune");
96 #ifdef DEBUG_SYMBOL_TREE
97   LOG(astring("zapping node for ") + to_zap->name());
98 #endif
99   int found = which(to_zap);  // find the node in the tree.
100   if (negative(found)) return common::NOT_FOUND;  // not found.
101 #ifdef DEBUG_SYMBOL_TREE
102   int kids = _associations->symbols();
103 #endif
104   _associations->whack(to_zap->name());  // remove from associations.
105 #ifdef DEBUG_SYMBOL_TREE
106   if (kids - 1 != _associations->symbols())
107     throw("error: symbol_tree::prune: failed to crop kid in symtab");
108 #endif
109   tree::prune(to_zap);  // remove from tree.
110   return common::OKAY;
111 }
112
113 symbol_tree *symbol_tree::branch(int index) const
114 { return dynamic_cast<symbol_tree *>(tree::branch(index)); }
115
116 // implementation snagged from basis/shell_sort.
117 void symbol_tree::sort()
118 {
119   int n = branches();
120   symbol_tree *temp;
121   int gap, i, j;
122   for (gap = n / 2; gap > 0; gap /= 2) {
123     for (i = gap; i < n; i++) {
124       for (j = i - gap; j >= 0 && branch(j)->name() > branch(j + gap)->name();
125           j = j - gap) {
126         // swap the elements that are disordered.
127         temp = branch(j + gap);
128         prune_index(j + gap);
129         insert(j, temp);
130         temp = branch(j + 1);
131         prune_index(j + 1);
132         insert(j + gap, temp);
133       }
134     }
135   }
136 }
137
138 symbol_tree *symbol_tree::find(const astring &to_find, find_methods how,
139     string_comparator_function *comp)
140 {
141 #ifdef DEBUG_SYMBOL_TREE
142   FUNCDEF("find");
143 #endif
144   if (comp == NULL_POINTER) comp = astring_comparator;
145 #ifdef DEBUG_SYMBOL_TREE
146   LOG(astring("finding node called ") + to_find);
147 #endif
148   // ensure that we compare the current node.
149   if (comp(name(), to_find)) return this;
150
151   // perform the upward recursion first, since it's pretty simple.
152   if (how == recurse_upward) {
153     symbol_tree *our_parent = dynamic_cast<symbol_tree *>(parent());
154     if (!our_parent) return NULL_POINTER;  // done recursing.
155     return our_parent->find(to_find, how, comp);
156   }
157
158   // see if our branches match the search term.
159   symbol_tree **found = _associations->find(to_find, comp);
160 #ifdef DEBUG_SYMBOL_TREE
161   if (!found) LOG(to_find + " was not found.")
162   else LOG(to_find + " was found successfully.");
163 #endif
164   if (!found) {
165     if (how == recurse_downward) {
166       // see if we can't find that name in a sub-node.
167       symbol_tree *answer = NULL_POINTER;
168       for (int i = 0; i < branches(); i++) {
169         // we will try each branch in turn and see if it has a child named
170         // appropriately.
171         symbol_tree *curr = dynamic_cast<symbol_tree *>(branch(i));
172 #ifdef DEBUG_SYMBOL_TREE
173         LOG(astring("recursing to ") + curr->name());
174 #endif
175         if (curr)
176           answer = curr->find(to_find, how, comp);
177         if (answer)
178           return answer;
179       }
180     }
181     return NULL_POINTER;
182   }
183   return *found;
184 }
185
186 //hmmm: is this useful elsewhere?
187 astring hier_prefix(int depth, int kids)
188 {
189   astring indent = string_manipulation::indentation( (depth - 1) * 2);
190   if (!depth) return "";
191   else if (!kids) return indent + "|--";
192   else return indent + "+--";
193 }
194
195 astring symbol_tree::text_form() const
196 {
197 #ifdef DEBUG_SYMBOL_TREE
198   FUNCDEF("text_form");
199 #endif
200   astring to_return;
201
202   tree::iterator ted = start(prefix);
203     // create our iterator to do a prefix traversal.
204
205   tree *curr = (tree *)ted.next();
206
207 //hmmm: this cast assumes that the tree only contains trees.  for more
208 //      safety, we might want a dynamic cast here also.
209   while (curr) {
210     // we have a good directory to show.
211     symbol_tree *curr_cast = dynamic_cast<symbol_tree *>(curr);
212     if (!curr_cast) {
213       // something very bad with that...
214 #ifdef DEBUG_SYMBOL_TREE
215       LOG("logic error: unknown type in symbol tree.");
216 #endif
217       ted.next();
218       continue;
219     }
220     astring name_to_log = curr_cast->name();
221     if (!ted.size()) name_to_log = "";
222 #ifdef DEBUG_SYMBOL_TREE
223     LOG(a_sprintf("depth %d kids %d name %s", ted.size(), curr_cast->branches(),
224         name_to_log.s()));
225 #endif
226     to_return += hier_prefix(curr->depth(), curr_cast->branches());
227     to_return += name_to_log;
228     to_return += parser_bits::platform_eol_to_chars();
229
230     curr = (tree *)ted.next();
231   }
232
233   return to_return;
234 }
235
236 } // namespace.
237