inline int buddy1(int width, int pos) { return pos ^ 1; }
inline int buddy2(int width, int pos) { return pos ^ width; }
inline int buddy3(int width, int pos) { return pos ^ (width|1); }

inline int child0(int width, int pos) { 
	int mask = width-1;
	int wy = pos & ~mask;
	int x = pos &  mask;
	return wy*4+x*2;
}

inline int parent(int width, int pos) {
	int mask = width-1;
	int wy = pos & ~mask;
	int x = pos &  mask;
	return wy/4+x/2;
}

void setSquare(int level, int pos)
{
	bitmaps[level][pos] = 1;
}

boolean squareFreeQ(int level, int pos)
{
	return bitmaps[level][pos] == 0;
}

void clearSquare(int level, int pos)
{
	if(mem[level][pos])
	{
		bitmaps[level][pos] = 0;
		freestack[level].push(pos);
	}
}

int split(int level, int pos)
{
	setSquare(level, pos);
	int width_cells = base_width_cells << level;
	int c0 = child0(width_cells, pos);
	level = level + 1;
	width_cells <<= 1;
	setSquare(level, c0);
	clearSquare(level, buddy1(width_cells, c0));
	clearSquare(level, buddy2(width_cells, c0));
	clearSquare(level, buddy3(width_cells, c0));
	return c0;
}

int freeSquare(int level, int pos)
{
	int width_cells = base_width_cells << level;
	int b1, b2, b3;
	while(level > 0 &&
	   squareFreeQ(level, b1 = buddy1(width_cells, pos)) &&
	   squareFreeQ(level, b2 = buddy2(width_cells, pos)) &&
	   squareFreeQ(level, b3 = buddy3(width_cells, pos)))
	{
		setSquare(level, pos);
		setSquare(level, b1);
		setSquare(level, b2);
		setSquare(level, b3);
		level = level - 1;
		pos = parent(pos);
	}
	clearSquare(level, pos);
}

int getNextFreeSquare(int level)
{
	while(freestack[level].size() != 0)
	{
		int pos = freestack[level].pop();
		if(squareFreeQ(pos))
		{
			return pos;
		}
	}
	return NONE;
}

int allocSquare(int allocLevel)
{
	for(int level = allocLevel; level >= 0; --level)
	{
		int pos = getNextFreeSquare(level);
		if(pos != NONE)
		{
			if(level < allocLevel)
			{
				// found a free square at a lower level, so split until we have one at the desired level.
				do 
				{
					pos = split(level, pos);
					level = level+1;
				}
				while(level < allocLevel);
			}
			return pos;
		}
	}
	return NONE;
}

static int base_width_cells;
static vector<byte> bitmaps[16];
static vector<int> free_stack[16];

void initialize(int base_width, int max_cell_width, int min_cell_width)
{
	base_width_cells = base_width/max_cell_width;
	int max_width_cells = base_width/min_cell_width;
	for(int level = 0; width_cells < max_width_cells; ++level)
	{
		int level_size = width_cells*width_cells;
		bitmaps[level].resize(level_size);
		memset(&bitmaps[level][0], 1, bitmaps[level].size());
		free_stack[level].reserve(level_size/4);
		width_cells <<= 1;
	}
	clearSquare(0, 0);
}