New fast extract.

3 files changed, 198 insertions, 7 deletions

diff --git a/src/misc/vec/vecInt.h b/src/misc/vec/vecInt.h
index 03427a0b..2fe15792 100644
--- a/src/misc/vec/vecInt.h
+++ b/src/misc/vec/vecInt.h
@@ -885,6 +885,20 @@ static inline int Vec_IntRemove( Vec_Int_t * p, int Entry )
     p->nSize--;
     return 1;
 }
+static inline int Vec_IntRemove1( Vec_Int_t * p, int Entry )
+{
+    int i;
+    for ( i = 1; i < p->nSize; i++ )
+        if ( p->pArray[i] == Entry )
+            break;
+    if ( i >= p->nSize )
+        return 0;
+    assert( i < p->nSize );
+    for ( i++; i < p->nSize; i++ )
+        p->pArray[i-1] = p->pArray[i];
+    p->nSize--;
+    return 1;
+}
 
 /**Function*************************************************************
 
@@ -1298,6 +1312,18 @@ static inline int Vec_IntTwoCountCommon( Vec_Int_t * vArr1, Vec_Int_t * vArr2 )
     }
     return Counter;
 }
+
+/**Function*************************************************************
+
+  Synopsis    [Collects common entries.]
+
+  Description [Assumes that the vectors are sorted in the increasing order.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
 static inline int Vec_IntTwoFindCommon( Vec_Int_t * vArr1, Vec_Int_t * vArr2, Vec_Int_t * vArr )
 {
     int * pBeg1 = vArr1->pArray;
@@ -1319,6 +1345,77 @@ static inline int Vec_IntTwoFindCommon( Vec_Int_t * vArr1, Vec_Int_t * vArr2, Ve
 
 /**Function*************************************************************
 
+  Synopsis    [Collects and removes common entries]
+
+  Description [Assumes that the vectors are sorted in the increasing order.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+static inline int Vec_IntTwoRemoveCommon( Vec_Int_t * vArr1, Vec_Int_t * vArr2, Vec_Int_t * vArr )
+{
+    int * pBeg1 = vArr1->pArray;
+    int * pBeg2 = vArr2->pArray;
+    int * pEnd1 = vArr1->pArray + vArr1->nSize;
+    int * pEnd2 = vArr2->pArray + vArr2->nSize;
+    int * pBeg1New = vArr1->pArray;
+    int * pBeg2New = vArr2->pArray;
+    Vec_IntClear( vArr );
+    while ( pBeg1 < pEnd1 && pBeg2 < pEnd2 )
+    {
+        if ( *pBeg1 == *pBeg2 )
+            Vec_IntPush( vArr, *pBeg1 ), pBeg1++, pBeg2++;
+        else if ( *pBeg1 < *pBeg2 )
+            *pBeg1New++ = *pBeg1++;
+        else 
+            *pBeg2New++ = *pBeg2++;
+    }
+    while ( pBeg1 < pEnd1 )
+        *pBeg1New++ = *pBeg1++;
+    while ( pBeg2 < pEnd2 )
+        *pBeg2New++ = *pBeg2++;
+    Vec_IntShrink( vArr1, pBeg1New - vArr1->pArray );
+    Vec_IntShrink( vArr2, pBeg2New - vArr2->pArray );
+    return Vec_IntSize(vArr);
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Removes entries of the second one from the first one.]
+
+  Description [Assumes that the vectors are sorted in the increasing order.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+static inline int Vec_IntTwoRemove( Vec_Int_t * vArr1, Vec_Int_t * vArr2 )
+{
+    int * pBeg1 = vArr1->pArray;
+    int * pBeg2 = vArr2->pArray;
+    int * pEnd1 = vArr1->pArray + vArr1->nSize;
+    int * pEnd2 = vArr2->pArray + vArr2->nSize;
+    int * pBeg1New = vArr1->pArray;
+    while ( pBeg1 < pEnd1 && pBeg2 < pEnd2 )
+    {
+        if ( *pBeg1 == *pBeg2 )
+            pBeg1++, pBeg2++;
+        else if ( *pBeg1 < *pBeg2 )
+            *pBeg1New++ = *pBeg1++;
+        else 
+            pBeg2++;
+    }
+    while ( pBeg1 < pEnd1 )
+        *pBeg1New++ = *pBeg1++;
+    Vec_IntShrink( vArr1, pBeg1New - vArr1->pArray );
+    return Vec_IntSize(vArr1);
+}
+
+/**Function*************************************************************
+
   Synopsis    [Returns the result of merging the two vectors.]
 
   Description [Assumes that the vectors are sorted in the increasing order.]
@@ -1358,7 +1455,7 @@ static inline Vec_Int_t * Vec_IntTwoMerge( Vec_Int_t * vArr1, Vec_Int_t * vArr2
 
 /**Function*************************************************************
 
-  Synopsis    [Returns the result of merging the two vectors.]
+  Synopsis    [Returns the result of splitting of the two vectors.]
 
   Description [Assumes that the vectors are sorted in the increasing order.]
                
diff --git a/src/misc/vec/vecQue.h b/src/misc/vec/vecQue.h
index 83be97a8..445c6fb3 100644
--- a/src/misc/vec/vecQue.h
+++ b/src/misc/vec/vecQue.h
@@ -94,7 +94,7 @@ static inline void Vec_QueFreeP( Vec_Que_t ** p )
 }
 static inline void Vec_QueSetCosts( Vec_Que_t * p, float * pCosts )
 {
-    assert( p->pCostsFlt == NULL );
+//    assert( p->pCostsFlt == NULL );
     p->pCostsFlt = pCosts;
 }
 static inline void Vec_QueGrow( Vec_Que_t * p, int nCapMin )
@@ -215,12 +215,15 @@ static inline void Vec_QueUpdate( Vec_Que_t * p, int v )
 ***********************************************************************/
 static inline int Vec_QueIsMember( Vec_Que_t * p, int v )
 {
-    return (int)( p->pOrder[v] >= 0 );
+    assert( v >= 0 );
+    return (int)( v < p->nCap && p->pOrder[v] >= 0 );
 }
 static inline void Vec_QuePush( Vec_Que_t * p, int v )
 {
-    if ( p->nSize == p->nCap )
-        Vec_QueGrow( p, 2 * p->nCap );
+    if ( p->nSize >= p->nCap )
+        Vec_QueGrow( p, Abc_MaxInt(p->nSize+1, 2*p->nCap) );
+    if ( v >= p->nCap )
+        Vec_QueGrow( p, Abc_MaxInt(v+1, 2*p->nCap) );
     assert( p->nSize < p->nCap );
     assert( p->pOrder[v] == -1 );
     assert( p->pHeap[p->nSize] == -1 );
diff --git a/src/misc/vec/vecWec.h b/src/misc/vec/vecWec.h
index 34d5d956..8a924f90 100644
--- a/src/misc/vec/vecWec.h
+++ b/src/misc/vec/vecWec.h
@@ -54,6 +54,8 @@ struct Vec_Wec_t_
 // iterators through levels 
 #define Vec_WecForEachLevel( vGlob, vVec, i )                                              \
     for ( i = 0; (i < Vec_WecSize(vGlob)) && (((vVec) = Vec_WecEntry(vGlob, i)), 1); i++ )
+#define Vec_WecForEachLevelVec( vLevels, vGlob, vVec, i )                                  \
+    for ( i = 0; (i < Vec_IntSize(vLevels)) && (((vVec) = Vec_WecEntry(vGlob, Vec_IntEntry(vLevels, i))), 1); i++ )
 #define Vec_WecForEachLevelStart( vGlob, vVec, i, LevelStart )                             \
     for ( i = LevelStart; (i < Vec_WecSize(vGlob)) && (((vVec) = Vec_WecEntry(vGlob, i)), 1); i++ )
 #define Vec_WecForEachLevelStop( vGlob, vVec, i, LevelStop )                               \
@@ -158,6 +160,27 @@ static inline int Vec_WecEntryEntry( Vec_Wec_t * p, int i, int k )
   SeeAlso     []
 
 ***********************************************************************/
+static inline Vec_Int_t * Vec_WecArray( Vec_Wec_t * p )
+{
+    return p->pArray;
+}
+static inline int Vec_WecLevelId( Vec_Wec_t * p, Vec_Int_t * vLevel )
+{
+    assert( p->pArray <= vLevel && vLevel < p->pArray + p->nSize );
+    return vLevel - p->pArray;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
 static inline int Vec_WecCap( Vec_Wec_t * p )
 {
     return p->nCap;
@@ -239,14 +262,21 @@ static inline void Vec_WecPush( Vec_Wec_t * p, int Level, int Entry )
 {
     if ( p->nSize < Level + 1 )
     {
-        Vec_WecGrow( p, Level + 1 );
+        Vec_WecGrow( p, Abc_MaxInt(2*p->nCap, Level + 1) );
         p->nSize = Level + 1;
     }
     Vec_IntPush( Vec_WecEntry(p, Level), Entry );
 }
 static inline Vec_Int_t * Vec_WecPushLevel( Vec_Wec_t * p )
 {
-    Vec_WecGrow( p, ++p->nSize );
+    if ( p->nSize == p->nCap )
+    {
+        if ( p->nCap < 16 )
+            Vec_WecGrow( p, 16 );
+        else
+            Vec_WecGrow( p, 2 * p->nCap );
+    }
+    ++p->nSize;
     return Vec_WecEntryLast( p );
 }
 
@@ -557,6 +587,67 @@ static inline Vec_Ptr_t * Vec_WecConvertToVecPtr( Vec_Wec_t * p )
     return vCopy;
 }
 
+
+/**Function*************************************************************
+
+  Synopsis    [Temporary vector marking.]
+
+  Description [The vector should be static when the marking is used.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+static inline int  Vec_WecIntHasMark( Vec_Int_t * vVec ) { return (vVec->nCap >> 30) & 1; }
+static inline void Vec_WecIntSetMark( Vec_Int_t * vVec ) { vVec->nCap |= (1<<30);         }
+static inline void Vec_WecIntXorMark( Vec_Int_t * vVec ) { vVec->nCap ^= (1<<30);         }
+static inline void Vec_WecMarkLevels( Vec_Wec_t * vCubes, Vec_Int_t * vLevels )
+{
+    Vec_Int_t * vCube;
+    int i;
+    Vec_WecForEachLevelVec( vLevels, vCubes, vCube, i )
+    {
+        assert( !Vec_WecIntHasMark( vCube ) );
+        Vec_WecIntXorMark( vCube );
+    }
+}
+static inline void Vec_WecUnmarkLevels( Vec_Wec_t * vCubes, Vec_Int_t * vLevels )
+{
+    Vec_Int_t * vCube;
+    int i;
+    Vec_WecForEachLevelVec( vLevels, vCubes, vCube, i )
+    {
+        assert( Vec_WecIntHasMark( vCube ) );
+        Vec_WecIntXorMark( vCube );
+    }
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Removes 0-size vectors.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+static inline void Vec_WecRemoveEmpty( Vec_Wec_t * vCubes )
+{
+    Vec_Int_t * vCube;
+    int i, k = 0;
+    Vec_WecForEachLevel( vCubes, vCube, i )
+        if ( Vec_IntSize(vCube) > 0 )
+            vCubes->pArray[k++] = *vCube;
+        else
+            ABC_FREE( vCube->pArray );
+    Vec_WecShrink( vCubes, k );
+//    Vec_WecSortByFirstInt( vCubes, 0 );
+}
+
+
 ABC_NAMESPACE_HEADER_END
 
 #endif