1 files changed, 137 insertions, 0 deletions
diff --git a/src/packedintarray.cpp b/src/packedintarray.cpp
new file mode 100644
index 0000000..817a7ab
--- /dev/null
+++ b/src/packedintarray.cpp
@@ -0,0 +1,137 @@
+#include "packedintarray.h"
+#include <bu/sio.h>
+#define bitsizeof( x )      ((sizeof(x))*8)
+#define StoreBits           ((bitsizeof(PackedIntArray::Store)))
+#define StoreCount( x )     (((x*iBitWidth)/StoreBits)+(((x*iBitWidth)%StoreBits)?1:0))
+PackedIntArray::PackedIntArray( PackedIntArray::Unit iBitWidth ) :
+    iBitWidth( iBitWidth ),
+    aData( NULL ),
+    iCapacity( 0 ),
+    iCount( 0 ),
+    uMask( 0 )
+{
+    aData = new Store[4];
+    iCapacity = (StoreBits*4)/iBitWidth;
+    if( iBitWidth < StoreBits )
+    {
+        if( (StoreBits%iBitWidth) == 0 )
+            iMaxSpan = 1;
+        else
+        {
+            iMaxSpan = (iBitWidth/StoreBits)+1;
+        }
+    }
+    for( int j = 0; j < iBitWidth; j++ )
+        uMask |= (1<<j);
+}
+PackedIntArray::PackedIntArray( PackedIntArray::Unit iBitWidth, int iCount ):
+    iBitWidth( iBitWidth ),
+    aData( NULL ),
+    iCapacity( StoreCount(iCount) ),
+    iCount( iCount ),
+    uMask( 0 )
+{
+    aData = new Store[StoreCount(iCapacity)];
+    memset( aData, 0, StoreCount(iCapacity));
+    for( int j = 0; j < iBitWidth; j++ )
+        uMask |= (1<<j);
+}
+PackedIntArray::~PackedIntArray()
+{
+    delete[] aData;
+}
+void PackedIntArray::append( PackedIntArray::Unit i )
+{
+    iCount++;
+    checkCapacity();
+    set( iCount-1, i );
+}
+PackedIntArray::Unit PackedIntArray::get( int idx ) const
+{
+    int iStore = idx*iBitWidth/StoreBits;
+    int iBit = (idx*iBitWidth)%StoreBits;
+//    Bu::println("idx = %1, iStore = %2, iBit = %3").
+//        arg( idx ).arg( iStore ).arg( iBit );
+    Unit ret = (aData[iStore]>>iBit)&uMask;
+    for( iBit = StoreBits-iBit; iBit < iBitWidth; )
+    {
+        iStore++;
+//        Bu::println("  ==> iStore = %2, iBit = %3").
+//            arg( idx ).arg( iStore ).arg( iBit );
+        ret |= (aData[iStore]&((Store)uMask)>>iBit)<<iBit;
+        iBit += StoreBits;
+    }
+    return ret;
+}
+PackedIntArray::Unit PackedIntArray::set( int idx, PackedIntArray::Unit i )
+{
+    int iStore = idx*iBitWidth/StoreBits;
+    int iBit = (idx*iBitWidth)%StoreBits;
+//    Bu::println("idx = %1, iStore = %2, iBit = %3").
+//        arg( idx ).arg( iStore ).arg( iBit );
+    aData[iStore] = (aData[iStore]& ~(((Store)uMask)<<iBit)) |
+        ((Store)i)<<iBit;
+    for( iBit = StoreBits-iBit; iBit < iBitWidth; )
+    {
+        iStore++;
+//        Bu::println("  ==> iStore = %2, iBit = %3").
+//            arg( idx ).arg( iStore ).arg( iBit );
+        aData[iStore] = (aData[iStore]& ~(((Store)uMask)>>iBit)) |
+            ((Store)i)>>iBit;
+        iBit += StoreBits;
+    }
+}
+Bu::String PackedIntArray::toBitString() const
+{
+    Bu::String sRet;
+    for( int j = iCount*iBitWidth-1; j >= 0; j-- )
+    {
+        sRet += (aData[j/StoreBits] & (1<<(j%StoreBits)))
+            ? "1" : "0";
+        if( j > 0 && j%iBitWidth == 0 )
+            sRet += " ";
+    }
+    return sRet;
+}
+Bu::String PackedIntArray::toString() const
+{
+    Bu::String sRet;
+    for( int j = iCount-1; j >= 0; j-- )
+    {
+        sRet += (char)(get(j))+'0';
+    }
+    return sRet;
+}
+void PackedIntArray::checkCapacity()
+{
+    if( iCount > iCapacity )
+    {
+        Bu::println("!!! Resizing !!!");
+        Store *aOldData = aData;
+        int iNewSize = StoreCount(iCapacity*2);
+        int iSize = StoreCount(iCapacity);
+        Bu::println("  %1 => %2 (%3 bit words)").arg( iSize ).arg( iNewSize )
+            .arg( StoreBits );
+        aData = new Store[iNewSize];
+        memset( aData, 0, iNewSize*sizeof(Store) );
+        memcpy( aData, aOldData, iSize*sizeof(Store) );
+        iCapacity *= 2;
+        delete[] aOldData;
+    }
+}

