[80]  1  /********************************************************************** <BR>


 2  This file is part of Crack dot Com's free source code release of


 3  Golgotha. <a href="http://www.crack.com/golgotha_release"> <BR> for


 4  information about compiling & licensing issues visit this URL</a>


 5  <PRE> If that doesn't help, contact Jonathan Clark at


 6  golgotha_source@usa.net (Subject should have "GOLG" in it)


 7  ***********************************************************************/


 8 


 9  #include "ttree.hh"


 10 


 11  void i4_base_ternary_tree::iterator::next()


 12  //{{{


 13  {


 14  current=0;


 15  while (!current)


 16  {


 17  if (end())


 18  return;


 19 


 20  // get current stack context


 21  node *n = node_stack[node_stack.size()1];


 22  int i = index_stack[index_stack.size()1]++;


 23 


 24  switch(i)


 25  {


 26  case 0:


 27  // traverse lo branch


 28  push(n>lo);


 29  break;


 30  case 1:


 31  // add character to current word


 32  if (pos<maxlen) buff[pos] = n>ch;


 33  pos++;


 34 


 35  if (n>ch)


 36  // traverse remaining word


 37  push(n>eq);


 38  else


 39  // found next valid word


 40  current = n;


 41  break;


 42  case 2:


 43  // remove character


 44  pos;


 45 


 46  // traverse hi branch;


 47  push(n>hi);


 48  break;


 49  case 3:


 50  // go up stack


 51  pop();


 52  break;


 53  }


 54  }


 55  }


 56  //}}}


 57 


 58  i4_bool i4_base_ternary_tree::unlink(node **o, const CHAR *s, void **old_data)


 59  //{{{


 60  // recursively traverses the tree to remove a key/value pair


 61  {


 62  node *n = *o;


 63 


 64  if (!n)


 65  return 0;


 66 


 67  i4_bool ret;


 68  i4_bool found=i4_F;


 69 


 70  if (*s < n>ch)


 71  ret = unlink(&n>lo, s, old_data);


 72  else if (*s > n>ch)


 73  ret = unlink(&n>hi, s, old_data);


 74  else if (*s)


 75  ret = unlink(&n>eq, s+1, old_data);


 76  else


 77  {


 78  ret = found = i4_T;


 79  // store old data


 80  if (old_data) *old_data = n>data();


 81  }


 82 


 83  if (found  !n>eq)


 84  {


 85  // node is either the terminator to be removed, or a node that now has no continuation,


 86  // so we should delete it, like deleting out of a binary tree


 87 


 88  if (!n>lo && !n>hi)


 89  // no children, just axe me


 90  *o=0;


 91  else if (!n>lo  !n>hi)


 92  // one child, just bump child up


 93  *o = n>lo? n>lo : n>hi;


 94  else


 95  {


 96  // two children, find succesor to replace me


 97 


 98  // find the successor


 99  node **psplice, *splice;


 100  psplice = &n>hi;


 101  while ((splice = *psplice)>lo)


 102  psplice = &splice>lo;


 103 


 104  // unlink successor from its parent


 105  *psplice = splice>hi;


 106 


 107  // splice successor in


 108  splice>lo = n>lo;


 109  splice>hi = n>hi;


 110  *o = splice;


 111  }


 112 


 113  heap.free(n);


 114  }


 115 


 116  return ret;


 117  }


 118  //}}}


 119 


 120  i4_base_ternary_tree::node *i4_base_ternary_tree::find_node(const CHAR *s) const


 121  //{{{


 122  {


 123  node *n=root;


 124 


 125  while (n)


 126  {


 127  if (*s < n>ch) n = n>lo;


 128  else if (*s > n>ch) n = n>hi;


 129  else if (*s) { n = n>eq; s++; }


 130  else return n;


 131  }


 132  return 0;


 133  }


 134  //}}}


 135 


 136  i4_bool i4_base_ternary_tree::add(const CHAR *s, void *new_data, i4_bool replace, void **old_data)


 137  //{{{


 138  {


 139  i4_bool collide = i4_T;


 140  node **p=&root, *n;


 141 


 142  while (1)


 143  {


 144  n = *p;


 145 


 146  if (!n)


 147  {


 148  // create new node


 149  n = heap.alloc();


 150  n>ch = *s;


 151  n>lo = n>hi = n>eq = 0;


 152  collide = i4_F;


 153  *p = n;


 154  }


 155 


 156  if (*s < n>ch) p = &n>lo;


 157  else if (*s > n>ch) p = &n>hi;


 158  else if (*s) { p = &n>eq; s++; }


 159  else


 160  {


 161  if (old_data)


 162  *old_data = n>data(); // store old data


 163  if (!collide  replace)


 164  n>set_data(new_data); // store new data


 165  return collide;


 166  }


 167  }


 168  }


 169  //}}}


 170 


 171  //{{{ Emacs Locals


 172  // Local Variables:


 173  // foldedfile: t


 174  // End:


 175  //}}}

