setregion2d.hh

Motion JPEG编解码器源代码

#ifndef __SETREGION2D_H__
#define __SETREGION2D_H__

// This file (C) 2004 Steven Boswell.  All rights reserved.
// Released to the public under the GNU General Public License.
// See the file COPYING for more information.

// SetRegion2D tracks a 2-dimensional region of arbitrary points.
// It's implemented by a sorted set of Extents.  This is pretty fast
// overall, and is very space efficient, even with sparse regions.

#include "Region2D.hh"
#include "Set.hh"



// Define this to compile in code to double-check and debug the region.
#ifndef DEBUG_REGION2D
//	#define DEBUG_SETREGION2D
#endif // DEBUG_REGION2D



// The 2-dimensional region class.  Parameterized by the numeric type
// to use for point indices, and the numeric type to use to count the
// contained number of points.
template <class INDEX, class SIZE>
class SetRegion2D : public Region2D<INDEX,SIZE>
{
private:
	typedef Region2D<INDEX,SIZE> BaseClass;
		// Keep track of who our base class is.
public:
	typedef typename BaseClass::Extent Extent;
		// (Wouldn't we automatically have access to Extent because
		// we're a subclass of Region2D<>?  Why is this needed?)
	typedef Set<Extent> Extents;
private:
	Extents m_setExtents;
		// The extents that make up the region.

public:
	typedef typename Extents::Allocator Allocator;
		// The type of allocator to use to allocate region extents.

	explicit SetRegion2D (Allocator &a_rAlloc
			= Extents::Imp::sm_oNodeAllocator);
		// Default constructor.  Must be followed by Init().

	SetRegion2D (Status_t &a_reStatus, Allocator &a_rAlloc
			= Extents::Imp::sm_oNodeAllocator);
		// Initializing constructor.  Creates an empty region.

	SetRegion2D (Status_t &a_reStatus,
			const SetRegion2D<INDEX,SIZE> &a_rOther);
		// Copy constructor.
	
	void Init (Status_t &a_reStatus);
		// Initializer.  Must be called on default-constructed regions.

	void Assign (Status_t &a_reStatus,
			const SetRegion2D<INDEX,SIZE> &a_rOther);
		// Make the current region a copy of the other region.

	virtual ~SetRegion2D();
		// Destructor.

#ifdef DEBUG_SETREGION2D

	void SetDebug (bool a_bDebug);
		// Set whether to run the region invariant before and after
		// methods.

	void Invariant (void) const;
		// Thoroughly analyze the region for structural integrity.

#endif // DEBUG_SETREGION2D

	inline SIZE NumberOfPoints (void) const;
		// Return the total number of points contained by the region.

	void Clear (void);
		// Clear the region, emptying it of all extents.

	void Union (Status_t &a_reStatus, INDEX a_tnY, INDEX a_tnXStart,
			INDEX a_tnXEnd);
		// Add the given horizontal extent to the region.  Note that
		// a_tnXEnd is technically one past the end of the extent.

	void Merge (Status_t &a_reStatus, INDEX a_tnY, INDEX a_tnXStart,
			INDEX a_tnXEnd);
		// Merge this extent into the current region.
		// The new extent can't intersect any of the region's existing
		// extents (including being horizontally contiguous).

	void Merge (SetRegion2D<INDEX,SIZE> &a_rOther);
		// Merge the other region into ourselves, emptying the other
		// region.  Like Union(), but doesn't allocate any new memory.
		// Also, the other region can't intersect any of the region's
		// existing extents (including being horizontally contiguous),
		// and both regions must use the same allocator.

	void Move (SetRegion2D<INDEX,SIZE> &a_rOther);
		// Move the contents of the other region into the current
		// region.
		// The current region must be empty.

	bool CanMove (const SetRegion2D<INDEX,SIZE> &a_rOther) const;
		// Returns true if the other region's contents can be moved
		// into the current region.

	bool CanMove (const Region2D<INDEX,SIZE> &a_rOther) const
			{ return false; }
	void Move (Region2D<INDEX,SIZE> &a_rOther) { assert (false); }
		// (We can move between SetRegion2D<>s, but not any arbitrary
		// Region2D<> subclass.)

