/* Calculate (unsigned)floor(log2(value)) */ /* If value is 0, returns -1 */ template struct Log2Floor { enum { Bits = Log2Floor::Bits + 1 }; }; template<> struct Log2Floor<1> { enum { Bits = 0 }; }; template<> struct Log2Floor<0> { enum { Bits = -1 }; }; /* Calculate (unsigned)ceil(log2(value)) */ /* Requires the fact that Log2Floor<0> returns -1 */ template struct Log2Ceil { enum { PowerOf2 = !(T&(T-1)), Bits = Log2Floor::Bits + 2 - PowerOf2 }; }; /* If the number of bytes is evenly divisible by sizeof(long), chooses long. * If the number of bytes is evenly divisible by sizeof(short), chooses short. * Otherwise chooses char. */ template struct OptimalTypePerRemainder { typedef unsigned char Type; }; template<> struct OptimalTypePerRemainder { typedef unsigned long Type; }; template<> struct OptimalTypePerRemainder { typedef unsigned short Type; }; /* Calculates the optimal storage type depending on number of bytes */ template struct OptimalStorageType { typedef typename OptimalTypePerRemainder::Type Type; }; template class CompressedIntArrayRep { private: enum { BitsPerOne = Log2Ceil::Bits }; enum { BinaryMaxValue = 1 << BitsPerOne }; enum { MaxBits = MaxCount*BitsPerOne }; enum { MaxBytes = (MaxBits+7)/8 }; typedef typename OptimalStorageType::Type ValueType; enum { ValueBits = sizeof(ValueType)*8 }; enum { MaxUnits = (MaxBytes*8+(ValueBits-1)) / ValueBits }; protected: ValueType Rep[MaxUnits]; public: unsigned Get_nth(unsigned index) const { unsigned result=0, done = 0; unsigned shift = index*BitsPerOne; unsigned bytepos = shift / ValueBits; for(shift %= ValueBits; done < BitsPerOne; shift=0,++bytepos) { unsigned bits_here = std::min(BitsPerOne-done, ValueBits-shift); unsigned mask = (1 << bits_here)-1; result += ((Rep[bytepos] >> shift) & mask) << done; done += bits_here; } return result; } void Set_nth(unsigned index, unsigned newvalue) { unsigned done = 0; unsigned shift = index*BitsPerOne; unsigned bytepos = shift / ValueBits; for(shift %= ValueBits; done < BitsPerOne; shift=0,++bytepos) { if(bytepos >= MaxUnits) { abort(); } unsigned bits_here = std::min(BitsPerOne-done, ValueBits-shift); unsigned mask = (1 << bits_here)-1; Rep[bytepos] = Rep[bytepos] & ~(mask << shift) | (((newvalue >> done) & mask) << shift); done += bits_here; } } } __attribute__((packed));