src/misc/extra/extraUtilBitMatrix.c File Reference

#include "extra.h"
Include dependency graph for extraUtilBitMatrix.c:

Go to the source code of this file.

Data Structures

struct  Extra_BitMat_t_

Functions

Extra_BitMat_t * Extra_BitMatrixStart (int nSize)
void Extra_BitMatrixClean (Extra_BitMat_t *p)
void Extra_BitMatrixStop (Extra_BitMat_t *p)
void Extra_BitMatrixPrint (Extra_BitMat_t *pMat)
int Extra_BitMatrixReadSize (Extra_BitMat_t *p)
void Extra_BitMatrixInsert1 (Extra_BitMat_t *p, int i, int k)
int Extra_BitMatrixLookup1 (Extra_BitMat_t *p, int i, int k)
void Extra_BitMatrixDelete1 (Extra_BitMat_t *p, int i, int k)
void Extra_BitMatrixInsert2 (Extra_BitMat_t *p, int i, int k)
int Extra_BitMatrixLookup2 (Extra_BitMat_t *p, int i, int k)
void Extra_BitMatrixDelete2 (Extra_BitMat_t *p, int i, int k)
void Extra_BitMatrixOr (Extra_BitMat_t *p, int i, unsigned *pInfo)
void Extra_BitMatrixOrTwo (Extra_BitMat_t *p, int i, int j)
int Extra_BitMatrixCountOnesUpper (Extra_BitMat_t *p)
int Extra_BitMatrixIsDisjoint (Extra_BitMat_t *p1, Extra_BitMat_t *p2)
int Extra_BitMatrixIsClique (Extra_BitMat_t *pMat)

Function Documentation

void Extra_BitMatrixClean ( Extra_BitMat_t *  p  ) 

Function*************************************************************

Synopsis [Stops the bit matrix.]

Description []

SideEffects []

SeeAlso []

Definition at line 107 of file extraUtilBitMatrix.c.

00108 {
00109     memset( p->ppData[0], 0, sizeof(unsigned) * p->nSize * p->nWords );
00110 }

int Extra_BitMatrixCountOnesUpper ( Extra_BitMat_t *  p  ) 

Function*************************************************************

