Version abc50904

1 files changed, 173 insertions, 0 deletions

diff --git a/src/misc/mvc/mvcContain.c b/src/misc/mvc/mvcContain.c
new file mode 100644
index 00000000..37b933b8
--- /dev/null
+++ b/src/misc/mvc/mvcContain.c
@@ -0,0 +1,173 @@
+/**CFile****************************************************************
+
+  FileName    [mvcContain.c]
+
+  PackageName [MVSIS 2.0: Multi-valued logic synthesis system.]
+
+  Synopsis    [Making the cover single-cube containment free.]
+
+  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"
+
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+static void Mvc_CoverRemoveDuplicates( Mvc_Cover_t * pCover );
+static void Mvc_CoverRemoveContained( Mvc_Cover_t * pCover );
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFITIONS                           ///
+////////////////////////////////////////////////////////////////////////
+
+
+/**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                                ///
+////////////////////////////////////////////////////////////////////////
+
+