symbol_tree.cpp

Go to the documentation of this file.

/*****************************************************************************\
*                                                                             *
*  Name   : symbol_tree                                                       *
*  Author : Chris Koeritz                                                     *
*                                                                             *
*******************************************************************************
* Copyright (c) 1992-$now By Author.  This program is free software; you can  *
* redistribute it and/or modify it under the terms of the GNU General Public  *
* License as published by the Free Software Foundation; either version 2 of   *
* the License or (at your option) any later version.  This is online at:      *
*     http://www.fsf.org/copyleft/gpl.html                                    *
* Please send any updates to: fred@gruntose.com                               *
\*****************************************************************************/
 
#include "symbol_tree.h"
 
#include <basis/functions.h>
#include <structures/symbol_table.h>
#include <textual/parser_bits.h>
#include <textual/string_manipulation.h>
 
//#define DEBUG_SYMBOL_TREE
  // uncomment for totally noisy version.
 
#include <loggers/program_wide_logger.h>
#undef LOG
#define LOG(s) CLASS_EMERGENCY_LOG(program_wide_logger::get(), astring(s) + a_sprintf(" [obj=%p]", this))
using namespace loggers;
 
using namespace basis;
using namespace structures;
using namespace textual;
 
namespace nodes {
 
//hmmm: used for... explain please.
class symbol_tree_associations : public symbol_table<symbol_tree *>
{
public:
  symbol_tree_associations(int estimated_elements)
      :  symbol_table<symbol_tree *>(estimated_elements) {}
  virtual ~symbol_tree_associations() {
//probably we don't actually want to whack here???
//    for (int i = 0; i < symbols(); i++) {
//      WHACK(use(i));
//    }
  }
};
 
 
symbol_tree::symbol_tree(const astring &node_name, int estimated_elements)
: tree(),
  _associations(new symbol_tree_associations(estimated_elements)),
  _name(new astring(node_name))
{
  FUNCDEF("constructor")
}
 
symbol_tree::~symbol_tree()
{
  FUNCDEF("destructor");
#ifdef DEBUG_SYMBOL_TREE
  LOG("symtree dtor: prior to whacks");
#endif
  WHACK(_associations);
#ifdef DEBUG_SYMBOL_TREE
  LOG("symtree dtor: after whacking associations");
#endif
  WHACK(_name);
#ifdef DEBUG_SYMBOL_TREE
  LOG("symtree dtor: after all whacks");
#endif
}
 
int symbol_tree::children() const { return _associations->symbols(); }
 
const astring &symbol_tree::name() const { return *_name; }
 
int symbol_tree::estimated_elements() const { return _associations->estimated_elements(); }
 
void symbol_tree::rehash(int estimated_elements) { _associations->rehash(estimated_elements); }
 
void symbol_tree::hash_appropriately(int estimated_elements)
{ _associations->hash_appropriately(estimated_elements); }
 
bool symbol_tree::add(symbol_tree *to_add)
{
#ifdef DEBUG_SYMBOL_TREE
  FUNCDEF("add");
  LOG(astring("adding node for ") + to_add->name());
#endif
  attach(to_add);  // add to tree.
  _associations->add(to_add->name(), to_add);  // add to associations.
  return true;
}
 
outcome symbol_tree::prune(tree *to_zap_in)
{
#ifdef DEBUG_SYMBOL_TREE
  FUNCDEF("prune");
#endif
  symbol_tree *to_zap = dynamic_cast<symbol_tree *>(to_zap_in);
  if (to_zap) {
#ifdef DEBUG_SYMBOL_TREE
    LOG(astring("zapping node for ") + to_zap->name());
#endif
    int found = which(to_zap);  // find the node in the tree.
    if (negative(found)) return common::NOT_FOUND;  // not found.
#ifdef DEBUG_SYMBOL_TREE
    int kids = _associations->symbols();
#endif
    _associations->whack(to_zap->name());  // remove from associations.
#ifdef DEBUG_SYMBOL_TREE
    if (kids - 1 != _associations->symbols())
      throw("error: symbol_tree::prune: failed to crop kid in symtab");
#endif
  } else { 
#ifdef DEBUG_SYMBOL_TREE
    LOG("skip symtree prune steps due to null symtree after dynamic cast.");
#endif
  }
#ifdef DEBUG_SYMBOL_TREE
  LOG("about to call base tree::prune...");
#endif
  tree::prune(to_zap);  // remove from tree.
#ifdef DEBUG_SYMBOL_TREE
  LOG("after called base tree::prune.");
#endif
  return common::OKAY;
}
 
symbol_tree *symbol_tree::branch(int index) const
{ return dynamic_cast<symbol_tree *>(tree::branch(index)); }
 
// implementation snagged from basis/shell_sort.
void symbol_tree::sort()
{
  int n = branches();
  symbol_tree *temp;
  int gap, i, j;
  for (gap = n / 2; gap > 0; gap /= 2) {
    for (i = gap; i < n; i++) {
      for (j = i - gap; j >= 0 && branch(j)->name() > branch(j + gap)->name();
          j = j - gap) {
        // swap the elements that are disordered.
        temp = branch(j + gap);
        prune_index(j + gap);
        insert(j, temp);
        temp = branch(j + 1);
        prune_index(j + 1);
        insert(j + gap, temp);
      }
    }
  }
}
 
symbol_tree *symbol_tree::find(const astring &to_find, find_methods how,
    string_comparator_function *comp)
{
#ifdef DEBUG_SYMBOL_TREE
  FUNCDEF("find");
#endif
  if (comp == NULL_POINTER) comp = astring_comparator;
#ifdef DEBUG_SYMBOL_TREE
  LOG(astring("finding node called ") + to_find);
#endif
  // ensure that we compare the current node.
  if (comp(name(), to_find)) return this;
 
  // perform the upward recursion first, since it's pretty simple.
  if (how == recurse_upward) {
    symbol_tree *our_parent = dynamic_cast<symbol_tree *>(parent());
    if (!our_parent) return NULL_POINTER;  // done recursing.
    return our_parent->find(to_find, how, comp);
  }
 
  // see if our branches match the search term.
  symbol_tree **found = _associations->find(to_find, comp);
#ifdef DEBUG_SYMBOL_TREE
  if (!found) LOG(to_find + " was not found.")
  else LOG(to_find + " was found successfully.");
#endif
  if (!found) {
    if (how == recurse_downward) {
      // see if we can't find that name in a sub-node.
      symbol_tree *answer = NULL_POINTER;
      for (int i = 0; i < branches(); i++) {
        // we will try each branch in turn and see if it has a child named
        // appropriately.
        symbol_tree *curr = dynamic_cast<symbol_tree *>(branch(i));
#ifdef DEBUG_SYMBOL_TREE
        LOG(astring("recursing to ") + curr->name());
#endif
        if (curr)
          answer = curr->find(to_find, how, comp);
        if (answer)
          return answer;
      }
    }
    return NULL_POINTER;
  }
  return *found;
}
 
//hmmm: is this useful elsewhere?
astring hier_prefix(int depth, int kids)
{
  astring indent = string_manipulation::indentation( (depth - 1) * 2);
  if (!depth) return "";
  else if (!kids) return indent + "|--";
  else return indent + "+--";
}
 
astring symbol_tree::text_form() const
{
#ifdef DEBUG_SYMBOL_TREE
  FUNCDEF("text_form");
#endif
  astring to_return;
 
  tree::iterator ted = start(prefix);
    // create our iterator to do a prefix traversal.
 
  tree *curr = (tree *)ted.next();
 
//hmmm: this cast assumes that the tree only contains trees.  for more
//      safety, we might want a dynamic cast here also.
  while (curr) {
    // we have a good directory to show.
    symbol_tree *curr_cast = dynamic_cast<symbol_tree *>(curr);
    if (!curr_cast) {
      // something very bad with that...
#ifdef DEBUG_SYMBOL_TREE
      LOG("logic error: unknown type in symbol tree.");
#endif
      ted.next();
      continue;
    }
    astring name_to_log = curr_cast->name();
    if (!ted.size()) name_to_log = "";
#ifdef DEBUG_SYMBOL_TREE
    LOG(a_sprintf("depth %d kids %d name %s", ted.size(), curr_cast->branches(),
        name_to_log.s()));
#endif
    to_return += hier_prefix(curr->depth(), curr_cast->branches());
    to_return += name_to_log;
    to_return += parser_bits::platform_eol_to_chars();
 
    curr = (tree *)ted.next();
  }
 
  return to_return;
}
 
} // namespace.