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>
23 // uncomment if you want lots of debugging info.
26 ///#define LOG(s) CLASS_EMERGENCY_LOG(program_wide_logger::get(), s)
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;
34 const int BACKWARDS_BRANCH = 0;
35 // BACKWARDS_BRANCH is the branch from this tree to its parent. this is
36 // steeped in the perspective that the root is the backwards direction (where
37 // we came from, in a sense) and that the children of this node are the
38 // forwards direction.
44 tree::iterator::iterator(const tree *initial, traversal_directions direction)
45 : path(initial), _order(direction), _aim(AWAY_FROM_ROOT)
49 tree::iterator::~iterator() { while (size()) pop(); }
51 bool tree::iterator::next_node(tree *&to_return)
56 to_return = NULL_POINTER;
58 if ( (_order != to_branches)
59 && (_order != reverse_branches) ) {
60 if (_aim == AWAY_FROM_ROOT) LOG("going down...")
61 else LOG("going up...");
66 if (_aim == AWAY_FROM_ROOT) {
67 // going down means this is the first time we have seen the current top
69 to_return = (tree *)(*this)[size() - 1];
71 // LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s());
72 if (to_return->branches()) LOG("pushing 0")
73 else LOG("switching direction");
75 if (to_return->branches())
76 push(to_return->branch(0));
80 // going up means that we need to get rid of some things before we
81 // start seeing new nodes again.
82 if (size() == 1) return false;
83 // the last node has been seen....
84 tree *last = (tree *)pop();
85 tree *current_tree = (tree *)current();
86 int lastnum = current_tree->which(last);
88 if (lastnum < current_tree->branches() - 1)
89 LOG(a_sprintf("going down %d", lastnum+1))
90 else LOG("still going up");
92 if (lastnum < current_tree->branches() - 1) {
93 _aim = AWAY_FROM_ROOT;
94 push(current_tree->branch(lastnum + 1));
95 } // else still going up.
100 if (_aim == AWAY_FROM_ROOT) {
101 // going down means starting on the left branch.
102 tree *temp = (tree *)current();
104 if (temp->branches()) LOG("pushing 0")
105 else LOG("switching direction");
107 if (temp->branches()) push(temp->branch(0));
110 to_return = (tree *)current();
112 // LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s()));
116 // going up means that the left branch is done and we need to either
117 // keep going up or go down the right branch.
118 if (size() == 1) return false;
119 // the last node has been seen....
120 tree *last = (tree *)pop();
121 tree *current_tree = (tree *)current();
122 int lastnum = current_tree->which(last);
124 if (lastnum < 1) LOG(a_sprintf("going down %d", lastnum+1))
125 else LOG("still going up");
128 _aim = AWAY_FROM_ROOT;
129 to_return = (tree *)current();
131 /// LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s()));
133 push(current_tree->branch(lastnum + 1));
134 } // else still going up.
139 if (_aim == TOWARD_ROOT) return false;
142 tree *temp = (tree *)current();
143 if (!temp->branches())
146 push(temp->branch(0));
148 tree *last = (tree *)pop();
149 tree *curr = (tree *)current();
150 int lastnum = curr->which(last);
151 if (lastnum < curr->branches() - 1)
152 push(curr->branch(lastnum + 1));
153 else _aim = TOWARD_ROOT;
159 case reverse_branches: {
160 if (_aim == TOWARD_ROOT) return false;
163 tree *temp = (tree *)current();
164 if (!temp->branches()) _aim = TOWARD_ROOT;
165 else push(temp->branch(temp->branches() - 1));
167 tree *last = (tree *)pop();
168 tree *curr = (tree *)current();
169 int lastnum = curr->which(last);
170 if (lastnum > 0) push(curr->branch(lastnum - 1));
171 else _aim = TOWARD_ROOT;
177 default: // intentional fall-through to postfix.
179 if (_aim == AWAY_FROM_ROOT) {
180 // going down means that the bottom is still being sought.
181 tree *temp = (tree *)current();
183 if (temp->branches()) LOG("pushing 0")
184 else LOG("switching direction");
186 if (temp->branches()) push(temp->branch(0));
187 else _aim = TOWARD_ROOT;
189 // going up means that all nodes below current have been hit.
190 if (!size()) return false; // the last node has been seen...
191 else if (size() == 1) {
192 to_return = (tree *)pop();
193 // this is the last node.
196 tree *last = (tree *)pop();
199 /// LOG(a_sprintf("[%s] ", to_return->get_contents()->held()));
201 tree *current_tree = (tree *)current();
202 int lastnum = current_tree->which(last);
204 if (lastnum < current_tree->branches() - 1)
205 LOG(a_sprintf("going down %d", lastnum+1))
206 else LOG("still going up");
208 if (lastnum < current_tree->branches() - 1) {
209 _aim = AWAY_FROM_ROOT;
210 push(current_tree->branch(lastnum + 1));
211 } // else still going up.
217 // it is assumed that termination conditions cause a return earlier on.
220 void tree::iterator::whack(tree *to_whack)
225 if (!to_whack) return; // that's a bad goof.
227 if (to_whack == current()) {
228 // we found that this is the one at the top right now.
231 LOG("found node in current top; removing it there.");
233 } else if (to_whack->parent() == current()) {
234 // the parent is the current top. make sure we don't mess up traversal.
236 LOG("found node's parent as current top; don't know what to do.");
240 LOG("found no match for either node to remove or parent in path.");
244 tree *parent = to_whack->parent();
247 LOG("no parent node for the one to whack! would have whacked "
251 parent->prune(to_whack);
256 tree *tree::iterator::next()
261 tree *to_return = NULL_POINTER;
262 bool found_tree = false;
263 while (!found_tree) {
264 bool still_running = next_node(to_return);
265 if (to_return || !still_running) found_tree = true;
276 { set_link(BACKWARDS_BRANCH, NULL_POINTER); }
280 FUNCDEF("destructor");
281 LOG("entry to tree destructor");
282 // must at least unhook ourselves from the parent so we don't become a lost
284 tree *my_parent = parent();
285 if (my_parent) my_parent->prune(this);
286 my_parent = NULL_POINTER; // disavow since we are loose now.
289 //hmmm: clean this code when it's been examined long enough. maybe already.
290 LOG("old code for tree destructor activating...");
292 //original version suffers from being too recursive on windoze,
293 //which blows out the stack. linux never showed this problem. so, i
294 //guess i'm glad i tested on windows.
295 //anyway, it's a general problem for a degenerate tree like the one
296 //i've constructed. current version has ~40000 direct descendants of
297 //the root in a single line, so the stack has to support 40000 frames
298 //for the delete implementation below to work.
300 // iterate over the child nodes and whack each individually.
301 while (branches()) delete branch(0);
302 // this relies on the child getting out of our branch list.
304 LOG("new code for tree destructor activating...");
306 // newer version of delete doesn't recurse; it just iterates instead,
307 // which avoids the massive recursive depth of the original approach.
308 tree *curr_node = this;
309 tree *stop_node = this; // don't whack self.
310 while (curr_node != NULL_POINTER) {
311 // make a breadcrumb for getting back to 'here' in the tree.
312 tree *way_back = curr_node;
313 // our main operation here is to go down a node without using any
314 // stack frames. so we just pick the first kid; it's either valid
315 // or there are no kids at all.
316 curr_node = curr_node->branch(0);
318 if (curr_node == NULL_POINTER) {
319 // wayback has no children, so we can take action.
320 LOG("tree dtor: can take action on childless node...");
322 // if wayback is the same as "this", then we exit from iterations since
323 // we've cleaned all the kids out.
324 if (way_back == this) {
325 LOG("tree dtor: breaking out since at wayback node...");
329 // we want to whack the wayback node at this point, since it's a parent
330 // with no kids, i.e. a leaf. we've guaranteed we're not going beyond
331 // our remit, since wayback is not the same node as the top level one
332 // in the destructor (as long as there are no cycles in the tree...).
333 curr_node = way_back->parent(); // go up in tree on next iteration.
334 LOG("tree dtor: reset currnode, about to whack wayback...");
335 WHACK(way_back); // whack a node, finally.
336 LOG("tree dtor: after whacking wayback...");
338 // okay, there's a node below here. we will spider down to it.
339 LOG("tree dtor: spidering to node below...");
347 tree *tree::parent() const { return (tree *)get_link(BACKWARDS_BRANCH); }
349 int tree::branches() const { return links() - 1; }
351 tree *tree::branch(int branch_number) const
354 bounds_return(branch_number, 1, branches(), NULL_POINTER);
355 return (tree *)get_link(branch_number);
358 int tree::which(tree *branch_to_find) const
359 { return node::which((node *)branch_to_find) - 1; }
361 tree *tree::root() const
363 const tree *traveler = this;
364 // keep looking at the backwards branch until it is a NULL_POINTER. the tree with
365 // a NULL_POINTER BACKWARDS_BRANCH is the root. return that tree.
366 while (traveler->get_link(BACKWARDS_BRANCH))
367 traveler = (tree *)traveler->get_link(BACKWARDS_BRANCH);
368 return const_cast<tree *>(traveler);
371 void tree::attach(tree *new_branch)
373 if (!new_branch) return;
374 insert_link(links(), new_branch);
375 new_branch->set_link(BACKWARDS_BRANCH, this);
378 void tree::insert(int branch_place, tree *new_branch)
381 insert_link(links(), NULL_POINTER);
382 if (branch_place >= links())
383 branch_place = links() - 1;
384 for (int i = links() - 1; i > branch_place; i--)
385 set_link(i, get_link(i-1));
386 set_link(branch_place, new_branch);
387 new_branch->set_link(BACKWARDS_BRANCH, this);
390 outcome tree::prune(tree *branch_to_cut)
392 int branch_number = which(branch_to_cut);
393 if (branch_number == basis::common::NOT_FOUND) return basis::common::NOT_FOUND;
394 return prune_index(branch_number);
397 outcome tree::prune_index(int branch_to_cut)
400 bounds_return(branch_to_cut, 1, branches(), basis::common::NOT_FOUND);
401 tree *that_branch = (tree *)get_link(branch_to_cut);
402 that_branch->set_link(BACKWARDS_BRANCH, NULL_POINTER);
403 zap_link(branch_to_cut);
404 return basis::common::OKAY;
407 int tree::depth() const
409 tree *my_root = root();
410 const tree *current_branch = this;
412 while (current_branch != my_root) {
413 current_branch = current_branch->parent();
419 //probably okay; we want to use this function rather than non-existent
420 //node base function which isn't implemented yet.
421 bool tree::generate_path(path &to_follow) const
423 if (to_follow.size()) {}
425 tree *traveller = this;
426 path to_accumulate(root());
427 while (traveller->parent() != NULL_POINTER) {
428 // int branch_number = traveller->parent()->which(traveller);
429 // if (branch_number == BRANCH_NOT_FOUND) non_continuable_error
430 // (class_name(), "generate_path", "branch not found during path construction");
431 // chunk *to_stuff = new chunk
432 // (SELF_OWNED, (byte *)&branch_number, sizeof(int));
433 to_accumulate.push(traveller);
434 traveller = traveller->parent();
436 // the order of things on the stack needs to be reversed now.
437 // path to_return = new stack(*to_accumulate.invert());
439 to_accumulate.invert();
440 return to_accumulate;
445 //hmmm: need text form!
447 tree::iterator tree::start(traversal_directions direction) const
448 { return iterator(this, direction); }