A fast and lightweight cell control

#pragma once

//using namespace Loki;
class CRgnLight {
	struct CRect : public RECT {
		CRect* m_pNext;
	};

	// Those two function are for allocating and freeing rectangle nodes.
	// You can implement them using standard new and delete operators, however
	// memory management for equally sized blocks can be done far more effectively.
	// I recommend you reading http://www.codeproject.com/cpp/advanced_heap.asp.
	// Now, it could be also a good idea to define those functions virtual (and possibly some other),
	// but my goal was to create a very light-weight implementation, so that
	// I didn't want to grant a virtual table to my objects, doubling their size.
	// If there is not enough memory to allocate a node the NodeAlloc() function should through
	// an exception.
	static CRect* NodeAlloc();
	static void NodeFree(CRect* p);

	CRect* m_pHead;
public:

	// Emptry constructor.
	CRgnLight() : m_pHead(NULL) {}

	// Destructor with cleanup.
	~CRgnLight() { Clear(); }

	// Swaps two region objects.
	void Swap(CRgnLight& rgnOther)
	{
		CRect* pHead = m_pHead;
		m_pHead = rgnOther.m_pHead;
		rgnOther.m_pHead = pHead;
	}

	// Clears the region, making it empty in fact.
	void Clear();

	// Constructs the region from a given GDI region handle
	void FromGdi(HRGN);

	// Constructs the GDI region from self
	HRGN ToGdi() const;

	// Exports the region into an array of rectangles. Prior to calling this function
	// you must query the count of rectanges by GetRectsCoount()
	void ToArr(RECT* pRect) const
	{
		for (CRect* pValue = m_pHead; pValue; pValue = pValue->m_pNext, ++pRect)
			*pRect = *pValue;
	}

	// Gets the bounding rectangle for the region and returns true.
	// If empty - returns false and fills the bounding rectangle with zeroes
	bool GetBox(RECT&) const;

	// Counts rectangles within the region
	ULONG GetRectsCoount() const
	{
		ULONG nCount = 0;
		for (CRect* pRect = m_pHead; pRect; pRect = pRect->m_pNext)
			nCount++;
		return nCount;
	}

	// Offsets the region by offsetting all its rectangles.
	void Offset(long nX, long nY);

	// Brings the region to the canonical form.
	void Optimize();

	// Subtracts a rectangle from the region.
	void Substract(const RECT& rcValue)
	{
		if ((rcValue.left < rcValue.right) && (rcValue.top < rcValue.bottom))
			PerfSubstract(rcValue, NULL);
	}

	// RGN_DIFF
	void Substract(const CRgnLight& rgnOther) { PerfSubstract(rgnOther, NULL); }

	// RGN_COPY
	void Copy(const CRgnLight& rgnOther) { Clear(); PerfAppend(rgnOther); }

	// RGN_AND
	void Intersect(const CRgnLight& rgnOther)
	{
		CRgnLight rgnIntersect;
		PerfSubstract(rgnOther, &rgnIntersect);
		Swap(rgnIntersect);
	}

	// RGN_OR
	void Combine(const CRgnLight& rgnOther) { Substract(rgnOther); PerfAppend(rgnOther); }

	// The following function subtracts one region from another,
	// and the intersection (that has been cut out) is appended to rgnIntersect parameter.
	// Pay attention: the rgnIntersect is NOT cleared, so that you must be sure
	// that it doesn't intersect with what it will be appended with.
	void SubstractEx(const CRgnLight& rgnValue, CRgnLight& rgnIntersect)
	{
		PerfSubstract(rgnValue, &rgnIntersect);
#ifdef _DEBUG
		rgnIntersect.AssertValid();
#endif
	}

	// Compares two regions. Assuming that both regions are optimized.
	bool IsEqual(const CRgnLight&) const;

	// Test if the region intersects with a givern rectangle.
	bool RectInRgn(const RECT& rcValue) const
	{
		if(rcValue.right>rcValue.left && rcValue.bottom>rcValue.top){
			for (CRect* pRect = m_pHead; pRect; pRect = pRect->m_pNext)
				if (RectsIntersect(rcValue, *pRect))
					return true;
		}
		return false;
	}

	// Test for emptiness.
	bool IsEmpty() const { return !m_pHead; }

	// Static function that tests two region for intersection.
	static bool RectsIntersect(const RECT& rcValue1, const RECT& rcValue2)
	{
		return 
			((rcValue1.left < rcValue2.left) ? (rcValue1.right > rcValue2.left) : (rcValue1.left < rcValue2.right)) &&
			((rcValue1.top < rcValue2.top) ? (rcValue1.bottom > rcValue2.top) : (rcValue1.top < rcValue2.bottom));
	}

	// Unite the region with a given rectangle.
	void AddRect(const RECT& rcValue)
	{
		if ((rcValue.right > rcValue.left) && (rcValue.bottom > rcValue.top))
		{
			PerfSubstract(rcValue, NULL);
			AddHead(rcValue);
		}
	}
	void AddRect(int nL, int nT, int nR, int nB)
	{
		RECT rcValue = { nL, nT, nR, nB };
		AddRect(rcValue);
	}

	// Iteration
	const RECT* GetFirst() const { return m_pHead; }
	static const RECT* GetNext(const RECT* pRect) { return ((CRect*) pRect)->m_pNext; }

	// Debug
#ifdef _DEBUG
	void AssertValid() const
	{
		for (CRect* pRect = m_pHead; pRect; pRect = pRect->m_pNext)
			for (CRect* pNext = pRect->m_pNext; pNext; pNext = pNext->m_pNext)
				_ASSERT(!RectsIntersect(*pRect, *pNext));
	}
	void AssertEqualNotOptimized(const CRgnLight& rgnOther)
	{
		CRgnLight rgnDup;
		rgnDup.Copy(rgnOther);
		rgnDup.PerfSubstract(*this, NULL);
		_ASSERT(rgnDup.IsEmpty());

		rgnDup.Copy(*this);
		rgnDup.Substract(rgnOther);
		_ASSERT(rgnDup.IsEmpty());
	}
#endif

private:
	void AddHead(const RECT& rcValue)
	{
		// the rcValue MUST be well-ordered and MUST NOT intersect with any of current rects.
		CRect* pRect = NodeAlloc();
		CopyMemory(pRect, &rcValue, sizeof(RECT));
		AddHead(pRect);
	}
	void AddHead(int nL, int nT, int nR, int nB)
	{
		RECT rcValue = { nL, nT, nR, nB };
		AddHead(rcValue);
	}
	void AddHead(CRect* pNode)
	{
		pNode->m_pNext = m_pHead;
		m_pHead = pNode;
	}
	CRect* SeekNextLine(CRect* pLine);
	void PerfSubstract(const RECT& rcValue, CRgnLight* prgnErased);
	void PerfSubstract(const CRgnLight& rgnValue, CRgnLight* prgnErased)
	{
		for (CRect* pRect = rgnValue.m_pHead; pRect; pRect = pRect->m_pNext)
			PerfSubstract(*pRect, prgnErased);
	}
	void PerfAppend(const CRgnLight& rgnValue)
	{
		for (CRect* pRect = rgnValue.m_pHead; pRect; pRect = pRect->m_pNext)
			AddHead(*pRect);
	}
	void AdvanceIteration(CRect*& pPrev2, CRect*& pPrev1, CRect*& pCurrent, bool bSwap);
};