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 = NIL;
  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 = NIL;
 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, NIL); }
 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
 282   // iterate over the child nodes and whack each individually.
 283   while (branches()) delete branch(0);
 284     // this relies on the child getting out of our branch list.
 285 }
 286
 287 tree *tree::parent() const { return (tree *)get_link(BACKWARDS_BRANCH); }
 288
 289 int tree::branches() const { return links() - 1; }
 290
 291 tree *tree::branch(int branch_number) const
 292 {
 293   branch_number++;
 294   bounds_return(branch_number, 1, branches(), NIL);
 295   return (tree *)get_link(branch_number);
 296 }
 297
 298 int tree::which(tree *branch_to_find) const
 299 { return node::which((node *)branch_to_find) - 1; }
 300
 301 tree *tree::root() const
 302 {
 303   const tree *traveler = this;
 304   // keep looking at the backwards branch until it is a NIL.  the tree with
 305   // a NIL BACKWARDS_BRANCH is the root.  return that tree.
 306   while (traveler->get_link(BACKWARDS_BRANCH))
 307     traveler = (tree *)traveler->get_link(BACKWARDS_BRANCH);
 308   return const_cast<tree *>(traveler);
 309 }
 310
 311 void tree::attach(tree *new_branch)
 312 {
 313   if (!new_branch) return;
 314   insert_link(links(), new_branch);
 315   new_branch->set_link(BACKWARDS_BRANCH, this);
 316 }
 317
 318 void tree::insert(int branch_place, tree *new_branch)
 319 {
 320   branch_place++;
 321   insert_link(links(), NIL);
 322   if (branch_place >= links())
 323     branch_place = links() - 1;
 324   for (int i = links() - 1; i > branch_place; i--)
 325     set_link(i, get_link(i-1));
 326   set_link(branch_place, new_branch);
 327   new_branch->set_link(BACKWARDS_BRANCH, this);
 328 }
 329
 330 outcome tree::prune(tree *branch_to_cut)
 331 {
 332   int branch_number = which(branch_to_cut);
 333   if (branch_number == basis::common::NOT_FOUND) return basis::common::NOT_FOUND;
 334   return prune_index(branch_number);
 335 }
 336
 337 outcome tree::prune_index(int branch_to_cut)
 338 {
 339   branch_to_cut++;
 340   bounds_return(branch_to_cut, 1, branches(), basis::common::NOT_FOUND);
 341   tree *that_branch = (tree *)get_link(branch_to_cut);
 342   that_branch->set_link(BACKWARDS_BRANCH, NIL);
 343   zap_link(branch_to_cut);
 344   return basis::common::OKAY;
 345 }
 346
 347 int tree::depth() const
 348 {
 349   tree *my_root = root();
 350   const tree *current_branch = this;
 351   int deep = 0;
 352   while (current_branch != my_root) {
 353     current_branch = current_branch->parent();
 354     deep++;
 355   }
 356   return deep;
 357 }
 358
 359 //probably okay; we want to use this function rather than non-existent
 360 //node base function which isn't implemented yet.
 361 bool tree::generate_path(path &to_follow) const
 362 {
 363 if (to_follow.size()) {}
 364 /*
 365   tree *traveller = this;
 366   path to_accumulate(root());
 367   while (traveller->parent() != NIL) {
 368 //    int branch_number = traveller->parent()->which(traveller);
 369 //    if (branch_number == BRANCH_NOT_FOUND) non_continuable_error
 370 //      (class_name(), "generate_path", "branch not found during path construction");
 371 //    chunk *to_stuff = new chunk
 372 //      (SELF_OWNED, (byte *)&branch_number, sizeof(int));
 373     to_accumulate.push(traveller);
 374     traveller = traveller->parent();
 375   }
 376   // the order of things on the stack needs to be reversed now.
 377 //  path to_return = new stack(*to_accumulate.invert());
 378 //  return to_return;
 379   to_accumulate.invert();
 380   return to_accumulate;
 381 */
 382 return false;//temp.
 383 }
 384
 385 //hmmm: need text form!
 386
 387 tree::iterator tree::start(traversal_directions direction) const
 388 { return iterator(this, direction); }
 389
 390 }  // namespace.
 391