summaryrefslogtreecommitdiffstats
path: root/abc70930/src/misc/extra/extraUtilBitMatrix.c
diff options
context:
space:
mode:
Diffstat (limited to 'abc70930/src/misc/extra/extraUtilBitMatrix.c')
-rw-r--r--abc70930/src/misc/extra/extraUtilBitMatrix.c415
1 files changed, 415 insertions, 0 deletions
diff --git a/abc70930/src/misc/extra/extraUtilBitMatrix.c b/abc70930/src/misc/extra/extraUtilBitMatrix.c
new file mode 100644
index 00000000..b860a538
--- /dev/null
+++ b/abc70930/src/misc/extra/extraUtilBitMatrix.c
@@ -0,0 +1,415 @@
+/**CFile****************************************************************
+
+ FileName [extraUtilBitMatrix.c]
+
+ PackageName [extra]
+
+ Synopsis [Various reusable software utilities.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - September 1, 2003.]
+
+ Revision [$Id: extraUtilBitMatrix.c,v 1.0 2003/09/01 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "extra.h"
+
+/*---------------------------------------------------------------------------*/
+/* Constant declarations */
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/* Stucture declarations */
+/*---------------------------------------------------------------------------*/
+
+struct Extra_BitMat_t_
+{
+ unsigned ** ppData; // bit data
+ int nSize; // the number of bits in one dimension
+ int nWords; // the number of words in one dimension
+ int nBitShift; // the number of bits to shift to get words
+ unsigned uMask; // the mask to get the number of bits in the word
+ int nLookups; // the number of lookups
+ int nInserts; // the number of inserts
+ int nDeletes; // the number of deletions
+};
+
+/*---------------------------------------------------------------------------*/
+/* Type declarations */
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/* Variable declarations */
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/* Macro declarations */
+/*---------------------------------------------------------------------------*/
+
+
+/**AutomaticStart*************************************************************/
+
+/*---------------------------------------------------------------------------*/
+/* Static function prototypes */
+/*---------------------------------------------------------------------------*/
+
+/**AutomaticEnd***************************************************************/
+
+
+/*---------------------------------------------------------------------------*/
+/* Definition of exported functions */
+/*---------------------------------------------------------------------------*/
+
+/**Function*************************************************************
+
+ Synopsis [Starts the bit matrix.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Extra_BitMat_t * Extra_BitMatrixStart( int nSize )
+{
+ Extra_BitMat_t * p;
+ int i;
+ p = ALLOC( Extra_BitMat_t, 1 );
+ memset( p, 0, sizeof(Extra_BitMat_t) );
+ p->nSize = nSize;
+ p->nBitShift = (sizeof(unsigned) == 4) ? 5: 6;
+ p->uMask = (sizeof(unsigned) == 4) ? 31: 63;
+ p->nWords = nSize / (8 * sizeof(unsigned)) + ((nSize % (8 * sizeof(unsigned))) > 0);
+ p->ppData = ALLOC( unsigned *, nSize );
+ p->ppData[0] = ALLOC( unsigned, nSize * p->nWords );
+ memset( p->ppData[0], 0, sizeof(unsigned) * nSize * p->nWords );
+ for ( i = 1; i < nSize; i++ )
+ p->ppData[i] = p->ppData[i-1] + p->nWords;
+ return p;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Stops the bit matrix.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Extra_BitMatrixClean( Extra_BitMat_t * p )
+{
+ memset( p->ppData[0], 0, sizeof(unsigned) * p->nSize * p->nWords );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Stops the bit matrix.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Extra_BitMatrixStop( Extra_BitMat_t * p )
+{
+ FREE( p->ppData[0] );
+ FREE( p->ppData );
+ FREE( p );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prints the bit-matrix.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Extra_BitMatrixPrint( Extra_BitMat_t * pMat )
+{
+ int i, k, nVars;
+ printf( "\n" );
+ nVars = Extra_BitMatrixReadSize( pMat );
+ for ( i = 0; i < nVars; i++ )
+ {
+ for ( k = 0; k <= i; k++ )
+ printf( " " );
+ for ( k = i+1; k < nVars; k++ )
+ if ( Extra_BitMatrixLookup1( pMat, i, k ) )
+ printf( "1" );
+ else
+ printf( "." );
+ printf( "\n" );
+ }
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Reads the matrix size.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Extra_BitMatrixReadSize( Extra_BitMat_t * p )
+{
+ return p->nSize;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Inserts the element into the upper part.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Extra_BitMatrixInsert1( Extra_BitMat_t * p, int i, int k )
+{
+ p->nInserts++;
+ if ( i < k )
+ p->ppData[i][k>>p->nBitShift] |= (1<<(k & p->uMask));
+ else
+ p->ppData[k][i>>p->nBitShift] |= (1<<(i & p->uMask));
+}
+
+/**Function*************************************************************
+
+ Synopsis [Inserts the element into the upper part.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Extra_BitMatrixLookup1( Extra_BitMat_t * p, int i, int k )
+{
+ p->nLookups++;
+ if ( i < k )
+ return ((p->ppData[i][k>>p->nBitShift] & (1<<(k & p->uMask))) > 0);
+ else
+ return ((p->ppData[k][i>>p->nBitShift] & (1<<(i & p->uMask))) > 0);
+}
+
+/**Function*************************************************************
+
+ Synopsis [Inserts the element into the upper part.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Extra_BitMatrixDelete1( Extra_BitMat_t * p, int i, int k )
+{
+ p->nDeletes++;
+ if ( i < k )
+ p->ppData[i][k>>p->nBitShift] &= ~(1<<(k & p->uMask));
+ else
+ p->ppData[k][i>>p->nBitShift] &= ~(1<<(i & p->uMask));
+}
+
+
+
+/**Function*************************************************************
+
+ Synopsis [Inserts the element into the upper part.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Extra_BitMatrixInsert2( Extra_BitMat_t * p, int i, int k )
+{
+ p->nInserts++;
+ if ( i > k )
+ p->ppData[i][k>>p->nBitShift] |= (1<<(k & p->uMask));
+ else
+ p->ppData[k][i>>p->nBitShift] |= (1<<(i & p->uMask));
+}
+
+/**Function*************************************************************
+
+ Synopsis [Inserts the element into the upper part.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Extra_BitMatrixLookup2( Extra_BitMat_t * p, int i, int k )
+{
+ p->nLookups++;
+ if ( i > k )
+ return ((p->ppData[i][k>>p->nBitShift] & (1<<(k & p->uMask))) > 0);
+ else
+ return ((p->ppData[k][i>>p->nBitShift] & (1<<(i & p->uMask))) > 0);
+}
+
+/**Function*************************************************************
+
+ Synopsis [Inserts the element into the upper part.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Extra_BitMatrixDelete2( Extra_BitMat_t * p, int i, int k )
+{
+ p->nDeletes++;
+ if ( i > k )
+ p->ppData[i][k>>p->nBitShift] &= ~(1<<(k & p->uMask));
+ else
+ p->ppData[k][i>>p->nBitShift] &= ~(1<<(i & p->uMask));
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Inserts the element into the upper part.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Extra_BitMatrixOr( Extra_BitMat_t * p, int i, unsigned * pInfo )
+{
+ int w;
+ for ( w = 0; w < p->nWords; w++ )
+ p->ppData[i][w] |= pInfo[w];
+}
+
+/**Function*************************************************************
+
+ Synopsis [Inserts the element into the upper part.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Extra_BitMatrixOrTwo( Extra_BitMat_t * p, int i, int j )
+{
+ int w;
+ for ( w = 0; w < p->nWords; w++ )
+ p->ppData[i][w] = p->ppData[j][w] = (p->ppData[i][w] | p->ppData[j][w]);
+}
+
+/**Function*************************************************************
+
+ Synopsis [Counts the number of 1's in the upper rectangle.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Extra_BitMatrixCountOnesUpper( Extra_BitMat_t * p )
+{
+ int i, k, nTotal = 0;
+ for ( i = 0; i < p->nSize; i++ )
+ for ( k = i + 1; k < p->nSize; k++ )
+ nTotal += ( (p->ppData[i][k>>5] & (1 << (k&31))) > 0 );
+ return nTotal;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns 1 if the matrices have no entries in common.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Extra_BitMatrixIsDisjoint( Extra_BitMat_t * p1, Extra_BitMat_t * p2 )
+{
+ int i, w;
+ assert( p1->nSize == p2->nSize );
+ for ( i = 0; i < p1->nSize; i++ )
+ for ( w = 0; w < p1->nWords; w++ )
+ if ( p1->ppData[i][w] & p2->ppData[i][w] )
+ return 0;
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns 1 if the matrix is a set of cliques.]
+
+ Description [For example pairwise symmetry info should satisfy this property.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Extra_BitMatrixIsClique( Extra_BitMat_t * pMat )
+{
+ int v, u, i;
+ for ( v = 0; v < pMat->nSize; v++ )
+ for ( u = v+1; u < pMat->nSize; u++ )
+ {
+ if ( !Extra_BitMatrixLookup1( pMat, v, u ) )
+ continue;
+ // v and u are symmetric
+ for ( i = 0; i < pMat->nSize; i++ )
+ {
+ if ( i == v || i == u )
+ continue;
+ // i is neither v nor u
+ // the symmetry status of i is the same w.r.t. to v and u
+ if ( Extra_BitMatrixLookup1( pMat, i, v ) != Extra_BitMatrixLookup1( pMat, i, u ) )
+ return 0;
+ }
+ }
+ return 1;
+}
+
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-01 23:51:25 +0000