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)
28 using namespace basis;
29 using namespace loggers;
33 const int BACKWARDS_BRANCH = 0;
34 // BACKWARDS_BRANCH is the branch from this tree to its parent. this is
35 // steeped in the perspective that the root is the backwards direction (where
36 // we came from, in a sense) and that the children of this node are the
37 // forwards direction.
43 tree::iterator::iterator(const tree *initial, traversal_directions direction)
44 : path(initial), _order(direction), _aim(AWAY_FROM_ROOT)
48 tree::iterator::~iterator() { while (size()) pop(); }
50 bool tree::iterator::next_node(tree *&to_return)
55 to_return = NULL_POINTER;
57 if ( (_order != to_branches)
58 && (_order != reverse_branches) ) {
59 if (_aim == AWAY_FROM_ROOT) LOG("going down...")
60 else LOG("going up...");
65 if (_aim == AWAY_FROM_ROOT) {
66 // going down means this is the first time we have seen the current top
68 to_return = (tree *)(*this)[size() - 1];
70 // LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s());
71 if (to_return->branches()) LOG("pushing 0")
72 else LOG("switching direction");
74 if (to_return->branches())
75 push(to_return->branch(0));
79 // going up means that we need to get rid of some things before we
80 // start seeing new nodes again.
81 if (size() == 1) return false;
82 // the last node has been seen....
83 tree *last = (tree *)pop();
84 tree *current_tree = (tree *)current();
85 int lastnum = current_tree->which(last);
87 if (lastnum < current_tree->branches() - 1)
88 LOG(a_sprintf("going down %d", lastnum+1))
89 else LOG("still going up");
91 if (lastnum < current_tree->branches() - 1) {
92 _aim = AWAY_FROM_ROOT;
93 push(current_tree->branch(lastnum + 1));
94 } // else still going up.
99 if (_aim == AWAY_FROM_ROOT) {
100 // going down means starting on the left branch.
101 tree *temp = (tree *)current();
103 if (temp->branches()) LOG("pushing 0")
104 else LOG("switching direction");
106 if (temp->branches()) push(temp->branch(0));
109 to_return = (tree *)current();
111 // LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s()));
115 // going up means that the left branch is done and we need to either
116 // keep going up or go down the right branch.
117 if (size() == 1) return false;
118 // the last node has been seen....
119 tree *last = (tree *)pop();
120 tree *current_tree = (tree *)current();
121 int lastnum = current_tree->which(last);
123 if (lastnum < 1) LOG(a_sprintf("going down %d", lastnum+1))
124 else LOG("still going up");
127 _aim = AWAY_FROM_ROOT;
128 to_return = (tree *)current();
130 /// LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s()));
132 push(current_tree->branch(lastnum + 1));
133 } // else still going up.
138 if (_aim == TOWARD_ROOT) return false;
141 tree *temp = (tree *)current();
142 if (!temp->branches())
145 push(temp->branch(0));
147 tree *last = (tree *)pop();
148 tree *curr = (tree *)current();
149 int lastnum = curr->which(last);
150 if (lastnum < curr->branches() - 1)
151 push(curr->branch(lastnum + 1));
152 else _aim = TOWARD_ROOT;
158 case reverse_branches: {
159 if (_aim == TOWARD_ROOT) return false;
162 tree *temp = (tree *)current();
163 if (!temp->branches()) _aim = TOWARD_ROOT;
164 else push(temp->branch(temp->branches() - 1));
166 tree *last = (tree *)pop();
167 tree *curr = (tree *)current();
168 int lastnum = curr->which(last);
169 if (lastnum > 0) push(curr->branch(lastnum - 1));
170 else _aim = TOWARD_ROOT;
176 default: // intentional fall-through to postfix.
178 if (_aim == AWAY_FROM_ROOT) {
179 // going down means that the bottom is still being sought.
180 tree *temp = (tree *)current();
182 if (temp->branches()) LOG("pushing 0")
183 else LOG("switching direction");
185 if (temp->branches()) push(temp->branch(0));
186 else _aim = TOWARD_ROOT;
188 // going up means that all nodes below current have been hit.
189 if (!size()) return false; // the last node has been seen...
190 else if (size() == 1) {
191 to_return = (tree *)pop();
192 // this is the last node.
195 tree *last = (tree *)pop();
198 /// LOG(a_sprintf("[%s] ", to_return->get_contents()->held()));
200 tree *current_tree = (tree *)current();
201 int lastnum = current_tree->which(last);
203 if (lastnum < current_tree->branches() - 1)
204 LOG(a_sprintf("going down %d", lastnum+1))
205 else LOG("still going up");
207 if (lastnum < current_tree->branches() - 1) {
208 _aim = AWAY_FROM_ROOT;
209 push(current_tree->branch(lastnum + 1));
210 } // else still going up.
216 // it is assumed that termination conditions cause a return earlier on.
219 void tree::iterator::whack(tree *to_whack)
224 if (!to_whack) return; // that's a bad goof.
226 if (to_whack == current()) {
227 // we found that this is the one at the top right now.
230 LOG("found node in current top; removing it there.");
232 } else if (to_whack->parent() == current()) {
233 // the parent is the current top. make sure we don't mess up traversal.
235 LOG("found node's parent as current top; don't know what to do.");
239 LOG("found no match for either node to remove or parent in path.");
243 tree *parent = to_whack->parent();
246 LOG("no parent node for the one to whack! would have whacked "
250 parent->prune(to_whack);
255 tree *tree::iterator::next()
260 tree *to_return = NULL_POINTER;
261 bool found_tree = false;
262 while (!found_tree) {
263 bool still_running = next_node(to_return);
264 if (to_return || !still_running) found_tree = true;
275 { set_link(BACKWARDS_BRANCH, NULL_POINTER); }
279 FUNCDEF("destructor");
280 // must at least unhook ourselves from the parent so we don't become a lost
282 tree *my_parent = parent();
283 if (my_parent) my_parent->prune(this);
284 my_parent = NULL_POINTER; // disavow since we are loose now.
287 //hmmm: clean this code when it's been examined long enough. maybe already.
289 //original version suffers from being too recursive on windoze,
290 //which blows out the stack. linux never showed this problem. so, i
291 //guess i'm glad i tested on windows.
292 //anyway, it's a general problem for a degenerate tree like the one
293 //i've constructed. current version has ~40000 direct descendants of
294 //the root in a single line, so the stack has to support 40000 frames
295 //for the delete implementation below to work.
297 // iterate over the child nodes and whack each individually.
298 while (branches()) delete branch(0);
299 // this relies on the child getting out of our branch list.
302 // newer version of delete doesn't recurse; it just iterates instead,
303 // which avoids the massive recursive depth of the original approach.
304 tree *curr_node = this;
305 tree *stop_node = this; // don't whack self.
306 while (curr_node != NULL_POINTER) {
307 // make a breadcrumb for getting back to 'here' in the tree.
308 tree *way_back = curr_node;
309 // our main operation here is to go down a node without using any
310 // stack frames. so we just pick the first kid; it's either valid
311 // or there are no kids at all.
312 curr_node = curr_node->branch(0);
314 if (curr_node == NULL_POINTER) {
315 // wayback has no children, so we can take action.
317 // if wayback is the same as "this", then we exit from iterations since
318 // we've cleaned all the kids out.
319 if (way_back == this) {
323 // we want to whack the wayback node at this point, since it's a parent
324 // with no kids, i.e. a leaf. we've guaranteed we're not going beyond
325 // our remit, since wayback is not the same node as the top level one
326 // in the destructor (as long as there are no cycles in the tree...).
327 curr_node = way_back->parent(); // go up in tree on next iteration.
328 WHACK(way_back); // whack a node, finally.
330 // okay, there's a node below here. we will spider down to it.
338 tree *tree::parent() const { return (tree *)get_link(BACKWARDS_BRANCH); }
340 int tree::branches() const { return links() - 1; }
342 tree *tree::branch(int branch_number) const
345 bounds_return(branch_number, 1, branches(), NULL_POINTER);
346 return (tree *)get_link(branch_number);
349 int tree::which(tree *branch_to_find) const
350 { return node::which((node *)branch_to_find) - 1; }
352 tree *tree::root() const
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);
362 void tree::attach(tree *new_branch)
364 if (!new_branch) return;
365 insert_link(links(), new_branch);
366 new_branch->set_link(BACKWARDS_BRANCH, this);
369 void tree::insert(int branch_place, tree *new_branch)
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);
381 outcome tree::prune(tree *branch_to_cut)
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);
388 outcome tree::prune_index(int 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;
398 int tree::depth() const
400 tree *my_root = root();
401 const tree *current_branch = this;
403 while (current_branch != my_root) {
404 current_branch = current_branch->parent();
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
414 if (to_follow.size()) {}
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();
427 // the order of things on the stack needs to be reversed now.
428 // path to_return = new stack(*to_accumulate.invert());
430 to_accumulate.invert();
431 return to_accumulate;
436 //hmmm: need text form!
438 tree::iterator tree::start(traversal_directions direction) const
439 { return iterator(this, direction); }