From f34eb76357fdfc314d6451fd11a2e4d6fcfce434 Mon Sep 17 00:00:00 2001
From: Mike Buland <mike@xagasoft.com>
Date: Mon, 15 Apr 2013 15:28:12 -0600
Subject: 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.
---
 src/packedintarray.cpp | 137 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 137 insertions(+)
 create mode 100644 src/packedintarray.cpp

(limited to 'src/packedintarray.cpp')

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;
+    }
+}
+
-- 
cgit v1.2.3