Synopsis [Counts the number of 1's in the upper rectangle.]

Description []

SideEffects []

SeeAlso []

Definition at line 346 of file extraUtilBitMatrix.c.

00347 {
00348     int i, k, nTotal = 0;
00349     for ( i = 0; i < p->nSize; i++ )
00350         for ( k = i + 1; k < p->nSize; k++ )
00351             nTotal += ( (p->ppData[i][k>>5] & (1 << (k&31))) > 0 );
00352     return nTotal;
00353 }

void Extra_BitMatrixDelete1 ( Extra_BitMat_t *  p,
int  i,
int  k 
)

Function*************************************************************

Synopsis [Inserts the element into the upper part.]

Description []

SideEffects []

SeeAlso []

Definition at line 227 of file extraUtilBitMatrix.c.

00228 {
00229     p->nDeletes++;
00230     if ( i < k )
00231         p->ppData[i][k>>p->nBitShift] &= ~(1<<(k & p->uMask));
00232     else
00233         p->ppData[k][i>>p->nBitShift] &= ~(1<<(i & p->uMask));
00234 }

void Extra_BitMatrixDelete2 ( Extra_BitMat_t *  p,
int  i,
int  k 
)

Function*************************************************************

Synopsis [Inserts the element into the upper part.]

Description []

SideEffects []

SeeAlso []

Definition at line 289 of file extraUtilBitMatrix.c.

00290 {
00291     p->nDeletes++;
00292     if ( i > k )
00293         p->ppData[i][k>>p->nBitShift] &= ~(1<<(k & p->uMask));
00294     else
00295         p->ppData[k][i>>p->nBitShift] &= ~(1<<(i & p->uMask));
00296 }

void Extra_BitMatrixInsert1 ( Extra_BitMat_t *  p,
int  i,
int  k 
)

Function*************************************************************

Synopsis [Inserts the element into the upper part.]

Description []

SideEffects []

SeeAlso []

Definition at line 187 of file extraUtilBitMatrix.c.

00188 {
00189     p->nInserts++;
00190     if ( i < k )
00191         p->ppData[i][k>>p->nBitShift] |= (1<<(k & p->uMask));
00192     else
00193         p->ppData[k][i>>p->nBitShift] |= (1<<(i & p->uMask));
00194 }

void Extra_BitMatrixInsert2 ( Extra_BitMat_t *  p,
int  i,
int  k 
)

Function*************************************************************

Synopsis [Inserts the element into the upper part.]

Description []

SideEffects []

SeeAlso []

Definition at line 249 of file extraUtilBitMatrix.c.

00250 {
00251     p->nInserts++;
00252     if ( i > k )
00253         p->ppData[i][k>>p->nBitShift] |= (1<<(k & p->uMask));
00254     else
00255         p->ppData[k][i>>p->nBitShift] |= (1<<(i & p->uMask));
00256 }

int Extra_BitMatrixIsClique ( Extra_BitMat_t *  pMat  ) 

Function*************************************************************

Synopsis [Returns 1 if the matrix is a set of cliques.]

Description [For example pairwise symmetry info should satisfy this property.]

SideEffects []

SeeAlso []

Definition at line 388 of file extraUtilBitMatrix.c.

00389 {
00390     int v, u, i;
00391     for ( v = 0; v < pMat->nSize; v++ )
00392     for ( u = v+1; u < pMat->nSize; u++ )
00393     {
00394         if ( !Extra_BitMatrixLookup1( pMat, v, u ) )
00395             continue;
00396         // v and u are symmetric
00397         for ( i = 0; i < pMat->nSize; i++ )
00398         {
00399             if ( i == v || i == u )
00400                 continue;
00401             // i is neither v nor u
00402             // the symmetry status of i is the same w.r.t. to v and u
00403             if ( Extra_BitMatrixLookup1( pMat, i, v ) != Extra_BitMatrixLookup1( pMat, i, u ) )
00404                 return 0;
00405         }
00406     }
00407     return 1;
00408 }

int Extra_BitMatrixIsDisjoint ( Extra_BitMat_t *  p1,
Extra_BitMat_t *  p2 
)

Function*************************************************************

Synopsis [Returns 1 if the matrices have no entries in common.]

Description []

SideEffects []

SeeAlso []

Definition at line 366 of file extraUtilBitMatrix.c.

00367 {
00368     int i, w;
00369     assert( p1->nSize == p2->nSize );
00370     for ( i = 0; i < p1->nSize; i++ )
00371         for ( w = 0; w < p1->nWords; w++ )
00372             if ( p1->ppData[i][w] & p2->ppData[i][w] )
00373                 return 0;
00374     return 1;
00375 }

int Extra_BitMatrixLookup1 ( Extra_BitMat_t *  p,
int  i,
int  k 
)

Function*************************************************************

Synopsis [Inserts the element into the upper part.]

Description []

SideEffects []

SeeAlso []

Definition at line 207 of file extraUtilBitMatrix.c.

00208 {
00209     p->nLookups++;
00210     if ( i < k )
00211         return ((p->ppData[i][k>>p->nBitShift] & (1<<(k & p->uMask))) > 0);
00212     else
00213         return ((p->ppData[k][i>>p->nBitShift] & (1<<(i & p->uMask))) > 0);
00214 }

int Extra_BitMatrixLookup2 ( Extra_BitMat_t *  p,
int  i,
int  k 
)

Function*************************************************************

Synopsis [Inserts the element into the upper part.]

Description []

SideEffects []

SeeAlso []

Definition at line 269 of file extraUtilBitMatrix.c.

00270 {
00271     p->nLookups++;
00272     if ( i > k )
00273         return ((p->ppData[i][k>>p->nBitShift] & (1<<(k & p->uMask))) > 0);
00274     else
00275         return ((p->ppData[k][i>>p->nBitShift] & (1<<(i & p->uMask))) > 0);
00276 }

void Extra_BitMatrixOr ( Extra_BitMat_t *  p,
int  i,
unsigned *  pInfo 
)

Function*************************************************************

Synopsis [Inserts the element into the upper part.]

Description []

SideEffects []

SeeAlso []

Definition at line 310 of file extraUtilBitMatrix.c.

00311 {
00312     int w;
00313     for ( w = 0; w < p->nWords; w++ )
00314         p->ppData[i][w] |= pInfo[w];
00315 }

void Extra_BitMatrixOrTwo ( Extra_BitMat_t *  p,
int  i,
int  j 
)

Function*************************************************************

Synopsis [Inserts the element into the upper part.]

Description []

SideEffects []

SeeAlso []

Definition at line 328 of file extraUtilBitMatrix.c.

00329 {
00330     int w;
00331     for ( w = 0; w < p->nWords; w++ )
00332         p->ppData[i][w] = p->ppData[j][w] = (p->ppData[i][w] | p->ppData[j][w]);
00333 }

void Extra_BitMatrixPrint ( Extra_BitMat_t *  pMat  ) 

Function*************************************************************

Synopsis [Prints the bit-matrix.]

Description []

SideEffects []

SeeAlso []

Definition at line 141 of file extraUtilBitMatrix.c.

00142 {
00143     int i, k, nVars;
00144     printf( "\n" );
00145     nVars = Extra_BitMatrixReadSize( pMat );
00146     for ( i = 0; i < nVars; i++ )
00147     {
00148         for ( k = 0; k <= i; k++ )
00149             printf( " " );
00150         for ( k = i+1; k < nVars; k++ )
00151             if ( Extra_BitMatrixLookup1( pMat, i, k ) )
00152                 printf( "1" );
00153             else
00154                 printf( "." );
00155         printf( "\n" );
00156     }
00157 }

int Extra_BitMatrixReadSize ( Extra_BitMat_t *  p  ) 

Function*************************************************************

Synopsis [Reads the matrix size.]

Description []

SideEffects []

SeeAlso []

Definition at line 171 of file extraUtilBitMatrix.c.

00172 {
00173     return p->nSize;
00174 }

Extra_BitMat_t* Extra_BitMatrixStart ( int  nSize  ) 

AutomaticStart AutomaticEnd Function*************************************************************

Synopsis [Starts the bit matrix.]

Description []

SideEffects []

SeeAlso []

Definition at line 78 of file extraUtilBitMatrix.c.

00079 {
00080     Extra_BitMat_t * p;
00081     int i;
00082     p = ALLOC( Extra_BitMat_t, 1 );
00083     memset( p, 0, sizeof(Extra_BitMat_t) );
00084     p->nSize     = nSize;
00085     p->nBitShift = (sizeof(unsigned) == 4) ?  5:  6;
00086     p->uMask     = (sizeof(unsigned) == 4) ? 31: 63;
00087     p->nWords    = nSize / (8 * sizeof(unsigned)) + ((nSize % (8 * sizeof(unsigned))) > 0);
00088     p->ppData    = ALLOC( unsigned *, nSize );
00089     p->ppData[0] = ALLOC( unsigned, nSize * p->nWords );
00090     memset( p->ppData[0], 0, sizeof(unsigned) * nSize * p->nWords );
00091     for ( i = 1; i < nSize; i++ )
00092         p->ppData[i] = p->ppData[i-1] + p->nWords;
00093     return p;
00094 }

void Extra_BitMatrixStop ( Extra_BitMat_t *  p  ) 

Function*************************************************************

Synopsis [Stops the bit matrix.]

Description []

SideEffects []

SeeAlso []

Definition at line 123 of file extraUtilBitMatrix.c.

00124 {
00125     FREE( p->ppData[0] );
00126     FREE( p->ppData );
00127     FREE( p );
00128 }

Generated on Tue Jan 5 12:19:14 2010 for abc70930 by  doxygen 1.6.1