source: vis_dev/glu-2.3/src/mtr/mtrBasic.c@ 66

Last change on this file since 66 was 13, checked in by cecile, 15 years ago

library glu 2.3
File size: 12.6 KB
Line 
1/**CFile***********************************************************************
2
3 FileName [mtrBasic.c]
4
5 PackageName [mtr]
6
7 Synopsis [Basic manipulation of multiway branching trees.]
8
9 Description [External procedures included in this module:
10 <ul>
11 <li> Mtr_AllocNode()
12 <li> Mtr_DeallocNode()
13 <li> Mtr_InitTree()
14 <li> Mtr_FreeTree()
15 <li> Mtr_CopyTree()
16 <li> Mtr_MakeFirstChild()
17 <li> Mtr_MakeLastChild()
18 <li> Mtr_CreateFirstChild()
19 <li> Mtr_CreateLastChild()
20 <li> Mtr_MakeNextSibling()
21 <li> Mtr_PrintTree()
22 </ul>
23 ]
24
25 SeeAlso [cudd package]
26
27 Author [Fabio Somenzi]
28
29 Copyright [Copyright (c) 1995-2004, Regents of the University of Colorado
30
31 All rights reserved.
32
33 Redistribution and use in source and binary forms, with or without
34 modification, are permitted provided that the following conditions
35 are met:
36
37 Redistributions of source code must retain the above copyright
38 notice, this list of conditions and the following disclaimer.
39
40 Redistributions in binary form must reproduce the above copyright
41 notice, this list of conditions and the following disclaimer in the
42 documentation and/or other materials provided with the distribution.
43
44 Neither the name of the University of Colorado nor the names of its
45 contributors may be used to endorse or promote products derived from
46 this software without specific prior written permission.
47
48 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
49 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
50 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
51 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
52 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
53 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
54 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
55 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
56 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
57 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
58 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
59 POSSIBILITY OF SUCH DAMAGE.]
60
61******************************************************************************/
62
63#include "util.h"
64#include "mtrInt.h"
65
66
67/*---------------------------------------------------------------------------*/
68/* Constant declarations */
69/*---------------------------------------------------------------------------*/
70
71/*---------------------------------------------------------------------------*/
72/* Stucture declarations */
73/*---------------------------------------------------------------------------*/
74
75/*---------------------------------------------------------------------------*/
76/* Type declarations */
77/*---------------------------------------------------------------------------*/
78
79/*---------------------------------------------------------------------------*/
80/* Variable declarations */
81/*---------------------------------------------------------------------------*/
82
83#ifndef lint
84static char rcsid[] MTR_UNUSED = "$Id: mtrBasic.c,v 1.13 2009/02/20 02:03:47 fabio Exp $";
85#endif
86
87/*---------------------------------------------------------------------------*/
88/* Macro declarations */
89/*---------------------------------------------------------------------------*/
90
91/**AutomaticStart*************************************************************/
92
93/*---------------------------------------------------------------------------*/
94/* Static function prototypes */
95/*---------------------------------------------------------------------------*/
96
97
98/**AutomaticEnd***************************************************************/
99
100
101/*---------------------------------------------------------------------------*/
102/* Definition of exported functions */
103/*---------------------------------------------------------------------------*/
104
105/**Function********************************************************************
106
107 Synopsis [Allocates new tree node.]
108
109 Description [Allocates new tree node. Returns pointer to node.]
110
111 SideEffects [None]
112
113 SeeAlso [Mtr_DeallocNode]
114
115******************************************************************************/
116MtrNode *
117Mtr_AllocNode(void)
118{
119 MtrNode *node;
120
121 node = ALLOC(MtrNode,1);
122 return node;
123
124} /* Mtr_AllocNode */
125
126
127/**Function********************************************************************
128
129 Synopsis [Deallocates tree node.]
130
131 Description []
132
133 SideEffects [None]
134
135 SeeAlso [Mtr_AllocNode]
136
137******************************************************************************/
138void
139Mtr_DeallocNode(
140 MtrNode * node /* node to be deallocated */)
141{
142 FREE(node);
143 return;
144
145} /* end of Mtr_DeallocNode */
146
147
148/**Function********************************************************************
149
150 Synopsis [Initializes tree with one node.]
151
152 Description [Initializes tree with one node. Returns pointer to node.]
153
154 SideEffects [None]
155
156 SeeAlso [Mtr_FreeTree Mtr_InitGroupTree]
157
158******************************************************************************/
159MtrNode *
160Mtr_InitTree(void)
161{
162 MtrNode *node;
163
164 node = Mtr_AllocNode();
165 if (node == NULL) return(NULL);
166
167 node->parent = node->child = node->elder = node->younger = NULL;
168 node->flags = 0;
169
170 return(node);
171
172} /* end of Mtr_InitTree */
173
174
175/**Function********************************************************************
176
177 Synopsis [Disposes of tree rooted at node.]
178
179 Description []
180
181 SideEffects [None]
182
183 SeeAlso [Mtr_InitTree]
184
185******************************************************************************/
186void
187Mtr_FreeTree(
188 MtrNode * node)
189{
190 if (node == NULL) return;
191 if (! MTR_TEST(node,MTR_TERMINAL)) Mtr_FreeTree(node->child);
192 Mtr_FreeTree(node->younger);
193 Mtr_DeallocNode(node);
194 return;
195
196} /* end of Mtr_FreeTree */
197
198
199/**Function********************************************************************
200
201 Synopsis [Makes a copy of tree.]
202
203 Description [Makes a copy of tree. If parameter expansion is greater
204 than 1, it will expand the tree by that factor. It is an error for
205 expansion to be less than 1. Returns a pointer to the copy if
206 successful; NULL otherwise.]
207
208 SideEffects [None]
209
210 SeeAlso [Mtr_InitTree]
211
212******************************************************************************/
213MtrNode *
214Mtr_CopyTree(
215 MtrNode * node,
216 int expansion)
217{
218 MtrNode *copy;
219
220 if (node == NULL) return(NULL);
221 if (expansion < 1) return(NULL);
222 copy = Mtr_AllocNode();
223 if (copy == NULL) return(NULL);
224 copy->parent = copy->elder = copy->child = copy->younger = NULL;
225 if (node->child != NULL) {
226 copy->child = Mtr_CopyTree(node->child, expansion);
227 if (copy->child == NULL) {
228 Mtr_DeallocNode(copy);
229 return(NULL);
230 }
231 }
232 if (node->younger != NULL) {
233 copy->younger = Mtr_CopyTree(node->younger, expansion);
234 if (copy->younger == NULL) {
235 Mtr_FreeTree(copy);
236 return(NULL);
237 }
238 }
239 copy->flags = node->flags;
240 copy->low = node->low * expansion;
241 copy->size = node->size * expansion;
242 copy->index = node->index * expansion;
243 if (copy->younger) copy->younger->elder = copy;
244 if (copy->child) {
245 MtrNode *auxnode = copy->child;
246 while (auxnode != NULL) {
247 auxnode->parent = copy;
248 auxnode = auxnode->younger;
249 }
250 }
251 return(copy);
252
253} /* end of Mtr_CopyTree */
254
255
256/**Function********************************************************************
257
258 Synopsis [Makes child the first child of parent.]
259
260 Description []
261
262 SideEffects [None]
263
264 SeeAlso [Mtr_MakeLastChild Mtr_CreateFirstChild]
265
266******************************************************************************/
267void
268Mtr_MakeFirstChild(
269 MtrNode * parent,
270 MtrNode * child)
271{
272 child->parent = parent;
273 child->younger = parent->child;
274 child->elder = NULL;
275 if (parent->child != NULL) {
276#ifdef MTR_DEBUG
277 assert(parent->child->elder == NULL);
278#endif
279 parent->child->elder = child;
280 }
281 parent->child = child;
282 return;
283
284} /* end of Mtr_MakeFirstChild */
285
286
287/**Function********************************************************************
288
289 Synopsis [Makes child the last child of parent.]
290
291 Description []
292
293 SideEffects [None]
294
295 SeeAlso [Mtr_MakeFirstChild Mtr_CreateLastChild]
296
297******************************************************************************/
298void
299Mtr_MakeLastChild(
300 MtrNode * parent,
301 MtrNode * child)
302{
303 MtrNode *node;
304
305 child->younger = NULL;
306
307 if (parent->child == NULL) {
308 parent->child = child;
309 child->elder = NULL;
310 } else {
311 for (node = parent->child;
312 node->younger != NULL;
313 node = node->younger);
314 node->younger = child;
315 child->elder = node;
316 }
317 child->parent = parent;
318 return;
319
320} /* end of Mtr_MakeLastChild */
321
322
323/**Function********************************************************************
324
325 Synopsis [Creates a new node and makes it the first child of parent.]
326
327 Description [Creates a new node and makes it the first child of
328 parent. Returns pointer to new child.]
329
330 SideEffects [None]
331
332 SeeAlso [Mtr_MakeFirstChild Mtr_CreateLastChild]
333
334******************************************************************************/
335MtrNode *
336Mtr_CreateFirstChild(
337 MtrNode * parent)
338{
339 MtrNode *child;
340
341 child = Mtr_AllocNode();
342 if (child == NULL) return(NULL);
343
344 child->child = child->younger = child-> elder = NULL;
345 child->flags = 0;
346 Mtr_MakeFirstChild(parent,child);
347 return(child);
348
349} /* end of Mtr_CreateFirstChild */
350
351
352/**Function********************************************************************
353
354 Synopsis [Creates a new node and makes it the last child of parent.]
355
356 Description [Creates a new node and makes it the last child of parent.
357 Returns pointer to new child.]
358
359 SideEffects [None]
360
361 SeeAlso [Mtr_MakeLastChild Mtr_CreateFirstChild]
362
363******************************************************************************/
364MtrNode *
365Mtr_CreateLastChild(
366 MtrNode * parent)
367{
368 MtrNode *child;
369
370 child = Mtr_AllocNode();
371 if (child == NULL) return(NULL);
372
373 child->child = child->younger = child->elder = NULL;
374 child->flags = 0;
375 Mtr_MakeLastChild(parent,child);
376 return(child);
377
378} /* end of Mtr_CreateLastChild */
379
380
381/**Function********************************************************************
382
383 Synopsis [Makes second the next sibling of first.]
384
385 Description [Makes second the next sibling of first. Second becomes a
386 child of the parent of first.]
387
388 SideEffects [None]
389
390 SeeAlso []
391
392******************************************************************************/
393void
394Mtr_MakeNextSibling(
395 MtrNode * first,
396 MtrNode * second)
397{
398 second->younger = first->younger;
399 if (first->younger != NULL) {
400 first->younger->elder = second;
401 }
402 second->parent = first->parent;
403 first->younger = second;
404 second->elder = first;
405 return;
406
407} /* end of Mtr_MakeNextSibling */
408
409
410/**Function********************************************************************
411
412 Synopsis [Prints a tree, one node per line.]
413
414 Description []
415
416 SideEffects [None]
417
418 SeeAlso [Mtr_PrintGroups]
419
420******************************************************************************/
421void
422Mtr_PrintTree(
423 MtrNode * node)
424{
425 if (node == NULL) return;
426 (void) fprintf(stdout,
427#if SIZEOF_VOID_P == 8
428 "N=0x%-8lx C=0x%-8lx Y=0x%-8lx E=0x%-8lx P=0x%-8lx F=%x L=%u S=%u\n",
429 (unsigned long) node, (unsigned long) node->child,
430 (unsigned long) node->younger, (unsigned long) node->elder,
431 (unsigned long) node->parent, node->flags, node->low, node->size);
432#else
433 "N=0x%-8x C=0x%-8x Y=0x%-8x E=0x%-8x P=0x%-8x F=%x L=%hu S=%hu\n",
434 (unsigned) node, (unsigned) node->child,
435 (unsigned) node->younger, (unsigned) node->elder,
436 (unsigned) node->parent, node->flags, node->low, node->size);
437#endif
438 if (!MTR_TEST(node,MTR_TERMINAL)) Mtr_PrintTree(node->child);
439 Mtr_PrintTree(node->younger);
440 return;
441
442} /* end of Mtr_PrintTree */
443
444/*---------------------------------------------------------------------------*/
445/* Definition of internal functions */
446/*---------------------------------------------------------------------------*/
447
448/*---------------------------------------------------------------------------*/
449/* Definition of static functions */
450/*---------------------------------------------------------------------------*/
Note: See TracBrowser for help on using the repository browser.