#include <stdio.h>
#include <stack.h>

#include <Region.h>

#include "AccelerantHWInterface.h"
#include "DirectWindowBuffer.h"

#include "DrawingEngine.h"

// constructor
DrawingEngine::DrawingEngine(AccelerantHWInterface* interface,
							 DirectWindowBuffer* buffer)
	: fHWInterface(interface),
	  fBuffer(buffer),
	  fCurrentClipping()
{
}

// destructor
DrawingEngine::~DrawingEngine()
{
}

// Lock
bool
DrawingEngine::Lock()
{
	return fHWInterface->Lock();
}

// Unlock
void
DrawingEngine::Unlock()
{
	fHWInterface->Unlock();
}

// ConstrainClipping
void
DrawingEngine::ConstrainClipping(BRegion* region)
{
	if (region)
		fCurrentClipping = *region;
	else
		fCurrentClipping.MakeEmpty();
}

// StraightLine
bool
DrawingEngine::StraightLine(BPoint a, BPoint b, const rgb_color& c)
{
	uint8* dst = (uint8*)fBuffer->Bits();
	uint32 bpr = fBuffer->BytesPerRow();

	if (dst && fCurrentClipping.Frame().IsValid()) {

		int32 clipBoxCount = fCurrentClipping.CountRects();

		uint32 color;
		color = (255 << 24) | (c.red << 16) | (c.green << 8) | (c.blue);

		if (a.x == b.x) {
			// vertical
			int32 x = (int32)a.x;
			dst += x * 4;
			int32 y1 = (int32)min_c(a.y, b.y);
			int32 y2 = (int32)max_c(a.y, b.y);
			// draw a line, iterate over clipping boxes
			for (int32 i = 0; i < clipBoxCount; i++) {
				clipping_rect rect = fCurrentClipping.RectAtInt(i);

				if (rect.left <= x &&
					rect.right >= x) {
					int32 i = max_c(rect.top, y1);
					int32 end = min_c(rect.bottom, y2);
					uint8* handle = dst + i * bpr;
					for (; i <= end; i++) {
						*(uint32*)handle = color;
						handle += bpr;
					}
				}
			}
	
			return true;
	
		} else if (a.y == b.y) {
			// horizontal
			int32 y = (int32)a.y;
			dst += y * bpr;
			int32 x1 = (int32)min_c(a.x, b.x);
			int32 x2 = (int32)max_c(a.x, b.x);
			// draw a line, iterate over clipping boxes
			for (int32 i = 0; i < clipBoxCount; i++) {
				clipping_rect rect = fCurrentClipping.RectAtInt(i);

				if (rect.top <= y &&
					rect.bottom >= y) {
					int32 i = max_c(rect.left, x1);
					int32 end = min_c(rect.right, x2);
					uint32* handle = (uint32*)(dst + i * 4);
					for (; i <= end; i++) {
						*handle++ = color;
					}
				}
			}	

			return true;
		}
	}
	return false;
}

// StrokeLine
void
DrawingEngine::StrokeLine(BPoint a, BPoint b, const rgb_color& color)
{
	if (!StraightLine(a, b, color)) {
		// ...
	}
}

// StrokeRect
void
DrawingEngine::StrokeRect(BRect r, const rgb_color& color)
{
	StrokeLine(r.LeftTop(), r.RightTop(), color);
	StrokeLine(r.RightTop(), r.RightBottom(), color);
	StrokeLine(r.RightBottom(), r.LeftBottom(), color);
	StrokeLine(r.LeftBottom(), r.LeftTop(), color);
}

// FillRegion
void
DrawingEngine::FillRegion(BRegion *region, const rgb_color& color)
{
	if (Lock()) {
		// for speed reasons, expected to be already clipped
		fHWInterface->FillRegion(*region, color);

		Unlock();
	}
}

// DrawString
void
DrawingEngine::DrawString(const char* string, BPoint baseLine,
						  const rgb_color& color)
{
}




