Merge branch 'main' of feistymeow.org:feisty_meow
[feisty_meow.git] / 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     /*!< NULL_POINTER 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 NULL_POINTER 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, NULL_POINTER 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 NULL_POINTER.  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 NULL_POINTER. */
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