	void Intersection (Status_t &a_reStatus,
			const SetRegion2D<INDEX,SIZE> &a_rOther);
		// Make the current region represent the intersection between
		// itself and the other given region.

	void Subtract (Status_t &a_reStatus, INDEX a_tnY, INDEX a_tnXStart,
			INDEX a_tnXEnd);
		// Subtract the given horizontal extent from the region.  Note
		// that a_tnXEnd is technically one past the end of the extent.

	void Subtract (Status_t &a_reStatus,
			const SetRegion2D<INDEX,SIZE> &a_rOther);
		// Subtract the other region from the current region, i.e.
		// remove from the current region any extents that exist in the
		// other region.
	
	void Offset (INDEX a_tnXOffset, INDEX a_tnYOffset);
		// Move all extents by the given offset.

	typedef typename Extents::ConstIterator ConstIterator;
	ConstIterator Begin (void) const { return m_setExtents.Begin(); }
	ConstIterator End (void) const { return m_setExtents.End(); }
		// Allow our client to iterate through the extents & get their
		// values.
	
	bool DoesContainPoint (INDEX a_tnY, INDEX a_tnX);
		// Returns true if the region contains the given point.

	bool DoesContainPoint (INDEX a_tnY, INDEX a_tnX,
			ConstIterator &a_ritHere);
		// Returns true if the region contains the given point.
		// Backpatches the extent that contains the point, or the
		// extent before where it should be.

	// A structure that implements flood-fills using SetRegion2D<> to
	// do the work.
	class FloodFillControl;

	template <class CONTROL>
	void FloodFill (Status_t &a_reStatus, CONTROL &a_rControl,
			bool a_bVerify);
		// Flood-fill the current region.  All points bordering the
		// current region are tested for inclusion; if a_bVerify is
		// true, all existing region points are tested first.

	template <class REGION>
	void MakeBorder (Status_t &a_reStatus, const REGION &a_rOther);
		// Make the current region represent the border of the other
		// region, i.e. every pixel that's adjacent to a pixel that's
		// in the region, but isn't already in the region.

	void UnionSurroundingExtents (Status_t &a_reStatus,
			INDEX a_tnY, INDEX a_tnXStart, INDEX a_tnXEnd);
		// Add all extents surrounding the given extent.
		// Used by FloodFill() and MakeBorder().

private:
	SIZE m_tnPoints;
		// The total number of points contained by the region.

	void Subtract (Status_t &a_reStatus, INDEX a_tnY, INDEX a_tnXStart,
			INDEX a_tnXEnd, const SetRegion2D<INDEX,SIZE> &a_rOther,
			typename Extents::ConstIterator &a_ritHere);
		// Subtract the given horizontal extent from the region.  Note
		// that a_tnXEnd is technically one past the end of the extent.
		// a_ritHere is a reference to the iterator that this extent
		// came from in a_rOther, or a_rOther.m_setExtents.End() if
		// there is no such iterator.  If there are no extents that
		// intersect the given extent, ritHere is backpatched with the
		// location of the first extent in a_rOther to intersect it.
		// This allows region subtractions to skip past irrelevant
		// areas.

#ifdef DEBUG_SETREGION2D

	bool m_bDebug;
		// true if the invariant should be checked.

#endif // DEBUG_SETREGION2D

#ifndef NDEBUG

// Count the number of region objects in existence.
private:
	static uint32_t sm_ulInstances;
public:
	static uint32_t GetInstances (void) { return sm_ulInstances; }
	
#endif // NDEBUG
};



// The flood-fill-control class.
template <class INDEX, class SIZE>
class SetRegion2D<INDEX,SIZE>::FloodFillControl
{
private:
	typedef SetRegion2D<INDEX,SIZE> Region_t;
		// Keep track of our region class.
public:
	// (Although these fields are public, they should be considered
	// opaque to the client.)

	Region_t m_oToDo;
		// Extents that still need to be be tested.

