/***********************************************************************\
*                              bitoffset.d                              *
*                                                                       *
* Data types to implement bit pointers and bit arrays with a bit offset *
*                                                                       *
*                           by Stewart Gordon                           *
*                               June 2004                               *
\***********************************************************************/
// imports used only in unit tests and debugging code
private import std.c.stdio;
private import std.asserterror;

static const int BIT_OFFSET_SHIFT = (uint.size << 3) - 3;

union BitPointer {
	private {
		struct {
			version (LittleEndian) {
				uint _bitOffset;
				ubyte* _bytePointer;
			} else {
				ubyte* _bytePointer;
				uint _bitOffset;
			}
		}
		ulong _wholeThing;
	}

	static assert (ulong.size == uint.size + (ubyte*).size);

	invariant {
		assert ((_bitOffset & ~((-1) << BIT_OFFSET_SHIFT)) == 0);
	}

	/*	to interface the current byte-aligned bit[] imp
	 *	will be obsolete when/if my BitArray is integrated as the new bit[]
	 */
	static BitPointer opCall(bit[] bits) {
		BitPointer p;
		p._bytePointer = cast(ubyte*) bits;
		return p;
	}

	/*	separate function rather than alias to avert DMD 0.92 bug causing
	 *	invalid page fault
	 */
	int opCmp(BitPointer p) { return opSub(p); }

	version (LittleEndian) {
		/*	D doesn't seem to have an overload for unary * at the moment
		 *	but if it did, I'm guessing it might be called this
		 */
		bit opPoint() {
			return cast(bit)
			  ((*_bytePointer >>> (_bitOffset >>> BIT_OFFSET_SHIFT)) & 1);
		}

		bit opPoint(bit b) {
			*_bytePointer &= ~(1 << (_bitOffset >>> BIT_OFFSET_SHIFT));
			*_bytePointer |= (b << (_bitOffset >>> BIT_OFFSET_SHIFT));
			return b;
		}
	} else {
		bit opPoint() {
			return cast(bit) ((*_bytePointer >>>
			    (7 - (_bitOffset >>> BIT_OFFSET_SHIFT))) & 1);
		}

		bit opPoint(bit b) {
			*_bytePointer &= ~(1 << (7 - (_bitOffset >>> BIT_OFFSET_SHIFT)));
			*_bytePointer |= (b << (7 - (_bitOffset >>> BIT_OFFSET_SHIFT)));
			return b;
		}
	}

	bit opIndex(int i) {
		return (*this + i).opPoint;
	}

	bit opIndex(int i, bit b) {
		return (*this + i).opPoint(b);
	}

	BitArray opSlice(int begin, int end) {
		BitArray ba;
		ba._start = *this + begin;
		ba._length = end - begin;
		ba._allocBytes = 0;

		return ba;
	}

	/*	D doesn't seem to have an overload for slice assignment at the moment
	 *	but if it did, I'm guessing the form would be consistent with
	 *	opIndex
	 *	(which probably means opSliceAssign when the form is finalised)
	 *	implementation of (*this)[begin..end] = value
	 */
	BitArray opSlice(int begin, int end, bit value) {
		BitArray slice = opSlice(begin, end);
		// *** optimise
		foreach (inout bit b; slice) {
			b = value;
		}
		return slice;
	}

	BitArray opSlice(int begin, int end, BitArray value)
	in {
		// check lengths match
		assert (end - begin == value._length);

		// check slices don't overlap
		assert (*this + end <= cast(BitPointer) value
		  || cast(BitPointer) value + value._length <= *this + begin);
	}
	out {
		assert ((*this)[begin..end] == value);
	}
	body {
		BitArray slice = opSlice(begin, end);
		// *** optimise
		foreach (int index, inout bit b; slice) {
			b = value[index];
		}
		return slice;
	}

	BitPointer opAdd(int i) {
		BitPointer p;
		p._wholeThing = _wholeThing + (cast(ulong) i << BIT_OFFSET_SHIFT);
		return p;
	}

	BitPointer opSub(int i) {
		BitPointer p;
		p._wholeThing = _wholeThing - (cast(ulong) i << BIT_OFFSET_SHIFT);
		return p;
	}

	int opSub(BitPointer p) {
		return (_wholeThing - p._wholeThing) >> BIT_OFFSET_SHIFT;
	}

	void* opCast()
	in {
		assert (_bitOffset == 0);
	}
	body {
		return _bytePointer;
	}
}


struct BitArray {
	private {
		BitPointer _start;
		int _length;
		int _allocBytes;
	}

	invariant {
		// will be 0 if a slice, otherwise must be big enough
		assert (_allocBytes == 0 || _length <= (_allocBytes << 3));
	}

