mvcContain.c 5.6 KB
Newer Older
Alan Mishchenko committed
1 2 3 4 5 6
/**CFile****************************************************************

  FileName    [mvcContain.c]

  PackageName [MVSIS 2.0: Multi-valued logic synthesis system.]

Alan Mishchenko committed
7
  Synopsis    [Making the cover single-cube containment ABC_FREE.]
Alan Mishchenko committed
8 9 10 11 12 13 14 15 16 17 18 19 20

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - February 1, 2003.]

  Revision    [$Id: mvcContain.c,v 1.4 2003/04/03 23:25:42 alanmi Exp $]

***********************************************************************/

#include "mvc.h"

21 22 23
ABC_NAMESPACE_IMPL_START


Alan Mishchenko committed
24 25 26 27 28 29 30 31
////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

static void Mvc_CoverRemoveDuplicates( Mvc_Cover_t * pCover );
static void Mvc_CoverRemoveContained( Mvc_Cover_t * pCover );

////////////////////////////////////////////////////////////////////////
Alan Mishchenko committed
32
///                     FUNCTION DEFINITIONS                         ///
Alan Mishchenko committed
33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176
////////////////////////////////////////////////////////////////////////


/**Function*************************************************************

  Synopsis    [Removes the contained cubes.]

  Description [Returns 1 if the cover has been changed.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int  Mvc_CoverContain( Mvc_Cover_t * pCover )
{
    int nCubes;
    nCubes = Mvc_CoverReadCubeNum( pCover );
    if ( nCubes < 2 )
        return 0;
    Mvc_CoverSetCubeSizes(pCover);
    Mvc_CoverSort( pCover, NULL, Mvc_CubeCompareSizeAndInt );
    Mvc_CoverRemoveDuplicates( pCover );
    if ( nCubes > 1 )
        Mvc_CoverRemoveContained( pCover );
    return (nCubes != Mvc_CoverReadCubeNum(pCover));
}

/**Function*************************************************************

  Synopsis    [Removes adjacent duplicated cubes from the cube list.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Mvc_CoverRemoveDuplicates( Mvc_Cover_t * pCover )
{
    Mvc_Cube_t * pPrev, * pCube, * pCube2;
    int  fEqual;

    // set the first cube of the cover
    pPrev = Mvc_CoverReadCubeHead(pCover);
    // go through all the cubes after this one
    Mvc_CoverForEachCubeStartSafe( Mvc_CubeReadNext(pPrev), pCube, pCube2 )
    {
        // compare the current cube with the prev cube
        Mvc_CubeBitEqual( fEqual, pPrev, pCube );
        if ( fEqual )
        { // they are equal - remove the current cube
            Mvc_CoverDeleteCube( pCover, pPrev, pCube );
            Mvc_CubeFree( pCover, pCube );
            // don't change the previous cube cube
        }
        else
        { // they are not equal - update the previous cube
            pPrev = pCube;
        }
    }
}

/**Function*************************************************************

  Synopsis    [Removes contained cubes from the sorted cube list.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Mvc_CoverRemoveContained( Mvc_Cover_t * pCover )
{
    Mvc_Cube_t * pCubeBeg, * pCubeEnd, * pCubeLarge;
    Mvc_Cube_t * pCube, * pCube2, * pPrev;
    unsigned sizeCur;
    int  Result;

    // since the cubes are sorted by size, it is sufficient 
    // to compare each cube with other cubes that have larger sizes
    // if the given cube implies a larger cube, the larger cube is removed
    pCubeBeg = Mvc_CoverReadCubeHead(pCover);
    do
    {
        // get the current cube size
        sizeCur = Mvc_CubeReadSize(pCubeBeg);

        // initialize the end of the given size group
        pCubeEnd = pCubeBeg;
        // find the beginning of the next size group
        Mvc_CoverForEachCubeStart( Mvc_CubeReadNext(pCubeBeg), pCube )
        {
            if ( sizeCur == Mvc_CubeReadSize(pCube) ) 
                pCubeEnd = pCube;
            else // pCube is the first cube in the new size group
                break;
        }
        // if we could not find the next size group
        // the containment check is finished
        if ( pCube == NULL )
            break;
        // otherwise, pCubeBeg/pCubeEnd are the first/last cubes of the group

        // go through all the cubes between pCubeBeg and pCubeEnd, inclusive,
        // and for each of them, try removing cubes after pCubeEnd
        Mvc_CoverForEachCubeStart( pCubeBeg, pCubeLarge )
        {
            pPrev = pCubeEnd;
            Mvc_CoverForEachCubeStartSafe( Mvc_CubeReadNext(pCubeEnd), pCube, pCube2 )
            {
                // check containment
                Mvc_CubeBitNotImpl( Result, pCube, pCubeLarge );
                if ( !Result )
                { // pCubeLarge implies pCube - remove pCube
                    Mvc_CoverDeleteCube( pCover, pPrev, pCube );
                    Mvc_CubeFree( pCover, pCube );
                    // don't update the previous cube
                }
                else
                {   // update the previous cube
                    pPrev = pCube;
                }
            }
            // quit, if the main cube was the last one of this size
            if ( pCubeLarge == pCubeEnd )
                break;
        }

        // set the beginning of the next group
        pCubeBeg = Mvc_CubeReadNext(pCubeEnd);
    }
    while ( pCubeBeg );
}


////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


177 178
ABC_NAMESPACE_IMPL_END