	Region_t m_oAlreadyDone;
		// Extents that have been tested.

	Region_t m_oNextToDo;
		// Extents contiguous with those that have just been added
		// to the flood-filled area.

	typedef typename Region_t::ConstIterator ConstIterator;
	typedef typename Region_t::Extent Extent;
		// The iterator/extent type for running through the above
		// regions.
	typedef typename Region_t::Allocator Allocator;
		// The allocator type for region extents.

public:
	explicit FloodFillControl (Allocator &a_rAllocator
			= Region_t::Extents::Imp::sm_oNodeAllocator);
		// Default constructor.  Must be followed by a call to Init().
	
	FloodFillControl (Status_t &a_reStatus, Allocator &a_rAllocator
			= Region_t::Extents::Imp::sm_oNodeAllocator);
		// Initializing constructor.
	
	void Init (Status_t &a_reStatus);
		// Initializer.  Must be called on default-constructed objects.
		// (May not be valid to call on subclasses, depending on
		// whether more parameters are needed for its Init().)

	// Methods to be redefined by clients implementing specific
	// flood-fills.

	bool ShouldUseExtent (Extent &a_rExtent) { return true; }
		// Return true if the flood-fill should examine the given
		// extent.  Clients should redefine this to define their own
		// criteria for when extents should be used, and to modify the
		// extent as needed (e.g. to clip the extent to a bounding box).
	
	bool IsPointInRegion (INDEX a_tnX, INDEX a_tnY) { return false; }
		// Returns true if the given point should be included in the
		// flood-fill.  Clients must redefine this to explain their
		// flood-fill criteria.
};



// Default constructor.  Must be followed by Init().
template <class INDEX, class SIZE>
SetRegion2D<INDEX,SIZE>::SetRegion2D (Allocator &a_rAlloc)
	: m_setExtents (Less<Extent>(), a_rAlloc)
{
#ifndef NDEBUG
	// One more instance.
	++sm_ulInstances;
#endif // NDEBUG

	// No points yet.
	m_tnPoints = 0;

#ifdef DEBUG_SETREGION2D

	// Check the invariant by default; they'll have to specifically
	// request not to.
	m_bDebug = true;

#endif // DEBUG_SETREGION2D
}



// Initializing constructor.  Creates an empty region.
template <class INDEX, class SIZE>
SetRegion2D<INDEX,SIZE>::SetRegion2D (Status_t &a_reStatus,
		Allocator &a_rAlloc)
	: m_setExtents (a_reStatus, false, Less<Extent>(), a_rAlloc)
{
#ifndef NDEBUG
	// One more instance.
	++sm_ulInstances;
#endif // NDEBUG

	// No points yet.
	m_tnPoints = 0;

#ifdef DEBUG_SETREGION2D

	// Check the invariant by default; they'll have to specifically
	// request not to.
	m_bDebug = true;

#endif // DEBUG_SETREGION2D
}



// Copy constructor.
template <class INDEX, class SIZE>
SetRegion2D<INDEX,SIZE>::SetRegion2D (Status_t &a_reStatus,
		const SetRegion2D<INDEX,SIZE> &a_rOther)
	: m_setExtents (a_reStatus, false, Less<Extent>(),
		a_rOther.m_setExtents.m_oImp.m_rNodeAllocator)
{
#ifndef NDEBUG
	// One more instance.
	++sm_ulInstances;
#endif // NDEBUG

	// No points yet.
	m_tnPoints = 0;

#ifdef DEBUG_SETREGION2D

	// Check the invariant by default; they'll have to specifically
	// request not to.
	m_bDebug = true;

#endif // DEBUG_SETREGION2D

	// If the construction of m_setExtents failed, bail.
	if (a_reStatus != g_kNoError)
		return;

	// Copy all the extents.
	m_setExtents.Insert (a_reStatus, a_rOther.m_setExtents.Begin(),
		a_rOther.m_setExtents.End());
	if (a_reStatus != g_kNoError)
		return;

	// Now we have as many points as the copied region.
	m_tnPoints = a_rOther.m_tnPoints;

#ifdef DEBUG_SETREGION2D
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SETREGION2D
}