	/* implementation of new bit[length] */
	static BitArray opCall(int len) {
		static const int BLOCK_SIZE_EXP	= 11;	// 2k blocks
		static const int MIN_SIZE		= 4;	// don't bother allocating
												// less than 4 bytes
		BitArray ba;
		ba._length = len;

		// number of whole bytes used (excluding final byte)
		int wholeBytes = ((len - 1) >> 3);

		// actual number of bytes to allocate
		if (wholeBytes >= (1 << (BLOCK_SIZE_EXP - 1))) {
			// more than half a block - allocate a whole number of blocks
			ba._allocBytes
			  = (((wholeBytes+1) >> BLOCK_SIZE_EXP) + 1) << BLOCK_SIZE_EXP;
		} else {
			// allocate a power of 2 bytes
			for (ba._allocBytes = MIN_SIZE; ba._allocBytes <= wholeBytes + 1;
			  ba._allocBytes <<= 1) {}
		}

		//_length = len;
		debug printf("alloc %d/%d\n", ba._allocBytes, len);

		ba._start._bytePointer = new ubyte[ba._allocBytes];

		return ba;
	}


	/*	to interface the current byte-aligned bit[] imp
	 *	will be obsolete when/if my BitArray is integrated as the new bit[]
	 */
	static BitArray opCall(bit[] bits) {
		BitArray ba;
		ba._length = bits.length;
		ba._start._bytePointer = cast(ubyte*) bits;

		return ba;
	}

	int opEquals(BitArray ba) {
		if (*this === ba) return true;
		if (ba._length != _length) return false;

		// *** optimise
		for (int index = 0; index < _length; index++) {
			if ((*this)[index] != ba[index]) return false;
		}

		return true;
	}

	bit opIndex(int i)
	in {
		assert (i >= 0);
		assert (i < _length);
	}
	body {
		return _start[i];
	}

	bit opIndex(int i, bit b)
	in {
		assert (i >= 0);
		assert (i < _length);
	}
	body {
		return _start[i] = b;
	}

	BitArray opSlice(int begin, int end)
	in {
		checkBounds(begin, end);
	}
	body {
		return _start[begin..end];
	}

	BitArray opSlice(int begin, int end, bit value)
	in {
		checkBounds(begin, end);
	}
	body {
		//return _start[begin..end] = value;
		return _start.opSlice(begin, end, value);
	}

	BitArray opSlice(int begin, int end, BitArray value)
	in {
		checkBounds(begin, end);
	}
	body {
		//return _start[begin..end] = value;
		return _start.opSlice(begin, end, value);
	}

	// implementation of (*this)[] = value
	BitArray opSlice(bit value) {
		return _start.opSlice(0, _length, value);
	}

	// implementation of (*this)[] = value
	BitArray opSlice(BitArray value) {
		return _start.opSlice(0, _length, value);
	}

	BitArray opCat(BitArray value) {
		BitArray ba = BitArray(_length + value._length);
		ba.opSlice(0, _length, *this);
		ba.opSlice(_length, _length + value._length, value);
		return ba;
	}

	BitArray opCatAssign(BitArray value) {
		int catAt = length;
		length = catAt + value.length;
		opSlice(catAt, catAt + value.length, value);
		return *this;
	}

	BitArray opCatAssign(bit value) {
		length = length + 1;
		(*this)[_length - 1] = value;
		return *this;
	}

	BitPointer opCast() {
		return _start;
	}

	int opApply(int delegate(inout bit) dg) {
		int result = 0;

		for (int i = 0; i < _length; i++) {
			bit b = _start[i];
			result = dg(b);
			_start[i] = b;
			if (result) break;
		}
		return result;
	}
	int opApply(int delegate(inout int, inout bit) dg) {
		int result = 0;

		for (int i = 0; i < _length; i++) {
			bit b = _start[i];
			result = dg(i, b);
			_start[i] = b;
			if (result) break;
		}
		return result;
	}

	BitArray dup()
	out (result) {
		assert (*this == result);
	}
	body {
		BitArray p = BitArray(_length);
		p.opSlice(*this);
		return p;
	}

	/* Return a byte-aligned version of the array */
	BitArray byteAlign() {
		if (_start._bitOffset == 0) {
			return *this;
		} else {
			return dup;
		}
	}

	int length() { return _length; }

	int length(int len)
	in {
		debug printf("Entered length(%d)\n", len);
		assert (len >= 0);
	}
	body {
		if (len > _length && len > (_allocBytes << 3)) {
			// too big - need to reallocate
			debug printf("Entering BitArray(%d)\n", len);
			BitArray reallocate = BitArray(len);
			debug printf("Exited BitArray(%d)\n", len);

			// copy data from this
			reallocate.opSlice(0, _length, *this);
			debug printf("Assigning reallocate\n", len);

			*this = reallocate;
			debug printf("Assigned reallocate\n", len);

		} else {
			_length = len;
		}
		debug printf("Exiting length(%d)\n", len);
		return len;
	}

	private void checkBounds(int begin, int end) {
		assert (begin >= 0);
		assert (begin <= end);
		assert (end <= _length);
	}
}


