symbol_tree.h

   1 #ifndef SYMBOL_TREE_CLASS
   2 #define SYMBOL_TREE_CLASS
   3
   4 /*****************************************************************************\
   5 *                                                                             *
   6 *  Name   : symbol_tree                                                       *
   7 *  Author : Chris Koeritz                                                     *
   8 *                                                                             *
   9 *******************************************************************************
  10 * Copyright (c) 1992-$now By Author.  This program is free software; you can  *
  11 * redistribute it and/or modify it under the terms of the GNU General Public  *
  12 * License as published by the Free Software Foundation; either version 2 of   *
  13 * the License or (at your option) any later version.  This is online at:      *
  14 *     http://www.fsf.org/copyleft/gpl.html                                    *
  15 * Please send any updates to: fred@gruntose.com                               *
  16 \*****************************************************************************/
  17
  18 #include "tree.h"
  19
  20 #include <basis/astring.h>
  21 #include <basis/definitions.h>
  22
  23 namespace nodes {
  24
  25 // forward.
  26 class symbol_tree_associations;
  27
  28 //! A symbol table that supports scope nesting and/or trees of symbol tables.
  29 /*!
  30   Note: although the symbol_tree is a tree, proper functioning is only
  31   guaranteed if you stick to its own add / find methods rather than calling
  32   on the base class's methods... but the tree's iterator support should be
  33   used for traversing the symbol_tree and prune should work as expected.
  34 */
  35
  36 class symbol_tree : public tree
  37 {
  38 public:
  39   symbol_tree(const basis::astring &node_name, int estimated_elements = 100);
  40     //!< creates a symbol_tree node with the "node_name".
  41     /*!< presumably this could be a child of another symbol tree also.  the "estimated_elements"
  42     is used to choose a size for the table holding the names.  */
  43
  44   virtual ~symbol_tree();
  45     //!< all child nodes will be deleted too.
  46     /*!< if the automatic child node deletion is not good for your purposes,
  47     be sure to unhook the children before deletion of the tree and manage them
  48     separately. */
  49
  50   DEFINE_CLASS_NAME("symbol_tree");
  51
  52   int children() const;  //!< returns the number of children of this node.
  53
  54   const basis::astring &name() const;  //!< returns the name of this node.
  55
  56   int estimated_elements() const;  //!< returns the number of bits in this node's table.
  57
  58   symbol_tree *branch(int index) const;  //!< returns the "index"th branch.
  59
  60   void rehash(int estimated_elements);
  61     //!< resizes the underlying symbol_table for this node.
  62
  63   void hash_appropriately(int estimated_elements);
  64     //!< resizes the hashing parameter to limit bucket sizes.
  65     /*!< rehashes the name table so that there will be no more (on average)
  66     than "max_per_bucket" items per hashing bucket.  this is the max that will
  67     need to be crossed to find an item, so reducing the number per bucket
  68     speeds access but also requires more memory. */
  69
  70   bool add(symbol_tree *to_add);
  71     //!< adds a child to this symbol_tree.
  72
  73   virtual basis::outcome prune(tree *to_zap);
  74     //!< removes a sub-tree "to_zap".
  75     /*!< the "to_zap" tree had better be a symbol_tree; we are just matching
  76     the lower-level virtual function prototype.  note that the tree node
  77     "to_zap" is not destroyed; it is just plucked from the tree. */
  78
  79   enum find_methods { just_branches, recurse_downward, recurse_upward };
  80
  81   symbol_tree *find(const basis::astring &to_find,
  82           find_methods how,
  83 ///= just_branches,
  84           basis::string_comparator_function *comp = NIL);
  85     //!< returns the node specified by "to_find" or NIL.
  86     /*!< this should be fairly quick due to the symbol table's hashing.
  87     the "how" method specifies the type of recursion to be used in searching
  88     if any.  if "how" is passed as "just_branches", then only the branches are
  89     checked and no recursion upwards or downwards is performed.  if "how" is
  90     "recurse_downward", then all sub-trees under the branches are checked
  91     also.  if "how" is given as "recurse_upward", then "this" node and parent
  92     nodes are checked.  the "comp" parameter will be used for comparing the
  93     strings if it's passed as non-NIL. */
  94
  95   void sort();
  96     //!< sorts the sub-nodes of this symbol_tree.
  97
  98   basis::astring text_form() const;
  99     //!< traverses the tree to build a textual list of the nodes.
 100
 101 private:
 102   symbol_tree_associations *_associations;  //!< the link from names to nodes.
 103   basis::astring *_name;  //!< the name of this symbol tree node.
 104 };
 105
 106 } // namespace.
 107
 108 #endif
 109