distr/mtr/doc/mtr.doc

   1 The mtr package
   2
   3 Multiway-branch tree manipulation
   4
   5 Fabio Somenzi
   6
   7 **********************************************************************
   8
   9 Mtr_AllocNode()                Allocates new tree node.
  10
  11 Mtr_CopyTree()                 Makes a copy of tree.
  12
  13 Mtr_CreateFirstChild()         Creates a new node and makes it the first child
  14                                of parent.
  15
  16 Mtr_CreateLastChild()          Creates a new node and makes it the last child
  17                                of parent.
  18
  19 Mtr_DeallocNode()              Deallocates tree node.
  20
  21 Mtr_DissolveGroup()            Merges the children of `group' with the
  22                                children of its parent.
  23
  24 Mtr_FindGroup()                Finds a group with size leaves starting at low,
  25                                if it exists.
  26
  27 Mtr_FreeTree()                 Disposes of tree rooted at node.
  28
  29 Mtr_InitGroupTree()            Allocate new tree.
  30
  31 Mtr_InitTree()                 Initializes tree with one node.
  32
  33 Mtr_MakeFirstChild()           Makes child the first child of parent.
  34
  35 Mtr_MakeGroup()                Makes a new group with size leaves starting at
  36                                low.
  37
  38 Mtr_MakeLastChild()            Makes child the last child of parent.
  39
  40 Mtr_MakeNextSibling()          Makes second the next sibling of first.
  41
  42 Mtr_PrintGroups()              Prints the groups as a parenthesized list.
  43
  44 Mtr_PrintTree()                Prints a tree, one node per line.
  45
  46 Mtr_ReadGroups()               Reads groups from a file and creates a group
  47                                tree.
  48
  49 Mtr_SwapGroups()               Swaps two children of a tree node.
  50
  51 **********************************************************************
  52
  53 This package provides two layers of functions. Functions   of the lower level
  54 manipulate multiway-branch trees, implemented   according to the classical
  55 scheme whereby each node points to its   first child and its previous and
  56 next siblings. These functions are   collected in mtrBasic.c.   Functions
  57 of the upper layer deal with group trees, that is the trees   used by group
  58 sifting to represent the grouping of variables. These   functions are
  59 collected in mtrGroup.c.
  60
  61 MtrNode *
  62 Mtr_AllocNode(
  63
  64 )
  65   Allocates new tree node. Returns pointer to node.
  66
  67   Side Effects: None
  68
  69 MtrNode *
  70 Mtr_CopyTree(
  71   MtrNode *         node,
  72   int               expansion
  73 )
  74   Makes a copy of tree. If parameter expansion is greater than 1, it will
  75   expand the tree by that factor. It is an error for expansion to be less than
  76   1. Returns a pointer to the copy if successful; NULL otherwise.
  77
  78   Side Effects: None
  79
  80 MtrNode *
  81 Mtr_CreateFirstChild(
  82   MtrNode *         parent
  83 )
  84   Creates a new node and makes it the first child of parent. Returns pointer
  85   to new child.
  86
  87   Side Effects: None
  88
  89 MtrNode *
  90 Mtr_CreateLastChild(
  91   MtrNode *         parent
  92 )
  93   Creates a new node and makes it the last child of parent. Returns pointer to
  94   new child.
  95
  96   Side Effects: None
  97
  98 void
  99 Mtr_DeallocNode(
 100   MtrNode *         node             node to be deallocated
 101 )
 102   Deallocates tree node.
 103
 104   Side Effects: None
 105
 106 MtrNode *
 107 Mtr_DissolveGroup(
 108   MtrNode *         group            group to be dissolved
 109 )
 110   Merges the children of `group' with the children of its parent. Disposes of
 111   the node pointed by group. If group is the root of the group tree, this
 112   procedure leaves the tree unchanged. Returns the pointer to the parent of
 113   `group' upon successful termination; NULL otherwise.
 114
 115   Side Effects: None
 116
 117 MtrNode *
 118 Mtr_FindGroup(
 119   MtrNode *         root,            root of the group tree
 120   unsigned int      low,             lower bound of the group
 121   unsigned int      size             upper bound of the group
 122 )
 123   Finds a group with size leaves starting at low, if it exists. This procedure
 124   relies on the low and size fields of each node. It also assumes that the
 125   children of each node are sorted in order of increasing low. Returns the
 126   pointer to the root of the group upon successful termination; NULL
 127   otherwise.
 128
 129   Side Effects: None
 130
 131 void
 132 Mtr_FreeTree(
 133   MtrNode *         node
 134 )
 135   Disposes of tree rooted at node.
 136
 137   Side Effects: None
 138
 139 MtrNode *
 140 Mtr_InitGroupTree(
 141   int               lower,
 142   int               size
 143 )
 144   Allocate new tree with one node, whose low and size fields are specified by
 145   the lower and size parameters. Returns pointer to tree root.
 146
 147   Side Effects: None
 148
 149 MtrNode *
 150 Mtr_InitTree(
 151
 152 )
 153   Initializes tree with one node. Returns pointer to node.
 154
 155   Side Effects: None
 156
 157 void
 158 Mtr_MakeFirstChild(
 159   MtrNode *         parent,
 160   MtrNode *         child
 161 )
 162   Makes child the first child of parent.
 163
 164   Side Effects: None
 165
 166 MtrNode *
 167 Mtr_MakeGroup(
 168   MtrNode *         root,            root of the group tree
 169   unsigned int      low,             lower bound of the group
 170   unsigned int      size,            upper bound of the group
 171   unsigned int      flags            flags for the new group
 172 )
 173   Makes a new group with size leaves starting at low. If the new group
 174   intersects an existing group, it must either contain it or be contained by
 175   it. This procedure relies on the low and size fields of each node. It also
 176   assumes that the children of each node are sorted in order of increasing
 177   low. In case of a valid request, the flags of the new group are set to the
 178   value passed in `flags.' This can also be used to change the flags of an
 179   existing group. Returns the pointer to the root of the new group upon
 180   successful termination; NULL otherwise. If the group already exists, the
 181   pointer to its root is returned.
 182
 183   Side Effects: None
 184
 185 void
 186 Mtr_MakeLastChild(
 187   MtrNode *         parent,
 188   MtrNode *         child
 189 )
 190   Makes child the last child of parent.
 191
 192   Side Effects: None
 193
 194 void
 195 Mtr_MakeNextSibling(
 196   MtrNode *         first,
 197   MtrNode *         second
 198 )
 199   Makes second the next sibling of first. Second becomes a child of the parent
 200   of first.
 201
 202   Side Effects: None
 203
 204 void
 205 Mtr_PrintGroups(
 206   MtrNode *         root,            root of the group tree
 207   int               silent           flag to check tree syntax only
 208 )
 209   Prints the groups as a parenthesized list. After each group, the group's
 210   flag are printed, preceded by a `|'. For each flag (except MTR_TERMINAL) a
 211   character is printed.  F: MTR_FIXED N: MTR_NEWNODE S:
 212   MTR_SOFT  The second argument, silent, if different from 0, causes
 213   Mtr_PrintGroups to only check the syntax of the group tree.
 214
 215   Side Effects: None
 216
 217 void
 218 Mtr_PrintTree(
 219   MtrNode *         node
 220 )
 221   Prints a tree, one node per line.
 222
 223   Side Effects: None
 224
 225 MtrNode *
 226 Mtr_ReadGroups(
 227   FILE *            fp,              file pointer
 228   int               nleaves          number of leaves of the new tree
 229 )
 230   Reads groups from a file and creates a group tree. Each group is specified
 231   by three fields: low size flags.  Low and size are (short)
 232   integers. Flags is a string composed of the following characters (with
 233   associated translation):  D: MTR_DEFAULT F: MTR_FIXED N:
 234   MTR_NEWNODE S: MTR_SOFT T: MTR_TERMINAL  Normally, the only
 235   flags that are needed are D and F. Groups and fields are separated by white
 236   space (spaces, tabs, and newlines). Returns a pointer to the group tree if
 237   successful; NULL otherwise.
 238
 239   Side Effects: None
 240
 241 int
 242 Mtr_SwapGroups(
 243   MtrNode *         first,           first node to be swapped
 244   MtrNode *         second           second node to be swapped
 245 )
 246   Swaps two children of a tree node. Adjusts the high and low fields of the
 247   two nodes and their descendants. The two children must be adjacent. However,
 248   first may be the younger sibling of second. Returns 1 in case of success; 0
 249   otherwise.
 250
 251   Side Effects: None
 252