unittest {
	static bit[] data = [1, 1, 0, 1, 0];
	BitPointer p = BitPointer(data);

	// pointing
	p.opPoint = 0;
	assert (data[0] == 0);
	p.opPoint = 1;
	assert (data[0] == 1);

	// indexing
	p[0] = 0;
	assert (data[0] == 0);
	p[0] = 1;
	assert (data[0] == 1);
	p[1] = 0;
	assert (data[1] == 0);
	p[1] = 1;
	assert (data[1] == 1);
	p[4] = 1;
	assert (data[4] == 1);
	p[4] = 0;
	assert (data[4] == 0);
	p[4] = p[1];
	assert (data[1] == data[4]);
	p[4] = p[2];
	assert (data[2] == data[4]);

	assert (p[0] == 1);
	assert (p[1] == 1);
	assert (p[2] == 0);
	assert (p[3] == 1);
	assert (p[4] == 0);

	// pointer arithmetic
	BitPointer q = p + 3;
	BitPointer o = q - 2;
	assert (o == p + 1);

	o[0] = 0;
	assert (p[1] == 0);
	p[1] = 1;
	assert (o[0] == 1);

	puts("BitPointer unit test passed!");

	BitArray ba = BitArray(data);

	// indexing
	ba[0] = 0;
	assert (data[0] == 0);
	ba[0] = 1;
	assert (data[0] == 1);
	ba[1] = 0;
	assert (data[1] == 0);
	ba[1] = 1;
	assert (data[1] == 1);
	ba[4] = 1;
	assert (data[4] == 1);
	ba[4] = 0;
	assert (data[4] == 0);
	ba[4] = ba[1];
	assert (data[1] == data[4]);
	ba[4] = ba[2];
	assert (data[2] == data[4]);

	assert (ba[0] == 1);
	assert (ba[1] == 1);
	assert (ba[2] == 0);
	assert (ba[3] == 1);
	assert (ba[4] == 0);

	// slicing
	BitArray slice = ba[2..4];

	slice[0] = 1;
	assert (ba[2] == 1);

	ba[2] = 0;
	assert (slice[0] == 0);

	puts("BitArray basic ops passed!");

	char[] textRep;


	// foreach - in unindexed
	foreach (bit b; ba) {
		//puts(b ? "true " : "false ");
		textRep ~= (b ? 't' : 'f');
	}
	assert (textRep == "ttftf");

	// foreach - inout unindexed
	foreach (inout bit b; ba) {
		b = !b;
	}

	textRep = "";

	// foreach - in indexed
	foreach (int i, bit b; ba) {
		textRep ~= '0' + i;
		textRep ~= (b ? 't' : 'f');
		//printf("Element %d: %d\n", i, cast(int) b);
	}
	assert (textRep == "0f1f2t3f4t");

	textRep = "";

	// foreach - inout indexed
	foreach (int i, inout bit b; ba) {
		/+printf("Element %d: changing %d ", i, cast(int) b);
		b = !b;
		printf("to %d\n", cast(int) b);+/
		textRep ~= '0' + i;
		textRep ~= (b ? 't' : 'f');
		b = !b;
		textRep ~= (b ? 't' : 'f');
	}

	assert (textRep == "0ft1ft2tf3ft4tf");

	puts("BitArray iteration passed!");

	ba.opSlice(1, 4, 0);
	foreach (bit b; ba[1..4]) assert (b == 0);

	ba.opSlice(1, 4, 1);
	foreach (bit b; ba[1..4]) assert (b == 1);
	assert (ba[0] == 1);
	assert (ba[4] == 0);

	puts("bit to BitArray slice assignment passed!");
}


unittest {
	static bit[] data = [0,0,0,1,0,0,1,1, 0,1,0,0,1,1,1,1];
	BitArray ba = BitArray(data);
	BitArray slice1 = ba[1..7];
	BitArray slice2 = ba[8..14];
	BitArray slice3 = ba[9..14];

	ba.opSlice(1, 7, slice2);

	assert (slice1 == slice2);
	assert (slice1 != ba[9..14]);
	assert (slice1 != ba[9..15]);
	assert (slice1 !== slice2);
	assert (slice1 === ba[1..7]);

	try {
		ba.opSlice(4, 8, ba[5..9]);
		throw new Error("Slice overlap validation failed!");
	} catch (AssertError e) {}

	puts("BitArray slice copying and comparison passed!");

	BitArray newData = ba;
	newData.length = 30;
	assert (newData[0..16] == ba);
	newData.length = 2049;
	assert (newData[0..16] == ba);

	puts("BitArray length setting passed!");

	newData = ba[2..5] ~ ba[10..16];
	assert (newData[0..3] == ba[2..5]);
	assert (newData[3..9] == ba[10..16]);

	newData ~= ba[8..13];
	newData ~= 0;
	newData ~= 1;
	assert (newData[9..14] == ba[8..13]);
	assert (newData[14] == 0);
	assert (newData[15] == 1);

	puts("BitArray concatenation passed!");
}