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
  28 using namespace basis;
  29 using namespace loggers;
  30
  31 namespace nodes {
  32
  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.
  38
  39 //////////////
  40
  41 // iterator methods:
  42
  43 tree::iterator::iterator(const tree *initial, traversal_directions direction)
  44 : path(initial), _order(direction), _aim(AWAY_FROM_ROOT)
  45 {
  46 }
  47
  48 tree::iterator::~iterator() { while (size()) pop(); }
  49
  50 bool tree::iterator::next_node(tree *&to_return)
  51 {
  52 #ifdef DEBUG_TREE
  53   FUNCDEF("next_node");
  54 #endif
  55   to_return = NULL_POINTER;
  56 #ifdef DEBUG_TREE
  57   if ( (_order != to_branches)
  58       && (_order != reverse_branches) ) {
  59     if (_aim == AWAY_FROM_ROOT) LOG("going down...")
  60     else LOG("going up...");
  61   }
  62 #endif
  63   switch (_order) {
  64     case prefix: {
  65       if (_aim == AWAY_FROM_ROOT) {
  66         // going down means this is the first time we have seen the current top
  67         // node on the stack.
  68         to_return = (tree *)(*this)[size() - 1];
  69 #ifdef DEBUG_TREE
  70 //        LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s());
  71         if (to_return->branches()) LOG("pushing 0")
  72         else LOG("switching direction");
  73 #endif
  74         if (to_return->branches())
  75           push(to_return->branch(0));
  76         else
  77           _aim = TOWARD_ROOT;
  78       } else {
  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);
  86 #ifdef DEBUG_TREE
  87         if (lastnum < current_tree->branches() - 1)
  88           LOG(a_sprintf("going down %d", lastnum+1))
  89         else LOG("still going up");
  90 #endif
  91         if (lastnum < current_tree->branches() - 1) {
  92           _aim = AWAY_FROM_ROOT;
  93           push(current_tree->branch(lastnum + 1));
  94         }  // else still going up.
  95       }
  96       break;
  97     }
  98     case infix: {
  99       if (_aim == AWAY_FROM_ROOT) {
 100         // going down means starting on the left branch.
 101         tree *temp = (tree *)current();
 102 #ifdef DEBUG_TREE
 103         if (temp->branches()) LOG("pushing 0")
 104         else LOG("switching direction");
 105 #endif
 106         if (temp->branches()) push(temp->branch(0));
 107         else {
 108           _aim = TOWARD_ROOT;
 109           to_return = (tree *)current();
 110 #ifdef DEBUG_TREE
 111 //          LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s()));
 112 #endif
 113         }
 114       } else {
 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);
 122 #ifdef DEBUG_TREE
 123         if (lastnum < 1) LOG(a_sprintf("going down %d", lastnum+1))
 124         else LOG("still going up");
 125 #endif
 126         if (lastnum < 1) {
 127           _aim = AWAY_FROM_ROOT;
 128           to_return = (tree *)current();
 129 #ifdef DEBUG_TREE
 130 ///          LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s()));
 131 #endif
 132           push(current_tree->branch(lastnum + 1));
 133         }  // else still going up.
 134       }
 135       break;
 136     }
 137     case to_branches: {
 138       if (_aim == TOWARD_ROOT) return false;
 139       else {
 140         if (size() == 1) {
 141           tree *temp = (tree *)current();
 142           if (!temp->branches())
 143             _aim = TOWARD_ROOT;
 144           else
 145             push(temp->branch(0));
 146         } else {
 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;
 153           to_return = last;
 154         }
 155       }
 156       break;
 157     }
 158     case reverse_branches: {
 159       if (_aim == TOWARD_ROOT) return false;
 160       else {
 161         if (size() == 1) {
 162           tree *temp = (tree *)current();
 163           if (!temp->branches()) _aim = TOWARD_ROOT;
 164           else push(temp->branch(temp->branches() - 1));
 165         } else {
 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;
 171           to_return = last;
 172         }
 173       }
 174       break;
 175     }
 176     default:   // intentional fall-through to postfix.
 177     case postfix: {
 178       if (_aim == AWAY_FROM_ROOT) {
 179         // going down means that the bottom is still being sought.
 180         tree *temp = (tree *)current();
 181 #ifdef DEBUG_TREE
 182         if (temp->branches()) LOG("pushing 0")
 183         else LOG("switching direction");
 184 #endif
 185         if (temp->branches()) push(temp->branch(0));
 186         else _aim = TOWARD_ROOT;
 187       } else {
 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.
 193           return true;
 194         }
 195         tree *last = (tree *)pop();
 196         to_return = last;
 197 #ifdef DEBUG_TREE
 198 ///        LOG(a_sprintf("[%s] ", to_return->get_contents()->held()));
 199 #endif
 200         tree *current_tree = (tree *)current();
 201         int lastnum = current_tree->which(last);
 202 #ifdef DEBUG_TREE
 203         if (lastnum < current_tree->branches() - 1)
 204           LOG(a_sprintf("going down %d", lastnum+1))
 205         else LOG("still going up");
 206 #endif
 207         if (lastnum < current_tree->branches() - 1) {
 208           _aim = AWAY_FROM_ROOT;
 209           push(current_tree->branch(lastnum + 1));
 210         }  // else still going up.
 211       }
 212       break;
 213     }
 214   }
 215   return true;
 216     // it is assumed that termination conditions cause a return earlier on.
 217 }
 218
 219 void tree::iterator::whack(tree *to_whack)
 220 {
 221 #ifdef DEBUG_TREE
 222   FUNCDEF("whack");
 223 #endif
 224   if (!to_whack) return;  // that's a bad goof.
 225   if (size()) {
 226     if (to_whack == current()) {
 227       // we found that this is the one at the top right now.
 228       pop();
 229 #ifdef DEBUG_TREE
 230       LOG("found node in current top; removing it there.");
 231 #endif
 232     } else if (to_whack->parent() == current()) {
 233       // the parent is the current top.  make sure we don't mess up traversal.
 234 #ifdef DEBUG_TREE
 235       LOG("found node's parent as current top; don't know what to do.");
 236 #endif
 237     } else {
 238 #ifdef DEBUG_TREE
 239       LOG("found no match for either node to remove or parent in path.");
 240 #endif
 241     }
 242   }
 243   tree *parent = to_whack->parent();
 244   if (!parent) {
 245 #ifdef DEBUG_TREE
 246     LOG("no parent node for the one to whack!  would have whacked "
 247         "root of tree!");
 248 #endif
 249   } else {
 250     parent->prune(to_whack);
 251     WHACK(to_whack);
 252   }
 253 }
 254
 255 tree *tree::iterator::next()
 256 {
 257 #ifdef DEBUG_TREE
 258   FUNCDEF("next");
 259 #endif
 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;
 265   }
 266   return to_return;
 267 }
 268
 269 //////////////
 270
 271 // tree methods:
 272
 273 tree::tree()
 274 : node(1)
 275 { set_link(BACKWARDS_BRANCH, NULL_POINTER); }
 276
 277 tree::~tree()
 278 {
 279   FUNCDEF("destructor");
 280   // must at least unhook ourselves from the parent so we don't become a lost
 281   // cousin.
 282   tree *my_parent = parent();
 283   if (my_parent) my_parent->prune(this);
 284   my_parent = NULL_POINTER;  // disavow since we are loose now.
 285
 286 #if 0
 287   //hmmm: clean this code when it's been examined long enough.  maybe already.
 288
 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.
 296
 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.
 300 #else
 301
 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);
 313
 314     if (curr_node == NULL_POINTER) {
 315       // wayback has no children, so we can take action.
 316
 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) {
 320         break;
 321       }
 322
 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.
 329     } else {
 330       // okay, there's a node below here.  we will spider down to it.
 331       continue;
 332     }
 333   }
 334
 335 #endif
 336 }
 337
 338 tree *tree::parent() const { return (tree *)get_link(BACKWARDS_BRANCH); }
 339
 340 int tree::branches() const { return links() - 1; }
 341
 342 tree *tree::branch(int branch_number) const
 343 {
 344   branch_number++;
 345   bounds_return(branch_number, 1, branches(), NULL_POINTER);
 346   return (tree *)get_link(branch_number);
 347 }
 348
 349 int tree::which(tree *branch_to_find) const
 350 { return node::which((node *)branch_to_find) - 1; }
 351
 352 tree *tree::root() const
 353 {
 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);
 360 }
 361
 362 void tree::attach(tree *new_branch)
 363 {
 364   if (!new_branch) return;
 365   insert_link(links(), new_branch);
 366   new_branch->set_link(BACKWARDS_BRANCH, this);
 367 }
 368
 369 void tree::insert(int branch_place, tree *new_branch)
 370 {
 371   branch_place++;
 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);
 379 }
 380
 381 outcome tree::prune(tree *branch_to_cut)
 382 {
 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);
 386 }
 387
 388 outcome tree::prune_index(int branch_to_cut)
 389 {
 390   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;
 396 }
 397
 398 int tree::depth() const
 399 {
 400   tree *my_root = root();
 401   const tree *current_branch = this;
 402   int deep = 0;
 403   while (current_branch != my_root) {
 404     current_branch = current_branch->parent();
 405     deep++;
 406   }
 407   return deep;
 408 }
 409
 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
 413 {
 414 if (to_follow.size()) {}
 415 /*
 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();
 426   }
 427   // the order of things on the stack needs to be reversed now.
 428 //  path to_return = new stack(*to_accumulate.invert());
 429 //  return to_return;
 430   to_accumulate.invert();
 431   return to_accumulate;
 432 */
 433 return false;//temp.
 434 }
 435
 436 //hmmm: need text form!
 437
 438 tree::iterator tree::start(traversal_directions direction) const
 439 { return iterator(this, direction); }
 440
 441 }  // namespace.
 442