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 #include <loggers/program_wide_logger.h>
  21 #include <structures/stack.h>
  22
  23 //#define DEBUG_TREE
  24   // uncomment if you want lots of debugging info.
  25
  26 #undef LOG
  27 #define LOG(s) CLASS_EMERGENCY_LOG(program_wide_logger::get(), astring(s) + a_sprintf(" [obj=%p]", this))
  28
  29 using namespace basis;
  30 using namespace loggers;
  31 using namespace structures;
  32
  33 namespace nodes {
  34
  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.
  40
  41 //////////////
  42
  43 // iterator methods:
  44
  45 tree::iterator::iterator(const tree *initial, traversal_directions direction)
  46 : path(initial), _order(direction), _aim(AWAY_FROM_ROOT)
  47 {
  48 }
  49
  50 tree::iterator::~iterator() { while (size()) pop(); }
  51
  52 bool tree::iterator::next_node(tree *&to_return)
  53 {
  54 #ifdef DEBUG_TREE
  55   FUNCDEF("next_node");
  56 #endif
  57   to_return = NULL_POINTER;
  58 #ifdef DEBUG_TREE
  59   if ( (_order != to_branches)
  60       && (_order != reverse_branches) ) {
  61     if (_aim == AWAY_FROM_ROOT) LOG("going down...")
  62     else LOG("going up...");
  63   }
  64 #endif
  65   switch (_order) {
  66     case prefix: {
  67       if (_aim == AWAY_FROM_ROOT) {
  68         // going down means this is the first time we have seen the current top
  69         // node on the stack.
  70         to_return = (tree *)(*this)[size() - 1];
  71 #ifdef DEBUG_TREE
  72 //        LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s());
  73         if (to_return->branches()) LOG("pushing 0")
  74         else LOG("switching direction");
  75 #endif
  76         if (to_return->branches())
  77           push(to_return->branch(0));
  78         else
  79           _aim = TOWARD_ROOT;
  80       } else {
  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);
  88 #ifdef DEBUG_TREE
  89         if (lastnum < current_tree->branches() - 1)
  90           LOG(a_sprintf("going down %d", lastnum+1))
  91         else LOG("still going up");
  92 #endif
  93         if (lastnum < current_tree->branches() - 1) {
  94           _aim = AWAY_FROM_ROOT;
  95           push(current_tree->branch(lastnum + 1));
  96         }  // else still going up.
  97       }
  98       break;
  99     }
 100     case infix: {
 101       if (_aim == AWAY_FROM_ROOT) {
 102         // going down means starting on the left branch.
 103         tree *temp = (tree *)current();
 104 #ifdef DEBUG_TREE
 105         if (temp->branches()) LOG("pushing 0")
 106         else LOG("switching direction");
 107 #endif
 108         if (temp->branches()) push(temp->branch(0));
 109         else {
 110           _aim = TOWARD_ROOT;
 111           to_return = (tree *)current();
 112 #ifdef DEBUG_TREE
 113 //          LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s()));
 114 #endif
 115         }
 116       } else {
 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);
 124 #ifdef DEBUG_TREE
 125         if (lastnum < 1) LOG(a_sprintf("going down %d", lastnum+1))
 126         else LOG("still going up");
 127 #endif
 128         if (lastnum < 1) {
 129           _aim = AWAY_FROM_ROOT;
 130           to_return = (tree *)current();
 131 #ifdef DEBUG_TREE
 132 ///          LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s()));
 133 #endif
 134           push(current_tree->branch(lastnum + 1));
 135         }  // else still going up.
 136       }
 137       break;
 138     }
 139     case to_branches: {
 140       if (_aim == TOWARD_ROOT) return false;
 141       else {
 142         if (size() == 1) {
 143           tree *temp = (tree *)current();
 144           if (!temp->branches())
 145             _aim = TOWARD_ROOT;
 146           else
 147             push(temp->branch(0));
 148         } else {
 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;
 155           to_return = last;
 156         }
 157       }
 158       break;
 159     }
 160     case reverse_branches: {
 161       if (_aim == TOWARD_ROOT) return false;
 162       else {
 163         if (size() == 1) {
 164           tree *temp = (tree *)current();
 165           if (!temp->branches()) _aim = TOWARD_ROOT;
 166           else push(temp->branch(temp->branches() - 1));
 167         } else {
 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;
 173           to_return = last;
 174         }
 175       }
 176       break;
 177     }
 178     default:   // intentional fall-through to postfix.
 179     case postfix: {
 180       if (_aim == AWAY_FROM_ROOT) {
 181         // going down means that the bottom is still being sought.
 182         tree *temp = (tree *)current();
 183 #ifdef DEBUG_TREE
 184         if (temp->branches()) LOG("pushing 0")
 185         else LOG("switching direction");
 186 #endif
 187         if (temp->branches()) push(temp->branch(0));
 188         else _aim = TOWARD_ROOT;
 189       } else {
 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.
 195           return true;
 196         }
 197         tree *last = (tree *)pop();
 198         to_return = last;
 199 #ifdef DEBUG_TREE
 200 ///        LOG(a_sprintf("[%s] ", to_return->get_contents()->held()));
 201 #endif
 202         tree *current_tree = (tree *)current();
 203         int lastnum = current_tree->which(last);
 204 #ifdef DEBUG_TREE
 205         if (lastnum < current_tree->branches() - 1)
 206           LOG(a_sprintf("going down %d", lastnum+1))
 207         else LOG("still going up");
 208 #endif
 209         if (lastnum < current_tree->branches() - 1) {
 210           _aim = AWAY_FROM_ROOT;
 211           push(current_tree->branch(lastnum + 1));
 212         }  // else still going up.
 213       }
 214       break;
 215     }
 216   }
 217   return true;
 218     // it is assumed that termination conditions cause a return earlier on.
 219 }
 220
 221 void tree::iterator::whack(tree *to_whack)
 222 {
 223 #ifdef DEBUG_TREE
 224   FUNCDEF("whack");
 225 #endif
 226   if (!to_whack) return;  // that's a bad goof.
 227   if (size()) {
 228     if (to_whack == current()) {
 229       // we found that this is the one at the top right now.
 230       pop();
 231 #ifdef DEBUG_TREE
 232       LOG("found node in current top; removing it there.");
 233 #endif
 234     } else if (to_whack->parent() == current()) {
 235       // the parent is the current top.  make sure we don't mess up traversal.
 236 #ifdef DEBUG_TREE
 237       LOG("found node's parent as current top; don't know what to do.");
 238 #endif
 239     } else {
 240 #ifdef DEBUG_TREE
 241       LOG("found no match for either node to remove or parent in path.");
 242 #endif
 243     }
 244   }
 245   tree *parent = to_whack->parent();
 246   if (!parent) {
 247 #ifdef DEBUG_TREE
 248     LOG("no parent node for the one to whack!  would have whacked "
 249         "root of tree!");
 250 #endif
 251   } else {
 252     parent->prune(to_whack);
 253     WHACK(to_whack);
 254   }
 255 }
 256
 257 tree *tree::iterator::next()
 258 {
 259 #ifdef DEBUG_TREE
 260   FUNCDEF("next");
 261 #endif
 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;
 267   }
 268   return to_return;
 269 }
 270
 271 //////////////
 272
 273 // tree methods:
 274
 275 tree::tree()
 276 : node(1)
 277 { set_link(BACKWARDS_BRANCH, NULL_POINTER); }
 278
 279 tree::~tree()
 280 {
 281   FUNCDEF("destructor");
 282 #ifdef DEBUG_TREE
 283   LOG("entry to tree destructor");
 284 #endif
 285   {
 286     // must at least unhook ourselves from the parent so we don't become a lost
 287     // cousin.
 288     tree *my_parent = parent();
 289     if (my_parent) my_parent->prune(this);
 290   }
 291
 292 #if 0
 293   //hmmm: clean this code when it's been examined long enough.  maybe already.
 294 LOG("old code for tree destructor activating...");
 295
 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.
 303
 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.
 307 #endif
 308
 309 #if 0
 310   LOG("new code for tree destructor activating...");
 311
 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??
 314
 315   // newer version of delete doesn't recurse; it just iterates instead,
 316   // which avoids the massive recursive depth of the original approach.
 317   while (branches()) {
 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);
 328
 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...");
 332
 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.
 339           WHACK(way_back);
 340 LOG("tree dtor: whacked wayback before inner break.");
 341           break;
 342         }
 343
 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.
 349
 350 LOG("tree dtor: reset currnode, about to whack wayback...");
 351
 352         if (curr_node == stop_node) {
 353 LOG("tree dtor: seeing curr_node hits our stop_node!");
 354 ///          break;
 355         } else if (curr_node == stop_node->parent()) {
 356 LOG("tree dtor: seeing curr_node ABOVE our stop_node!");
 357         }
 358
 359         WHACK(way_back);  // whack a node, finally.
 360
 361 LOG("tree dtor: after whacking wayback...");
 362       } else {
 363         // okay, there's a node below here.  we will spider down to it.
 364 LOG("tree dtor: spidering to node below...");
 365         continue;
 366       }
 367     }
 368   }
 369 #endif
 370
 371 #if 1
 372 #ifdef DEBUG_TREE
 373   LOG("newest code for tree destructor (stack based) activating...");
 374 #endif
 375
 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.
 380
 381   stack<tree *> sleestak;  // accumulates nodes that we still need to clean up.
 382
 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).
 385   while (branches()) {
 386     // get our current last branch...
 387     tree *bran = branch(branches() - 1);
 388     // pull that branch off the tree (non-destructively)...
 389     prune(bran);
 390     // and add that branch to the stack.
 391 #ifdef DEBUG_TREE
 392     LOG(a_sprintf("tree dtor: adding child %p on stack.", bran));
 393 #endif
 394     sleestak.push(bran);
 395   }
 396
 397   // now iterate across our stack until we have dealt with every node in it.
 398   while (sleestak.size()) {
 399
 400     tree *popper = NULL_POINTER;
 401     sleestak.acquire_pop(popper);
 402 #ifdef DEBUG_TREE
 403     LOG(a_sprintf("tree dtor: popped a tree %p off stack.", popper));
 404 #endif
 405
 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);
 409       popper->prune(bran);
 410 #ifdef DEBUG_TREE
 411     LOG(a_sprintf("tree dtor: inner, adding child %p on stack.", bran));
 412 #endif
 413       sleestak.push(bran);
 414     }
 415
 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.
 418 #ifdef DEBUG_TREE
 419     LOG(a_sprintf("tree dtor: about to zap a tree %p.", popper));
 420 #endif
 421     WHACK(popper);
 422 #ifdef DEBUG_TREE
 423     LOG("tree dtor: whacked that tree.");
 424 #endif
 425   }
 426 #endif
 427 }
 428
 429 tree *tree::parent() const { return (tree *)get_link(BACKWARDS_BRANCH); }
 430
 431 int tree::branches() const { return links() - 1; }
 432
 433 tree *tree::branch(int branch_number) const
 434 {
 435   branch_number++;
 436   bounds_return(branch_number, 1, branches(), NULL_POINTER);
 437   return (tree *)get_link(branch_number);
 438 }
 439
 440 int tree::which(tree *branch_to_find) const
 441 { return node::which((node *)branch_to_find) - 1; }
 442
 443 tree *tree::root() const
 444 {
 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);
 451 }
 452
 453 void tree::attach(tree *new_branch)
 454 {
 455   if (!new_branch) return;
 456   insert_link(links(), new_branch);
 457   new_branch->set_link(BACKWARDS_BRANCH, this);
 458 }
 459
 460 void tree::insert(int branch_place, tree *new_branch)
 461 {
 462   branch_place++;
 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);
 470 }
 471
 472 outcome tree::prune(tree *branch_to_cut)
 473 {
 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);
 477 }
 478
 479 outcome tree::prune_index(int branch_to_cut)
 480 {
 481   FUNCDEF("prune_index");
 482   branch_to_cut++;
 483   bounds_return(branch_to_cut, 1, branches(), basis::common::NOT_FOUND);
 484 #ifdef DEBUG_TREE
 485   LOG(a_sprintf("got legit branch %d to cut", branch_to_cut));
 486 #endif
 487   tree *that_branch = (tree *)get_link(branch_to_cut);
 488 #ifdef DEBUG_TREE
 489   LOG(a_sprintf("whacking off branch %p", that_branch));
 490 #endif
 491   that_branch->set_link(BACKWARDS_BRANCH, NULL_POINTER);
 492 #ifdef DEBUG_TREE
 493   LOG(a_sprintf("zapping link branch %d", branch_to_cut));
 494 #endif
 495   zap_link(branch_to_cut);
 496 #ifdef DEBUG_TREE
 497   LOG("returning, finished.");
 498 #endif
 499   return basis::common::OKAY;
 500 }
 501
 502 int tree::depth() const
 503 {
 504   tree *my_root = root();
 505   const tree *current_branch = this;
 506   int deep = 0;
 507   while (current_branch != my_root) {
 508     current_branch = current_branch->parent();
 509     deep++;
 510   }
 511   return deep;
 512 }
 513
 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
 517 {
 518 if (to_follow.size()) {}
 519 /*
 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();
 530   }
 531   // the order of things on the stack needs to be reversed now.
 532 //  path to_return = new stack(*to_accumulate.invert());
 533 //  return to_return;
 534   to_accumulate.invert();
 535   return to_accumulate;
 536 */
 537 return false;//temp.
 538 }
 539
 540 //hmmm: need text form!
 541
 542 tree::iterator tree::start(traversal_directions direction) const
 543 { return iterator(this, direction); }
 544
 545 }  // namespace.
 546