Bitmap

bitmap.d

module bitmap;

struct Index
{
	size_t numberIndex;
	size_t bitIndex;
}

int getMask(TNumber)(Index index) 
{ 
	return cast(TNumber)((cast(TNumber) 1) << index.bitIndex); 
}
unittest
{
	assert(Index(0, 7).mask == 0x0000_0080);
}

struct Bitmap(TNumber)
{
	enum bitCount = TNumber.sizeof * 8;
	const size_t width;
	size_t height() const { return numbers.length * bitCount / width; }
	TNumber[] numbers;
	
	Index mapIndices(size_t[2] indices) const
	{
		size_t bitIndex = indices[0] * width + indices[1];
		
		Index result;
		result.numberIndex = bitIndex / bitCount;
		result.bitIndex = bitIndex - result.numberIndex * bitCount;
		return result;
	}
	
	struct Ranges
	{
		size_t[2] rows;
		size_t[2] cols;
	}
	
	// Rows
	size_t[2] opSlice(size_t dim)(size_t a, size_t b) 
		if (dim >= 0 && dim < 2)
	{ 
		return [a, b]; 
	}

	TNumber[2] getMasks(Index[2] range)
	{
		enum ones = ~(cast(TNumber) 0);
		return [
			ones << range[0].bitIndex,
			ones >> (bitCount - range[1].bitIndex - 1)
		];
	}
	
	void opIndexAssign(int value, Index[2] range)
	{
		if (range[0].numberIndex > range[1].numberIndex)
			return;
		
		void set(ref TNumber dest, TNumber mask)
		{
			if (value) dest |= mask;
			else       dest &= ~mask;
		}

		TNumber[2] masks = getMasks(range);

		if (range[0].numberIndex == range[1].numberIndex)
		{
			set(numbers[range[0].numberIndex], masks[0] & masks[1]);
			return;
		}

		static foreach (i; 0..2)
			set(numbers[range[i].numberIndex], masks[i]);

		foreach (numberIndex; range[0].numberIndex + 1 .. range[1].numberIndex)
			set(numbers[numberIndex], ~(cast(TNumber) 0));
	}
	
	Bitmap!TNumber opIndexAssign(in Bitmap!TNumber other, Index[2] range) return
		in (other.width == width && other.height == height)
	{
		if (range[0].numberIndex < range[1].numberIndex)
			return this;
		
		TNumber[2] masks = getMasks(range);
		if (range[0].numberIndex == range[1].numberIndex)
		{
			size_t numIndex = range[0].numberIndex;
			TNumber mask = masks[0] & masks[1];
			TNumber things = (numbers[numIndex] | other.numbers[numIndex]) & mask;
			numbers[numIndex] = (numbers[numIndex] & ~mask) | things;
			return this;
		}

		static foreach (i; 0..2)
			numbers[range[i].numberIndex] |= other.numbers[range[i].numberIndex] & masks[i];
		
		foreach (i; range[0].numberIndex + 1 .. range[1].numberIndex)
			numbers[i] = other.numbers[i];
		
		return this;
	}
	
	Bitmap!TNumber assignSubmatrix(TValues)(in TValues values, Ranges ranges) return
	{
		if (ranges.rows[0] >= ranges.rows[1])
			return this;
		if (ranges.cols[0] >= ranges.cols[1])
			return this;
		
		// Simplified case: whole rows
		if (ranges.cols[1] - ranges.cols[0] == width)
		{   
			opIndexAssign(values, [
				mapIndices([ranges.rows[0], 0]), 
				mapIndices([ranges.rows[1] - 1, width - 1])
			]);
			return this;
		}
		
		// General case: submatrix
		foreach (rowIndex; ranges.rows[0] .. ranges.rows[1])
		{
			opIndexAssign(values, [
				mapIndices([rowIndex, ranges.cols[0]]), 
				mapIndices([rowIndex, ranges.cols[1] - 1])
			]);  
		}
							 
		return this;
	}
							 
	size_t opDollar(size_t dimension : 0)() { return height; }
	size_t opDollar(size_t dimension : 1)() { return width; }
	
	Bitmap!TNumber opIndexAssign(in Bitmap!TNumber other, size_t[2] rows, size_t[2] cols) return
		in (other.width == width && other.height == height)
	{
		return assignSubmatrix(other, Ranges(rows, cols));
	}
							 
	Bitmap!TNumber opIndexAssign(int value, size_t[2] rows, size_t[2] cols) return
	{
		return assignSubmatrix(value, Ranges(rows, cols));
	}

	auto opIndexAssign(TValues)(in TValues values, size_t row, size_t[2] cols) return
	{
		return opIndexAssign(values, [row, row + 1], cols);
	}
	auto opIndexAssign(TValues)(in TValues values, size_t[2] rows, size_t col) return
	{
		return opIndexAssign(values, rows, [col, col + 1]);
	}
	
	auto opIndex(size_t x, size_t y) const
	{
		return opIndex(mapIndices([x, y]));
	}
	
	auto opIndexAssign(int value, size_t x, size_t y)
	{
		return opIndexAssign(value, mapIndices([x, y]));
	}
	
	int opIndex(Index index) const
		in (index.numberIndex < numbers.length)
	{
		return (numbers[index.numberIndex] >> index.bitIndex) & 1;
	}
	
	int opIndexAssign(int value, Index index)
		in (index.numberIndex < numbers.length)
	{
		if (value)
			return numbers[index.numberIndex] |= getMask!TNumber(index);
		return numbers[index.numberIndex] &= ~getMask!TNumber(index);
	}
}
unittest
{
	auto bmp = bitmap(2, 2);
	bmp[0, 0] = 1;
	assert(bmp[0, 0] == 1);
	bmp[0, 0] = 0;
	assert(bmp[0, 0] == 0);
	bmp[0, 1] = 1;
	writeln(bmp[0, 1]);
	assert(bmp[0, 1] == 1);
	bmp[1, 0] = 1;
	bmp[1, 1] = 1;
	assert(bmp.numbers[0] == 0x0000_000E);
}

Bitmap!T bitmap(T = uint)(size_t width, size_t height)
{
	return Bitmap!(T)(width, new T[]((width * height + 31) / 32));
}
unittest
{
	assert(bitmap(8, 8).numbers.length == 2);
}


import std.stdio;

void writeBitmapNumbers(B : Bitmap!T, T)(in B bmp)
{
	foreach (number; bmp.numbers)
		writefln("%032b", number);
}

void writeBitmap(B : Bitmap!T, T)(in B bmp)
{
	foreach (rowIndex; 0..bmp.height)
	{
		foreach (colIndex; 0..bmp.width)
			write(bmp[rowIndex, colIndex]);
		writeln();   
	}
}

void main()
{
	auto bmp = bitmap(8, 8);
	bmp[0..$, 0..$] = 1;
	bmp[0..2, 0..2] = 0;
	bmp[4..6, 2..5] = 0;
	bmp[0..$, 6] = 0;
	writeBitmap(bmp);
	writeln();

	auto bmp2 = bitmap(8, 8);
	bmp2[0..$, 0..$] = 1;
	bmp[0..4, 0..$] = bmp2;
	writeBitmap(bmp);
}