core/library/nodes/tree.h

   1 #ifndef TREE_CLASS
   2 #define TREE_CLASS
   3
   4 /*****************************************************************************\
   5 *                                                                             *
   6 *  Name   : 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 "node.h"
  19 #include "path.h"
  20
  21 #include <basis/enhance_cpp.h>
  22
  23 namespace nodes {
  24
  25 //! A dynamically linked tree with an arbitrary number of branches.
  26 /*!
  27   A tree is defined as a node with n branch nodes, where n is dynamic.
  28   Each branch is also a tree.  Branch numbers range from 0 through n-1 in
  29   the methods below.  Trees can be self-cleaning, meaning that the tree
  30   will destroy all of its children when it is destroyed.
  31
  32   NOTE: the node indices are not numbered completely obviously; it is better
  33   to use the tree functions for manipulating the node rather than
  34   muddling with it directly.  the branch to the tree node's parent is
  35   stored as node zero, in actuality, rather than node zero being the
  36   first branch.
  37 */
  38
  39 class tree : public node
  40 {
  41 public:
  42   tree();
  43     //!< constructs a new tree with a root and zero branches.
  44
  45   virtual ~tree();
  46     //!< destroys the tree by recursively destroying all child tree nodes.
  47
  48   DEFINE_CLASS_NAME("tree");
  49
  50   virtual tree *branch(int branch_number) const;
  51     //!< Returns the specified branch of this tree.
  52     /*!< NIL is returned if the "branch_number" refers to a branch that
  53     does not exist. */
  54
  55   virtual int which(tree *branch_to_find) const;
  56     //!< Returns the branch number for a particular branch in this tree.
  57     /*!< common::NOT_FOUND if the branch is not one of the child nodes. */
  58
  59   virtual int branches() const;
  60     //!< Returns the number of branches currently connected to this tree.
  61
  62   virtual tree *parent() const;
  63     //!< Returns the tree node that is the immediate ancestor of this one.
  64     /*!< if this is the root node, then NIL is returned. */
  65
  66   virtual tree *root() const;
  67     //!< Locates and returns the absolute root of the tree containing this tree.
  68     /*!< If this tree IS the absolute root, then "this" is returned. */
  69
  70   virtual int depth() const;
  71     //!< Returns the distance of "this" from the root.  The root's depth is 0.
  72
  73   virtual void attach(tree *new_branch);
  74     //!< Attaches the specified branch to the current tree.
  75
  76   virtual void insert(int branch_place, tree *new_branch);
  77     //!< inserts "new_branch" before the branches starting at "branch_place".
  78     /*!< Places a branch at a particular index and pushes the branches at that
  79     index (and after it) over by one branch. */
  80
  81   virtual basis::outcome prune(tree *branch_to_cut);
  82     //!< Removes the specified branch from this tree.
  83     /*!< note that the pruning does not affect the branch being removed; it
  84     just detaches that branch from the tree.  if one wants to get rid of the
  85     branch, it should be deleted.  if this cannot find the tree specified in
  86     the available branches then the branches of this tree are not touched and
  87     common::NOT_FOUND is returned. */
  88   virtual basis::outcome prune_index(int branch_to_cut);
  89     //!< Removes the branch at the specified index from this tree.
  90     /*!< if this is given an invalid branch number, then the available
  91     branches then the branches of this tree are not touched and
  92     common::NOT_FOUND is returned. */
  93
  94   enum traversal_directions { prefix, infix, postfix, to_branches,
  95           reverse_branches };
  96     //!< these are the different kinds of tree traversal that are supported.
  97     /*!< "prefix" means that tree nodes will be visited as soon as they are
  98     seen; the deepest nodes have to wait the longest to be seen by the
  99     traversal.  "postfix" means that tree nodes are not visited until all of
 100     their ancestors have been visited; the nodes nearer the start of traversal
 101     will wait the longest to be visited.  the "infix" direction visits
 102     the left branch, then the starting node, then the right branch.
 103     "infix" is only valid for binary or unary trees; it is an error to
 104     apply "infix" to a tree containing a node that has more than 2 branches.
 105     the direction "to_branches" visits each of the branches in the order
 106     defined by the branch() method.  "to_branches" does not visit this
 107     tree's node.  "reverse_branches" operates in the opposite direction
 108     of traversal from "to_branches".  "reverse_branches" also does not
 109     visit this node.  "reverse_branches" can be used to prune off subtrees
 110     during iteration without changing the ordering of the branches; this
 111     is valuable because a pruning operation applied in "to_branches" order
 112     would keep reducing the index of the branches. */
 113
 114   enum elevator_directions { TOWARD_ROOT, AWAY_FROM_ROOT };
 115     //!< movement in the tree is either towards or away from the root.
 116     /*!< distinguishes between motion towards the root node of the tree and
 117     motion away from the root (towards one's children). */
 118
 119   class iterator : public path
 120   {
 121   public:
 122     iterator(const tree *initial, traversal_directions direction);
 123     ~iterator();
 124
 125     tree *next();
 126       //!< Returns a pointer to the next tree in the direction of traversal.
 127       /*!< If the traversal is finished, NIL is returned. */
 128
 129     void whack(tree *to_whack);
 130       //!< destroys the tree "to_whack".
 131       /*!< whacks the node "to_whack" by patching this iterator so that future
 132       iterations will be correct.  it is required that the "to_whack" node
 133       was just returned from a call to next().
 134       NOTE: this has only been tested with postfix so far. */
 135
 136     traversal_directions _order;
 137     elevator_directions _aim;
 138
 139   private:
 140     bool next_node(tree *&to_return);
 141       //!< sets "to_return" to the next tree in the direction of tree traversal.
 142       /*!< if the next node could not be found in one invocation of next_node,
 143       then "to_return" is set to NIL.  the function returns a boolean which
 144       is true only if the iteration process can be continued by another call
 145       to next_node.  if the function returns false, the iteration is
 146       complete and "to_return" will always be NIL. */
 147   };
 148
 149   iterator start(traversal_directions direction) const;
 150     //!< Returns a fresh iterator positioned at this tree node.
 151
 152   virtual bool generate_path(path &to_follow) const;
 153     //!< Returns the path to "this" path_tree from its root.
 154
 155 private:
 156   // unavailable.
 157   tree(const tree &);
 158   tree &operator =(const tree &);
 159 };
 160
 161 } // namespace.
 162
 163 #endif
 164