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