bitmapregion2d.hh

来自「Motion JPEG编解码器源代码」· HH 代码 · 共 1,442 行 · 第 1/3 页

#ifndef __BITMAPREGION2D_H__
#define __BITMAPREGION2D_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.

// BitmapRegion2D tracks a 2-dimensional region of arbitrary points,
// implemented with a bitmap.

#include <assert.h>
#include <string.h>
#include "Region2D.hh"



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



// Part of BitmapRegion2D<> breaks gcc 2.95.  An earlier arrangement of
// the code also broke gcc 3.3, but that seems to be in remission now.
#if defined(__GNUC__) && defined(__GNUC_MINOR__)
#if __GNUC__ == 2 && __GNUC_MINOR__ < 96
#define GCC_295_WORKAROUND
#endif
#endif



// 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 BitmapRegion2D : 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?)

	BitmapRegion2D();
		// Default constructor.  Must be followed by Init().

	BitmapRegion2D (Status_t &a_reStatus, INDEX a_tnWidth,
			INDEX a_tnHeight);
		// Initializing constructor.  Creates an empty region with the
		// given extent.

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

	template <class OTHER>
	void Assign (Status_t &a_reStatus, const OTHER &a_rOther);
		// Make the current region a copy of the other region.

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

	virtual ~BitmapRegion2D();
		// Destructor.

	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 (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 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.
		// (This version is for interface compatibility with the
		// set-based region.)

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

	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 the region in any way.

	void Merge (BitmapRegion2D<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 us in any way, and
		// both regions must use the same allocator.

	void Move (BitmapRegion2D<INDEX,SIZE> &a_rOther);
		// Move the contents of the other region into the current
		// region.

	bool CanMove (const BitmapRegion2D<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 BitmapRegion2D<>s, but not any arbitrary
		// Region2D<> subclass.)

	void Intersection (Status_t &a_reStatus,
			const BitmapRegion2D<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.

	template <class OTHER>
	void Subtract (Status_t &a_reStatus, const OTHER &a_rOther);
		// Subtract the other region from the current region, i.e.
		// remove from the current region any areas that exist in the
		// other region.

	void Subtract (Status_t &a_reStatus,
			const BitmapRegion2D<INDEX,SIZE> &a_rOther);
		// Subtract the other region from the current region, i.e.
		// remove from the current region any areas that exist in the
		// other region.
	
	bool DoesContainPoint (INDEX a_tnY, INDEX a_tnX) const;
		// Returns true if the region contains the given point.

	// A structure that implements flood-fills using BitmapRegion2D<> to
	// do the work.  (The definition of this class follows the
	// definition of Region<>.)
	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.

	template <class OTHER>
	void MakeBorder (Status_t &a_reStatus, const OTHER &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.

	// An iterator for the bitmap-oriented region.
	class ConstIterator
	{
	protected:
		friend class BitmapRegion2D<INDEX,SIZE>;
			// Let the region implement our operations.
		const BitmapRegion2D<INDEX,SIZE> *m_pThis;
			// The region that we're iterating through.
		Extent m_oExtent;
			// The extent we currently represent.
	public:
		ConstIterator() { m_pThis = NULL; }
		ConstIterator (const ConstIterator &a_rOther)
			: m_pThis (a_rOther.m_pThis),
			m_oExtent (a_rOther.m_oExtent) {}
		const Extent &operator*() const { return m_oExtent; }
		ConstIterator& operator++();
		ConstIterator operator++(int) { ConstIterator oTmp = *this;
			++*this; return oTmp; }
		ConstIterator& operator--();
		ConstIterator operator--(int) { ConstIterator oTmp = *this;
			--*this; return oTmp; }
		bool operator== (const ConstIterator &a_rOther) const
			{ return (m_pThis == a_rOther.m_pThis
				&& m_oExtent == a_rOther.m_oExtent) ? true : false; }
		bool operator!= (const ConstIterator &a_rOther) const
			{ return (m_pThis != a_rOther.m_pThis
				|| m_oExtent != a_rOther.m_oExtent) ? true : false; }
	};

	ConstIterator Begin (void) const;
	ConstIterator End (void) const;
		// Allow our client to iterate through the extents & get their
		// values.

	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().
	
	void IteratorForward (ConstIterator &a_ritHere) const;
		// Move one of our iterators forward.
	
	void IteratorBackward (ConstIterator &a_ritHere) const;
		// Move one of our iterators backward.
	
	static int FindFirstSetBit (unsigned int a_nWord, int a_nSkip);
	static int FindFirstClearBit (unsigned int a_nWord, int a_nSkip);
	static int FindLastSetBit (unsigned int a_nWord, int a_nSkip);
	static int FindLastClearBit (unsigned int a_nWord, int a_nSkip);
		// Find the index of the first/last set/clear bit, skipping
		// the first/last a_nSkip bits.
		// Used to implement iterator increment/decrement.

private:
	INDEX m_tnWidth, m_tnHeight;
		// The extent of the bitmap.
	
	unsigned int *m_pnPoints;
		// The bitmap representing the region.
	
	SIZE m_tnBitmapInts;
		// The number of integers in our bitmap.
	
	static int8_t m_anSetBitsPerByte[256];
		// The number of set bits in every possible byte value.
	
	static bool m_bSetBitsPerByte;
		// Whether the set-bits-per-byte table has been set up.

#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
};



// A structure that implements flood-fills using BitmapRegion2D<> to
// do the work.
template <class INDEX, class SIZE>
class BitmapRegion2D<INDEX,SIZE>::FloodFillControl
#ifndef GCC_295_WORKAROUND
	: public Region2D<INDEX,SIZE>::
		template FloodFillControl<BitmapRegion2D<INDEX,SIZE> >
#endif // ! GCC_295_WORKAROUND
{
public:
#ifdef GCC_295_WORKAROUND
	// (Although these fields are public, they should be considered
	// opaque to the client.)

	BitmapRegion2D<INDEX,SIZE> m_oToDo;
		// Extents that still need to be be tested.

	BitmapRegion2D<INDEX,SIZE> m_oAlreadyDone;
		// Extents that have been tested.

	BitmapRegion2D<INDEX,SIZE> m_oNextToDo;
		// Extents contiguous with those that have just been added
		// to the flood-filled area.

	typedef typename BitmapRegion2D<INDEX,SIZE>::ConstIterator
		ConstIterator;
	typedef typename BitmapRegion2D<INDEX,SIZE>::Extent Extent;
		// The iterator/extent type for running through the above
		// regions.
#endif // GCC_295_WORKAROUND

	FloodFillControl();
		// Default constructor.  Must be followed by a call to Init().
	
	FloodFillControl (Status_t &a_reStatus, INDEX a_tnWidth,
			INDEX a_tnHeight);
		// Initializing constructor.
	
	void Init (Status_t &a_reStatus, INDEX a_tnWidth, INDEX a_tnHeight);
		// Initializer.  Must be called on default-constructed objects.

#ifdef GCC_295_WORKAROUND
	// 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.
#endif // GCC_295_WORKAROUND
};



// Default constructor.  Must be followed by Init().
template <class INDEX, class SIZE>
BitmapRegion2D<INDEX,SIZE>::BitmapRegion2D()
{
#ifndef NDEBUG
	// One more instance.
	++sm_ulInstances;
#endif // NDEBUG

	// No bitmap yet.
	m_tnWidth = m_tnHeight = INDEX (0);
	m_pnPoints = NULL;
	m_tnBitmapInts = SIZE (0);
}



// Initializing constructor.  Creates an empty region.
template <class INDEX, class SIZE>
BitmapRegion2D<INDEX,SIZE>::BitmapRegion2D (Status_t &a_reStatus,
	INDEX a_tnWidth, INDEX a_tnHeight)
{
#ifndef NDEBUG
	// One more instance.
	++sm_ulInstances;
#endif // NDEBUG

	// No bitmap yet.
	m_tnWidth = m_tnHeight = INDEX (0);
	m_pnPoints = NULL;
	m_tnBitmapInts = SIZE (0);

	// Save the width & height.
	m_tnWidth = a_tnWidth;
	m_tnHeight = a_tnHeight;

	// Allocate the bitmap.
	m_tnBitmapInts = (SIZE (m_tnWidth) * SIZE (m_tnHeight))
		/ (g_knBitsPerByte * sizeof (unsigned int)) + 1;
	m_pnPoints = new unsigned int[m_tnBitmapInts];
	if (m_pnPoints == NULL)
	{
		a_reStatus = g_kOutOfMemory;
		return;
	}

	// No points yet.
	for (SIZE i = 0; i < m_tnBitmapInts; ++i)
		m_pnPoints[i] = 0U;
}



// Copy constructor.
template <class INDEX, class SIZE>
BitmapRegion2D<INDEX,SIZE>::BitmapRegion2D (Status_t &a_reStatus,
	const BitmapRegion2D<INDEX,SIZE> &a_rOther)
{
#ifndef NDEBUG
	// One more instance.
	++sm_ulInstances;
#endif // NDEBUG

	// No bitmap yet.
	m_tnWidth = m_tnHeight = INDEX (0);
	m_pnPoints = NULL;
	m_tnBitmapInts = SIZE (0);

	// Copy the width & height.
	m_tnWidth = a_rOther.m_tnWidth;
	m_tnHeight = a_rOther.m_tnHeight;

	// Allocate the bitmap.
	m_tnBitmapInts = (SIZE (m_tnWidth) * SIZE (m_tnHeight))
		/ (g_knBitsPerByte * sizeof (unsigned int)) + 1;
	m_pnPoints = new unsigned int[m_tnBitmapInts];
	if (m_pnPoints == NULL)
	{
		a_reStatus = g_kOutOfMemory;
		return;
	}

	// Copy the bitmap.
	memcpy (m_pnPoints, a_rOther.m_pnPoints,
		m_tnBitmapInts * sizeof (unsigned int));
}



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

	// Save the width & height.
	m_tnWidth = a_tnWidth;
	m_tnHeight = a_tnHeight;

	// Allocate the bitmap.
	m_tnBitmapInts = (SIZE (m_tnWidth) * SIZE (m_tnHeight))
		/ (g_knBitsPerByte * sizeof (unsigned int)) + 1;
	m_pnPoints = new unsigned int[m_tnBitmapInts];
	if (m_pnPoints == NULL)
	{
		a_reStatus = g_kOutOfMemory;
		return;
	}

	// No points yet.
	for (SIZE i = 0; i < m_tnBitmapInts; ++i)
		m_pnPoints[i] = 0U;
}



// Make the current region a copy of the other region.
template <class INDEX, class SIZE>
template <class OTHER>
void
BitmapRegion2D<INDEX,SIZE>::Assign (Status_t &a_reStatus,
	const OTHER &a_rOther)
{
	typename OTHER::ConstIterator itExtent;
		// Used to loop through extents to copy.

	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Clear our contents, in preparation for being assigned.
	Clear();

	// Loop through the other region's extents, clip them to the current
	// region's boundaries, and add them to the current region.
	for (itExtent = a_rOther.Begin();
		 itExtent != a_rOther.End();
		 ++itExtent)
	{
		// Get the extent.
		typename OTHER::Extent oExtent = *itExtent;

		// Add it to the current region.
		Union (a_reStatus, oExtent.m_tnY, oExtent.m_tnXStart,
			oExtent.m_tnXEnd);
		assert (a_reStatus == g_kNoError);	// (should always succeed.)
		if (a_reStatus != g_kNoError)
			return;
	}
}



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

	// If the region is not the exact same size, use the more
	// generic version.
	if (m_tnWidth != a_rOther.m_tnWidth
		|| m_tnHeight != a_rOther.m_tnHeight)
	{
		Assign<BitmapRegion2D<INDEX,SIZE> > (a_reStatus, *this);
		return;
	}

	// Make sure the region is the exact same size.
	assert (m_tnWidth == a_rOther.m_tnWidth