diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2012-11-06 22:08:54 -0800 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2012-11-06 22:08:54 -0800 |
commit | 36d8c000a4b1337d1d04496a1d0bd84c464618be (patch) | |
tree | 59f037106c04c35edffc77f931b6787c9285f148 /src | |
parent | 5ed242ac549a3ae3d1c01f0b328047c1eee24db3 (diff) | |
download | abc-36d8c000a4b1337d1d04496a1d0bd84c464618be.tar.gz abc-36d8c000a4b1337d1d04496a1d0bd84c464618be.tar.bz2 abc-36d8c000a4b1337d1d04496a1d0bd84c464618be.zip |
Slightly improved cut computation.
Diffstat (limited to 'src')
-rw-r--r-- | src/map/if/ifCut.c | 86 |
1 files changed, 85 insertions, 1 deletions
diff --git a/src/map/if/ifCut.c b/src/map/if/ifCut.c index efeacdac..d23c4365 100644 --- a/src/map/if/ifCut.c +++ b/src/map/if/ifCut.c @@ -145,7 +145,7 @@ int If_CutFilter( If_Set_t * pCutSet, If_Cut_t * pCut ) SeeAlso [] ***********************************************************************/ -static inline int If_CutMergeOrdered( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC ) +static inline int If_CutMergeOrderedOld( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC ) { int i, k, c; assert( pC0->nLeaves >= pC1->nLeaves ); @@ -224,6 +224,90 @@ static inline int If_CutMergeOrdered( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * Synopsis [Merges two cuts.] + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int If_CutMergeOrdered( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC ) +{ + int nLimit = pC0->nLimit; + int nSizeC0 = pC0->nLeaves; + int nSizeC1 = pC1->nLeaves; + int i, k, c; + assert( nSizeC0 >= nSizeC1 ); + + // the case when one of the cuts is the largest + if ( nSizeC0 == nLimit ) + { + // the case of the largest cut sizes + if ( nSizeC1 == nLimit ) + { + for ( i = 0; i < nSizeC0; i++ ) + if ( pC0->pLeaves[i] != pC1->pLeaves[i] ) + return 0; + } + else + { + for ( i = 0; i < nSizeC1; i++ ) + { + for ( k = nSizeC0 - 1; k >= 0; k-- ) + if ( pC0->pLeaves[k] == pC1->pLeaves[i] ) + break; + if ( k == -1 ) // did not find + return 0; + } + } + for ( i = 0; i < nSizeC0; i++ ) + pC->pLeaves[i] = pC0->pLeaves[i]; + pC->nLeaves = nLimit; + return 1; + } + + // compare two cuts with different numbers + i = k = c = 0; + while ( 1 ) + { + if ( c == nLimit ) return 0; + if ( pC0->pLeaves[i] < pC1->pLeaves[k] ) + { + pC->pLeaves[c++] = pC0->pLeaves[i++]; + if ( i >= nSizeC0 ) goto FlushCut1; + } + else if ( pC0->pLeaves[i] > pC1->pLeaves[k] ) + { + pC->pLeaves[c++] = pC1->pLeaves[k++]; + if ( k >= nSizeC1 ) goto FlushCut0; + } + else + { + pC->pLeaves[c++] = pC0->pLeaves[i++]; k++; + if ( i >= nSizeC0 ) goto FlushCut1; + if ( k >= nSizeC1 ) goto FlushCut0; + } + } + +FlushCut0: + if ( c + nSizeC0 > nLimit + i ) return 0; + while ( i < nSizeC0 ) + pC->pLeaves[c++] = pC0->pLeaves[i++]; + pC->nLeaves = c; + return 1; + +FlushCut1: + if ( c + nSizeC1 > nLimit + k ) return 0; + while ( k < nSizeC1 ) + pC->pLeaves[c++] = pC1->pLeaves[k++]; + pC->nLeaves = c; + return 1; +} + +/**Function************************************************************* + + Synopsis [Merges two cuts.] + Description [Special case when the cut is known to exist.] SideEffects [] |