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
  21 //#define DEBUG_TREE
  22   // uncomment if you want lots of debugging info.
  23
  24 #undef LOG
  25 #define LOG(s) CLASS_EMERGENCY_LOG(program_wide_logger::get(), s)
  26
  27 using namespace basis;
  28
  29 namespace nodes {
  30
  31 const int BACKWARDS_BRANCH = 0;
  32   // BACKWARDS_BRANCH is the branch from this tree to its parent.  this is
  33   // steeped in the perspective that the root is the backwards direction (where
  34   // we came from, in a sense) and that the children of this node are the
  35   // forwards direction.
  36
  37 //////////////
  38
  39 // iterator methods:
  40
  41 tree::iterator::iterator(const tree *initial, traversal_directions direction)
  42 : path(initial), _order(direction), _aim(AWAY_FROM_ROOT)
  43 {
  44 }
  45
  46 tree::iterator::~iterator() { while (size()) pop(); }
  47
  48 bool tree::iterator::next_node(tree *&to_return)
  49 {
  50 #ifdef DEBUG_TREE
  51   FUNCDEF("next_node");
  52 #endif
  53   to_return = NULL_POINTER;
  54 #ifdef DEBUG_TREE
  55   if ( (_order != to_branches)
  56       && (_order != reverse_branches) ) {
  57     if (_aim == AWAY_FROM_ROOT) LOG("going down")
  58     else LOG("going up");
  59   }
  60 #endif
  61   switch (_order) {
  62     case prefix: {
  63       if (_aim == AWAY_FROM_ROOT) {
  64         // going down means this is the first time we have seen the current top
  65         // node on the stack.
  66         to_return = (tree *)(*this)[size() - 1];
  67 #ifdef DEBUG_TREE
  68 //        LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s());
  69         if (to_return->branches()) LOG("pushing 0")
  70         else LOG("switching direction");
  71 #endif
  72         if (to_return->branches())
  73           push(to_return->branch(0));
  74         else
  75           _aim = TOWARD_ROOT;
  76       } else {
  77         // going up means that we need to get rid of some things before we
  78         // start seeing new nodes again.
  79         if (size() == 1) return false;
  80           // the last node has been seen....
  81         tree *last = (tree *)pop();
  82         tree *current_tree = (tree *)current();
  83         int lastnum = current_tree->which(last);
  84 #ifdef DEBUG_TREE
  85         if (lastnum < current_tree->branches() - 1)
  86           LOG(a_sprintf("going down %d", lastnum+1))
  87         else LOG("still going up");
  88 #endif
  89         if (lastnum < current_tree->branches() - 1) {
  90           _aim = AWAY_FROM_ROOT;
  91           push(current_tree->branch(lastnum + 1));
  92         }  // else still going up.
  93       }
  94       break;
  95     }
  96     case infix: {
  97       if (_aim == AWAY_FROM_ROOT) {
  98         // going down means starting on the left branch.
  99         tree *temp = (tree *)current();
 100 #ifdef DEBUG_TREE
 101         if (temp->branches()) LOG("pushing 0")
 102         else LOG("switching direction");
 103 #endif
 104         if (temp->branches()) push(temp->branch(0));
 105         else {
 106           _aim = TOWARD_ROOT;
 107           to_return = (tree *)current();
 108 #ifdef DEBUG_TREE
 109 //          LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s()));
 110 #endif
 111         }
 112       } else {
 113         // going up means that the left branch is done and we need to either
 114         // keep going up or go down the right branch.
 115         if (size() == 1) return false;
 116           // the last node has been seen....
 117         tree *last = (tree *)pop();
 118         tree *current_tree = (tree *)current();
 119         int lastnum = current_tree->which(last);
 120 #ifdef DEBUG_TREE
 121         if (lastnum < 1) LOG(a_sprintf("going down %d", lastnum+1))
 122         else LOG("still going up");
 123 #endif
 124         if (lastnum < 1) {
 125           _aim = AWAY_FROM_ROOT;
 126           to_return = (tree *)current();
 127 #ifdef DEBUG_TREE
 128 ///          LOG(a_sprintf("[%s] ", to_return->get_contents()->held().s()));
 129 #endif
 130           push(current_tree->branch(lastnum + 1));
 131         }  // else still going up.
 132       }
 133       break;
 134     }
 135     case to_branches: {
 136       if (_aim == TOWARD_ROOT) return false;
 137       else {
 138         if (size() == 1) {
 139           tree *temp = (tree *)current();
 140           if (!temp->branches())
 141             _aim = TOWARD_ROOT;
 142           else
 143             push(temp->branch(0));
 144         } else {
 145           tree *last = (tree *)pop();
 146           tree *curr = (tree *)current();
 147           int lastnum = curr->which(last);
 148           if (lastnum < curr->branches() - 1)
 149             push(curr->branch(lastnum + 1));
 150           else _aim = TOWARD_ROOT;
 151           to_return = last;
 152         }
 153       }
 154       break;
 155     }
 156     case reverse_branches: {
 157       if (_aim == TOWARD_ROOT) return false;
 158       else {
 159         if (size() == 1) {
 160           tree *temp = (tree *)current();
 161           if (!temp->branches()) _aim = TOWARD_ROOT;
 162           else push(temp->branch(temp->branches() - 1));
 163         } else {
 164           tree *last = (tree *)pop();
 165           tree *curr = (tree *)current();
 166           int lastnum = curr->which(last);
 167           if (lastnum > 0) push(curr->branch(lastnum - 1));
 168           else _aim = TOWARD_ROOT;
 169           to_return = last;
 170         }
 171       }
 172       break;
 173     }
 174     default:   // intentional fall-through to postfix.
 175     case postfix: {
 176       if (_aim == AWAY_FROM_ROOT) {
 177         // going down means that the bottom is still being sought.
 178         tree *temp = (tree *)current();
 179 #ifdef DEBUG_TREE
 180         if (temp->branches()) LOG("pushing 0")
 181         else LOG("switching direction");
 182 #endif
 183         if (temp->branches()) push(temp->branch(0));
 184         else _aim = TOWARD_ROOT;
 185       } else {
 186         // going up means that all nodes below current have been hit.
 187         if (!size()) return false;  // the last node has been seen...
 188         else if (size() == 1) {
 189           to_return = (tree *)pop();
 190             // this is the last node.
 191           return true;
 192         }
 193         tree *last = (tree *)pop();
 194         to_return = last;
 195 #ifdef DEBUG_TREE
 196 ///        LOG(a_sprintf("[%s] ", to_return->get_contents()->held()));
 197 #endif
 198         tree *current_tree = (tree *)current();
 199         int lastnum = current_tree->which(last);
 200 #ifdef DEBUG_TREE
 201         if (lastnum < current_tree->branches() - 1)
 202           LOG(a_sprintf("going down %d", lastnum+1))
 203         else LOG("still going up");
 204 #endif
 205         if (lastnum < current_tree->branches() - 1) {
 206           _aim = AWAY_FROM_ROOT;
 207           push(current_tree->branch(lastnum + 1));
 208         }  // else still going up.
 209       }
 210       break;
 211     }
 212   }
 213   return true;
 214     // it is assumed that termination conditions cause a return earlier on.
 215 }
 216
 217 void tree::iterator::whack(tree *to_whack)
 218 {
 219 #ifdef DEBUG_TREE
 220   FUNCDEF("whack");
 221 #endif
 222   if (!to_whack) return;  // that's a bad goof.
 223   if (size()) {
 224     if (to_whack == current()) {
 225       // we found that this is the one at the top right now.
 226       pop();
 227 #ifdef DEBUG_TREE
 228       LOG("found node in current top; removing it there.");
 229 #endif
 230     } else if (to_whack->parent() == current()) {
 231       // the parent is the current top.  make sure we don't mess up traversal.
 232 #ifdef DEBUG_TREE
 233       LOG("found node's parent as current top; don't know what to do.");
 234 #endif
 235     } else {
 236 #ifdef DEBUG_TREE
 237       LOG("found no match for either node to remove or parent in path.");
 238 #endif
 239     }
 240   }
 241   tree *parent = to_whack->parent();
 242   if (!parent) {
 243 #ifdef DEBUG_TREE
 244     LOG("no parent node for the one to whack!  would have whacked "
 245         "root of tree!");
 246 #endif
 247   } else {
 248     parent->prune(to_whack);
 249     WHACK(to_whack);
 250   }
 251 }
 252
 253 tree *tree::iterator::next()
 254 {
 255 #ifdef DEBUG_TREE
 256   FUNCDEF("next");
 257 #endif
 258   tree *to_return = NULL_POINTER;
 259   bool found_tree = false;
 260   while (!found_tree) {
 261     bool still_running = next_node(to_return);
 262     if (to_return || !still_running) found_tree = true;
 263   }
 264   return to_return;
 265 }
 266
 267 //////////////
 268
 269 // tree methods:
 270
 271 tree::tree()
 272 : node(1)
 273 { set_link(BACKWARDS_BRANCH, NULL_POINTER); }
 274
 275 tree::~tree()
 276 {
 277   // must at least unhook ourselves from the parent so we don't become a lost
 278   // cousin.
 279   tree *my_parent = parent();
 280   if (my_parent) my_parent->prune(this);
 281   my_parent = NULL_POINTER;  // disavow since we are loose now.
 282
 283 #if 0
 284
 285   //original version suffers from being too recursive on windoze,
 286   //which blows out the stack.  linux never showed this problem.  so, i
 287   //guess i'm glad i tested on windows.
 288   //anyway, it's a general problem for a degenerate tree like the one
 289   //i've constructed.  current version has ~40000 direct descendants of
 290   //the root in a single line, so the stack has to support 40000 frames
 291   //for the delete implementation below to work.
 292
 293   // iterate over the child nodes and whack each individually.
 294   while (branches()) delete branch(0);
 295     // this relies on the child getting out of our branch list.
 296 #else
 297
 298   // newer version of delete doesn't recurse; it just iterates instead,
 299   // which avoids the massive recursive depth of the original approach.
 300   tree *curr_node = this;
 301   while (curr_node != NULL_POINTER) {
 302     // make a breadcrumb for getting back to 'here' in the tree.
 303     tree *way_back = curr_node;
 304     // our main operation here is to go down a node without using any
 305     // stack frames.  so we just pick the first kid; it's either valid
 306     // or there are no kids at all.
 307     curr_node = curr_node->branch(0);
 308
 309     if (curr_node == NULL_POINTER) {
 310       // wayback has no children, so we can take action.
 311
 312       // if wayback is the same as "this", then we exit from iterations since
 313       // we've cleaned all the kids out.
 314       if (way_back == this) {
 315         break;
 316       }
 317
 318       // we want to whack the wayback node at this point, since it's a parent
 319       // with no kids, i.e. a leaf.  we've guaranteed we're not going beyond
 320       // our remit, since wayback is not the same node as the top level one
 321       // in the destructor (as long as there are no cycles in the tree...).
 322       curr_node = way_back->parent();  // go up in tree on next iteration.
 323       delete way_back;  // whack a node, finally.
 324
 325     } else {
 326       // okay, there's a node below here.  we will spider down to it.
 327       continue;
 328     }
 329
 330
 331   }
 332
 333 #endif
 334
 335
 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