1 /*****************************************************************************\
4 * Author : Chris Koeritz *
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 \*****************************************************************************/
17 #include <basis/common_outcomes.h>
18 #include <basis/functions.h>
19 #include <basis/guards.h>
20 #include <loggers/program_wide_logger.h>
21 #include <structures/stack.h>
24 // uncomment if you want lots of debugging info.
27 #define LOG(s) CLASS_EMERGENCY_LOG(program_wide_logger::get(), astring(s) + a_sprintf(" [obj=%p]", this))
29 using namespace basis;
30 using namespace loggers;
31 using namespace structures;
35 const int BACKWARDS_BRANCH = 0;
36 // BACKWARDS_BRANCH is the branch from this tree to its parent. this is
37 // steeped in the perspective that the root is the backwards direction (where
38 // we came from, in a sense) and that the children of this node are the
39 // forwards direction.
45 tree::iterator::iterator(const tree *initial, traversal_directions direction)
46 : path(initial), _order(direction), _aim(AWAY_FROM_ROOT)
50 tree::iterator::~iterator() { while (size()) pop(); }
52 bool tree::iterator::next_node(tree *&to_return)
57 to_return = NULL_POINTER;
59 if ( (_order != to_branches)
60 && (_order != reverse_branches) ) {
61 if (_aim == AWAY_FROM_ROOT) LOG("going down...")
62 else LOG("going up...");
67 if (_aim == AWAY_FROM_ROOT) {
68 // going down means this is the first time we have seen the current top
70 to_return = (tree *)(*this)[size() - 1];
72 // LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s());
73 if (to_return->branches()) LOG("pushing 0")
74 else LOG("switching direction");
76 if (to_return->branches())
77 push(to_return->branch(0));
81 // going up means that we need to get rid of some things before we
82 // start seeing new nodes again.
83 if (size() == 1) return false;
84 // the last node has been seen....
85 tree *last = (tree *)pop();
86 tree *current_tree = (tree *)current();
87 int lastnum = current_tree->which(last);
89 if (lastnum < current_tree->branches() - 1)
90 LOG(a_sprintf("going down %d", lastnum+1))
91 else LOG("still going up");
93 if (lastnum < current_tree->branches() - 1) {
94 _aim = AWAY_FROM_ROOT;
95 push(current_tree->branch(lastnum + 1));
96 } // else still going up.
101 if (_aim == AWAY_FROM_ROOT) {
102 // going down means starting on the left branch.
103 tree *temp = (tree *)current();
105 if (temp->branches()) LOG("pushing 0")
106 else LOG("switching direction");
108 if (temp->branches()) push(temp->branch(0));
111 to_return = (tree *)current();
113 // LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s()));
117 // going up means that the left branch is done and we need to either
118 // keep going up or go down the right branch.
119 if (size() == 1) return false;
120 // the last node has been seen....
121 tree *last = (tree *)pop();
122 tree *current_tree = (tree *)current();
123 int lastnum = current_tree->which(last);
125 if (lastnum < 1) LOG(a_sprintf("going down %d", lastnum+1))
126 else LOG("still going up");
129 _aim = AWAY_FROM_ROOT;
130 to_return = (tree *)current();
132 /// LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s()));
134 push(current_tree->branch(lastnum + 1));
135 } // else still going up.
140 if (_aim == TOWARD_ROOT) return false;
143 tree *temp = (tree *)current();
144 if (!temp->branches())
147 push(temp->branch(0));
149 tree *last = (tree *)pop();
150 tree *curr = (tree *)current();
151 int lastnum = curr->which(last);
152 if (lastnum < curr->branches() - 1)
153 push(curr->branch(lastnum + 1));
154 else _aim = TOWARD_ROOT;
160 case reverse_branches: {
161 if (_aim == TOWARD_ROOT) return false;
164 tree *temp = (tree *)current();
165 if (!temp->branches()) _aim = TOWARD_ROOT;
166 else push(temp->branch(temp->branches() - 1));
168 tree *last = (tree *)pop();
169 tree *curr = (tree *)current();
170 int lastnum = curr->which(last);
171 if (lastnum > 0) push(curr->branch(lastnum - 1));
172 else _aim = TOWARD_ROOT;
178 default: // intentional fall-through to postfix.
180 if (_aim == AWAY_FROM_ROOT) {
181 // going down means that the bottom is still being sought.
182 tree *temp = (tree *)current();
184 if (temp->branches()) LOG("pushing 0")
185 else LOG("switching direction");
187 if (temp->branches()) push(temp->branch(0));
188 else _aim = TOWARD_ROOT;
190 // going up means that all nodes below current have been hit.
191 if (!size()) return false; // the last node has been seen...
192 else if (size() == 1) {
193 to_return = (tree *)pop();
194 // this is the last node.
197 tree *last = (tree *)pop();
200 /// LOG(a_sprintf("[%s] ", to_return->get_contents()->held()));
202 tree *current_tree = (tree *)current();
203 int lastnum = current_tree->which(last);
205 if (lastnum < current_tree->branches() - 1)
206 LOG(a_sprintf("going down %d", lastnum+1))
207 else LOG("still going up");
209 if (lastnum < current_tree->branches() - 1) {
210 _aim = AWAY_FROM_ROOT;
211 push(current_tree->branch(lastnum + 1));
212 } // else still going up.
218 // it is assumed that termination conditions cause a return earlier on.
221 void tree::iterator::whack(tree *to_whack)
226 if (!to_whack) return; // that's a bad goof.
228 if (to_whack == current()) {
229 // we found that this is the one at the top right now.
232 LOG("found node in current top; removing it there.");
234 } else if (to_whack->parent() == current()) {
235 // the parent is the current top. make sure we don't mess up traversal.
237 LOG("found node's parent as current top; don't know what to do.");
241 LOG("found no match for either node to remove or parent in path.");
245 tree *parent = to_whack->parent();
248 LOG("no parent node for the one to whack! would have whacked "
252 parent->prune(to_whack);
257 tree *tree::iterator::next()
262 tree *to_return = NULL_POINTER;
263 bool found_tree = false;
264 while (!found_tree) {
265 bool still_running = next_node(to_return);
266 if (to_return || !still_running) found_tree = true;
277 { set_link(BACKWARDS_BRANCH, NULL_POINTER); }
281 FUNCDEF("destructor");
283 LOG("entry to tree destructor");
286 // must at least unhook ourselves from the parent so we don't become a lost
288 tree *my_parent = parent();
289 if (my_parent) my_parent->prune(this);
293 //hmmm: clean this code when it's been examined long enough. maybe already.
294 LOG("old code for tree destructor activating...");
296 //original version suffers from being too recursive on windoze,
297 //which blows out the stack. linux never showed this problem. so, i
298 //guess i'm glad i tested on windows.
299 //anyway, it's a general problem for a degenerate tree like the one
300 //i've constructed. current version has ~40000 direct descendants of
301 //the root in a single line, so the stack has to support 40000 frames
302 //for the delete implementation below to work.
304 // iterate over the child nodes and whack each individually.
305 while (branches()) delete branch(0);
306 // this relies on the child getting out of our branch list.
310 LOG("new code for tree destructor activating...");
312 //hmmm: this new code stinks on ice. keeps doing something awful, either double deleting or deleting wrong thing.
313 // why didn't we just use our own iterator to traverse the tree depth first and clean that way??
315 // newer version of delete doesn't recurse; it just iterates instead,
316 // which avoids the massive recursive depth of the original approach.
318 // we know we have a branch to work on, due to conditional above.
319 tree *stop_node = branch(0); // don't whack the node we're at until we're done with its kids.
320 tree *curr_node = stop_node;
321 while (curr_node != NULL_POINTER) {
322 // make a breadcrumb for getting back to 'here' in the tree.
323 tree *way_back = curr_node;
324 // our main operation here is to go down a node without using any
325 // stack frames. so we just pick the first kid; it's either valid
326 // or there are no kids at all.
327 curr_node = curr_node->branch(0);
329 if (curr_node == NULL_POINTER) {
330 // wayback has no children, so we can take action.
331 LOG("tree dtor: can take action on childless node...");
333 // if wayback is the same as stop_node, then we exit from iterations since
334 // we've cleaned all the kids out.
335 if (way_back == stop_node) {
336 LOG("tree dtor: stopping since at wayback node...");
337 // we can actually delete wayback here, because we are at the stopping point.
338 // and since a tree node whack removes it from its parent, we are clean one branch now.
340 LOG("tree dtor: whacked wayback before inner break.");
344 // we want to whack the wayback node at this point, since it's a parent
345 // with no kids, i.e. a leaf. we've guaranteed we're not going beyond
346 // our remit, since wayback is not the same node as the top level one
347 // in the destructor (as long as there are no cycles in the tree...).
348 curr_node = way_back->parent(); // go up in tree on next iteration.
350 LOG("tree dtor: reset currnode, about to whack wayback...");
352 if (curr_node == stop_node) {
353 LOG("tree dtor: seeing curr_node hits our stop_node!");
355 } else if (curr_node == stop_node->parent()) {
356 LOG("tree dtor: seeing curr_node ABOVE our stop_node!");
359 WHACK(way_back); // whack a node, finally.
361 LOG("tree dtor: after whacking wayback...");
363 // okay, there's a node below here. we will spider down to it.
364 LOG("tree dtor: spidering to node below...");
373 LOG("newest code for tree destructor (stack based) activating...");
376 // this version of delete doesn't recurse; it just iterates instead,
377 // which avoids the massive recursive depth of the original approach.
378 // it does use a stack object however, but that will use main memory,
379 // which is usually in greater supply than stack/heap space.
381 stack<tree *> sleestak; // accumulates nodes that we still need to clean up.
383 // iterate across this node first, to feed the stack.
384 // we feed it in reverse branch order, so that the first branch will be dealt with first (popped off stack first).
386 // get our current last branch...
387 tree *bran = branch(branches() - 1);
388 // pull that branch off the tree (non-destructively)...
390 // and add that branch to the stack.
392 LOG(a_sprintf("tree dtor: adding child %p on stack.", bran));
397 // now iterate across our stack until we have dealt with every node in it.
398 while (sleestak.size()) {
400 tree *popper = NULL_POINTER;
401 sleestak.acquire_pop(popper);
403 LOG(a_sprintf("tree dtor: popped a tree %p off stack.", popper));
406 // familiar scheme below; push last branch first, then we'll pop first branch first.
407 while (popper->branches()) {
408 tree *bran = popper->branch(popper->branches() - 1);
411 LOG(a_sprintf("tree dtor: inner, adding child %p on stack.", bran));
416 // now the popper gets cleaned up; this should be totally safe since all its kids
417 // have been pruned and put into the stack.
419 LOG(a_sprintf("tree dtor: about to zap a tree %p.", popper));
423 LOG("tree dtor: whacked that tree.");
429 tree *tree::parent() const { return (tree *)get_link(BACKWARDS_BRANCH); }
431 int tree::branches() const { return links() - 1; }
433 tree *tree::branch(int branch_number) const
436 bounds_return(branch_number, 1, branches(), NULL_POINTER);
437 return (tree *)get_link(branch_number);
440 int tree::which(tree *branch_to_find) const
441 { return node::which((node *)branch_to_find) - 1; }
443 tree *tree::root() const
445 const tree *traveler = this;
446 // keep looking at the backwards branch until it is a NULL_POINTER. the tree with
447 // a NULL_POINTER BACKWARDS_BRANCH is the root. return that tree.
448 while (traveler->get_link(BACKWARDS_BRANCH))
449 traveler = (tree *)traveler->get_link(BACKWARDS_BRANCH);
450 return const_cast<tree *>(traveler);
453 void tree::attach(tree *new_branch)
455 if (!new_branch) return;
456 insert_link(links(), new_branch);
457 new_branch->set_link(BACKWARDS_BRANCH, this);
460 void tree::insert(int branch_place, tree *new_branch)
463 insert_link(links(), NULL_POINTER);
464 if (branch_place >= links())
465 branch_place = links() - 1;
466 for (int i = links() - 1; i > branch_place; i--)
467 set_link(i, get_link(i-1));
468 set_link(branch_place, new_branch);
469 new_branch->set_link(BACKWARDS_BRANCH, this);
472 outcome tree::prune(tree *branch_to_cut)
474 int branch_number = which(branch_to_cut);
475 if (branch_number == basis::common::NOT_FOUND) return basis::common::NOT_FOUND;
476 return prune_index(branch_number);
479 outcome tree::prune_index(int branch_to_cut)
481 FUNCDEF("prune_index");
483 bounds_return(branch_to_cut, 1, branches(), basis::common::NOT_FOUND);
485 LOG(a_sprintf("got legit branch %d to cut", branch_to_cut));
487 tree *that_branch = (tree *)get_link(branch_to_cut);
489 LOG(a_sprintf("whacking off branch %p", that_branch));
491 that_branch->set_link(BACKWARDS_BRANCH, NULL_POINTER);
493 LOG(a_sprintf("zapping link branch %d", branch_to_cut));
495 zap_link(branch_to_cut);
497 LOG("returning, finished.");
499 return basis::common::OKAY;
502 int tree::depth() const
504 tree *my_root = root();
505 const tree *current_branch = this;
507 while (current_branch != my_root) {
508 current_branch = current_branch->parent();
514 //probably okay; we want to use this function rather than non-existent
515 //node base function which isn't implemented yet.
516 bool tree::generate_path(path &to_follow) const
518 if (to_follow.size()) {}
520 tree *traveller = this;
521 path to_accumulate(root());
522 while (traveller->parent() != NULL_POINTER) {
523 // int branch_number = traveller->parent()->which(traveller);
524 // if (branch_number == BRANCH_NOT_FOUND) non_continuable_error
525 // (class_name(), "generate_path", "branch not found during path construction");
526 // chunk *to_stuff = new chunk
527 // (SELF_OWNED, (byte *)&branch_number, sizeof(int));
528 to_accumulate.push(traveller);
529 traveller = traveller->parent();
531 // the order of things on the stack needs to be reversed now.
532 // path to_return = new stack(*to_accumulate.invert());
534 to_accumulate.invert();
535 return to_accumulate;
540 //hmmm: need text form!
542 tree::iterator tree::start(traversal_directions direction) const
543 { return iterator(this, direction); }