doc/D.Formidable-snippets

   1
   2
   3 1. Walking A Tree
   4 ~~~~~~~~~~~~~~~~~
   5
   6 Suppose a binary tree.  Each node has two pointers to subtrees, like this
   7
   8         class Node {
   9                 Node *less, *more;
  10         };
  11
  12 The tree can be a simple binary search tree, a dynamic binary search tree
  13 with auto-balance (described in dbstree.tex), an integer tree (inttree.tex)
  14 or any other black-red-whatever tree.  To do something for every node of the
  15 tree we use a recursive procedure, like below:
  16
  17         void do_something (Node *n) {
  18                 if (n->less) do_something (n->less);
  19                 /* do something with n ... */
  20                 if (n->more) do_something (n->more);
  21         }
  22
  23 And the procedure is initiated by calling 'do_something (root_of_the_tree)'.
  24
  25 Here is the optimum lwc way of walking a tree with auto functions, compile-time
  26 polymorphism, etc:
  27
  28         class foreach_node
  29         {
  30                 void Do (Node*) = 0;
  31         auto    void walktree (Node*) = 0;
  32         auto    void enter (Node*);
  33         };
  34
  35         void foreach_node.enter (Node *n)
  36         {
  37                 if (n) walktree (n);
  38         }
  39
  40         //
  41         // do in-order
  42         //
  43
  44         class foreach_node_IO : foreach_node
  45         {
  46                 void walktree (Node*);
  47         }
  48
  49         void foreach_node_IO.walktree (Node *n)
  50         {
  51                 if (n->less) walktree (n->less);
  52                 Do (n);
  53                 if (n->more) walktree (n->more);
  54         }
  55
  56         //
  57         // do post-order
  58         //
  59
  60         class foreach_node_PO : foreach_node
  61         {
  62                 void walktree (Node*);
  63         }
  64
  65         void foreach_node_PO.walktree (Node *n)
  66         {
  67                 if (n->less) walktree (n->less);
  68                 if (n->more) walktree (n->more);
  69                 Do (n);
  70         }
  71
  72 Now, suppose we have a tree of strings where the nodes are defined as:
  73
  74         class NodeStr : Node {
  75                 char *str;
  76         };
  77
  78 -A] If we want to walk the tree and print all the strings. We only have to
  79 define the function 'Do' to print the string of each node. Everything else
  80 is already arranged by the auto-functions.
  81
  82         class print_tree : foreach_node_IO
  83         {
  84                 void Do (Node*);
  85            public:
  86                 print_tree (Node *root)         { enter (root); }
  87         };
  88
  89         void print_tree.Do (Node *n)
  90         {
  91                 NodeStr *s = (NodeStr*) n;
  92                 printf ("%s\n", s->str);
  93         }
  94
  95         //
  96         // use it on a tree starting at 'root'
  97         //
  98         int sample_use ()
  99         {
 100                 print_tree (root);
 101         }
 102
 103
 104 -B] If we want to count all the nodes of a tree, we can:
 105
 106         class count_nodes : foreach_node_IO
 107         {
 108                 void Do (Node*);
 109           public:
 110                 int cnt;
 111                 count_nodes (Node *root)        { cnt = 0; enter (root); }
 112         };
 113
 114         void count_nodes.Do (Node*)
 115         {
 116                 cnt++;
 117         }
 118
 119         //
 120         // use it on a tree starting at 'root'
 121         //
 122         int sample_use ()
 123         {
 124                 count_nodes C (root);
 125                 printf ("tree has %i nodes\n", C.cnt);
 126         }
 127
 128 -C] If we've counted the nodes and we want to store all the strings
 129 in an array, sorted, we can:
 130
 131         class tree_to_array : foreach_node_IO
 132         {
 133                 void Do (Node*);
 134            public:
 135                 char **array;
 136                 tree_to_array (char *a[], Node *root)   { array = a; enter (root); }
 137         };
 138
 139         void tree_to_array.Do (Node *n)
 140         {
 141                 NodeStr *s = (NodeStr*) n;
 142                 *array++ = s->str;
 143         }
 144
 145         //
 146         // use it on a tree starting at 'root'
 147         //
 148         int sample_use ()
 149         {
 150                 count_nodes C (root);
 151                 char *array [C.cnt];
 152                 tree_to_array A (array, root);
 153         }
 154
 155 NOTES: The member functions of the foreach_node class can be 'modular' in
 156 some cases. In case (A), Do() does not use 'this'. Making functions modular
 157 will avoid passing the extra argument in walktree() which can't be inlined
 158 due to recursion.