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

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

src glu
File size: 21.8 KB
RevLine 
[8]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
83static 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
96static 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******************************************************************************/
118MtrNode *
119Mtr_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******************************************************************************/
155MtrNode *
156Mtr_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******************************************************************************/
354MtrNode *
355Mtr_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******************************************************************************/
406MtrNode *
407Mtr_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******************************************************************************/
467int
468Mtr_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******************************************************************************/
534void
535Mtr_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******************************************************************************/
600MtrNode *
601Mtr_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******************************************************************************/
689static int
690mtrShiftHL(
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.