Scid  4.6.5
strtree.h
Go to the documentation of this file.
1 //////////////////////////////////////////////////////////////////////
2 //
3 // FILE: strtree.h
4 // String tree template class
5 //
6 // Part of: Scid (Shane's Chess Information Database)
7 // Version: 1.0
8 //
9 // Notice: Copyright (c) 1999 Shane Hudson. All rights reserved.
10 //
11 // Author: Shane Hudson (sgh@users.sourceforge.net)
12 //
13 //////////////////////////////////////////////////////////////////////
14 
15 // String tree template class:
16 // Binary search tree for strings, with periodic rebalancing.
17 // Templatised for adding other data to nodes.
18 
19 // A StrTree operates in two modes: Tree and List mode.
20 
21 // Tree mode:
22 // First and Last are unused.
23 // Each Root[b] contains the binary search tree for all the nodes
24 // with a string starting with the character b, or NULL if no
25 // strings starting with b are in the tree.
26 
27 // List mode:
28 // First is the first node in the ordered linked list, and Last
29 // is the last node.
30 // Each Root[b] points to the first node in the linked list with
31 // a string starting with the character b, or NULL if no such node
32 // exists.
33 
34 // The methods Lookup(), Insert(), GetFirstMatches() convert the StrTree
35 // to Tree mode if necessary.
36 // The methods AddLast(), IterateStart() and LongestPrefix() convert
37 // to List mode if necessary.
38 
39 // When converting to Tree mode, the trees created are perfectly balanced.
40 // Converting between List and Tree modes takes linear time, but the
41 // current algorithm uses recursive function calls. The stack should
42 // not grow very deep, since each starting character has its own tree
43 // and trees are perfectly balanced when first created (by adding all the
44 // nodes in order with AddLast() instead of Insert()).
45 
46 // Advantages of the two modes:
47 // -- When adding data known to be in alphabetical order, AddLast()
48 // can be used for constant-time updates. Then, when the first
49 // insertion or lookup is done, the StrTree will get converted in
50 // linear time to a perfectly balanced tree for each starting
51 // character b.
52 // -- Iterating through all the nodes of a StrTree in alphabetical order
53 // is easy, by putting the StrTree in List mode first.
54 
55 
56 #ifndef SCID_STRTREE_H
57 #define SCID_STRTREE_H
58 
59 #include "common.h"
60 #include "misc.h"
61 #include <stdio.h>
62 
63 
64 
65 // nodeT template: a StrTree node.
66 template <class C>
67 struct nodeT {
68  char * name; // The string for this node.
69  C data; // Template-specific information.
72 };
73 
74 // There is one tree for each possible starting byte in a string:
75 const uint NUM_StrTrees = 256;
76 
77 template <class C>
78 class StrTree
79 {
80  private:
81 
82  uint TreeSize [NUM_StrTrees];
83  uint TotalSize;
84  uint TreeHeight;
85  bool TreeMode; // false for list layout, true for tree layout.
86 
87  bool AllocateStrings; // If false, caller will allocate strings.
88 
89  // Statistics:
90  uint Stat_InsertsNew;
91  uint Stat_InsertsFound;
92  uint Stat_Lookups;
93  uint Stat_LookupsFound;
94  uint Stat_StrCompares;
95  uint Stat_Rebalances;
96  uint SearchCharCount [NUM_StrTrees]; // For statistics, a count of how
97  // many search strings start with each char.
98 
99  protected:
100 
105 
106  private:
107 
108  void MakeSubList (nodeT<C> * node);
109  nodeT<C> * MakeSubTree (int size, uint depth);
110 
111  public:
112 #ifdef WINCE
113  void* operator new(size_t sz) {
114  void* m = my_Tcl_Alloc(sz);
115  return m;
116  }
117  void operator delete(void* m) {
118  my_Tcl_Free((char*)m);
119  }
120  void* operator new [] (size_t sz) {
121  void* m = my_Tcl_AttemptAlloc(sz);
122  return m;
123  }
124 
125  void operator delete [] (void* m) {
126  my_Tcl_Free((char*)m);
127  }
128 
129 #endif
130  StrTree();
131  ~StrTree();
132 
133  void DestroyTree (nodeT<C> * node);
134  void DestroyList ();
135 
136  // SetAllocateStrings(): sets the allocation mode. A true value means
137  // the StrTree explicitly allocates copies of names when inserting;
138  // false means it leaves the caller to set the name pointer.
139  // The mode can ONLY be changed for an empty tree!
140 
141  void SetAllocateStrings (bool b) {
142  if (TotalSize > 0) { AllocateStrings = b; }
143  }
144  bool GetAllocateStrings () { return AllocateStrings; }
145 
146  uint Size () { return TotalSize; }
147  uint Height() { return TreeHeight; }
148  uint FirstByteSize (byte b) { return TreeSize[b]; }
149 
150  void IterateStart() { Iterator = NULL; }
151  inline nodeT<C> * Iterate ();
152 
153  void MakeList ();
154  void MakeTree ();
155  void Rebalance () { MakeList(); MakeTree(); }
156 
157  nodeT<C> * Lookup (const char * str);
158  errorT Insert (const char * str, nodeT<C> ** returnNode);
159  errorT AddLast (const char * str, nodeT<C> ** returnNode);
160  nodeT<C> * LongestPrefix (const char * str);
161  nodeT<C> * Delete (const char * str);
162 
163  void FindMatches (const char * str, int strLen, nodeT<C> * node,
164  uint * matches, uint maxMatches, nodeT<C> ** array);
165  uint GetFirstMatches (const char * str, uint max, nodeT<C> ** results);
166 
167  void DumpStats (FILE * fp);
168  void DumpRecurse (FILE * fp, const nodeT<C> * node, int height);
169  void DumpTree (FILE * fp);
170 };
171 
172 
173 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
174 // StrTree Constructor.
175 //
176 template <class C>
178 {
179  TotalSize = 0;
180  TreeHeight = 0;
181  First = Last = Iterator = NULL;
182  TreeMode = true;
183 
184  // By default, the StrTree allocates strings itself:
185  AllocateStrings = 1;
186 
187  Stat_InsertsNew = Stat_InsertsFound = Stat_Lookups = 0;
188  Stat_LookupsFound = Stat_StrCompares = Stat_Rebalances = 0;
189 
190  for (uint i=0; i < NUM_StrTrees; i++) {
191  TreeSize[i] = 0;
192  Root[i] = NULL;
193  SearchCharCount[i] = 0;
194  }
195 }
196 
197 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
198 // StrTree Destructor
199 //
200 template <class C>
202 {
203  if (TreeMode) {
204  for (uint i=0; i < NUM_StrTrees; i++) {
205  DestroyTree (Root[i]);
206  }
207  } else {
208  DestroyList();
209  }
210 }
211 
212 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
213 // StrTree::DestroyTree(): recursively frees all nodes.
214 //
215 template <class C>
216 void
218 {
219  if (node == NULL) { return; }
220  DestroyTree (node->left);
221  DestroyTree (node->right);
222 #ifdef WINCE
223  if (AllocateStrings) { my_Tcl_Free((char*) node->name); }
224  my_Tcl_Free((char*) node);
225 #else
226  if (AllocateStrings) { delete[] node->name; }
227  delete node;
228 #endif
229 }
230 
231 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
232 // StrTree::DestroyList(): destroys the tree when in list form.
233 //
234 template <class C>
235 void
237 {
238  ASSERT (TreeMode == 0);
239  nodeT<C> * node = First;
240  nodeT<C> * temp;
241  while (node != NULL) {
242  temp = node->right;
243 #ifdef WINCE
244  if (AllocateStrings) { my_Tcl_Free((char*) node->name); }
245  my_Tcl_Free((char*) node);
246 #else
247  if (AllocateStrings) { delete[] node->name; }
248  delete node;
249 #endif
250  node = temp;
251  }
252 }
253 
254 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
255 // StrTree::Iterate(): used to successively grab each node in order.
256 //
257 template <class C>
258 inline nodeT<C> *
260 {
261  if (TreeMode) { MakeList(); }
262  if (Iterator == NULL) {
263  Iterator = First;
264  } else {
265  Iterator = Iterator->right;
266  }
267  return Iterator;
268 }
269 
270 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
271 // StrTree::MakeSubList(): recursively converts tree to list.
272 //
273 template <class C>
274 void
276 {
277  ASSERT (node != NULL);
278  if (node->left != NULL) { MakeSubList (node->left); }
279  if (Last == NULL) {
280  Last = First = node;
281  } else {
282  Last->right = node;
283  Last = node;
284  }
285  if (node->right != NULL) { MakeSubList (node->right); }
286 }
287 
288 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
289 // StrTree::MakeList(): Converts the tree to list format, so that it
290 // can be rebalanced with MakeTree() or iterated.
291 // Pre: tree structures, with Root[i] as the root of each tree of
292 // strings starting with i.
293 // Post: ordered linked list, with First as the 1st node, and Last as
294 // the last node. Root[i] points to the first node in the list
295 // whose string starts with i.
296 //
297 template <class C>
298 void
300  if (! TreeMode) { return; } // already have a List.
301  First = Last = NULL;
302 
303  for (uint i=0; i < NUM_StrTrees; i++) {
304  if (Root[i] != NULL) {
305  MakeSubList (Root[i]);
306  }
307  Root[i] = NULL;
308  }
309  if (Last != NULL) {
310  Last->right = NULL;
311  }
312 
313  // Now set each Root[i] to be the first node starting with 'i':
314 
315  nodeT<C> * node = First;
316  while (node != NULL) {
317  byte b = (byte) node->name[0];
318  if (Root[b] == NULL) {
319  Root[b] = node;
320  }
321  node = node->right;
322  }
323 
324  Iterator = NULL;
325  TreeHeight = 0;
326  TreeMode = false;
327 }
328 
329 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
330 // StrTree::MakeSubTree(): recursively converts list to tree.
331 //
332 template <class C>
333 nodeT<C> *
334 StrTree<C>::MakeSubTree (int size, uint depth)
335 {
336  if (size == 0) { return NULL; }
337  int nLeft = (size - 1) / 2;
338  int nRight = size - nLeft - 1;
339 
340  nodeT<C> * leftNode;
341  nodeT<C> * root;
342 
343  leftNode = MakeSubTree (nLeft, depth + 1);
344  ASSERT (First != NULL);
345  root = First;
346  First = First->right;
347  root->left = leftNode;
348  root->right = MakeSubTree (nRight, depth + 1);
349 
350  // Set TreeHeight if a new depth is reached:
351  if (depth > TreeHeight) { TreeHeight = depth; }
352 
353  return root;
354 }
355 
356 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
357 // StrTree::MakeTree(): Converts from list to tree structure.
358 // Pre: First is 1st node, right pointer of each node points to
359 // next node in the list.
360 // Post: Each Root[b] is the root of a perfectly balanced tree of
361 // all the nodes with string starting with the character 'b'.
362 //
363 template <class C>
364 void
366 {
367  if (TreeMode) { return; } // already have a Tree.
368  for (uint i=0; i < NUM_StrTrees; i++) {
369  if (TreeSize[i] == 0) {
370  Root[i] = NULL;
371  } else {
372  Root[i] = MakeSubTree (TreeSize[i], 1);
373  // Assert that this tree has nodes that start with the
374  // correct character:
375  ASSERT ((byte)(Root[i]->name[0]) == i);
376  }
377  }
378  First = Last = Iterator = NULL;
379  Stat_Rebalances++;
380  TreeMode = true;
381 }
382 
383 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
384 // StrTree::Lookup():
385 // Returns a pointer to the located node, or NULL.
386 //
387 template <class C>
388 nodeT<C> *
389 StrTree<C>::Lookup (const char * str)
390 {
391  if (! TreeMode) { MakeTree(); }
392  Stat_Lookups++;
393  SearchCharCount[(byte) *str]++;
394 
395  nodeT<C> * node;
396  node = Root [(byte) *str];
397 
398  while (node != NULL) {
399  Stat_StrCompares++;
400  int result = strCompare(str, node->name);
401 
402  if (result < 0) {
403  node = node->left;
404  } else if (result > 0) {
405  node = node->right;
406  } else {
407  Stat_LookupsFound++;
408  return node;
409  }
410  }
411  return NULL;
412 }
413 
414 
415 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
416 // StrTree::Insert()
417 // Inserts a string. Returns OK if it was not in the tree, or
418 // returns ERROR_Exists if the string is already in the tree.
419 // In either case, *returnNode is set to the found or inserted node.
420 //
421 template <class C>
422 errorT
423 StrTree<C>::Insert (const char * str, nodeT<C> ** returnNode)
424 {
425  if (! TreeMode) { MakeTree(); }
426 
427  uint treeNumber = (byte) *str;
428 
429  nodeT<C> * parent = NULL;
430  nodeT<C> * node = Root [treeNumber];
431  uint height = 1;
432  enum {SIDE_Left, SIDE_Right} side = SIDE_Left;
433 
434  // Find the node or the place in the tree to insert it:
435 
436  while (node != NULL) {
437  height++;
438  Stat_StrCompares++;
439 
440  int res = strCompare(str, node->name);
441  if (res < 0) { // Go into left subtree:
442  side = SIDE_Left;
443  parent = node;
444  node = node->left;
445 
446  } else if (res > 0) { // Go into right subtree:
447  side = SIDE_Right;
448  parent = node;
449  node = node->right;
450 
451  } else { // Match!
452  Stat_InsertsFound++;
453  if (returnNode != NULL) { *returnNode = node; }
454  return ERROR_Exists;
455  }
456  }
457 
458  // If we reach here, we must add a new node:
459 
460  Stat_InsertsNew++;
461 #ifdef WINCE
462  node = (nodeT<C> *) my_Tcl_Alloc(sizeof( nodeT<C>));
463 #else
464  node = new nodeT<C>;
465 #endif
466  if (AllocateStrings) { // Allocate memory for the name string:
467  node->name = strDuplicate (str);
468  } else { // Leave it to the caller to set the name string:
469  node->name = NULL;
470  }
471  node->left = node->right = NULL;
472  if (parent) {
473  if (side == SIDE_Left) {
474  parent->left = node;
475  } else {
476  parent->right = node;
477  }
478  } else {
479  Root [treeNumber] = node;
480  }
481 
482  TreeSize [treeNumber]++;
483  TotalSize++;
484 
485  // Set new maximum tree height:
486  if (height > TreeHeight) {
487  // It should only have grown by 1 at most!
488  // ASSERT (height == TreeHeight + 1);
489  TreeHeight = height;
490  }
491  if (returnNode != NULL) {
492  *returnNode = node;
493  }
494 
495  return OK;
496 }
497 
498 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
499 // StrTree::AddLast():
500 // Adds a new node to the tree, assuming that it will be the
501 // LAST node in alphabetical order.
502 // If not already stored as a list, the tree will be converted
503 // to a list before adding the node.
504 // Returns: OK if successful, or ERROR_Corrupt if the name was
505 // not greater alphabetically than the existing last node.
506 //
507 template <class C>
508 errorT
509 StrTree<C>::AddLast (const char * str, nodeT<C> ** returnNode)
510 {
511  if (TreeMode) { MakeList(); }
512  if (TotalSize > 0) {
513  // Make sure this string is larger than the previous string added:
514  // Only do this if the string starts with the same character as the
515  // previous string, to avoid problems with the string comparison
516  // of characters clashing with the order of the root nodes (string
517  // comparison uses signed chars, but the Root[] array is of unsigned
518  // chars).
519 
520  if (*str == *(Last->name) &&
521  strCompare_INLINE (str, Last->name) <= 0) {
522  return ERROR_Corrupt;
523  }
524  }
525 #ifdef WINCE
526  nodeT<C> * node = (nodeT<C> *) my_Tcl_Alloc(sizeof(nodeT<C>));
527 #else
528  nodeT<C> * node = new nodeT<C>;
529 #endif
530  if (AllocateStrings) { // Allocate memory for the name string:
531  node->name = strDuplicate (str);
532  } else { // Leave it to the caller to set the name string:
533  node->name = NULL;
534  }
535  node->right = NULL;
536 
537  if (TotalSize == 0) {
538  First = Last = node;
539  } else {
540  Last->right = node;
541  Last = node;
542  }
543 
544  byte b = (byte) *str;
545  if (Root[b] == NULL) {
546  Root[b] = node;
547  }
548  TreeSize[b]++;
549  TotalSize++;
550 
551  if (returnNode) { *returnNode = node; }
552 
553  return OK;
554 }
555 
556 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
557 // StrTree::FindMatches():
558 // Finds the first 'maxMatches' matching nodes for the string 'str'
559 // which has length 'strLen', and places them in the node array
560 // 'array'. Recursively calls itself for subtrees.
561 //
562 template <class C>
563 void
564 StrTree<C>::FindMatches (const char * str, int strLen, nodeT<C> * node,
565  uint * matches, uint maxMatches, nodeT<C> ** array)
566 {
567  if (node == NULL) return;
568  if (*matches >= maxMatches) return;
569 
570  int result = strncmp (str, node->name, strLen);
571  if (result > 0) {
572  // str is bigger than this node, we must move to the right:
573  FindMatches (str, strLen, node->right, matches, maxMatches, array);
574 
575  } else if (result < 0) {
576  // Move to the left:
577  FindMatches (str, strLen, node->left, matches, maxMatches, array);
578 
579  } else { // Match!
580  // First, look for more matches in the left subtree:
581 
582  FindMatches (str, strLen, node->left, matches, maxMatches, array);
583 
584  // Now, is there room for this match to be added?
585 
586  if (*matches >= maxMatches) { return; }
587  array[*matches] = node;
588  *matches += 1;
589 
590  // Now look for more in the right subtree, if appropriate:
591 
592  if (*matches >= maxMatches) { return; }
593  FindMatches (str, strLen, node->right, matches, maxMatches, array);
594  }
595 }
596 
597 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
598 // StrTree::GetFirstMatches():
599 // Finds the first 'maxMatches' string matches for 'str' and
600 // places them in the node array 'array'.
601 // Calls FindMatches() with the appropriate Root node, which
602 // recurses through that tree.
603 // Returns the number of matches found, which will be in the
604 // range [0 .. maxMatches].
605 //
606 template <class C>
607 uint
608 StrTree<C>::GetFirstMatches (const char * str, uint maxMatches,
609  nodeT<C> ** array)
610 {
611  ASSERT (array != NULL && maxMatches > 0);
612  if (! TreeMode) { MakeTree(); }
613  uint matches = 0;
614  nodeT<C> * root = Root[(byte) *str];
615  FindMatches (str, strlen(str), root, &matches, maxMatches, array);
616  return matches;
617 }
618 
619 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
620 // StrTree::LongestPrefix():
621 // Finds the longest string in the tree that is a prefix
622 // of the input string.
623 //
624 // Example: if the input string starts "therein ..." and
625 // both "the" and "there" are in the tree, then the node
626 // for "there" will be returned.
627 //
628 // Returns NULL if no prefix string exists in the tree.
629 //
630 template <class C>
631 nodeT<C> *
632 StrTree<C>::LongestPrefix (const char * str)
633 {
634  if (TreeMode) { MakeList(); }
635 
636  nodeT<C> * longestMatch = NULL;
637  nodeT<C> * node;
638 
639  node = Root [(byte) *str];
640 
641  while (node != NULL) {
642  if (node->name[0] != *str) { break; }
643  if (strIsPrefix (node->name, str)) {
644  longestMatch = node;
645  }
646  node = node->right;
647  }
648 
649  return longestMatch;
650 }
651 
652 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
653 // StrTree::Delete():
654 // Deletes the node matching the key string.
655 // Returns: the node (if the key was deleted), or NULL
656 // if the key was not in the tree.
657 //
658 // The reason it returns the node that is extracted from the tree
659 // instead of deleting it, is so the caller can free any memory
660 // in the node's data field first. So it is the caller's
661 // responsibility to actually delete the node returned.
662 // The only memory this function deletes is the name, if it was
663 // allocated by the StrTree at insertion (that is, if AllocateStrings
664 // is true).
665 //
666 // This function takes O(log N) time, and guarantees to keep the
667 // tree height the same or decrease it -- some naive implementations
668 // of deletion in a binary search tree can actually increase the
669 // height.
670 //
671 template <class C>
672 nodeT<C> *
673 StrTree<C>::Delete (const char * key)
674 {
675  ASSERT (key != NULL);
676 
677  nodeT<C> ** parentPtr; // Address of the parent pointer.
678  nodeT<C> * toDelete; // Node that will be deleted.
679  nodeT<C> * child; // Node that will replace toDelete in the tree.
680 
681  if (! TreeMode) { MakeTree(); }
682 
683  // First, find the node to be deleted, and the address of the parent
684  // pointer that points to it, so that can be changed:
685  parentPtr = &(Root[(byte) *key]);
686  toDelete = Root[(byte) *key];
687 
688  while (toDelete) {
689  Stat_StrCompares++;
690  int result = strCompare (key, toDelete->name);
691 
692  if (result < 0) {
693  // Move into left subtree:
694  parentPtr = &(toDelete->left);
695  toDelete = toDelete->left;
696 
697  } else if (result > 0) {
698  // Move into right subtree:
699  parentPtr = &(toDelete->right);
700  toDelete = toDelete->right;
701 
702  } else { // Found the node to be deleted:
703  break;
704  }
705  }
706 
707  if (toDelete == NULL) { return NULL; }
708 
709  // Now, we need to find a candidate child node that will move to
710  // the place in the tree where toDelete is.
711  // First we check simple cases: if toDelete has an empty subtree
712  // pointer, the other subtree (which may/may not be empty) is the
713  // child to replace toDelete.
714  //
715  // The next simple case is, if toDelete->right has no left subtree,
716  // then toDelete->right is the candidate to replace toDelete.
717  //
718  // If none of these simple cases works, we find the next node after
719  // toDelete in its right subtree (by going right once then left as
720  // far as possible) and that node (which may be a leaf node, or may
721  // have a right subtree, but obviously cannot have a left subtree)
722  // is the candidate to replace toDelete.
723 
724  // First the three easy cases: see the comment above.
725  if (toDelete->left == NULL) {
726  child = toDelete->right;
727  } else if (toDelete->right == NULL) {
728  child = toDelete->left;
729  } else if (toDelete->right->left == NULL) {
730  child = toDelete->right;
731  child->left = toDelete->left;
732  } else {
733  // Now the last case which involves finding the closest
734  // successor of toDelete in its right subtree:
735 
736  ASSERT (toDelete->right->left);
737  // searchNode is set to the parent of the successor of toDelete
738  // so searchNode->left is the actual successor. This is so we
739  // can snip searchNode->left (making it searchNode->left->right)
740  // to remove the candidate from that part of the tree.
741 
742  nodeT<C> * searchNode;
743  searchNode = toDelete->right;
744  while (searchNode->left->left) { searchNode = searchNode->left; }
745  ASSERT (searchNode->left);
746  child = searchNode->left;
747  searchNode->left = searchNode->left->right;
748 
749  // child will replace toDelete, so it needs toDelete's children as
750  // its children:
751  child->left = toDelete->left;
752  child->right = toDelete->right;
753  }
754 
755  // Finally, we can delete toDelete and set the parent pointer to
756  // the child that replaces toDelete.
757  // Note that child could be NULL here.
758 
759  *parentPtr = child;
760  TotalSize--;
761  TreeSize[(byte) *key]--;
762 
763  // We only delete toDelete->name if we allocated it, otherwise it
764  // was set explicitly by the caller when it was inserted.
765  if (AllocateStrings) {
766 #ifdef WINCE
767  my_Tcl_Free(toDelete->name);
768 #else
769  delete[] toDelete->name;
770 #endif
771  toDelete->name = NULL;
772  }
773 
774  // Finally, we return the deleted node, setting its children nodes
775  // to NULL just for safety. The caller can do what it needs with
776  // the node data and then delete the node itself.
777 
778  toDelete->left = toDelete->right = NULL;
779  return toDelete;
780 }
781 
782 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
783 // StrTree::DumpTree():
784 // Dumps a visual representation of the tree to an open file.
785 //
786 template <class C>
787 void
788 StrTree<C>::DumpRecurse (FILE * fp, const nodeT<C> * node, int height)
789 {
790  if (node != NULL) {
791  DumpRecurse (fp, node->right, height + 2);
792  for (int i=0; i < height; i++) { putc (' ', fp); }
793  fprintf (fp, "%s\n", node->name);
794  DumpRecurse (fp, node->left, height + 2);
795  }
796 }
797 
798 template <class C>
799 void
801 {
802  ASSERT (fp != NULL);
803  if (! TreeMode) { MakeTree(); }
804  fprintf (fp, "Height: %u\n", TreeHeight);
805  for (uint i=0; i < NUM_StrTrees; i++) {
806  DumpRecurse (fp, Root[i], 0);
807  }
808 }
809 
810 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
811 // StrTree::DumpStats():
812 // Dump statistics to an open file.
813 //
814 template <class C>
815 void
817 {
818  fprintf (fp, "Insertions: %u found, %u new, %u total\n",
819  Stat_InsertsFound, Stat_InsertsNew,
820  Stat_InsertsFound + Stat_InsertsNew);
821  fprintf (fp, "Lookups: %u, of which %u were successfull\n",
822  Stat_Lookups, Stat_LookupsFound);
823  fprintf (fp, "Rebalances: %u\n", Stat_Rebalances);
824  fprintf (fp, "String comparisons: %u\n", Stat_StrCompares);
825  fprintf (fp, "First chars: actual / searched\n");
826  for (int i=0; i < 256; i++) {
827  if (TreeSize[i] || SearchCharCount[i]) {
828  fprintf (fp, " %c %7u %7u\n", i, TreeSize[i],
829  SearchCharCount[i]);
830  }
831  }
832 }
833 
834 #endif // ifndef SCID_STRTREE_H
835 
836 //////////////////////////////////////////////////////////////////////
837 // EOF: strtree.h
838 //////////////////////////////////////////////////////////////////////
839 
nodeT< C > * Delete(const char *str)
Definition: strtree.h:673
Definition: strtree.h:67
unsigned char byte
Definition: common.h:97
nodeT< C > * Last
Definition: strtree.h:103
void DumpRecurse(FILE *fp, const nodeT< C > *node, int height)
Definition: strtree.h:788
char * name
Definition: strtree.h:68
uint FirstByteSize(byte b)
Definition: strtree.h:148
errorT AddLast(const char *str, nodeT< C > **returnNode)
Definition: strtree.h:509
const errorT OK
Definition: error.h:23
bool strIsPrefix(const char *prefix, const char *longStr)
Definition: misc.h:412
char * strDuplicate(const char *original)
Definition: misc.cpp:239
uint max(int a, int b)
Definition: crosstab.cpp:237
void IterateStart()
Definition: strtree.h:150
#define ASSERT(f)
Definition: common.h:67
const uint NUM_StrTrees
Definition: strtree.h:75
void DumpTree(FILE *fp)
Definition: strtree.h:800
errorT Insert(const char *str, nodeT< C > **returnNode)
Definition: strtree.h:423
nodeT< C > * Iterator
Definition: strtree.h:104
nodeT< C > * LongestPrefix(const char *str)
Definition: strtree.h:632
sizew
Definition: board.tcl:619
void MakeTree()
Definition: strtree.h:365
uint32_t uint
Definition: common.h:99
nodeT< C > * right
Definition: strtree.h:71
void DumpStats(FILE *fp)
Definition: strtree.h:816
~StrTree()
Definition: strtree.h:201
void DestroyTree(nodeT< C > *node)
Definition: strtree.h:217
void MakeList()
Definition: strtree.h:299
nodeT< C > * First
Definition: strtree.h:102
uint Height()
Definition: strtree.h:147
nodeT< C > * Iterate()
Definition: strtree.h:259
unsigned short errorT
Definition: error.h:20
void Rebalance()
Definition: strtree.h:155
void DestroyList()
Definition: strtree.h:236
void SetAllocateStrings(bool b)
Definition: strtree.h:141
const errorT ERROR_Corrupt
Definition: error.h:46
resultsreportType fmt
Definition: optable.tcl:642
nodeT< C > * left
Definition: strtree.h:70
C data
Definition: strtree.h:69
nodeT< C > * Lookup(const char *str)
Definition: strtree.h:389
void FindMatches(const char *str, int strLen, nodeT< C > *node, uint *matches, uint maxMatches, nodeT< C > **array)
Definition: strtree.h:564
int strCompare(const char *s1, const char *s2)
Definition: misc.h:361
bool GetAllocateStrings()
Definition: strtree.h:144
StrTree()
Definition: strtree.h:177
uint GetFirstMatches(const char *str, uint max, nodeT< C > **results)
Definition: strtree.h:608
uint Size()
Definition: strtree.h:146
const errorT ERROR_Exists
Definition: error.h:51