Initial checkin.

This project will most likely just be stuck into libbu++, but I didn't
want to deal with building it all in windows.

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;

+    }

+}

+