Context Navigation

source: vis_dev/glu-2.1/src/mtr/mtrGroup.c @ 8

Last change on this file since 8 was 8, checked in by cecile, 13 years ago
src glu
File size: 21.8 KB

Line
1	/CFile*********************************************************************
2
3	FileName [mtrGroup.c]
4
5	PackageName [mtr]
6
7	Synopsis [Functions to support group specification for reordering.]
8
9	Description [External procedures included in this module:
10	<ul>
11	<li> Mtr_InitGroupTree()
12	<li> Mtr_MakeGroup()
13	<li> Mtr_DissolveGroup()
14	<li> Mtr_FindGroup()
15	<li> Mtr_SwapGroups()
16	<li> Mtr_PrintGroups()
17	<li> Mtr_ReadGroups()
18	</ul>
19	Static procedures included in this module:
20	<ul>
21	<li> mtrShiftHL
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	/* Constant declarations */
68	/---------------------------------------------------------------------------/
69
70	/---------------------------------------------------------------------------/
71	/* Stucture declarations */
72	/---------------------------------------------------------------------------/
73
74	/---------------------------------------------------------------------------/
75	/* Type declarations */
76	/---------------------------------------------------------------------------/
77
78	/---------------------------------------------------------------------------/
79	/* Variable declarations */
80	/---------------------------------------------------------------------------/
81
82	#ifndef lint
83	static char rcsid[] MTR_UNUSED = "$Id: mtrGroup.c,v 1.16 2004/08/13 18:15:11 fabio Exp $";
84	#endif
85
86	/---------------------------------------------------------------------------/
87	/* Macro declarations */
88	/---------------------------------------------------------------------------/
89
90	/AutomaticStart***********************************************************/
91
92	/---------------------------------------------------------------------------/
93	/* Static function prototypes */
94	/---------------------------------------------------------------------------/
95
96	static int mtrShiftHL (MtrNode *node, int shift);
97
98	/AutomaticEnd*************************************************************/
99
100	/---------------------------------------------------------------------------/
101	/* Definition of exported functions */
102	/---------------------------------------------------------------------------/
103
104
105	/Function******************************************************************
106
107	Synopsis [Allocate new tree.]
108
109	Description [Allocate new tree with one node, whose low and size
110	fields are specified by the lower and size parameters.
111	Returns pointer to tree root.]
112
113	SideEffects [None]
114
115	SeeAlso [Mtr_InitTree Mtr_FreeTree]
116
117	******************************************************************************/
118	MtrNode *
119	Mtr_InitGroupTree(
120	int lower,
121	int size)
122	{
123	MtrNode *root;
124
125	root = Mtr_InitTree();
126	if (root == NULL) return(NULL);
127	root->flags = MTR_DEFAULT;
128	root->low = lower;
129	root->size = size;
130	return(root);
131
132	} /* end of Mtr_InitGroupTree */
133
134
135	/Function******************************************************************
136
137	Synopsis [Makes a new group with size leaves starting at low.]
138
139	Description [Makes a new group with size leaves starting at low.
140	If the new group intersects an existing group, it must
141	either contain it or be contained by it. This procedure relies on
142	the low and size fields of each node. It also assumes that the
143	children of each node are sorted in order of increasing low. In
144	case of a valid request, the flags of the new group are set to the
145	value passed in `flags.' This can also be used to change the flags
146	of an existing group. Returns the pointer to the root of the new
147	group upon successful termination; NULL otherwise. If the group
148	already exists, the pointer to its root is returned.]
149
150	SideEffects [None]
151
152	SeeAlso [Mtr_DissolveGroup Mtr_ReadGroups Mtr_FindGroup]
153
154	******************************************************************************/
155	MtrNode *
156	Mtr_MakeGroup(
157	MtrNode * root /* root of the group tree */,
158	unsigned int low /* lower bound of the group */,
159	unsigned int size /* upper bound of the group */,
160	unsigned int flags /* flags for the new group */)
161	{
162	MtrNode *node,
163	*first,
164	*last,
165	*previous,
166	*newn;
167
168	/* Sanity check. */
169	if (size == 0)
170	return(NULL);
171
172	/* Check whether current group includes new group. This check is
173	** necessary at the top-level call. In the subsequent calls it is
174	** redundant. */
175	if (low < (unsigned int) root->low \|\|
176	low + size > (unsigned int) (root->low + root->size))
177	return(NULL);
178
179	/* Trying to create an existing group has the effect of updating
180	** the flags. */
181	if (root->size == size && root->low == low) {
182	root->flags = flags;
183	return(root);
184	}
185
186	/* At this point we know that the new group is properly contained
187	** in the group of root. We have two possible cases here: - root
188	** is a terminal node; - root has children. */
189
190	/* Root has no children: create a new group. */
191	if (root->child == NULL) {
192	newn = Mtr_AllocNode();
193	if (newn == NULL) return(NULL); /* out of memory */
194	newn->low = low;
195	newn->size = size;
196	newn->flags = flags;
197	newn->parent = root;
198	newn->elder = newn->younger = newn->child = NULL;
199	root->child = newn;
200	return(newn);
201	}
202
203	/* Root has children: Find all chidren of root that are included
204	** in the new group. If the group of any child entirely contains
205	** the new group, call Mtr_MakeGroup recursively. */
206	previous = NULL;
207	first = root->child; /* guaranteed to be non-NULL */
208	while (first != NULL && low >= (unsigned int) (first->low + first->size)) {
209	previous = first;
210	first = first->younger;
211	}
212	if (first == NULL) {
213	/* We have scanned the entire list and we need to append a new
214	** child at the end of it. Previous points to the last child
215	** of root. */
216	newn = Mtr_AllocNode();
217	if (newn == NULL) return(NULL); /* out of memory */
218	newn->low = low;
219	newn->size = size;
220	newn->flags = flags;
221	newn->parent = root;
222	newn->elder = previous;
223	previous->younger = newn;
224	newn->younger = newn->child = NULL;
225	return(newn);
226	}
227	/* Here first is non-NULL and low < first->low + first->size. */
228	if (low >= (unsigned int) first->low &&
229	low + size <= (unsigned int) (first->low + first->size)) {
230	/* The new group is contained in the group of first. */
231	newn = Mtr_MakeGroup(first, low, size, flags);
232	return(newn);
233	} else if (low + size <= first->low) {
234	/* The new group is entirely contained in the gap between
235	** previous and first. */
236	newn = Mtr_AllocNode();
237	if (newn == NULL) return(NULL); /* out of memory */
238	newn->low = low;
239	newn->size = size;
240	newn->flags = flags;
241	newn->child = NULL;
242	newn->parent = root;
243	newn->elder = previous;
244	newn->younger = first;
245	first->elder = newn;
246	if (previous != NULL) {
247	previous->younger = newn;
248	} else {
249	root->child = newn;
250	}
251	return(newn);
252	} else if (low < (unsigned int) first->low &&
253	low + size < (unsigned int) (first->low + first->size)) {
254	/* Trying to cut an existing group: not allowed. */
255	return(NULL);
256	} else if (low > first->low) {
257	/* The new group neither is contained in the group of first
258	** (this was tested above) nor contains it. It is therefore
259	** trying to cut an existing group: not allowed. */
260	return(NULL);
261	}
262
263	/* First holds the pointer to the first child contained in the new
264	** group. Here low <= first->low and low + size >= first->low +
265	** first->size. One of the two inequalities is strict. */
266	last = first->younger;
267	while (last != NULL &&
268	(unsigned int) (last->low + last->size) < low + size) {
269	last = last->younger;
270	}
271	if (last == NULL) {
272	/* All the chilren of root from first onward become children
273	** of the new group. */
274	newn = Mtr_AllocNode();
275	if (newn == NULL) return(NULL); /* out of memory */
276	newn->low = low;
277	newn->size = size;
278	newn->flags = flags;
279	newn->child = first;
280	newn->parent = root;
281	newn->elder = previous;
282	newn->younger = NULL;
283	first->elder = NULL;
284	if (previous != NULL) {
285	previous->younger = newn;
286	} else {
287	root->child = newn;
288	}
289	last = first;
290	while (last != NULL) {
291	last->parent = newn;
292	last = last->younger;
293	}
294	return(newn);
295	}
296
297	/* Here last != NULL and low + size <= last->low + last->size. */
298	if (low + size - 1 >= (unsigned int) last->low &&
299	low + size < (unsigned int) (last->low + last->size)) {
300	/* Trying to cut an existing group: not allowed. */
301	return(NULL);
302	}
303
304	/* First and last point to the first and last of the children of
305	** root that are included in the new group. Allocate a new node
306	** and make all children of root between first and last chidren of
307	** the new node. Previous points to the child of root immediately
308	** preceeding first. If it is NULL, then first is the first child
309	** of root. */
310	newn = Mtr_AllocNode();
311	if (newn == NULL) return(NULL); /* out of memory */
312	newn->low = low;
313	newn->size = size;
314	newn->flags = flags;
315	newn->child = first;
316	newn->parent = root;
317	if (previous == NULL) {
318	root->child = newn;
319	} else {
320	previous->younger = newn;
321	}
322	newn->elder = previous;
323	newn->younger = last->younger;
324	if (last->younger != NULL) {
325	last->younger->elder = newn;
326	}
327	last->younger = NULL;
328	first->elder = NULL;
329	for (node = first; node != NULL; node = node->younger) {
330	node->parent = newn;
331	}
332
333	return(newn);
334
335	} /* end of Mtr_MakeGroup */
336
337
338	/Function******************************************************************
339
340	Synopsis [Merges the children of `group' with the children of its
341	parent.]
342
343	Description [Merges the children of `group' with the children of its
344	parent. Disposes of the node pointed by group. If group is the
345	root of the group tree, this procedure leaves the tree unchanged.
346	Returns the pointer to the parent of `group' upon successful
347	termination; NULL otherwise.]
348
349	SideEffects [None]
350
351	SeeAlso [Mtr_MakeGroup]
352
353	******************************************************************************/
354	MtrNode *
355	Mtr_DissolveGroup(
356	MtrNode * group /* group to be dissolved */)
357	{
358	MtrNode *parent;
359	MtrNode *last;
360
361	parent = group->parent;
362
363	if (parent == NULL) return(NULL);
364	if (MTR_TEST(group,MTR_TERMINAL) \|\| group->child == NULL) return(NULL);
365
366	/* Make all children of group children of its parent, and make
367	** last point to the last child of group. */
368	for (last = group->child; last->younger != NULL; last = last->younger) {
369	last->parent = parent;
370	}
371	last->parent = parent;
372
373	last->younger = group->younger;
374	if (group->younger != NULL) {
375	group->younger->elder = last;
376	}
377
378	group->child->elder = group->elder;
379	if (group == parent->child) {
380	parent->child = group->child;
381	} else {
382	group->elder->younger = group->child;
383	}
384
385	Mtr_DeallocNode(group);
386	return(parent);
387
388	} /* end of Mtr_DissolveGroup */
389
390
391	/Function******************************************************************
392
393	Synopsis [Finds a group with size leaves starting at low, if it exists.]
394
395	Description [Finds a group with size leaves starting at low, if it
396	exists. This procedure relies on the low and size fields of each
397	node. It also assumes that the children of each node are sorted in
398	order of increasing low. Returns the pointer to the root of the
399	group upon successful termination; NULL otherwise.]
400
401	SideEffects [None]
402
403	SeeAlso []
404
405	******************************************************************************/
406	MtrNode *
407	Mtr_FindGroup(
408	MtrNode * root /* root of the group tree */,
409	unsigned int low /* lower bound of the group */,
410	unsigned int size /* upper bound of the group */)
411	{
412	MtrNode *node;
413
414	#ifdef MTR_DEBUG
415	/* We cannot have a non-empty proper subgroup of a singleton set. */
416	assert(!MTR_TEST(root,MTR_TERMINAL));
417	#endif
418
419	/* Sanity check. */
420	if (size < 1) return(NULL);
421
422	/* Check whether current group includes the group sought. This
423	** check is necessary at the top-level call. In the subsequent
424	** calls it is redundant. */
425	if (low < (unsigned int) root->low \|\|
426	low + size > (unsigned int) (root->low + root->size))
427	return(NULL);
428
429	if (root->size == size && root->low == low)
430	return(root);
431
432	if (root->child == NULL)
433	return(NULL);
434
435	/* Find all chidren of root that are included in the new group. If
436	** the group of any child entirely contains the new group, call
437	** Mtr_MakeGroup recursively. */
438	node = root->child;
439	while (low >= (unsigned int) (node->low + node->size)) {
440	node = node->younger;
441	}
442	if (low + size <= (unsigned int) (node->low + node->size)) {
443	/* The group is contained in the group of node. */
444	node = Mtr_FindGroup(node, low, size);
445	return(node);
446	} else {
447	return(NULL);
448	}
449
450	} /* end of Mtr_FindGroup */
451
452
453	/Function******************************************************************
454
455	Synopsis [Swaps two children of a tree node.]
456
457	Description [Swaps two children of a tree node. Adjusts the high and
458	low fields of the two nodes and their descendants. The two children
459	must be adjacent. However, first may be the younger sibling of second.
460	Returns 1 in case of success; 0 otherwise.]
461
462	SideEffects [None]
463
464	SeeAlso []
465
466	******************************************************************************/
467	int
468	Mtr_SwapGroups(
469	MtrNode * first /* first node to be swapped */,
470	MtrNode * second /* second node to be swapped */)
471	{
472	MtrNode *node;
473	MtrNode *parent;
474	int sizeFirst;
475	int sizeSecond;
476
477	if (second->younger == first) { /* make first first */
478	node = first;
479	first = second;
480	second = node;
481	} else if (first->younger != second) { /* non-adjacent */
482	return(0);
483	}
484
485	sizeFirst = first->size;
486	sizeSecond = second->size;
487
488	/* Swap the two nodes. */
489	parent = first->parent;
490	if (parent == NULL \|\| second->parent != parent) return(0);
491	if (parent->child == first) {
492	parent->child = second;
493	} else { /* first->elder != NULL */
494	first->elder->younger = second;
495	}
496	if (second->younger != NULL) {
497	second->younger->elder = first;
498	}
499	first->younger = second->younger;
500	second->elder = first->elder;
501	first->elder = second;
502	second->younger = first;
503
504	/* Adjust the high and low fields. */
505	if (!mtrShiftHL(first,sizeSecond)) return(0);
506	if (!mtrShiftHL(second,-sizeFirst)) return(0);
507
508	return(1);
509
510	} /* end of Mtr_SwapGroups */
511
512
513	/Function******************************************************************
514
515	Synopsis [Prints the groups as a parenthesized list.]
516
517	Description [Prints the groups as a parenthesized list. After each
518	group, the group's flag are printed, preceded by a `\|'. For each
519	flag (except MTR_TERMINAL) a character is printed.
520	<ul>
521	<li>F: MTR_FIXED
522	<li>N: MTR_NEWNODE
523	<li>S: MTR_SOFT
524	</ul>
525	The second argument, silent, if different from 0, causes
526	Mtr_PrintGroups to only check the syntax of the group tree.
527	]
528
529	SideEffects [None]
530
531	SeeAlso [Mtr_PrintTree]
532
533	******************************************************************************/
534	void
535	Mtr_PrintGroups(
536	MtrNode * root /* root of the group tree */,
537	int silent /* flag to check tree syntax only */)
538	{
539	MtrNode *node;
540
541	assert(root != NULL);
542	assert(root->younger == NULL \|\| root->younger->elder == root);
543	assert(root->elder == NULL \|\| root->elder->younger == root);
544	if (!silent) (void) printf("(%d",root->low);
545	if (MTR_TEST(root,MTR_TERMINAL) \|\| root->child == NULL) {
546	if (!silent) (void) printf(",");
547	} else {
548	node = root->child;
549	while (node != NULL) {
550	assert(node->low >= root->low && (int) (node->low + node->size) <= (int) (root->low + root->size));
551	assert(node->parent == root);
552	Mtr_PrintGroups(node,silent);
553	node = node->younger;
554	}
555	}
556	if (!silent) {
557	(void) printf("%d", root->low + root->size - 1);
558	if (root->flags != MTR_DEFAULT) {
559	(void) printf("\|");
560	if (MTR_TEST(root,MTR_FIXED)) (void) printf("F");
561	if (MTR_TEST(root,MTR_NEWNODE)) (void) printf("N");
562	if (MTR_TEST(root,MTR_SOFT)) (void) printf("S");
563	}
564	(void) printf(")");
565	if (root->parent == NULL) (void) printf("\n");
566	}
567	assert((root->flags &~(MTR_TERMINAL \| MTR_SOFT \| MTR_FIXED \| MTR_NEWNODE)) == 0);
568	return;
569
570	} /* end of Mtr_PrintGroups */
571
572
573	/Function******************************************************************
574
575	Synopsis [Reads groups from a file and creates a group tree.]
576
577	Description [Reads groups from a file and creates a group tree.
578	Each group is specified by three fields:
579	<xmp>
580	low size flags.
581	</xmp>
582	Low and size are (short) integers. Flags is a string composed of the
583	following characters (with associated translation):
584	<ul>
585	<li>D: MTR_DEFAULT
586	<li>F: MTR_FIXED
587	<li>N: MTR_NEWNODE
588	<li>S: MTR_SOFT
589	<li>T: MTR_TERMINAL
590	</ul>
591	Normally, the only flags that are needed are D and F. Groups and
592	fields are separated by white space (spaces, tabs, and newlines).
593	Returns a pointer to the group tree if successful; NULL otherwise.]
594
595	SideEffects [None]
596
597	SeeAlso [Mtr_InitGroupTree Mtr_MakeGroup]
598
599	******************************************************************************/
600	MtrNode *
601	Mtr_ReadGroups(
602	FILE * fp /* file pointer */,
603	int nleaves /* number of leaves of the new tree */)
604	{
605	int low;
606	int size;
607	int err;
608	unsigned int flags;
609	MtrNode *root;
610	MtrNode *node;
611	char attrib[8*sizeof(unsigned int)+1];
612	char *c;
613
614	root = Mtr_InitGroupTree(0,nleaves);
615	if (root == NULL) return NULL;
616
617	while (! feof(fp)) {
618	/* Read a triple and check for consistency. */
619	err = fscanf(fp, "%d %d %s", &low, &size, attrib);
620	if (err == EOF) {
621	break;
622	} else if (err != 3) {
623	return(NULL);
624	} else if (low < 0 \|\| low+size > nleaves \|\| size < 1) {
625	return(NULL);
626	} else if (strlen(attrib) > 8 * sizeof(MtrHalfWord)) {
627	/* Not enough bits in the flags word to store these many
628	** attributes. */
629	return(NULL);
630	}
631
632	/* Parse the flag string. Currently all flags are permitted,
633	** to make debugging easier. Normally, specifying NEWNODE
634	** wouldn't be allowed. */
635	flags = MTR_DEFAULT;
636	for (c=attrib; *c != 0; c++) {
637	switch (*c) {
638	case 'D':
639	break;
640	case 'F':
641	flags \|= MTR_FIXED;
642	break;
643	case 'N':
644	flags \|= MTR_NEWNODE;
645	break;
646	case 'S':
647	flags \|= MTR_SOFT;
648	break;
649	case 'T':
650	flags \|= MTR_TERMINAL;
651	break;
652	default:
653	return NULL;
654	}
655	}
656	node = Mtr_MakeGroup(root, (MtrHalfWord) low, (MtrHalfWord) size,
657	flags);
658	if (node == NULL) return(NULL);
659	}
660
661	return(root);
662
663	} /* end of Mtr_ReadGroups */
664
665
666	/---------------------------------------------------------------------------/
667	/* Definition of internal functions */
668	/---------------------------------------------------------------------------/
669
670	/---------------------------------------------------------------------------/
671	/* Definition of static functions */
672	/---------------------------------------------------------------------------/
673
674
675	/Function******************************************************************
676
677	Synopsis [Adjusts the low fields of a node and its descendants.]
678
679	Description [Adjusts the low fields of a node and its
680	descendants. Adds shift to low of each node. Checks that no
681	out-of-bounds values result. Returns 1 in case of success; 0
682	otherwise.]
683
684	SideEffects [None]
685
686	SeeAlso []
687
688	******************************************************************************/
689	static int
690	mtrShiftHL(
691	MtrNode * node /* group tree node */,
692	int shift /* amount by which low should be changed */)
693	{
694	MtrNode *auxnode;
695	int low;
696
697	low = (int) node->low;
698
699
700	low += shift;
701
702	if (low < 0 \|\| low + (int) (node->size - 1) > (int) MTR_MAXHIGH) return(0);
703
704	node->low = (MtrHalfWord) low;
705
706	if (!MTR_TEST(node,MTR_TERMINAL) && node->child != NULL) {
707	auxnode = node->child;
708	do {
709	if (!mtrShiftHL(auxnode,shift)) return(0);
710	auxnode = auxnode->younger;
711	} while (auxnode != NULL);
712	}
713
714	return(1);
715
716	} /* end of mtrShiftHL */

Note: See TracBrowser for help on using the repository browser.

Download in other formats: