a087b0b74edaeb032771f1b725eb80d3a4e000bb
[feisty_meow.git] / tree.cpp
1 /*****************************************************************************\
2 *                                                                             *
3 *  Name   : 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 "tree.h"
16
17 #include <basis/common_outcomes.h>
18 #include <basis/functions.h>
19 #include <basis/guards.h>
20
21 //#define DEBUG_TREE
22   // uncomment if you want lots of debugging info.
23
24 #undef LOG
25 #define LOG(s) CLASS_EMERGENCY_LOG(program_wide_logger::get(), s)
26
27 using namespace basis;
28
29 namespace nodes {
30
31 const int BACKWARDS_BRANCH = 0;
32   // BACKWARDS_BRANCH is the branch from this tree to its parent.  this is
33   // steeped in the perspective that the root is the backwards direction (where
34   // we came from, in a sense) and that the children of this node are the
35   // forwards direction.
36
37 //////////////
38
39 // iterator methods:
40
41 tree::iterator::iterator(const tree *initial, traversal_directions direction)
42 : path(initial), _order(direction), _aim(AWAY_FROM_ROOT)
43 {
44 }
45
46 tree::iterator::~iterator() { while (size()) pop(); }
47
48 bool tree::iterator::next_node(tree *&to_return)
49 {
50 #ifdef DEBUG_TREE
51   FUNCDEF("next_node");
52 #endif
53   to_return = NIL;
54 #ifdef DEBUG_TREE
55   if ( (_order != to_branches)
56       && (_order != reverse_branches) ) {
57     if (_aim == AWAY_FROM_ROOT) LOG("going down")
58     else LOG("going up");
59   }
60 #endif
61   switch (_order) {
62     case prefix: {
63       if (_aim == AWAY_FROM_ROOT) {
64         // going down means this is the first time we have seen the current top
65         // node on the stack.
66         to_return = (tree *)(*this)[size() - 1];
67 #ifdef DEBUG_TREE
68 //        LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s());
69         if (to_return->branches()) LOG("pushing 0")
70         else LOG("switching direction");
71 #endif
72         if (to_return->branches())
73           push(to_return->branch(0));
74         else
75           _aim = TOWARD_ROOT;
76       } else {
77         // going up means that we need to get rid of some things before we
78         // start seeing new nodes again.
79         if (size() == 1) return false;
80           // the last node has been seen....
81         tree *last = (tree *)pop();
82         tree *current_tree = (tree *)current();
83         int lastnum = current_tree->which(last);
84 #ifdef DEBUG_TREE
85         if (lastnum < current_tree->branches() - 1)
86           LOG(a_sprintf("going down %d", lastnum+1))
87         else LOG("still going up");
88 #endif
89         if (lastnum < current_tree->branches() - 1) {
90           _aim = AWAY_FROM_ROOT;
91           push(current_tree->branch(lastnum + 1));
92         }  // else still going up.
93       }
94       break;
95     }
96     case infix: {
97       if (_aim == AWAY_FROM_ROOT) {
98         // going down means starting on the left branch.
99         tree *temp = (tree *)current();
100 #ifdef DEBUG_TREE
101         if (temp->branches()) LOG("pushing 0")
102         else LOG("switching direction");
103 #endif
104         if (temp->branches()) push(temp->branch(0));
105         else {
106           _aim = TOWARD_ROOT;
107           to_return = (tree *)current();
108 #ifdef DEBUG_TREE
109 //          LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s()));
110 #endif
111         }
112       } else {
113         // going up means that the left branch is done and we need to either
114         // keep going up or go down the right branch.
115         if (size() == 1) return false;
116           // the last node has been seen....
117         tree *last = (tree *)pop();
118         tree *current_tree = (tree *)current();
119         int lastnum = current_tree->which(last);
120 #ifdef DEBUG_TREE
121         if (lastnum < 1) LOG(a_sprintf("going down %d", lastnum+1))
122         else LOG("still going up");
123 #endif
124         if (lastnum < 1) {
125           _aim = AWAY_FROM_ROOT;
126           to_return = (tree *)current();
127 #ifdef DEBUG_TREE
128 ///          LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s()));
129 #endif
130           push(current_tree->branch(lastnum + 1));
131         }  // else still going up.
132       }
133       break;
134     }
135     case to_branches: {
136       if (_aim == TOWARD_ROOT) return false;
137       else {
138         if (size() == 1) {
139           tree *temp = (tree *)current();
140           if (!temp->branches())
141             _aim = TOWARD_ROOT;
142           else
143             push(temp->branch(0));
144         } else {
145           tree *last = (tree *)pop();
146           tree *curr = (tree *)current();
147           int lastnum = curr->which(last);
148           if (lastnum < curr->branches() - 1)
149             push(curr->branch(lastnum + 1));
150           else _aim = TOWARD_ROOT;
151           to_return = last;
152         }
153       }
154       break;
155     }
156     case reverse_branches: {
157       if (_aim == TOWARD_ROOT) return false;
158       else {
159         if (size() == 1) {
160           tree *temp = (tree *)current();
161           if (!temp->branches()) _aim = TOWARD_ROOT;
162           else push(temp->branch(temp->branches() - 1));
163         } else {
164           tree *last = (tree *)pop();
165           tree *curr = (tree *)current();
166           int lastnum = curr->which(last);
167           if (lastnum > 0) push(curr->branch(lastnum - 1));
168           else _aim = TOWARD_ROOT;
169           to_return = last;
170         }
171       }
172       break;
173     }
174     default:   // intentional fall-through to postfix.
175     case postfix: {
176       if (_aim == AWAY_FROM_ROOT) {
177         // going down means that the bottom is still being sought.
178         tree *temp = (tree *)current();
179 #ifdef DEBUG_TREE
180         if (temp->branches()) LOG("pushing 0")
181         else LOG("switching direction");
182 #endif
183         if (temp->branches()) push(temp->branch(0));
184         else _aim = TOWARD_ROOT;
185       } else {
186         // going up means that all nodes below current have been hit.
187         if (!size()) return false;  // the last node has been seen...
188         else if (size() == 1) {
189           to_return = (tree *)pop();
190             // this is the last node.
191           return true;
192         }
193         tree *last = (tree *)pop();
194         to_return = last;
195 #ifdef DEBUG_TREE
196 ///        LOG(a_sprintf("[%s] ", to_return->get_contents()->held()));
197 #endif
198         tree *current_tree = (tree *)current();
199         int lastnum = current_tree->which(last);
200 #ifdef DEBUG_TREE
201         if (lastnum < current_tree->branches() - 1)
202           LOG(a_sprintf("going down %d", lastnum+1))
203         else LOG("still going up");
204 #endif
205         if (lastnum < current_tree->branches() - 1) {
206           _aim = AWAY_FROM_ROOT;
207           push(current_tree->branch(lastnum + 1));
208         }  // else still going up.
209       }
210       break;
211     }
212   }
213   return true;
214     // it is assumed that termination conditions cause a return earlier on.
215 }
216
217 void tree::iterator::whack(tree *to_whack)
218 {
219 #ifdef DEBUG_TREE
220   FUNCDEF("whack");
221 #endif
222   if (!to_whack) return;  // that's a bad goof.
223   if (size()) {
224     if (to_whack == current()) {
225       // we found that this is the one at the top right now.
226       pop();
227 #ifdef DEBUG_TREE
228       LOG("found node in current top; removing it there.");
229 #endif
230     } else if (to_whack->parent() == current()) {
231       // the parent is the current top.  make sure we don't mess up traversal.
232 #ifdef DEBUG_TREE
233       LOG("found node's parent as current top; don't know what to do.");
234 #endif
235     } else {
236 #ifdef DEBUG_TREE
237       LOG("found no match for either node to remove or parent in path.");
238 #endif
239     }
240   }
241   tree *parent = to_whack->parent();
242   if (!parent) {
243 #ifdef DEBUG_TREE
244     LOG("no parent node for the one to whack!  would have whacked "
245         "root of tree!");
246 #endif
247   } else {
248     parent->prune(to_whack);
249     WHACK(to_whack);
250   }
251 }
252
253 tree *tree::iterator::next()
254 {
255 #ifdef DEBUG_TREE
256   FUNCDEF("next");
257 #endif
258   tree *to_return = NIL;
259   bool found_tree = false;
260   while (!found_tree) {
261     bool still_running = next_node(to_return);
262     if (to_return || !still_running) found_tree = true;
263   }
264   return to_return;
265 }
266
267 //////////////
268
269 // tree methods:
270
271 tree::tree()
272 : node(1)
273 { set_link(BACKWARDS_BRANCH, NIL); }
274
275 tree::~tree()
276 {
277   // must at least unhook ourselves from the parent so we don't become a lost
278   // cousin.
279   tree *my_parent = parent();
280   if (my_parent) my_parent->prune(this);
281
282   // iterate over the child nodes and whack each individually.
283   while (branches()) delete branch(0);
284     // this relies on the child getting out of our branch list.
285 }
286
287 tree *tree::parent() const { return (tree *)get_link(BACKWARDS_BRANCH); }
288
289 int tree::branches() const { return links() - 1; }
290
291 tree *tree::branch(int branch_number) const
292 {
293   branch_number++;
294   bounds_return(branch_number, 1, branches(), NIL);
295   return (tree *)get_link(branch_number);
296 }
297
298 int tree::which(tree *branch_to_find) const
299 { return node::which((node *)branch_to_find) - 1; }
300
301 tree *tree::root() const
302 {
303   const tree *traveler = this;
304   // keep looking at the backwards branch until it is a NIL.  the tree with
305   // a NIL BACKWARDS_BRANCH is the root.  return that tree.
306   while (traveler->get_link(BACKWARDS_BRANCH))
307     traveler = (tree *)traveler->get_link(BACKWARDS_BRANCH);
308   return const_cast<tree *>(traveler);
309 }
310
311 void tree::attach(tree *new_branch)
312 {
313   if (!new_branch) return;
314   insert_link(links(), new_branch);
315   new_branch->set_link(BACKWARDS_BRANCH, this);
316 }
317
318 void tree::insert(int branch_place, tree *new_branch)
319 {
320   branch_place++;
321   insert_link(links(), NIL);
322   if (branch_place >= links())
323     branch_place = links() - 1;
324   for (int i = links() - 1; i > branch_place; i--)
325     set_link(i, get_link(i-1));
326   set_link(branch_place, new_branch);
327   new_branch->set_link(BACKWARDS_BRANCH, this);
328 }
329
330 outcome tree::prune(tree *branch_to_cut)
331 {
332   int branch_number = which(branch_to_cut);
333   if (branch_number == basis::common::NOT_FOUND) return basis::common::NOT_FOUND;
334   return prune_index(branch_number);
335 }
336
337 outcome tree::prune_index(int branch_to_cut)
338 {
339   branch_to_cut++;
340   bounds_return(branch_to_cut, 1, branches(), basis::common::NOT_FOUND);
341   tree *that_branch = (tree *)get_link(branch_to_cut);
342   that_branch->set_link(BACKWARDS_BRANCH, NIL);
343   zap_link(branch_to_cut);
344   return basis::common::OKAY;
345 }
346
347 int tree::depth() const
348 {
349   tree *my_root = root();
350   const tree *current_branch = this;
351   int deep = 0;
352   while (current_branch != my_root) {
353     current_branch = current_branch->parent();
354     deep++;
355   }
356   return deep;
357 }
358
359 //probably okay; we want to use this function rather than non-existent
360 //node base function which isn't implemented yet.
361 bool tree::generate_path(path &to_follow) const
362 {
363 if (to_follow.size()) {} 
364 /*
365   tree *traveller = this;
366   path to_accumulate(root());
367   while (traveller->parent() != NIL) {
368 //    int branch_number = traveller->parent()->which(traveller);
369 //    if (branch_number == BRANCH_NOT_FOUND) non_continuable_error
370 //      (class_name(), "generate_path", "branch not found during path construction");
371 //    chunk *to_stuff = new chunk
372 //      (SELF_OWNED, (byte *)&branch_number, sizeof(int));
373     to_accumulate.push(traveller);
374     traveller = traveller->parent();
375   }
376   // the order of things on the stack needs to be reversed now.
377 //  path to_return = new stack(*to_accumulate.invert());
378 //  return to_return;
379   to_accumulate.invert();
380   return to_accumulate;
381 */
382 return false;//temp.
383 }
384
385 //hmmm: need text form!
386
387 tree::iterator tree::start(traversal_directions direction) const
388 { return iterator(this, direction); }
389
390 }  // namespace.
391