// ================================================================================
// ==      This file is a part of Turbo Badger. (C) 2011-2014, Emil Segerås      ==
// ==                     See tb_core.h for more information.                    ==
// ================================================================================

#include "tb_geometry.h"
#include <assert.h>

namespace tb {

// == TBRect ============================================================================

bool TBRect::Intersects(const TBRect &rect) const
{
	if (IsEmpty() || rect.IsEmpty())
		return false;
	if (x + w > rect.x && x < rect.x + rect.w &&
		y + h > rect.y && y < rect.y + rect.h)
		return true;
	return false;
}

TBRect TBRect::MoveIn(const TBRect &bounding_rect) const
{
	return TBRect(ClampClipMax(x, bounding_rect.x, bounding_rect.x + bounding_rect.w - w),
				ClampClipMax(y, bounding_rect.y, bounding_rect.y + bounding_rect.h - h),
				w, h);
}

TBRect TBRect::CenterIn(const TBRect &bounding_rect) const
{
	return TBRect(bounding_rect.x + (bounding_rect.w - w) / 2, bounding_rect.y + (bounding_rect.h - h) / 2, w, h);
}

TBRect TBRect::Union(const TBRect &rect) const
{
	assert(!IsInsideOut());
	assert(!rect.IsInsideOut());

	if (IsEmpty())
		return rect;
	if (rect.IsEmpty())
		return *this;

	int minx = MIN(x, rect.x);
	int miny = MIN(y, rect.y);
	int maxx = x + w > rect.x + rect.w ?
				x + w : rect.x + rect.w;
	int maxy = y + h > rect.y + rect.h ?
				y + h : rect.y + rect.h;
	return TBRect(minx, miny, maxx - minx, maxy - miny);
}

TBRect TBRect::Clip(const TBRect &clip_rect) const
{
	assert(!clip_rect.IsInsideOut());
	TBRect tmp;
	if (!Intersects(clip_rect))
		return tmp;
	tmp.x = MAX(x, clip_rect.x);
	tmp.y = MAX(y, clip_rect.y);
	tmp.w = MIN(x + w, clip_rect.x + clip_rect.w) - tmp.x;
	tmp.h = MIN(y + h, clip_rect.y + clip_rect.h) - tmp.y;
	return tmp;
}

// == TBRegion ==========================================================================

TBRegion::TBRegion()
	: m_rects(nullptr)
	, m_num_rects(0)
	, m_capacity(0)
{
}

TBRegion::~TBRegion()
{
	RemoveAll(true);
}

void TBRegion::RemoveRect(int index)
{
	assert(index >= 0 && index < m_num_rects);
	for (int i = index; i < m_num_rects - 1; i++)
		m_rects[i] = m_rects[i + 1];
	m_num_rects--;
}

void TBRegion::RemoveRectFast(int index)
{
	assert(index >= 0 && index < m_num_rects);
	m_rects[index] = m_rects[--m_num_rects];
}

void TBRegion::RemoveAll(bool free_memory)
{
	m_num_rects = 0;
	if (free_memory)
	{
		delete [] m_rects;
		m_rects = nullptr;
		m_capacity = 0;
	}
}

bool TBRegion::Set(const TBRect &rect)
{
	RemoveAll();
	return AddRect(rect, false);
}

bool TBRegion::GrowIfNeeded()
{
	if (m_num_rects == m_capacity)
	{
		int new_m_capacity = CLAMP(4, m_capacity * 2, 1024);
		TBRect *new_rects = new TBRect[new_m_capacity];
		if (!new_rects)
			return false;
		if (m_rects)
			memmove(new_rects, m_rects, sizeof(TBRect) * m_capacity);
		delete [] m_rects;
		m_rects = new_rects;
		m_capacity = new_m_capacity;
	}
	return true;
}

bool TBRegion::AddRect(const TBRect &rect, bool coalesce)
{
	if (coalesce)
	{
		// If the rect can coalesce with any existing rect,
		// just replace it with the union of both, doing coalesce
		// check again recursively.
		// Searching backwards is most likely to give a hit quicker
		// in many usage scenarios.
		for (int i = m_num_rects - 1; i >= 0; i--)
		{
			if ( // Can coalesce vertically
				(rect.x == m_rects[i].x && rect.w == m_rects[i].w &&
				(rect.y == m_rects[i].y + m_rects[i].h || rect.y + rect.h == m_rects[i].y))
				|| // Can coalesce horizontally
				(rect.y == m_rects[i].y && rect.h == m_rects[i].h &&
				(rect.x == m_rects[i].x + m_rects[i].w || rect.x + rect.w == m_rects[i].x))
				)
			{
				TBRect union_rect = m_rects[i].Union(rect);
				RemoveRectFast(i);
				return AddRect(union_rect, true);
			}
		}
	}

	if (!GrowIfNeeded())
		return false;
	m_rects[m_num_rects++] = rect;
	return true;
}

bool TBRegion::IncludeRect(const TBRect &include_rect)
{
	for (int i = 0; i < m_num_rects; i++)
	{
		if (include_rect.Intersects(m_rects[i]))
		{
			// Make a region containing the non intersecting parts and then include
			// those recursively (they might still intersect some other part of the region).
			TBRegion inclusion_region;
			if (!inclusion_region.AddExcludingRects(include_rect, m_rects[i], false))
				return false;
			for (int j = 0; j < inclusion_region.m_num_rects; j++)
			{
				if (!IncludeRect(inclusion_region.m_rects[j]))
					return false;
			}
			return true;
		}
	}
	// Now we know that the rect can be added without overlap.
	// Add it with coalesce checking to keep the number of rects down.
	return AddRect(include_rect, true);
}

bool TBRegion::ExcludeRect(const TBRect &exclude_rect)
{
	int num_rects_to_check = m_num_rects;
	for (int i = 0; i < num_rects_to_check; i++)
	{
		if (m_rects[i].Intersects(exclude_rect))
		{
			// Remove the existing rectangle we found we intersect
			// and add the pieces we don't intersect. New rects
			// will be added at the end of the list, so we can decrease
			// num_rects_to_check.
			TBRect rect = m_rects[i];
			RemoveRect(i);
			num_rects_to_check--;
			i--;

			if (!AddExcludingRects(rect, exclude_rect, true))
				return false;
		}
	}
	return true;
}

bool TBRegion::AddExcludingRects(const TBRect &rect, const TBRect &exclude_rect, bool coalesce)
{
	assert(rect.Intersects(exclude_rect));
	TBRect remove = exclude_rect.Clip(rect);

	if (remove.y > rect.y)
		if (!AddRect(TBRect(rect.x, rect.y, rect.w, remove.y - rect.y), coalesce))
			return false;
	if (remove.x > rect.x)
		if (!AddRect(TBRect(rect.x, remove.y, remove.x - rect.x, remove.h), coalesce))
			return false;
	if (remove.x + remove.w < rect.x + rect.w)
		if (!AddRect(TBRect(remove.x + remove.w, remove.y, rect.x + rect.w - (remove.x + remove.w), remove.h), coalesce))
			return false;
	if (remove.y + remove.h < rect.y + rect.h)
		if (!AddRect(TBRect(rect.x, remove.y + remove.h, rect.w, rect.y + rect.h - (remove.y + remove.h)), coalesce))
			return false;
	return true;
}

const TBRect &TBRegion::GetRect(int index) const
{
	assert(index >= 0 && index < m_num_rects);
	return m_rects[index];
}

} // namespace tb
