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