trans.cc

A C++ library which finds associations within sets of items, using a fast in-memory algorithm

#include <unistd.h>
//#include <stdio.h>
#include <math.h>
#include <fstream.h>

#include "Trans.h"

//Trans::Trans( int nn ) { size = nn; t = (int *) malloc( nn*sizeof(int)) ;};
// initialize and ++ around to 1st subset
Trans::Trans( int const *p, int nn ) { size = nn; t = p; mask = 1; };
//Trans::Trans( int *p, int nn, bmap msk ) { t = p; size =nn; mask = msk; };

// floats know where their high bits are
// mask off leftmost i bits and floatify
int inline Trans::nxt( int & i ) const {  // next elt after i
	int j;
	i++;
	bmap x = (mask & ((((bmap)1)<<(size-i))-1));
	if( x ) {
		frexp( (float) x, &j );
		i = size - j ;
		return( t[i] );
		}
	else	{  // no bits left
		i = -1;
		return( -1 );
		};
};


int Trans::nxtsub() { mask = (mask + 1) % (bmap)1<<size; return mask > 0; };
int Trans::nitems() const
	{ int i = 0; bmap tmp=mask; while( tmp -= (tmp &( -tmp ))) i++; return i; };

int Trans::binsearch( int x, int l ) const {
	int u = size-1;
	while( l <= u ){
		int i = (l + u)/2;
		if( x > t[i] )
			u = i-1;
		else if( x < t[i] )
			l = i+1;
		else return i;   // found
	};
	return l;
};

// increment t past (>=) t2su
//  if t == t2, increment > t2
//  find max <= t2:
//  scan t2, while both have matching elts, set t's matches
//  if t2 runs out of elts, we have == subsets, break
//  if t runs out of elts, break
//  after mismatch t[i] < t1[j], set remaining elts of t to 1
//
//  increment t
//  check for end of 2^t
//
//   or find first miss, increment/carry from previous elt (same effect)
//
//   DCA  DB  ---> DC
//   assume input t <= t2
int Trans::nxtsub( Trans const &t2 ) {
	bmap newmask = 0;
	int i = 0, j = -1, tt;
	int eq = 0;
	while( (tt = t2.nxt(j)) > -1 )  {
		//while( i < size && t[i] > tt ) { i++; };
		//nscan+= i;
		i = binsearch( tt, i );
		if( i >= size )
			{ eq = 0;  break; }   // t ran out before t2
		// if mismatch, mask 1's for t's < tt
		if( t[i] < tt ) {
			eq = 0;
			newmask |= ((((bmap)1) << (size - i)) -1) ;
			break; };

		newmask |= ((bmap)1)<<( size- (i+1) );  //record match
		eq++;  // would like to count size of matching prefix
		};

	if( eq && newmask > mask )
		mask = newmask;
	else {
		newmask++ ;  // go to next subset > t2
		if( newmask <= mask ) { prt(1); t2.prt(1); //printf( "%lld %lld----\n", mask, newmask);
		};
		mask = newmask % (((bmap)1)<<size) ;
		};

	return( mask > 0 );

};


void Trans::prt( bool debug ) const {
	if( debug ) {
		cout << '[' << size << ',' << mask << "] " ;
		for( int i = 0; i < size; i++ ) {
			cout <<  (mask & 1<<(size-(i+1))) ? '*' : ' ' ;
			cout <<  t[i] ;
			};
		}
	else	{
		for( int i = 0; i < size; i++ )
		if(mask & 1<<(size-(i+1)))
			cout << t[i] << ' ';
		};

	cout << "\n" ;
};


// ------friend functions------

// can also compare by finding newmask as above and compare <>= mask
//  fits into compare-increment cycle
// 1. find t1.newmask >= peek() (flag if == )
// 2. return t1.mask <>== newmask
// 3. increment t1:  mask = newmask
// 4. swapsert t1 t2
int ncmp = 0;
int nintcmp = 0;

int inline cmp( Trans const & t1, Trans const & t2 ) {
	int i1 = -1, i2 = -1;
	int diff;
	ncmp++;
	nintcmp++;
	while( !(diff = (t1.nxt(i1) - t2.nxt(i2))) && i1 >= 0 && i2 >= 0) nintcmp++;
	return( diff );
};

int operator < ( Trans const &t1, Trans const &t2 ) { return( cmp( t1,t2 ) < 0 );};
int operator ==( Trans const &t1, Trans const &t2 ) { return( cmp( t1,t2 ) ==  0 );};
int operator <=( Trans const &t1, Trans const &t2 ) { return( cmp( t1,t2 ) <=  0 );};