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
  22 //#define DEBUG_TREE
  23   // uncomment if you want lots of debugging info.
  24
  25 #undef LOG
  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))
  28
  29 using namespace basis;
  30 using namespace loggers;
  31
  32 namespace nodes {
  33
  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.
  39
  40 //////////////
  41
  42 // iterator methods:
  43
  44 tree::iterator::iterator(const tree *initial, traversal_directions direction)
  45 : path(initial), _order(direction), _aim(AWAY_FROM_ROOT)
  46 {
  47 }
  48
  49 tree::iterator::~iterator() { while (size()) pop(); }
  50
  51 bool tree::iterator::next_node(tree *&to_return)
  52 {
  53 #ifdef DEBUG_TREE
  54   FUNCDEF("next_node");
  55 #endif
  56   to_return = NULL_POINTER;
  57 #ifdef DEBUG_TREE
  58   if ( (_order != to_branches)
  59       && (_order != reverse_branches) ) {
  60     if (_aim == AWAY_FROM_ROOT) LOG("going down...")
  61     else LOG("going up...");
  62   }
  63 #endif
  64   switch (_order) {
  65     case prefix: {
  66       if (_aim == AWAY_FROM_ROOT) {
  67         // going down means this is the first time we have seen the current top
  68         // node on the stack.
  69         to_return = (tree *)(*this)[size() - 1];
  70 #ifdef DEBUG_TREE
  71 //        LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s());
  72         if (to_return->branches()) LOG("pushing 0")
  73         else LOG("switching direction");
  74 #endif
  75         if (to_return->branches())
  76           push(to_return->branch(0));
  77         else
  78           _aim = TOWARD_ROOT;
  79       } else {
  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);
  87 #ifdef DEBUG_TREE
  88         if (lastnum < current_tree->branches() - 1)
  89           LOG(a_sprintf("going down %d", lastnum+1))
  90         else LOG("still going up");
  91 #endif
  92         if (lastnum < current_tree->branches() - 1) {
  93           _aim = AWAY_FROM_ROOT;
  94           push(current_tree->branch(lastnum + 1));
  95         }  // else still going up.
  96       }
  97       break;
  98     }
  99     case infix: {
 100       if (_aim == AWAY_FROM_ROOT) {
 101         // going down means starting on the left branch.
 102         tree *temp = (tree *)current();
 103 #ifdef DEBUG_TREE
 104         if (temp->branches()) LOG("pushing 0")
 105         else LOG("switching direction");
 106 #endif
 107         if (temp->branches()) push(temp->branch(0));
 108         else {
 109           _aim = TOWARD_ROOT;
 110           to_return = (tree *)current();
 111 #ifdef DEBUG_TREE
 112 //          LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s()));
 113 #endif
 114         }
 115       } else {
 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);
 123 #ifdef DEBUG_TREE
 124         if (lastnum < 1) LOG(a_sprintf("going down %d", lastnum+1))
 125         else LOG("still going up");
 126 #endif
 127         if (lastnum < 1) {
 128           _aim = AWAY_FROM_ROOT;
 129           to_return = (tree *)current();
 130 #ifdef DEBUG_TREE
 131 ///          LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s()));
 132 #endif
 133           push(current_tree->branch(lastnum + 1));
 134         }  // else still going up.
 135       }
 136       break;
 137     }
 138     case to_branches: {
 139       if (_aim == TOWARD_ROOT) return false;
 140       else {
 141         if (size() == 1) {
 142           tree *temp = (tree *)current();
 143           if (!temp->branches())
 144             _aim = TOWARD_ROOT;
 145           else
 146             push(temp->branch(0));
 147         } else {
 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;
 154           to_return = last;
 155         }
 156       }
 157       break;
 158     }
 159     case reverse_branches: {
 160       if (_aim == TOWARD_ROOT) return false;
 161       else {
 162         if (size() == 1) {
 163           tree *temp = (tree *)current();
 164           if (!temp->branches()) _aim = TOWARD_ROOT;
 165           else push(temp->branch(temp->branches() - 1));
 166         } else {
 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;
 172           to_return = last;
 173         }
 174       }
 175       break;
 176     }
 177     default:   // intentional fall-through to postfix.
 178     case postfix: {
 179       if (_aim == AWAY_FROM_ROOT) {
 180         // going down means that the bottom is still being sought.
 181         tree *temp = (tree *)current();
 182 #ifdef DEBUG_TREE
 183         if (temp->branches()) LOG("pushing 0")
 184         else LOG("switching direction");
 185 #endif
 186         if (temp->branches()) push(temp->branch(0));
 187         else _aim = TOWARD_ROOT;
 188       } else {
 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.
 194           return true;
 195         }
 196         tree *last = (tree *)pop();
 197         to_return = last;
 198 #ifdef DEBUG_TREE
 199 ///        LOG(a_sprintf("[%s] ", to_return->get_contents()->held()));
 200 #endif
 201         tree *current_tree = (tree *)current();
 202         int lastnum = current_tree->which(last);
 203 #ifdef DEBUG_TREE
 204         if (lastnum < current_tree->branches() - 1)
 205           LOG(a_sprintf("going down %d", lastnum+1))
 206         else LOG("still going up");
 207 #endif
 208         if (lastnum < current_tree->branches() - 1) {
 209           _aim = AWAY_FROM_ROOT;
 210           push(current_tree->branch(lastnum + 1));
 211         }  // else still going up.
 212       }
 213       break;
 214     }
 215   }
 216   return true;
 217     // it is assumed that termination conditions cause a return earlier on.
 218 }
 219
 220 void tree::iterator::whack(tree *to_whack)
 221 {
 222 #ifdef DEBUG_TREE
 223   FUNCDEF("whack");
 224 #endif
 225   if (!to_whack) return;  // that's a bad goof.
 226   if (size()) {
 227     if (to_whack == current()) {
 228       // we found that this is the one at the top right now.
 229       pop();
 230 #ifdef DEBUG_TREE
 231       LOG("found node in current top; removing it there.");
 232 #endif
 233     } else if (to_whack->parent() == current()) {
 234       // the parent is the current top.  make sure we don't mess up traversal.
 235 #ifdef DEBUG_TREE
 236       LOG("found node's parent as current top; don't know what to do.");
 237 #endif
 238     } else {
 239 #ifdef DEBUG_TREE
 240       LOG("found no match for either node to remove or parent in path.");
 241 #endif
 242     }
 243   }
 244   tree *parent = to_whack->parent();
 245   if (!parent) {
 246 #ifdef DEBUG_TREE
 247     LOG("no parent node for the one to whack!  would have whacked "
 248         "root of tree!");
 249 #endif
 250   } else {
 251     parent->prune(to_whack);
 252     WHACK(to_whack);
 253   }
 254 }
 255
 256 tree *tree::iterator::next()
 257 {
 258 #ifdef DEBUG_TREE
 259   FUNCDEF("next");
 260 #endif
 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;
 266   }
 267   return to_return;
 268 }
 269
 270 //////////////
 271
 272 // tree methods:
 273
 274 tree::tree()
 275 : node(1)
 276 { set_link(BACKWARDS_BRANCH, NULL_POINTER); }
 277
 278 tree::~tree()
 279 {
 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
 283   // cousin.
 284   tree *my_parent = parent();
 285   if (my_parent) my_parent->prune(this);
 286   my_parent = NULL_POINTER;  // disavow since we are loose now.
 287
 288 #if 1
 289   //hmmm: clean this code when it's been examined long enough.  maybe already.
 290 LOG("old code for tree destructor activating...");
 291
 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.
 299
 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.
 303 #else
 304 LOG("new code for tree destructor activating...");
 305
 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);
 317
 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...");
 321
 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...");
 326         break;
 327       }
 328
 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...");
 337     } else {
 338       // okay, there's a node below here.  we will spider down to it.
 339 LOG("tree dtor: spidering to node below...");
 340       continue;
 341     }
 342   }
 343
 344 #endif
 345 }
 346
 347 tree *tree::parent() const { return (tree *)get_link(BACKWARDS_BRANCH); }
 348
 349 int tree::branches() const { return links() - 1; }
 350
 351 tree *tree::branch(int branch_number) const
 352 {
 353   branch_number++;
 354   bounds_return(branch_number, 1, branches(), NULL_POINTER);
 355   return (tree *)get_link(branch_number);
 356 }
 357
 358 int tree::which(tree *branch_to_find) const
 359 { return node::which((node *)branch_to_find) - 1; }
 360
 361 tree *tree::root() const
 362 {
 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);
 369 }
 370
 371 void tree::attach(tree *new_branch)
 372 {
 373   if (!new_branch) return;
 374   insert_link(links(), new_branch);
 375   new_branch->set_link(BACKWARDS_BRANCH, this);
 376 }
 377
 378 void tree::insert(int branch_place, tree *new_branch)
 379 {
 380   branch_place++;
 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);
 388 }
 389
 390 outcome tree::prune(tree *branch_to_cut)
 391 {
 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);
 395 }
 396
 397 outcome tree::prune_index(int branch_to_cut)
 398 {
 399   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;
 405 }
 406
 407 int tree::depth() const
 408 {
 409   tree *my_root = root();
 410   const tree *current_branch = this;
 411   int deep = 0;
 412   while (current_branch != my_root) {
 413     current_branch = current_branch->parent();
 414     deep++;
 415   }
 416   return deep;
 417 }
 418
 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
 422 {
 423 if (to_follow.size()) {}
 424 /*
 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();
 435   }
 436   // the order of things on the stack needs to be reversed now.
 437 //  path to_return = new stack(*to_accumulate.invert());
 438 //  return to_return;
 439   to_accumulate.invert();
 440   return to_accumulate;
 441 */
 442 return false;//temp.
 443 }
 444
 445 //hmmm: need text form!
 446
 447 tree::iterator tree::start(traversal_directions direction) const
 448 { return iterator(this, direction); }
 449
 450 }  // namespace.
 451