recording grub mod for system 76 laptops
[feisty_meow.git] / nucleus / library / nodes / 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 = NULL_POINTER;
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 = NULL_POINTER;
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, NULL_POINTER); }
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   my_parent = NULL_POINTER;  // disavow since we are loose now.
282
283 #if 0
284
285   //original version suffers from being too recursive on windoze,
286   //which blows out the stack.  linux never showed this problem.  so, i
287   //guess i'm glad i tested on windows.
288   //anyway, it's a general problem for a degenerate tree like the one
289   //i've constructed.  current version has ~40000 direct descendants of
290   //the root in a single line, so the stack has to support 40000 frames
291   //for the delete implementation below to work.
292
293   // iterate over the child nodes and whack each individually.
294   while (branches()) delete branch(0);
295     // this relies on the child getting out of our branch list.
296 #else
297
298   // newer version of delete doesn't recurse; it just iterates instead,
299   // which avoids the massive recursive depth of the original approach.
300   tree *curr_node = this;
301   while (curr_node != NULL_POINTER) {
302     // make a breadcrumb for getting back to 'here' in the tree.
303     tree *way_back = curr_node;
304     // our main operation here is to go down a node without using any
305     // stack frames.  so we just pick the first kid; it's either valid
306     // or there are no kids at all.
307     curr_node = curr_node->branch(0);
308
309     if (curr_node = NULL_POINTER) {
310       // wayback has no children, so we can take action.
311
312       // if wayback is the same as "this", then we exit from iterations since
313       // we've cleaned all the kids out.
314       if (way_back == this) {
315         break;
316       }
317
318       // we want to whack the wayback node at this point, since it's a parent
319       // with no kids, i.e. a leaf.  we've guaranteed we're not going beyond
320       // our remit, since wayback is not the same node as the top level one
321       // in the destructor (as long as there are no cycles in the tree...).
322       curr_node = way_back->parent();  // go up in tree on next iteration.
323       delete way_back;  // whack a node, finally.
324
325     } else {
326       // okay, there's a node below here.  we will spider down to it.
327       continue;
328     }
329
330
331   }
332
333 #endif
334
335
336 }
337
338 tree *tree::parent() const { return (tree *)get_link(BACKWARDS_BRANCH); }
339
340 int tree::branches() const { return links() - 1; }
341
342 tree *tree::branch(int branch_number) const
343 {
344   branch_number++;
345   bounds_return(branch_number, 1, branches(), NULL_POINTER);
346   return (tree *)get_link(branch_number);
347 }
348
349 int tree::which(tree *branch_to_find) const
350 { return node::which((node *)branch_to_find) - 1; }
351
352 tree *tree::root() const
353 {
354   const tree *traveler = this;
355   // keep looking at the backwards branch until it is a NULL_POINTER.  the tree with
356   // a NULL_POINTER BACKWARDS_BRANCH is the root.  return that tree.
357   while (traveler->get_link(BACKWARDS_BRANCH))
358     traveler = (tree *)traveler->get_link(BACKWARDS_BRANCH);
359   return const_cast<tree *>(traveler);
360 }
361
362 void tree::attach(tree *new_branch)
363 {
364   if (!new_branch) return;
365   insert_link(links(), new_branch);
366   new_branch->set_link(BACKWARDS_BRANCH, this);
367 }
368
369 void tree::insert(int branch_place, tree *new_branch)
370 {
371   branch_place++;
372   insert_link(links(), NULL_POINTER);
373   if (branch_place >= links())
374     branch_place = links() - 1;
375   for (int i = links() - 1; i > branch_place; i--)
376     set_link(i, get_link(i-1));
377   set_link(branch_place, new_branch);
378   new_branch->set_link(BACKWARDS_BRANCH, this);
379 }
380
381 outcome tree::prune(tree *branch_to_cut)
382 {
383   int branch_number = which(branch_to_cut);
384   if (branch_number == basis::common::NOT_FOUND) return basis::common::NOT_FOUND;
385   return prune_index(branch_number);
386 }
387
388 outcome tree::prune_index(int branch_to_cut)
389 {
390   branch_to_cut++;
391   bounds_return(branch_to_cut, 1, branches(), basis::common::NOT_FOUND);
392   tree *that_branch = (tree *)get_link(branch_to_cut);
393   that_branch->set_link(BACKWARDS_BRANCH, NULL_POINTER);
394   zap_link(branch_to_cut);
395   return basis::common::OKAY;
396 }
397
398 int tree::depth() const
399 {
400   tree *my_root = root();
401   const tree *current_branch = this;
402   int deep = 0;
403   while (current_branch != my_root) {
404     current_branch = current_branch->parent();
405     deep++;
406   }
407   return deep;
408 }
409
410 //probably okay; we want to use this function rather than non-existent
411 //node base function which isn't implemented yet.
412 bool tree::generate_path(path &to_follow) const
413 {
414 if (to_follow.size()) {} 
415 /*
416   tree *traveller = this;
417   path to_accumulate(root());
418   while (traveller->parent() != NULL_POINTER) {
419 //    int branch_number = traveller->parent()->which(traveller);
420 //    if (branch_number == BRANCH_NOT_FOUND) non_continuable_error
421 //      (class_name(), "generate_path", "branch not found during path construction");
422 //    chunk *to_stuff = new chunk
423 //      (SELF_OWNED, (byte *)&branch_number, sizeof(int));
424     to_accumulate.push(traveller);
425     traveller = traveller->parent();
426   }
427   // the order of things on the stack needs to be reversed now.
428 //  path to_return = new stack(*to_accumulate.invert());
429 //  return to_return;
430   to_accumulate.invert();
431   return to_accumulate;
432 */
433 return false;//temp.
434 }
435
436 //hmmm: need text form!
437
438 tree::iterator tree::start(traversal_directions direction) const
439 { return iterator(this, direction); }
440
441 }  // namespace.
442