source: vis_dev/glu-2.3/src/mtr/mtrGroup.c @ 42

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

library glu 2.3
File size: 22.1 KB
RevLine 
[13]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.18 2009/02/20 02:03:47 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 SIZEOF_VOID_P == 8
545    if (!silent) (void) printf("(%u",root->low);
546#else
547    if (!silent) (void) printf("(%hu",root->low);
548#endif
549    if (MTR_TEST(root,MTR_TERMINAL) || root->child == NULL) {
550        if (!silent) (void) printf(",");
551    } else {
552        node = root->child;
553        while (node != NULL) {
554            assert(node->low >= root->low && (int) (node->low + node->size) <= (int) (root->low + root->size));
555            assert(node->parent == root);
556            Mtr_PrintGroups(node,silent);
557            node = node->younger;
558        }
559    }
560    if (!silent) {
561#if SIZEOF_VOID_P == 8
562        (void) printf("%u", root->low + root->size - 1);
563#else
564        (void) printf("%hu", root->low + root->size - 1);
565#endif
566        if (root->flags != MTR_DEFAULT) {
567            (void) printf("|");
568            if (MTR_TEST(root,MTR_FIXED)) (void) printf("F");
569            if (MTR_TEST(root,MTR_NEWNODE)) (void) printf("N");
570            if (MTR_TEST(root,MTR_SOFT)) (void) printf("S");
571        }
572        (void) printf(")");
573        if (root->parent == NULL) (void) printf("\n");
574    }
575    assert((root->flags &~(MTR_TERMINAL | MTR_SOFT | MTR_FIXED | MTR_NEWNODE)) == 0);
576    return;
577
578} /* end of Mtr_PrintGroups */
579
580
581/**Function********************************************************************
582
583  Synopsis    [Reads groups from a file and creates a group tree.]
584
585  Description [Reads groups from a file and creates a group tree.
586  Each group is specified by three fields:
587  <xmp>
588       low size flags.
589  </xmp>
590  Low and size are (short) integers. Flags is a string composed of the
591  following characters (with associated translation):
592  <ul>
593  <li>D: MTR_DEFAULT
594  <li>F: MTR_FIXED
595  <li>N: MTR_NEWNODE
596  <li>S: MTR_SOFT
597  <li>T: MTR_TERMINAL
598  </ul>
599  Normally, the only flags that are needed are D and F.  Groups and
600  fields are separated by white space (spaces, tabs, and newlines).
601  Returns a pointer to the group tree if successful; NULL otherwise.]
602
603  SideEffects [None]
604
605  SeeAlso     [Mtr_InitGroupTree Mtr_MakeGroup]
606
607******************************************************************************/
608MtrNode *
609Mtr_ReadGroups(
610  FILE * fp /* file pointer */,
611  int  nleaves /* number of leaves of the new tree */)
612{
613    int low;
614    int size;
615    int err;
616    unsigned int flags;
617    MtrNode *root;
618    MtrNode *node;
619    char attrib[8*sizeof(unsigned int)+1];
620    char *c;
621
622    root = Mtr_InitGroupTree(0,nleaves);
623    if (root == NULL) return NULL;
624
625    while (! feof(fp)) {
626        /* Read a triple and check for consistency. */
627        err = fscanf(fp, "%d %d %s", &low, &size, attrib);
628        if (err == EOF) {
629            break;
630        } else if (err != 3) {
631            Mtr_FreeTree(root);
632            return(NULL);
633        } else if (low < 0 || low+size > nleaves || size < 1) {
634            Mtr_FreeTree(root);
635            return(NULL);
636        } else if (strlen(attrib) > 8 * sizeof(MtrHalfWord)) {
637            /* Not enough bits in the flags word to store these many
638            ** attributes. */
639            Mtr_FreeTree(root);
640            return(NULL);
641        }
642
643        /* Parse the flag string. Currently all flags are permitted,
644        ** to make debugging easier. Normally, specifying NEWNODE
645        ** wouldn't be allowed. */
646        flags = MTR_DEFAULT;
647        for (c=attrib; *c != 0; c++) {
648            switch (*c) {
649            case 'D':
650                break;
651            case 'F':
652                flags |= MTR_FIXED;
653                break;
654            case 'N':
655                flags |= MTR_NEWNODE;
656                break;
657            case 'S':
658                flags |= MTR_SOFT;
659                break;
660            case 'T':
661                flags |= MTR_TERMINAL;
662                break;
663            default:
664                return NULL;
665            }
666        }
667        node = Mtr_MakeGroup(root, (MtrHalfWord) low, (MtrHalfWord) size,
668                             flags);
669        if (node == NULL) {
670            Mtr_FreeTree(root);
671            return(NULL);
672        }
673    }
674
675    return(root);
676
677} /* end of Mtr_ReadGroups */
678
679
680/*---------------------------------------------------------------------------*/
681/* Definition of internal functions                                          */
682/*---------------------------------------------------------------------------*/
683
684/*---------------------------------------------------------------------------*/
685/* Definition of static functions                                            */
686/*---------------------------------------------------------------------------*/
687
688
689/**Function********************************************************************
690
691  Synopsis    [Adjusts the low fields of a node and its descendants.]
692
693  Description [Adjusts the low fields of a node and its
694  descendants. Adds shift to low of each node. Checks that no
695  out-of-bounds values result.  Returns 1 in case of success; 0
696  otherwise.]
697
698  SideEffects [None]
699
700  SeeAlso     []
701
702******************************************************************************/
703static int
704mtrShiftHL(
705  MtrNode * node /* group tree node */,
706  int  shift /* amount by which low should be changed */)
707{
708    MtrNode *auxnode;
709    int low;
710
711    low = (int) node->low;
712
713
714    low += shift;
715
716    if (low < 0 || low + (int) (node->size - 1) > (int) MTR_MAXHIGH) return(0);
717
718    node->low = (MtrHalfWord) low;
719
720    if (!MTR_TEST(node,MTR_TERMINAL) && node->child != NULL) {
721        auxnode = node->child;
722        do {
723            if (!mtrShiftHL(auxnode,shift)) return(0);
724            auxnode = auxnode->younger;
725        } while (auxnode != NULL);
726    }
727
728    return(1);
729
730} /* end of mtrShiftHL */
Note: See TracBrowser for help on using the repository browser.