emergency commit
[cl-cudd.git] / distr / mtr / doc / mtrExtDet.html
blob8300c3d6a49fd02b6d30c32f1ba14b5e8cf0c885
1 <html>
2 <head><title>The mtr package</title></head>
3 <body>
5 <h1>The mtr package</h1>
6 <h2>Multiway-branch tree manipulation</h2>
7 <h3></h3>
8 <hr>
9 <ul>
10 <li><a href="mtrExtAbs.html"><h3>External abstracts</h3></a>
11 <li><a href="mtrAllAbs.html"><h3>All abstracts</h3></a>
12 <li><a href="mtrExtDet.html#prototypes"><h3>External functions</h3></a>
13 <li><a href="mtrAllDet.html#prototypes"><h3>All functions</h3></a>
14 </ul>
16 <hr>
18 <a name="description">
19 This package provides two layers of functions. Functions
20 of the lower level manipulate multiway-branch trees, implemented
21 according to the classical scheme whereby each node points to its
22 first child and its previous and next siblings. These functions are
23 collected in mtrBasic.c.<p>
24 Functions of the upper layer deal with group trees, that is the trees
25 used by group sifting to represent the grouping of variables. These
26 functions are collected in mtrGroup.c.
27 </a>
29 <hr>
30 <!-- Function Prototypes and description -->
32 <dl>
33 <a name="prototypes"></a>
34 <dt><pre>
35 MtrNode * <i></i>
36 <a name="Mtr_AllocNode"><b>Mtr_AllocNode</b></a>(
37 <b></b> <i></i>
39 </pre>
40 <dd> Allocates new tree node. Returns pointer to node.
41 <p>
43 <dd> <b>Side Effects</b> None
44 <p>
46 <dd> <b>See Also</b> <code><a href="mtrAllDet.html#Mtr_DeallocNode">Mtr_DeallocNode</a>
47 </code>
49 <dt><pre>
50 MtrNode * <i></i>
51 <a name="Mtr_CopyTree"><b>Mtr_CopyTree</b></a>(
52 MtrNode * <b>node</b>, <i></i>
53 int <b>expansion</b> <i></i>
55 </pre>
56 <dd> Makes a copy of tree. If parameter expansion is greater than 1, it will expand the tree by that factor. It is an error for expansion to be less than 1. Returns a pointer to the copy if successful; NULL otherwise.
57 <p>
59 <dd> <b>Side Effects</b> None
60 <p>
62 <dd> <b>See Also</b> <code><a href="mtrAllDet.html#Mtr_InitTree">Mtr_InitTree</a>
63 </code>
65 <dt><pre>
66 MtrNode * <i></i>
67 <a name="Mtr_CreateFirstChild"><b>Mtr_CreateFirstChild</b></a>(
68 MtrNode * <b>parent</b> <i></i>
70 </pre>
71 <dd> Creates a new node and makes it the first child of parent. Returns pointer to new child.
72 <p>
74 <dd> <b>Side Effects</b> None
75 <p>
77 <dd> <b>See Also</b> <code><a href="mtrAllDet.html#Mtr_MakeFirstChild">Mtr_MakeFirstChild</a>
78 <a href="mtrAllDet.html#Mtr_CreateLastChild">Mtr_CreateLastChild</a>
79 </code>
81 <dt><pre>
82 MtrNode * <i></i>
83 <a name="Mtr_CreateLastChild"><b>Mtr_CreateLastChild</b></a>(
84 MtrNode * <b>parent</b> <i></i>
86 </pre>
87 <dd> Creates a new node and makes it the last child of parent. Returns pointer to new child.
88 <p>
90 <dd> <b>Side Effects</b> None
91 <p>
93 <dd> <b>See Also</b> <code><a href="mtrAllDet.html#Mtr_MakeLastChild">Mtr_MakeLastChild</a>
94 <a href="mtrAllDet.html#Mtr_CreateFirstChild">Mtr_CreateFirstChild</a>
95 </code>
97 <dt><pre>
98 void <i></i>
99 <a name="Mtr_DeallocNode"><b>Mtr_DeallocNode</b></a>(
100 MtrNode * <b>node</b> <i>node to be deallocated</i>
102 </pre>
103 <dd> Deallocates tree node.
106 <dd> <b>Side Effects</b> None
109 <dd> <b>See Also</b> <code><a href="mtrAllDet.html#Mtr_AllocNode">Mtr_AllocNode</a>
110 </code>
112 <dt><pre>
113 MtrNode * <i></i>
114 <a name="Mtr_DissolveGroup"><b>Mtr_DissolveGroup</b></a>(
115 MtrNode * <b>group</b> <i>group to be dissolved</i>
117 </pre>
118 <dd> Merges the children of `group' with the children of its parent. Disposes of the node pointed by group. If group is the root of the group tree, this procedure leaves the tree unchanged. Returns the pointer to the parent of `group' upon successful termination; NULL otherwise.
121 <dd> <b>Side Effects</b> None
124 <dd> <b>See Also</b> <code><a href="mtrAllDet.html#Mtr_MakeGroup">Mtr_MakeGroup</a>
125 </code>
127 <dt><pre>
128 MtrNode * <i></i>
129 <a name="Mtr_FindGroup"><b>Mtr_FindGroup</b></a>(
130 MtrNode * <b>root</b>, <i>root of the group tree</i>
131 unsigned int <b>low</b>, <i>lower bound of the group</i>
132 unsigned int <b>size</b> <i>upper bound of the group</i>
134 </pre>
135 <dd> Finds a group with size leaves starting at low, if it exists. This procedure relies on the low and size fields of each node. It also assumes that the children of each node are sorted in order of increasing low. Returns the pointer to the root of the group upon successful termination; NULL otherwise.
138 <dd> <b>Side Effects</b> None
141 <dt><pre>
142 void <i></i>
143 <a name="Mtr_FreeTree"><b>Mtr_FreeTree</b></a>(
144 MtrNode * <b>node</b> <i></i>
146 </pre>
147 <dd> Disposes of tree rooted at node.
150 <dd> <b>Side Effects</b> None
153 <dd> <b>See Also</b> <code><a href="mtrAllDet.html#Mtr_InitTree">Mtr_InitTree</a>
154 </code>
156 <dt><pre>
157 MtrNode * <i></i>
158 <a name="Mtr_InitGroupTree"><b>Mtr_InitGroupTree</b></a>(
159 int <b>lower</b>, <i></i>
160 int <b>size</b> <i></i>
162 </pre>
163 <dd> Allocate new tree with one node, whose low and size fields are specified by the lower and size parameters. Returns pointer to tree root.
166 <dd> <b>Side Effects</b> None
169 <dd> <b>See Also</b> <code><a href="mtrAllDet.html#Mtr_InitTree">Mtr_InitTree</a>
170 <a href="mtrAllDet.html#Mtr_FreeTree">Mtr_FreeTree</a>
171 </code>
173 <dt><pre>
174 MtrNode * <i></i>
175 <a name="Mtr_InitTree"><b>Mtr_InitTree</b></a>(
176 <b></b> <i></i>
178 </pre>
179 <dd> Initializes tree with one node. Returns pointer to node.
182 <dd> <b>Side Effects</b> None
185 <dd> <b>See Also</b> <code><a href="mtrAllDet.html#Mtr_FreeTree">Mtr_FreeTree</a>
186 <a href="mtrAllDet.html#Mtr_InitGroupTree">Mtr_InitGroupTree</a>
187 </code>
189 <dt><pre>
190 void <i></i>
191 <a name="Mtr_MakeFirstChild"><b>Mtr_MakeFirstChild</b></a>(
192 MtrNode * <b>parent</b>, <i></i>
193 MtrNode * <b>child</b> <i></i>
195 </pre>
196 <dd> Makes child the first child of parent.
199 <dd> <b>Side Effects</b> None
202 <dd> <b>See Also</b> <code><a href="mtrAllDet.html#Mtr_MakeLastChild">Mtr_MakeLastChild</a>
203 <a href="mtrAllDet.html#Mtr_CreateFirstChild">Mtr_CreateFirstChild</a>
204 </code>
206 <dt><pre>
207 MtrNode * <i></i>
208 <a name="Mtr_MakeGroup"><b>Mtr_MakeGroup</b></a>(
209 MtrNode * <b>root</b>, <i>root of the group tree</i>
210 unsigned int <b>low</b>, <i>lower bound of the group</i>
211 unsigned int <b>size</b>, <i>upper bound of the group</i>
212 unsigned int <b>flags</b> <i>flags for the new group</i>
214 </pre>
215 <dd> Makes a new group with size leaves starting at low. If the new group intersects an existing group, it must either contain it or be contained by it. This procedure relies on the low and size fields of each node. It also assumes that the children of each node are sorted in order of increasing low. In case of a valid request, the flags of the new group are set to the value passed in `flags.' This can also be used to change the flags of an existing group. Returns the pointer to the root of the new group upon successful termination; NULL otherwise. If the group already exists, the pointer to its root is returned.
218 <dd> <b>Side Effects</b> None
221 <dd> <b>See Also</b> <code><a href="mtrAllDet.html#Mtr_DissolveGroup">Mtr_DissolveGroup</a>
222 <a href="mtrAllDet.html#Mtr_ReadGroups">Mtr_ReadGroups</a>
223 <a href="mtrAllDet.html#Mtr_FindGroup">Mtr_FindGroup</a>
224 </code>
226 <dt><pre>
227 void <i></i>
228 <a name="Mtr_MakeLastChild"><b>Mtr_MakeLastChild</b></a>(
229 MtrNode * <b>parent</b>, <i></i>
230 MtrNode * <b>child</b> <i></i>
232 </pre>
233 <dd> Makes child the last child of parent.
236 <dd> <b>Side Effects</b> None
239 <dd> <b>See Also</b> <code><a href="mtrAllDet.html#Mtr_MakeFirstChild">Mtr_MakeFirstChild</a>
240 <a href="mtrAllDet.html#Mtr_CreateLastChild">Mtr_CreateLastChild</a>
241 </code>
243 <dt><pre>
244 void <i></i>
245 <a name="Mtr_MakeNextSibling"><b>Mtr_MakeNextSibling</b></a>(
246 MtrNode * <b>first</b>, <i></i>
247 MtrNode * <b>second</b> <i></i>
249 </pre>
250 <dd> Makes second the next sibling of first. Second becomes a child of the parent of first.
253 <dd> <b>Side Effects</b> None
256 <dt><pre>
257 void <i></i>
258 <a name="Mtr_PrintGroups"><b>Mtr_PrintGroups</b></a>(
259 MtrNode * <b>root</b>, <i>root of the group tree</i>
260 int <b>silent</b> <i>flag to check tree syntax only</i>
262 </pre>
263 <dd> Prints the groups as a parenthesized list. After each group, the group's flag are printed, preceded by a `|'. For each flag (except MTR_TERMINAL) a character is printed. <ul> <li>F: MTR_FIXED <li>N: MTR_NEWNODE <li>S: MTR_SOFT </ul> The second argument, silent, if different from 0, causes Mtr_PrintGroups to only check the syntax of the group tree.
266 <dd> <b>Side Effects</b> None
269 <dd> <b>See Also</b> <code><a href="mtrAllDet.html#Mtr_PrintTree">Mtr_PrintTree</a>
270 </code>
272 <dt><pre>
273 void <i></i>
274 <a name="Mtr_PrintTree"><b>Mtr_PrintTree</b></a>(
275 MtrNode * <b>node</b> <i></i>
277 </pre>
278 <dd> Prints a tree, one node per line.
281 <dd> <b>Side Effects</b> None
284 <dd> <b>See Also</b> <code><a href="mtrAllDet.html#Mtr_PrintGroups">Mtr_PrintGroups</a>
285 </code>
287 <dt><pre>
288 MtrNode * <i></i>
289 <a name="Mtr_ReadGroups"><b>Mtr_ReadGroups</b></a>(
290 FILE * <b>fp</b>, <i>file pointer</i>
291 int <b>nleaves</b> <i>number of leaves of the new tree</i>
293 </pre>
294 <dd> Reads groups from a file and creates a group tree. Each group is specified by three fields: <xmp> low size flags. </xmp> Low and size are (short) integers. Flags is a string composed of the following characters (with associated translation): <ul> <li>D: MTR_DEFAULT <li>F: MTR_FIXED <li>N: MTR_NEWNODE <li>S: MTR_SOFT <li>T: MTR_TERMINAL </ul> Normally, the only flags that are needed are D and F. Groups and fields are separated by white space (spaces, tabs, and newlines). Returns a pointer to the group tree if successful; NULL otherwise.
297 <dd> <b>Side Effects</b> None
300 <dd> <b>See Also</b> <code><a href="mtrAllDet.html#Mtr_InitGroupTree">Mtr_InitGroupTree</a>
301 <a href="mtrAllDet.html#Mtr_MakeGroup">Mtr_MakeGroup</a>
302 </code>
304 <dt><pre>
305 int <i></i>
306 <a name="Mtr_SwapGroups"><b>Mtr_SwapGroups</b></a>(
307 MtrNode * <b>first</b>, <i>first node to be swapped</i>
308 MtrNode * <b>second</b> <i>second node to be swapped</i>
310 </pre>
311 <dd> Swaps two children of a tree node. Adjusts the high and low fields of the two nodes and their descendants. The two children must be adjacent. However, first may be the younger sibling of second. Returns 1 in case of success; 0 otherwise.
314 <dd> <b>Side Effects</b> None
318 </dl>
320 <hr>
322 Generated automatically by <code>extdoc</code> on 970123
324 </body></html>