Mercurial > projects > ldc
diff tango/tango/core/BitArray.d @ 132:1700239cab2e trunk
[svn r136] MAJOR UNSTABLE UPDATE!!!
Initial commit after moving to Tango instead of Phobos.
Lots of bugfixes...
This build is not suitable for most things.
author | lindquist |
---|---|
date | Fri, 11 Jan 2008 17:57:40 +0100 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tango/tango/core/BitArray.d Fri Jan 11 17:57:40 2008 +0100 @@ -0,0 +1,971 @@ +/** + * 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; + + +/** + * An array of bits. + */ +struct BitArray +{ + size_t len; + uint* ptr; + + + /** + * + */ + static BitArray opCall( bool[] bits ) + { + BitArray temp; + + temp.length = bits.length; + foreach( pos, val; bits ) + temp[pos] = val; + return temp; + } + + /** + * + */ + size_t length() + { + return len; + } + + + /** + * + */ + void length(size_t newlen) + { + if (newlen != len) + { + size_t olddim = dim(); + size_t newdim = (newlen + 31) / 32; + + if (newdim != olddim) + { + // Create a fake array so we can use D's realloc machinery + uint[] b = ptr[0 .. olddim]; + + b.length = newdim; // realloc + ptr = b.ptr; + if (newdim & 31) + { + // Set any pad bits to 0 + ptr[newdim - 1] &= ~(~0 << (newdim & 31)); + } + } + len = newlen; + } + } + + + /** + * + */ + size_t dim() + { + return (len + 31) / 32; + } + + + /** + * Support for array.dup property for BitArray. + */ + BitArray dup() + { + BitArray ba; + + uint[] b = ptr[0 .. dim].dup; + ba.len = len; + ba.ptr = b.ptr; + return ba; + } + + + debug( UnitTest ) + { + unittest + { + BitArray a; + BitArray b; + int i; + + a.length = 3; + a[0] = 1; a[1] = 0; a[2] = 1; + b = a.dup; + assert(b.length == 3); + for (i = 0; i < 3; i++) + { + //printf("b[%d] = %d\n", i, b[i]); + assert(b[i] == (((i ^ 1) & 1) ? true : false)); + } + } + } + + + /** + * Set BitArray to contents of ba[] + */ + void opAssign(bool[] ba) + { + length = ba.length; + foreach (i, b; ba) + { + (*this)[i] = b; + } + } + + + /** + * Map BitArray onto v[], with numbits being the number of bits + * in the array. Does not copy the data. + * + * This is the inverse of opCast. + */ + void init(void[] v, size_t numbits) + in + { + assert(numbits <= v.length * 8); + assert((v.length & 3) == 0); + } + body + { + ptr = cast(uint*)v.ptr; + len = numbits; + } + + + debug( UnitTest ) + { + unittest + { + BitArray a = [1,0,1,0,1]; + BitArray b; + void[] v; + + v = cast(void[])a; + b.init(v, 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); + } + } + + + /** + * Support for array.reverse property for BitArray. + */ + 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 + { + BitArray b; + static bool[5] data = [1,0,1,1,0]; + int i; + + b = data; + b.reverse; + for (i = 0; i < data.length; i++) + { + assert(b[i] == data[4 - i]); + } + } + } + + + /** + * Support for array.sort property for BitArray. + */ + BitArray sort() + out (result) + { + assert(result == *this); + } + body + { + if (len >= 2) + { + size_t lo, hi; + + lo = 0; + hi = len - 1; + while (1) + { + while (1) + { + if (lo >= hi) + goto Ldone; + if ((*this)[lo] == true) + break; + lo++; + } + + while (1) + { + 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); + } + } + + + /** + * Support for foreach loops for BitArray. + */ + int opApply(int delegate(inout 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(inout size_t, inout 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(0); + } + 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(0); + } + } + } + } + + + /** + * Support for operators == and != for bit arrays. + */ + int opEquals(BitArray a2) + { + int i; + + if (this.length != a2.length) + return 0; // not equal + byte *p1 = cast(byte*)this.ptr; + byte *p2 = cast(byte*)a2.ptr; + uint n = this.length / 8; + for (i = 0; i < n; i++) + { + if (p1[i] != p2[i]) + return 0; // not equal + } + + ubyte mask; + + n = this.length & 7; + mask = cast(ubyte)((1 << n) - 1); + //printf("i = %d, n = %d, mask = %x, %x, %x\n", i, n, mask, p1[i], p2[i]); + return (mask == 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); + } + } + + + /** + * Implement comparison operators. + */ + int opCmp(BitArray a2) + { + uint len; + uint i; + + len = this.length; + if (a2.length < len) + len = a2.length; + ubyte* p1 = cast(ubyte*)this.ptr; + ubyte* p2 = cast(ubyte*)a2.ptr; + uint n = len / 8; + for (i = 0; i < n; i++) + { + if (p1[i] != p2[i]) + break; // not equal + } + for (uint j = i * 8; j < len; j++) + { ubyte mask = cast(ubyte)(1 << j); + int c; + + c = cast(int)(p1[i] & mask) - cast(int)(p2[i] & mask); + if (c) + return c; + } + return cast(int)this.len - cast(int)a2.length; + } + + 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 >= b); + assert(a < c); + assert(a <= c); + assert(a < d); + assert(a <= d); + assert(a == e); + assert(a <= e); + assert(a >= e); + } + } + + + /** + * Convert to void[]. + */ + 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 [$(I index)] operation for BitArray. + */ + bool opIndex(size_t i) + in + { + assert(i < len); + } + body + { + return cast(bool)bt(ptr, i); + } + + + /** + * Support for unary operator ~ for bit arrays. + */ + 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); + } + } + + + /** + * Support for binary operator & for bit arrays. + */ + BitArray opAnd(BitArray e2) + in + { + assert(len == e2.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] & e2.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); + } + } + + + /** + * Support for binary operator | for bit arrays. + */ + BitArray opOr(BitArray e2) + in + { + assert(len == e2.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] | e2.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); + } + } + + + /** + * Support for binary operator ^ for bit arrays. + */ + BitArray opXor(BitArray e2) + in + { + assert(len == e2.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] ^ e2.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); + } + } + + + /** + * Support for binary operator - for bit arrays. + * + * $(I a - b) for BitArrays means the same thing as $(I a & ~b). + */ + BitArray opSub(BitArray e2) + in + { + assert(len == e2.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] & ~e2.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); + } + } + + + /** + * Support for binary operator ~ for bit arrays. + */ + BitArray opCat(bool b) + { + BitArray r; + + r = this.dup; + r.length = len + 1; + r[len] = b; + return r; + } + + + /** ditto */ + BitArray opCat_r(bool b) + { + BitArray r; + + r.length = len + 1; + r[0] = b; + for (size_t i = 0; i < len; i++) + r[1 + i] = (*this)[i]; + return r; + } + + + /** ditto */ + BitArray opCat(BitArray b) + { + BitArray r; + + r = this.dup(); + r ~= b; + return r; + } + + + 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 [$(I index)] operation for BitArray. + */ + bool opIndexAssign(bool b, size_t i) + in + { + assert(i < len); + } + body + { + if (b) + bts(ptr, i); + else + btr(ptr, i); + return b; + } + + + /** + * Support for operator &= bit arrays. + */ + BitArray opAndAssign(BitArray e2) + in + { + assert(len == e2.length); + } + body + { + auto dim = this.dim(); + + for (size_t i = 0; i < dim; i++) + ptr[i] &= e2.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); + } + } + + + /** + * Support for operator |= for bit arrays. + */ + BitArray opOrAssign(BitArray e2) + in + { + assert(len == e2.length); + } + body + { + auto dim = this.dim(); + + for (size_t i = 0; i < dim; i++) + ptr[i] |= e2.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); + } + } + + + /** + * Support for operator ^= for bit arrays. + */ + BitArray opXorAssign(BitArray e2) + in + { + assert(len == e2.length); + } + body + { + auto dim = this.dim(); + + for (size_t i = 0; i < dim; i++) + ptr[i] ^= e2.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); + } + } + + + /** + * Support for operator -= for bit arrays. + * + * $(I a -= b) for BitArrays means the same thing as $(I a &= ~b). + */ + BitArray opSubAssign(BitArray e2) + in + { + assert(len == e2.length); + } + body + { + auto dim = this.dim(); + + for (size_t i = 0; i < dim; i++) + ptr[i] &= ~e2.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); + } + } + + + /** + * Support for operator ~= for bit arrays. + */ + 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 b) + { + auto istart = len; + length = len + b.length; + for (auto i = istart; i < len; i++) + (*this)[i] = b[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); + } + } +}