diff --git a/src/packedintarray.cpp b/src/packedintarray.cpp new file mode 100644 index 0000000..817a7ab --- /dev/null +++ b/src/packedintarray.cpp
@@ -0,0 +1,137 @@
	1	#include "packedintarray.h"
	2
	3	#include <bu/sio.h>
	4
	5	#define bitsizeof( x ) ((sizeof(x))*8)
	6	#define StoreBits ((bitsizeof(PackedIntArray::Store)))
	7	#define StoreCount( x ) (((xiBitWidth)/StoreBits)+(((xiBitWidth)%StoreBits)?1:0))
	8
	9	PackedIntArray::PackedIntArray( PackedIntArray::Unit iBitWidth ) :
	10	iBitWidth( iBitWidth ),
	11	aData( NULL ),
	12	iCapacity( 0 ),
	13	iCount( 0 ),
	14	uMask( 0 )
	15	{
	16	aData = new Store[4];
	17	iCapacity = (StoreBits*4)/iBitWidth;
	18	if( iBitWidth < StoreBits )
	19	{
	20	if( (StoreBits%iBitWidth) == 0 )
	21	iMaxSpan = 1;
	22	else
	23	{
	24	iMaxSpan = (iBitWidth/StoreBits)+1;
	25	}
	26	}
	27	for( int j = 0; j < iBitWidth; j++ )
	28	uMask \|= (1<<j);
	29	}
	30
	31	PackedIntArray::PackedIntArray( PackedIntArray::Unit iBitWidth, int iCount ):
	32	iBitWidth( iBitWidth ),
	33	aData( NULL ),
	34	iCapacity( StoreCount(iCount) ),
	35	iCount( iCount ),
	36	uMask( 0 )
	37	{
	38	aData = new Store[StoreCount(iCapacity)];
	39	memset( aData, 0, StoreCount(iCapacity));
	40	for( int j = 0; j < iBitWidth; j++ )
	41	uMask \|= (1<<j);
	42	}
	43
	44	PackedIntArray::~PackedIntArray()
	45	{
	46	delete[] aData;
	47	}
	48
	49	void PackedIntArray::append( PackedIntArray::Unit i )
	50	{
	51	iCount++;
	52	checkCapacity();
	53	set( iCount-1, i );
	54	}
	55
	56	PackedIntArray::Unit PackedIntArray::get( int idx ) const
	57	{
	58	int iStore = idx*iBitWidth/StoreBits;
	59	int iBit = (idx*iBitWidth)%StoreBits;
	60	// Bu::println("idx = %1, iStore = %2, iBit = %3").
	61	// arg( idx ).arg( iStore ).arg( iBit );
	62
	63	Unit ret = (aData[iStore]>>iBit)&uMask;
	64
	65	for( iBit = StoreBits-iBit; iBit < iBitWidth; )
	66	{
	67	iStore++;
	68	// Bu::println(" ==> iStore = %2, iBit = %3").
	69	// arg( idx ).arg( iStore ).arg( iBit );
	70	ret \|= (aData[iStore]&((Store)uMask)>>iBit)<<iBit;
	71	iBit += StoreBits;
	72	}
	73	return ret;
	74	}
	75
	76	PackedIntArray::Unit PackedIntArray::set( int idx, PackedIntArray::Unit i )
	77	{
	78	int iStore = idx*iBitWidth/StoreBits;
	79	int iBit = (idx*iBitWidth)%StoreBits;
	80	// Bu::println("idx = %1, iStore = %2, iBit = %3").
	81	// arg( idx ).arg( iStore ).arg( iBit );
	82
	83	aData[iStore] = (aData[iStore]& ~(((Store)uMask)<<iBit)) \|
	84	((Store)i)<<iBit;
	85	for( iBit = StoreBits-iBit; iBit < iBitWidth; )
	86	{
	87	iStore++;
	88	// Bu::println(" ==> iStore = %2, iBit = %3").
	89	// arg( idx ).arg( iStore ).arg( iBit );
	90	aData[iStore] = (aData[iStore]& ~(((Store)uMask)>>iBit)) \|
	91	((Store)i)>>iBit;
	92	iBit += StoreBits;
	93	}
	94	}
	95
	96	Bu::String PackedIntArray::toBitString() const
	97	{
	98	Bu::String sRet;
	99	for( int j = iCount*iBitWidth-1; j >= 0; j-- )
	100	{
	101	sRet += (aData[j/StoreBits] & (1<<(j%StoreBits)))
	102	? "1" : "0";
	103	if( j > 0 && j%iBitWidth == 0 )
	104	sRet += " ";
	105	}
	106	return sRet;
	107	}
	108
	109	Bu::String PackedIntArray::toString() const
	110	{
	111	Bu::String sRet;
	112	for( int j = iCount-1; j >= 0; j-- )
	113	{
	114	sRet += (char)(get(j))+'0';
	115	}
	116
	117	return sRet;
	118	}
	119
	120	void PackedIntArray::checkCapacity()
	121	{
	122	if( iCount > iCapacity )
	123	{
	124	Bu::println("!!! Resizing !!!");
	125	Store *aOldData = aData;
	126	int iNewSize = StoreCount(iCapacity*2);
	127	int iSize = StoreCount(iCapacity);
	128	Bu::println(" %1 => %2 (%3 bit words)").arg( iSize ).arg( iNewSize )
	129	.arg( StoreBits );
	130	aData = new Store[iNewSize];
	131	memset( aData, 0, iNewSize*sizeof(Store) );
	132	memcpy( aData, aOldData, iSize*sizeof(Store) );
	133	iCapacity *= 2;
	134	delete[] aOldData;
	135	}
	136	}
	137