From 0c6505a26a537dc911b6566f82d759521e527c08 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Wed, 30 Jan 2008 20:01:00 -0800 Subject: Version abc80130_2 --- src/misc/vec/vecInt.h | 223 ++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 216 insertions(+), 7 deletions(-) (limited to 'src/misc/vec/vecInt.h') diff --git a/src/misc/vec/vecInt.h b/src/misc/vec/vecInt.h index 7556dd87..082ebe70 100644 --- a/src/misc/vec/vecInt.h +++ b/src/misc/vec/vecInt.h @@ -26,7 +26,6 @@ //////////////////////////////////////////////////////////////////////// #include -#include "extra.h" //////////////////////////////////////////////////////////////////////// /// PARAMETERS /// @@ -45,16 +44,20 @@ struct Vec_Int_t_ }; //////////////////////////////////////////////////////////////////////// -/// MACRO DEFITIONS /// +/// MACRO DEFINITIONS /// //////////////////////////////////////////////////////////////////////// #define Vec_IntForEachEntry( vVec, Entry, i ) \ for ( i = 0; (i < Vec_IntSize(vVec)) && (((Entry) = Vec_IntEntry(vVec, i)), 1); i++ ) #define Vec_IntForEachEntryStart( vVec, Entry, i, Start ) \ for ( i = Start; (i < Vec_IntSize(vVec)) && (((Entry) = Vec_IntEntry(vVec, i)), 1); i++ ) +#define Vec_IntForEachEntryStartStop( vVec, Entry, i, Start, Stop ) \ + for ( i = Start; (i < Stop) && (((Entry) = Vec_IntEntry(vVec, i)), 1); i++ ) +#define Vec_IntForEachEntryReverse( vVec, pEntry, i ) \ + for ( i = Vec_IntSize(vVec) - 1; (i >= 0) && (((pEntry) = Vec_IntEntry(vVec, i)), 1); i-- ) //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -100,6 +103,28 @@ static inline Vec_Int_t * Vec_IntStart( int nSize ) return p; } +/**Function************************************************************* + + Synopsis [Allocates a vector with the given size and cleans it.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline Vec_Int_t * Vec_IntStartNatural( int nSize ) +{ + Vec_Int_t * p; + int i; + p = Vec_IntAlloc( nSize ); + p->nSize = nSize; + for ( i = 0; i < nSize; i++ ) + p->pArray[i] = i; + return p; +} + /**Function************************************************************* Synopsis [Creates the vector from an integer array of the given size.] @@ -159,7 +184,7 @@ static inline Vec_Int_t * Vec_IntDup( Vec_Int_t * pVec ) Vec_Int_t * p; p = ALLOC( Vec_Int_t, 1 ); p->nSize = pVec->nSize; - p->nCap = pVec->nCap; + p->nCap = pVec->nSize; p->pArray = p->nCap? ALLOC( int, p->nCap ) : NULL; memcpy( p->pArray, pVec->pArray, sizeof(int) * pVec->nSize ); return p; @@ -292,6 +317,23 @@ static inline void Vec_IntWriteEntry( Vec_Int_t * p, int i, int Entry ) p->pArray[i] = Entry; } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Vec_IntAddToEntry( Vec_Int_t * p, int i, int Addition ) +{ + assert( i >= 0 && i < p->nSize ); + p->pArray[i] += Addition; +} + /**Function************************************************************* Synopsis [] @@ -305,6 +347,7 @@ static inline void Vec_IntWriteEntry( Vec_Int_t * p, int i, int Entry ) ***********************************************************************/ static inline int Vec_IntEntryLast( Vec_Int_t * p ) { + assert( p->nSize > 0 ); return p->pArray[p->nSize-1]; } @@ -324,6 +367,7 @@ static inline void Vec_IntGrow( Vec_Int_t * p, int nCapMin ) if ( p->nCap >= nCapMin ) return; p->pArray = REALLOC( int, p->pArray, nCapMin ); + assert( p->pArray ); p->nCap = nCapMin; } @@ -435,6 +479,33 @@ static inline void Vec_IntPush( Vec_Int_t * p, int Entry ) SeeAlso [] +***********************************************************************/ +static inline void Vec_IntPushFirst( Vec_Int_t * p, int Entry ) +{ + int i; + if ( p->nSize == p->nCap ) + { + if ( p->nCap < 16 ) + Vec_IntGrow( p, 16 ); + else + Vec_IntGrow( p, 2 * p->nCap ); + } + p->nSize++; + for ( i = p->nSize - 1; i >= 1; i-- ) + p->pArray[i] = p->pArray[i-1]; + p->pArray[0] = Entry; +} + +/**Function************************************************************* + + Synopsis [Inserts the entry while preserving the increasing order.] + + Description [] + + SideEffects [] + + SeeAlso [] + ***********************************************************************/ static inline void Vec_IntPushOrder( Vec_Int_t * p, int Entry ) { @@ -455,6 +526,27 @@ static inline void Vec_IntPushOrder( Vec_Int_t * p, int Entry ) p->pArray[i+1] = Entry; } +/**Function************************************************************* + + Synopsis [Inserts the entry while preserving the increasing order.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Vec_IntPushUniqueOrder( Vec_Int_t * p, int Entry ) +{ + int i; + for ( i = 0; i < p->nSize; i++ ) + if ( p->pArray[i] == Entry ) + return 1; + Vec_IntPushOrder( p, Entry ); + return 0; +} + /**Function************************************************************* Synopsis [] @@ -476,6 +568,31 @@ static inline int Vec_IntPushUnique( Vec_Int_t * p, int Entry ) return 0; } +/**Function************************************************************* + + Synopsis [Returns the pointer to the next nWords entries in the vector.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline unsigned * Vec_IntFetch( Vec_Int_t * p, int nWords ) +{ + if ( nWords == 0 ) + return NULL; + assert( nWords > 0 ); + p->nSize += nWords; + if ( p->nSize > p->nCap ) + { +// Vec_IntGrow( p, 2 * p->nSize ); + return NULL; + } + return ((unsigned *)p->pArray) + p->nSize - nWords; +} + /**Function************************************************************* Synopsis [Returns the last entry and removes it from the list.] @@ -493,6 +610,26 @@ static inline int Vec_IntPop( Vec_Int_t * p ) return p->pArray[--p->nSize]; } +/**Function************************************************************* + + Synopsis [Find entry.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Vec_IntFind( Vec_Int_t * p, int Entry ) +{ + int i; + for ( i = 0; i < p->nSize; i++ ) + if ( p->pArray[i] == Entry ) + return i; + return -1; +} + /**Function************************************************************* Synopsis [] @@ -504,16 +641,19 @@ static inline int Vec_IntPop( Vec_Int_t * p ) SeeAlso [] ***********************************************************************/ -static inline void Vec_IntRemove( Vec_Int_t * p, int Entry ) +static inline int Vec_IntRemove( Vec_Int_t * p, int Entry ) { int i; for ( i = 0; 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************************************************************* @@ -617,9 +757,78 @@ static inline void Vec_IntSortUnsigned( Vec_Int_t * p ) (int (*)(const void *, const void *)) Vec_IntSortCompareUnsigned ); } +/**Function************************************************************* + + Synopsis [Returns the number of common entries.] + + Description [Assumes that the vectors are sorted in the increasing order.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Vec_IntTwoCountCommon( 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 Counter = 0; + while ( pBeg1 < pEnd1 && pBeg2 < pEnd2 ) + { + if ( *pBeg1 == *pBeg2 ) + pBeg1++, pBeg2++, Counter++; + else if ( *pBeg1 < *pBeg2 ) + pBeg1++; + else + pBeg2++; + } + return Counter; +} + +/**Function************************************************************* + + Synopsis [Returns the result of merging the two vectors.] + + Description [Assumes that the vectors are sorted in the increasing order.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline Vec_Int_t * Vec_IntTwoMerge( Vec_Int_t * vArr1, Vec_Int_t * vArr2 ) +{ + Vec_Int_t * vArr = Vec_IntAlloc( vArr1->nSize + vArr2->nSize ); + int * pBeg = vArr->pArray; + int * pBeg1 = vArr1->pArray; + int * pBeg2 = vArr2->pArray; + int * pEnd1 = vArr1->pArray + vArr1->nSize; + int * pEnd2 = vArr2->pArray + vArr2->nSize; + while ( pBeg1 < pEnd1 && pBeg2 < pEnd2 ) + { + if ( *pBeg1 == *pBeg2 ) + *pBeg++ = *pBeg1++, pBeg2++; + else if ( *pBeg1 < *pBeg2 ) + *pBeg++ = *pBeg1++; + else + *pBeg++ = *pBeg2++; + } + while ( pBeg1 < pEnd1 ) + *pBeg++ = *pBeg1++; + while ( pBeg2 < pEnd2 ) + *pBeg++ = *pBeg2++; + vArr->nSize = pBeg - vArr->pArray; + assert( vArr->nSize <= vArr->nCap ); + assert( vArr->nSize >= vArr1->nSize ); + assert( vArr->nSize >= vArr2->nSize ); + return vArr; +} + +#endif + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// -#endif - -- cgit v1.2.3