// Initializer.  Must be called on default-constructed regions.
template <class INDEX, class SIZE>
void
SetRegion2D<INDEX,SIZE>::Init (Status_t &a_reStatus)
{
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Initialize our set of extents.
	m_setExtents.Init (a_reStatus, false);
	if (a_reStatus != g_kNoError)
		return;
}



// Make the current region a copy of the other region.
template <class INDEX, class SIZE>
void
SetRegion2D<INDEX,SIZE>::Assign (Status_t &a_reStatus,
	const SetRegion2D<INDEX,SIZE> &a_rOther)
{
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

#ifdef DEBUG_SETREGION2D
	// Make sure both regions are intact.
	Invariant();
	a_rOther.Invariant();
#endif // DEBUG_SETREGION2D

	// Assign the other region's extents to ourselves.
	m_setExtents.Assign (a_reStatus, a_rOther.m_setExtents);
	if (a_reStatus != g_kNoError)
		return;

	// Now we have as many points as they do.
	m_tnPoints = a_rOther.m_tnPoints;

#ifdef DEBUG_SETREGION2D
	// Make sure we're intact.
	Invariant();
#endif // DEBUG_SETREGION2D
}



// Destructor.
template <class INDEX, class SIZE>
SetRegion2D<INDEX,SIZE>::~SetRegion2D()
{
#ifndef NDEBUG
	// One less instance.
	--sm_ulInstances;
#endif // NDEBUG
}



#ifdef DEBUG_SETREGION2D

// Set whether to run the region invariant before and after
// methods.
template <class INDEX, class SIZE>
void
SetRegion2D<INDEX,SIZE>::SetDebug (bool a_bDebug)
{
	// Easy enough.
	m_bDebug = a_bDebug;

#ifdef DEBUG_SKIPLIST

	// Have the set of extents check itself too, to make sure we didn't
	// do anything to break it.
	m_setExtents.SetDebug (a_bDebug);

#endif // DEBUG_SKIPLIST
}



// Thoroughly analyze the region for structural integrity.
template <class INDEX, class SIZE>
void
SetRegion2D<INDEX,SIZE>::Invariant (void) const
{
	SIZE tnPoints;
		// Our total of the number of points in the region.
	typename Extents::ConstIterator itHere, itNext;
		// Used to run through the extents.

	// Only check the invariant if they requested we do.
	if (!m_bDebug)
		return;
	
#ifdef DEBUG_SKIPLIST

	// Make sure the contained set is intact.  (That will verify that
	// the extents are sorted properly, so we don't have to do that
	// here.)
	m_setExtents.Invariant();

#endif // DEBUG_SKIPLIST

	// Run through the extents, make sure that they're not contiguous
	// with each other, and count up the number of contained points.
	tnPoints = 0;
	for (itHere = m_setExtents.Begin();
		 itHere != m_setExtents.End();
		 itHere = itNext)
	{
		// Find the next extent.
		itNext = itHere;
		++itNext;

		// Make sure that the extents aren't horizontally contiguous.
		// (Horizontally contiguous extents should have been merged
		// together.)
		assert (itNext == m_setExtents.End()
			|| (*itHere).m_tnY != (*itNext).m_tnY
			|| (*itHere).m_tnXEnd < (*itNext).m_tnXStart);
	
		// Add the number of points in this extent to our total.
		tnPoints += (*itHere).m_tnXEnd - (*itHere).m_tnXStart;
	}

	// Make sure the point total is accurate.
	assert (m_tnPoints == tnPoints);
}

#endif // DEBUG_SETREGION2D



// Return the total number of points contained by the region.
template <class INDEX, class SIZE>
inline SIZE
SetRegion2D<INDEX,SIZE>::NumberOfPoints (void) const
{
	// Easy enough.
	return m_tnPoints;
}



// Clear the region, emptying it of all extents.
template <class INDEX, class SIZE>
void
SetRegion2D<INDEX,SIZE>::Clear (void)
{