12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187 |
|
/**
* This module contains a packed bit array implementation in the style of D's
* built-in dynamic arrays.
*
* Copyright: Copyright (C) 2005-2006 Digital Mars, www.digitalmars.com.
* All rights reserved.
* License: BSD style: $(LICENSE)
* Authors: Walter Bright, Sean Kelly
*/
module tango.core.BitArray;
private import tango.core.BitManip;
/**
* This struct represents an array of boolean values, each of which occupy one
* bit of memory for storage. Thus an array of 32 bits would occupy the same
* space as one integer value. The typical array operations--such as indexing
* and sorting--are supported, as well as bitwise operations such as and, or,
* xor, and complement.
*/
struct BitArray
{
size_t len;
uint* ptr;
/**
* This initializes a BitArray of bits.length bits, where each bit value
* matches the corresponding boolean value in bits.
*
* Params:
* bits = The initialization value.
*
* Returns:
* A BitArray with the same number and sequence of elements as bits.
*/
static BitArray opCall( bool[] bits )
{
BitArray temp;
temp.length = bits.length;
foreach( pos, val; bits )
temp[pos] = val;
return temp;
}
/**
* Get the number of bits in this array.
*
* Returns:
* The number of bits in this array.
*/
size_t length()
{
return len;
}
/**
* Resizes this array to newlen bits. If newlen is larger than the current
* length, the new bits will be initialized to zero.
*
* Params:
* newlen = The number of bits this array should contain.
*/
void length( size_t newlen )
{
if( newlen != len )
{
auto olddim = dim();
auto newdim = (newlen + 31) / 32;
if( newdim != olddim )
{
// Create a fake array so we can use D's realloc machinery
uint[] buf = ptr[0 .. olddim];
buf.length = newdim; // realloc
ptr = buf.ptr;
if( newdim & 31 )
{
// Set any pad bits to 0
ptr[newdim - 1] &= ~(~0 << (newdim & 31));
}
}
len = newlen;
}
}
/**
* Gets the length of a uint array large enough to hold all stored bits.
*
* Returns:
* The size a uint array would have to be to store this array.
*/
size_t dim()
{
return (len + 31) / 32;
}
/**
* Duplicates this array, much like the dup property for built-in arrays.
*
* Returns:
* A duplicate of this array.
*/
BitArray dup()
{
BitArray ba;
uint[] buf = ptr[0 .. dim].dup;
ba.len = len;
ba.ptr = buf.ptr;
return ba;
}
debug( UnitTest )
{
unittest
{
BitArray a;
BitArray b;
a.length = 3;
a[0] = 1; a[1] = 0; a[2] = 1;
b = a.dup;
assert( b.length == 3 );
for( int i = 0; i < 3; ++i )
{
assert( b[i] == (((i ^ 1) & 1) ? true : false) );
}
}
}
/**
* Resets the length of this array to bits.length and then initializes this
*
* Resizes this array to hold bits.length bits and initializes each bit
* value to match the corresponding boolean value in bits.
*
* Params:
* bits = The initialization value.
*/
void opAssign( bool[] bits )
{
length = bits.length;
foreach( i, b; bits )
{
(*this)[i] = b;
}
}
/**
* Copy the bits from one array into this array. This is not a shallow
* copy.
*
* Params:
* rhs = A BitArray with at least the same number of bits as this bit
* array.
*
* Returns:
* A shallow copy of this array.
*
* --------------------
* BitArray ba = [0,1,0,1,0];
* BitArray ba2;
* ba2.length = ba.length;
* ba2[] = ba; // perform the copy
* ba[0] = true;
* assert(ba2[0] == false);
*/
BitArray opSliceAssign(BitArray rhs)
in
{
assert(rhs.len == len);
}
body
{
size_t mDim=len/32;
ptr[0..mDim] = rhs.ptr[0..mDim];
int rest=cast(int)(len & cast(size_t)31u);
if (rest){
uint mask=(~0u)<<rest;
ptr[mDim]=(rhs.ptr[mDim] & (~mask))|(ptr[mDim] & mask);
}
return *this;
}
/**
* Map BitArray onto target, with numbits being the number of bits in the
* array. Does not copy the data. This is the inverse of opCast.
*
* Params:
* target = The array to map.
* numbits = The number of bits to map in target.
*/
void init( void[] target, size_t numbits )
in
{
assert( numbits <= target.length * 8 );
assert( (target.length & 3) == 0 );
}
body
{
ptr = cast(uint*)target.ptr;
len = numbits;
}
debug( UnitTest )
{
unittest
{
BitArray a = [1,0,1,0,1];
BitArray b;
void[] buf;
buf = cast(void[])a;
b.init( buf, a.length );
assert( b[0] == 1 );
assert( b[1] == 0 );
assert( b[2] == 1 );
assert( b[3] == 0 );
assert( b[4] == 1 );
a[0] = 0;
assert( b[0] == 0 );
assert( a == b );
// test opSliceAssign
BitArray c;
c.length = a.length;
c[] = a;
assert( c == a );
a[0] = 1;
assert( c != a );
}
}
/**
* Reverses the contents of this array in place, much like the reverse
* property for built-in arrays.
*
* Returns:
* A shallow copy of this array.
*/
BitArray reverse()
out( result )
{
assert( result == *this );
}
body
{
if( len >= 2 )
{
bool t;
size_t lo, hi;
lo = 0;
hi = len - 1;
for( ; lo < hi; ++lo, --hi )
{
t = (*this)[lo];
(*this)[lo] = (*this)[hi];
(*this)[hi] = t;
}
}
return *this;
}
debug( UnitTest )
{
unittest
{
static bool[5] data = [1,0,1,1,0];
BitArray b = data;
b.reverse;
for( size_t i = 0; i < data.length; ++i )
{
assert( b[i] == data[4 - i] );
}
}
}
/**
* Sorts this array in place, with zero entries sorting before one. This
* is equivalent to the sort property for built-in arrays.
*
* Returns:
* A shallow copy of this array.
*/
BitArray sort()
out( result )
{
assert( result == *this );
}
body
{
if( len >= 2 )
{
size_t lo, hi;
lo = 0;
hi = len - 1;
while( true )
{
while( true )
{
if( lo >= hi )
goto Ldone;
if( (*this)[lo] == true )
break;
++lo;
}
while( true )
{
if( lo >= hi )
goto Ldone;
if( (*this)[hi] == false )
break;
--hi;
}
(*this)[lo] = false;
(*this)[hi] = true;
++lo;
--hi;
}
Ldone:
;
}
return *this;
}
debug( UnitTest )
{
unittest
{
static uint x = 0b1100011000;
static BitArray ba = { 10, &x };
ba.sort;
for( size_t i = 0; i < 6; ++i )
assert( ba[i] == false );
for( size_t i = 6; i < 10; ++i )
assert( ba[i] == true );
}
}
/**
* Operates on all bits in this array.
*
* Params:
* dg = The supplied code as a delegate.
*/
int opApply( int delegate(ref bool) dg )
{
int result;
for( size_t i = 0; i < len; ++i )
{
bool b = opIndex( i );
result = dg( b );
opIndexAssign( b, i );
if( result )
break;
}
return result;
}
/** ditto */
int opApply( int delegate(ref size_t, ref bool) dg )
{
int result;
for( size_t i = 0; i < len; ++i )
{
bool b = opIndex( i );
result = dg( i, b );
opIndexAssign( b, i );
if( result )
break;
}
return result;
}
debug( UnitTest )
{
unittest
{
BitArray a = [1,0,1];
int i;
foreach( b; a )
{
switch( i )
{
case 0: assert( b == true ); break;
case 1: assert( b == false ); break;
case 2: assert( b == true ); break;
default: assert( false );
}
i++;
}
foreach( j, b; a )
{
switch( j )
{
case 0: assert( b == true ); break;
case 1: assert( b == false ); break;
case 2: assert( b == true ); break;
default: assert( false );
}
}
}
}
/**
* Compares this array to another for equality. Two bit arrays are equal
* if they are the same size and contain the same series of bits.
*
* Params:
* rhs = The array to compare against.
*
* Returns:
* zero if not equal and non-zero otherwise.
*/
int opEquals( BitArray rhs )
{
if( this.length != rhs.length )
return 0; // not equal
uint* p1 = this.ptr;
uint* p2 = rhs.ptr;
size_t n = this.length / 32;
size_t i;
for( i = 0; i < n; ++i )
{
if( p1[i] != p2[i] )
return 0; // not equal
}
int rest = cast(int)(this.length & cast(size_t)31u);
uint mask = ~((~0u)<<rest);
return (rest == 0) || (p1[i] & mask) == (p2[i] & mask);
}
debug( UnitTest )
{
unittest
{
BitArray a = [1,0,1,0,1];
BitArray b = [1,0,1];
BitArray c = [1,0,1,0,1,0,1];
BitArray d = [1,0,1,1,1];
BitArray e = [1,0,1,0,1];
assert(a != b);
assert(a != c);
assert(a != d);
assert(a == e);
}
}
/**
* Performs a lexicographical comparison of this array to the supplied
* array.
*
* Params:
* rhs = The array to compare against.
*
* Returns:
* A value less than zero if this array sorts before the supplied array,
* zero if the arrays are equavalent, and a value greater than zero if
* this array sorts after the supplied array.
*/
int opCmp( BitArray rhs )
{
auto len = this.length;
if( rhs.length < len )
len = rhs.length;
uint* p1 = this.ptr;
uint* p2 = rhs.ptr;
size_t n = len / 32;
size_t i;
for( i = 0; i < n; ++i )
{
if( p1[i] != p2[i] ){
return ((p1[i] < p2[i])?-1:1);
}
}
int rest=cast(int)(len & cast(size_t) 31u);
if (rest>0) {
uint mask=~((~0u)<<rest);
uint v1=p1[i] & mask;
uint v2=p2[i] & mask;
if (v1 != v2) return ((v1<v2)?-1:1);
}
return ((this.length<rhs.length)?-1:((this.length==rhs.length)?0:1));
}
debug( UnitTest )
{
unittest
{
BitArray a = [1,0,1,0,1];
BitArray b = [1,0,1];
BitArray c = [1,0,1,0,1,0,1];
BitArray d = [1,0,1,1,1];
BitArray e = [1,0,1,0,1];
BitArray f = [1,0,1,0];
assert( a > b );
assert( a >= b );
assert( a < c );
assert( a <= c );
assert( a < d );
assert( a <= d );
assert( a == e );
assert( a <= e );
assert( a >= e );
assert( f > b );
}
}
/**
* Convert this array to a void array.
*
* Returns:
* This array represented as a void array.
*/
void[] opCast()
{
return cast(void[])ptr[0 .. dim];
}
debug( UnitTest )
{
unittest
{
BitArray a = [1,0,1,0,1];
void[] v = cast(void[])a;
assert( v.length == a.dim * uint.sizeof );
}
}
/**
* Support for index operations, much like the behavior of built-in arrays.
*
* Params:
* pos = The desired index position.
*
* In:
* pos must be less than the length of this array.
*
* Returns:
* The value of the bit at pos.
*/
bool opIndex( size_t pos )
in
{
assert( pos < len );
}
body
{
return cast(bool)bt( ptr, pos );
}
/**
* Generates a copy of this array with the unary complement operation
* applied.
*
* Returns:
* A new array which is the complement of this array.
*/
BitArray opCom()
{
auto dim = this.dim();
BitArray result;
result.length = len;
for( size_t i = 0; i < dim; ++i )
result.ptr[i] = ~this.ptr[i];
if( len & 31 )
result.ptr[dim - 1] &= ~(~0 << (len & 31));
return result;
}
debug( UnitTest )
{
unittest
{
BitArray a = [1,0,1,0,1];
BitArray b = ~a;
assert(b[0] == 0);
assert(b[1] == 1);
assert(b[2] == 0);
assert(b[3] == 1);
assert(b[4] == 0);
}
}
/**
* Generates a new array which is the result of a bitwise and operation
* between this array and the supplied array.
*
* Params:
* rhs = The array with which to perform the bitwise and operation.
*
* In:
* rhs.length must equal the length of this array.
*
* Returns:
* A new array which is the result of a bitwise and with this array and
* the supplied array.
*/
BitArray opAnd( BitArray rhs )
in
{
assert( len == rhs.length );
}
body
{
auto dim = this.dim();
BitArray result;
result.length = len;
for( size_t i = 0; i < dim; ++i )
result.ptr[i] = this.ptr[i] & rhs.ptr[i];
return result;
}
debug( UnitTest )
{
unittest
{
BitArray a = [1,0,1,0,1];
BitArray b = [1,0,1,1,0];
BitArray c = a & b;
assert(c[0] == 1);
assert(c[1] == 0);
assert(c[2] == 1);
assert(c[3] == 0);
assert(c[4] == 0);
}
}
/**
* Generates a new array which is the result of a bitwise or operation
* between this array and the supplied array.
*
* Params:
* rhs = The array with which to perform the bitwise or operation.
*
* In:
* rhs.length must equal the length of this array.
*
* Returns:
* A new array which is the result of a bitwise or with this array and
* the supplied array.
*/
BitArray opOr( BitArray rhs )
in
{
assert( len == rhs.length );
}
body
{
auto dim = this.dim();
BitArray result;
result.length = len;
for( size_t i = 0; i < dim; ++i )
result.ptr[i] = this.ptr[i] | rhs.ptr[i];
return result;
}
debug( UnitTest )
{
unittest
{
BitArray a = [1,0,1,0,1];
BitArray b = [1,0,1,1,0];
BitArray c = a | b;
assert(c[0] == 1);
assert(c[1] == 0);
assert(c[2] == 1);
assert(c[3] == 1);
assert(c[4] == 1);
}
}
/**
* Generates a new array which is the result of a bitwise xor operation
* between this array and the supplied array.
*
* Params:
* rhs = The array with which to perform the bitwise xor operation.
*
* In:
* rhs.length must equal the length of this array.
*
* Returns:
* A new array which is the result of a bitwise xor with this array and
* the supplied array.
*/
BitArray opXor( BitArray rhs )
in
{
assert( len == rhs.length );
}
body
{
auto dim = this.dim();
BitArray result;
result.length = len;
for( size_t i = 0; i < dim; ++i )
result.ptr[i] = this.ptr[i] ^ rhs.ptr[i];
return result;
}
debug( UnitTest )
{
unittest
{
BitArray a = [1,0,1,0,1];
BitArray b = [1,0,1,1,0];
BitArray c = a ^ b;
assert(c[0] == 0);
assert(c[1] == 0);
assert(c[2] == 0);
assert(c[3] == 1);
assert(c[4] == 1);
}
}
/**
* Generates a new array which is the result of this array minus the
* supplied array. $(I a - b) for BitArrays means the same thing as
* $(I a & ~b).
*
* Params:
* rhs = The array with which to perform the subtraction operation.
*
* In:
* rhs.length must equal the length of this array.
*
* Returns:
* A new array which is the result of this array minus the supplied array.
*/
BitArray opSub( BitArray rhs )
in
{
assert( len == rhs.length );
}
body
{
auto dim = this.dim();
BitArray result;
result.length = len;
for( size_t i = 0; i < dim; ++i )
result.ptr[i] = this.ptr[i] & ~rhs.ptr[i];
return result;
}
debug( UnitTest )
{
unittest
{
BitArray a = [1,0,1,0,1];
BitArray b = [1,0,1,1,0];
BitArray c = a - b;
assert( c[0] == 0 );
assert( c[1] == 0 );
assert( c[2] == 0 );
assert( c[3] == 0 );
assert( c[4] == 1 );
}
}
/**
* Generates a new array which is the result of this array concatenated
* with the supplied array.
*
* Params:
* rhs = The array with which to perform the concatenation operation.
*
* Returns:
* A new array which is the result of this array concatenated with the
* supplied array.
*/
BitArray opCat( bool rhs )
{
BitArray result;
result = this.dup;
result.length = len + 1;
result[len] = rhs;
return result;
}
/** ditto */
BitArray opCat_r( bool lhs )
{
BitArray result;
result.length = len + 1;
result[0] = lhs;
for( size_t i = 0; i < len; ++i )
result[1 + i] = (*this)[i];
return result;
}
/** ditto */
BitArray opCat( BitArray rhs )
{
BitArray result;
result = this.dup();
result ~= rhs;
return result;
}
debug( UnitTest )
{
unittest
{
BitArray a = [1,0];
BitArray b = [0,1,0];
BitArray c;
c = (a ~ b);
assert( c.length == 5 );
assert( c[0] == 1 );
assert( c[1] == 0 );
assert( c[2] == 0 );
assert( c[3] == 1 );
assert( c[4] == 0 );
c = (a ~ true);
assert( c.length == 3 );
assert( c[0] == 1 );
assert( c[1] == 0 );
assert( c[2] == 1 );
c = (false ~ a);
assert( c.length == 3 );
assert( c[0] == 0 );
assert( c[1] == 1 );
assert( c[2] == 0 );
}
}
/**
* Support for index operations, much like the behavior of built-in arrays.
*
* Params:
* b = The new bit value to set.
* pos = The desired index position.
*
* In:
* pos must be less than the length of this array.
*
* Returns:
* The new value of the bit at pos.
*/
bool opIndexAssign( bool b, size_t pos )
in
{
assert( pos < len );
}
body
{
if( b )
bts( ptr, pos );
else
btr( ptr, pos );
return b;
}
/**
* Updates the contents of this array with the result of a bitwise and
* operation between this array and the supplied array.
*
* Params:
* rhs = The array with which to perform the bitwise and operation.
*
* In:
* rhs.length must equal the length of this array.
*
* Returns:
* A shallow copy of this array.
*/
BitArray opAndAssign( BitArray rhs )
in
{
assert( len == rhs.length );
}
body
{
auto dim = this.dim();
for( size_t i = 0; i < dim; ++i )
ptr[i] &= rhs.ptr[i];
return *this;
}
debug( UnitTest )
{
unittest
{
BitArray a = [1,0,1,0,1];
BitArray b = [1,0,1,1,0];
a &= b;
assert( a[0] == 1 );
assert( a[1] == 0 );
assert( a[2] == 1 );
assert( a[3] == 0 );
assert( a[4] == 0 );
}
}
/**
* Updates the contents of this array with the result of a bitwise or
* operation between this array and the supplied array.
*
* Params:
* rhs = The array with which to perform the bitwise or operation.
*
* In:
* rhs.length must equal the length of this array.
*
* Returns:
* A shallow copy of this array.
*/
BitArray opOrAssign( BitArray rhs )
in
{
assert( len == rhs.length );
}
body
{
auto dim = this.dim();
for( size_t i = 0; i < dim; ++i )
ptr[i] |= rhs.ptr[i];
return *this;
}
debug( UnitTest )
{
unittest
{
BitArray a = [1,0,1,0,1];
BitArray b = [1,0,1,1,0];
a |= b;
assert( a[0] == 1 );
assert( a[1] == 0 );
assert( a[2] == 1 );
assert( a[3] == 1 );
assert( a[4] == 1 );
}
}
/**
* Updates the contents of this array with the result of a bitwise xor
* operation between this array and the supplied array.
*
* Params:
* rhs = The array with which to perform the bitwise xor operation.
*
* In:
* rhs.length must equal the length of this array.
*
* Returns:
* A shallow copy of this array.
*/
BitArray opXorAssign( BitArray rhs )
in
{
assert( len == rhs.length );
}
body
{
auto dim = this.dim();
for( size_t i = 0; i < dim; ++i )
ptr[i] ^= rhs.ptr[i];
return *this;
}
debug( UnitTest )
{
unittest
{
BitArray a = [1,0,1,0,1];
BitArray b = [1,0,1,1,0];
a ^= b;
assert( a[0] == 0 );
assert( a[1] == 0 );
assert( a[2] == 0 );
assert( a[3] == 1 );
assert( a[4] == 1 );
}
}
/**
* Updates the contents of this array with the result of this array minus
* the supplied array. $(I a - b) for BitArrays means the same thing as
* $(I a & ~b).
*
* Params:
* rhs = The array with which to perform the subtraction operation.
*
* In:
* rhs.length must equal the length of this array.
*
* Returns:
* A shallow copy of this array.
*/
BitArray opSubAssign( BitArray rhs )
in
{
assert( len == rhs.length );
}
body
{
auto dim = this.dim();
for( size_t i = 0; i < dim; ++i )
ptr[i] &= ~rhs.ptr[i];
return *this;
}
debug( UnitTest )
{
unittest
{
BitArray a = [1,0,1,0,1];
BitArray b = [1,0,1,1,0];
a -= b;
assert( a[0] == 0 );
assert( a[1] == 0 );
assert( a[2] == 0 );
assert( a[3] == 0 );
assert( a[4] == 1 );
}
}
/**
* Updates the contents of this array with the result of this array
* concatenated with the supplied array.
*
* Params:
* rhs = The array with which to perform the concatenation operation.
*
* Returns:
* A shallow copy of this array.
*/
BitArray opCatAssign( bool b )
{
length = len + 1;
(*this)[len - 1] = b;
return *this;
}
debug( UnitTest )
{
unittest
{
BitArray a = [1,0,1,0,1];
BitArray b;
b = (a ~= true);
assert( a[0] == 1 );
assert( a[1] == 0 );
assert( a[2] == 1 );
assert( a[3] == 0 );
assert( a[4] == 1 );
assert( a[5] == 1 );
assert( b == a );
}
}
/** ditto */
BitArray opCatAssign( BitArray rhs )
{
auto istart = len;
length = len + rhs.length;
for( auto i = istart; i < len; ++i )
(*this)[i] = rhs[i - istart];
return *this;
}
debug( UnitTest )
{
unittest
{
BitArray a = [1,0];
BitArray b = [0,1,0];
BitArray c;
c = (a ~= b);
assert( a.length == 5 );
assert( a[0] == 1 );
assert( a[1] == 0 );
assert( a[2] == 0 );
assert( a[3] == 1 );
assert( a[4] == 0 );
assert( c == a );
}
}
}
|