struct node {
			node()
			{
				pointers = NULL;
			}
			node(const BRect& r, int32 maxPointers)
			{
				init(r, maxPointers);
			}
			~node()
			{
				delete [] pointers;
			}

	void	init(const BRect& r, int32 maxPointers)
			{
				rect = r;
				pointers = new node*[maxPointers];
				in_degree = 0;
				next_pointer = 0;
			}

	void	push(node* node)
			{
				pointers[next_pointer] = node;
				next_pointer++;
			}
	node*	top()
			{
				return pointers[next_pointer];
			}
	node*	pop()
			{
				node* ret = top();
				next_pointer--;
				return ret;
			}

	BRect	rect;
	int32	in_degree;
	node**	pointers;
	int32	next_pointer;
};

bool
is_left_of(const BRect& a, const BRect& b)
{
	return (a.right < b.left);
}
bool
is_above(const BRect& a, const BRect& b)
{
	return (a.bottom < b.top);
}

void
DrawingEngine::CopyRegion(BRegion* region, int32 xOffset, int32 yOffset)
{
	if (Lock()) {

		int32 count = region->CountRects();
	
		// TODO: make this step unnecessary
		// (by using different stack impl inside node)
		node nodes[count];
		for (int32 i= 0; i < count; i++) {
			nodes[i].init(region->RectAt(i), count);
		}
	
		for (int32 i = 0; i < count; i++) {
			BRect a = region->RectAt(i);
			for (int32 k = i + 1; k < count; k++) {
				BRect b = region->RectAt(k);
				int cmp = 0;
				// compare horizontally
				if (xOffset > 0) {
					if (is_left_of(a, b)) {
						cmp -= 1;
					} else if (is_left_of(b, a)) {
						cmp += 1;
					}
				} else if (xOffset < 0) {
					if (is_left_of(a, b)) {
						cmp += 1;
					} else if (is_left_of(b, a)) {
						cmp -= 1;
					}
				}
				// compare vertically
				if (yOffset > 0) {
					if (is_above(a, b)) {
						cmp -= 1;	
					} else if (is_above(b, a)) {
						cmp += 1;
					}
				} else if (yOffset < 0) {
					if (is_above(a, b)) {
						cmp += 1;
					} else if (is_above(b, a)) {
						cmp -= 1;
					}
				}
				// add appropriate node as successor
				if (cmp > 0) {
					nodes[i].push(&nodes[k]);
					nodes[k].in_degree++;
				} else if (cmp < 0) {
					nodes[k].push(&nodes[i]);
					nodes[i].in_degree++;
				}
			}
		}
		// put all nodes onto a stack that have an "indegree" count of zero
		stack<node*> inDegreeZeroNodes;
		for (int32 i = 0; i < count; i++) {
			if (nodes[i].in_degree == 0) {
				inDegreeZeroNodes.push(&nodes[i]);
			}
		}
		// pop the rects from the stack, do the actual copy operation
		// and decrease the "indegree" count of the other rects not
		// currently on the stack and to which the current rect pointed
		// to. If their "indegree" count reaches zero, put them onto the
		// stack as well.

		clipping_rect* sortedRectList = new clipping_rect[count];
		int32 nextSortedIndex = 0;

		while (!inDegreeZeroNodes.empty()) {
			node* n = inDegreeZeroNodes.top();
			inDegreeZeroNodes.pop();

			sortedRectList[nextSortedIndex].left	= (int32)n->rect.left;
			sortedRectList[nextSortedIndex].top		= (int32)n->rect.top;
			sortedRectList[nextSortedIndex].right	= (int32)n->rect.right;
			sortedRectList[nextSortedIndex].bottom	= (int32)n->rect.bottom;
			nextSortedIndex++;

			for (int32 k = 0; k < n->next_pointer; k++) {
				n->pointers[k]->in_degree--;
				if (n->pointers[k]->in_degree == 0)
					inDegreeZeroNodes.push(n->pointers[k]);
			}
		}

		// trigger the HW accelerated blit
		fHWInterface->CopyRegion(sortedRectList, count, xOffset, yOffset);

		delete[] sortedRectList;

		Unlock();
	}
}