setregion2d.hh

Motion JPEG编解码器源代码

			return;
		}
		else
		{
			// The found extent gets its end cut off.

			// Remember the end of the found extent.
			INDEX nOldEnd = (*itStart).m_tnXEnd;

			// Cut off the end of the found extent.
			m_tnPoints -= (*itStart).m_tnXEnd - a_tnXStart;
			(*itStart).m_tnXEnd = a_tnXStart;

			// If the extent being subtracted ends at the same place
			// as this found extent, then we're done.
			if (nOldEnd == a_tnXEnd)
				return;

			// Move forward, and fall through to deal with the end of
			// the range being subtracted.
			++itStart;
		}
	}

	// Find the last extent that may get removed or modified by this
	// subtraction.  (That's the first existing extent
	// that's >= (y, x-end).)
	oKey.m_tnY = a_tnY;
	oKey.m_tnXStart = a_tnXEnd;
	itEnd = m_setExtents.LowerBound (oKey);

	// If that put us past any extent we'll have to remove, we can just
	// skip to the end, where the range we located will be removed.
	// Otherwise, we have to figure out the implications of the end of
	// the subtracted range.
	if (itEnd == m_setExtents.End()
	|| (*itEnd).m_tnY != a_tnY
	|| (*itEnd).m_tnXStart > a_tnXEnd)
	{
		// Move back one.
		--itEnd;

		// If that didn't put us out of the range of existing extents
		// that are getting removed, we have 2 cases: either the entire
		// extent is getting removed, or its beginning is getting
		// chopped off.
		if (itEnd != m_setExtents.End() && (*itEnd).m_tnY == a_tnY)
		{
			// How much of this extent is getting removed?
			if ((*itEnd).m_tnXEnd <= a_tnXEnd)
			{
				// The entire extent is getting removed.  Move forward
				// again.
				++itEnd;
			}
			else
			{
				// The found extent's beginning is getting chopped off.
				// (The search above ensures that this extent starts
				// before the end of the range being removed, but we
				// check our sanity anyway.)
				assert ((*itEnd).m_tnXStart < a_tnXEnd);
				m_tnPoints -= a_tnXEnd - (*itEnd).m_tnXStart;
				(*itEnd).m_tnXStart = a_tnXEnd;
			}
		}
	}

	// Loop through the range of extents to remove, subtract their
	// contribution to our point total.
	for (typename Extents::Iterator itHere = itStart;
		 itHere != itEnd;
		 itHere++)
	{
		m_tnPoints -= (*itHere).m_tnXEnd - (*itHere).m_tnXStart;
	}

	// Remove any range of extents found.
	m_setExtents.Erase (itStart, itEnd);

#ifdef DEBUG_SETREGION2D

	// Make sure we're intact.
	Invariant();

#endif // DEBUG_SETREGION2D
}



// Subtract the given horizontal extent from the region.
template <class INDEX, class SIZE>
void
SetRegion2D<INDEX,SIZE>::Subtract (Status_t &a_reStatus, INDEX a_tnY,
	INDEX a_tnXStart, INDEX a_tnXEnd)
{
	// Defer to our private helper function.
	ConstIterator itUnused = m_setExtents.End();
	Subtract (a_reStatus, a_tnY, a_tnXStart, a_tnXEnd, *this,
		itUnused);
}



// Subtract the other region from the current region, i.e.
// remove from the current region any areas that exist in the
// other region.
template <class INDEX, class SIZE>
void
SetRegion2D<INDEX,SIZE>::Subtract (Status_t &a_reStatus,
	const SetRegion2D<INDEX,SIZE> &a_rOther)
{
	typename Extents::ConstIterator itHere, itNext;
		// Where we are in the other region's extents.

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

	// Run through the extents in the other region, subtract them from
	// the current region.
	for (itHere = a_rOther.m_setExtents.Begin();
		 itHere != a_rOther.m_setExtents.End();
		 itHere = itNext)
	{
		// Subtract this extent from the current region.
		itNext = itHere;
		Subtract (a_reStatus, (*itHere).m_tnY, (*itHere).m_tnXStart,
			(*itHere).m_tnXEnd, a_rOther, itNext);
		if (a_reStatus != g_kNoError)
			return;

		// If this region is now empty, leave.
		if (m_setExtents.Size() == 0)
			return;
		
		// If there was no intersection, then itNext has the location of
		// the first extent in a_rOther that intersects one of our
		// extents.  Otherwise, move forward.
		if (itHere == itNext)
			++itNext;
	}
}



// Move all extents by the given offset.
template <class INDEX, class SIZE>
void
SetRegion2D<INDEX,SIZE>::Offset (INDEX a_tnXOffset, INDEX a_tnYOffset)
{
	typename Extents::Iterator itHere;
		// Where we're offsetting an extent.
	
	// Run through all the extents, offset them.  (NOTE: during this
	// operation, the skip-list's sorting is broken, but we don't
	// leave it broken.
	for (itHere = m_setExtents.Begin();
		 itHere != m_setExtents.End();
		 ++itHere)
	{
		Extent &rExtent = *itHere;
		rExtent.m_tnY += a_tnYOffset;
		rExtent.m_tnXStart += a_tnXOffset;
		rExtent.m_tnXEnd += a_tnXOffset;
	}
}



// Returns true if the region contains the given point.
template <class INDEX, class SIZE>
bool
SetRegion2D<INDEX,SIZE>::DoesContainPoint (INDEX a_tnY, INDEX a_tnX)
{
	Extent oKey;
	ConstIterator itKey;
		// Used to search for the extent that would contain this point.

	// Find the extent that would contain this point.
	oKey.m_tnY = a_tnY;
	oKey.m_tnXStart = a_tnX;
	itKey = m_setExtents.UpperBound (oKey);
	--itKey;

	// Return whether it does.
	if (itKey != m_setExtents.End()
	&& (*itKey).m_tnY == a_tnY
	&& a_tnX >= (*itKey).m_tnXStart
	&& a_tnX < (*itKey).m_tnXEnd)
		return true;
	else
		return false;
}



// Returns true if the region contains the given point.
template <class INDEX, class SIZE>
bool
SetRegion2D<INDEX,SIZE>::DoesContainPoint (INDEX a_tnY, INDEX a_tnX,
	ConstIterator &a_ritHere)
{
	Extent oKey;
	ConstIterator itKey;
		// Used to search for the extent that would contain this point.

	// Find the extent that would contain this point.
	oKey.m_tnY = a_tnY;
	oKey.m_tnXStart = a_tnX;
	itKey = m_setExtents.UpperBound (oKey);
	--itKey;

	// Pass it back to our caller.
	a_ritHere = itKey;

	// Return whether it does.
	if (itKey != m_setExtents.End()
	&& (*itKey).m_tnY == a_tnY
	&& a_tnX >= (*itKey).m_tnXStart
	&& a_tnX < (*itKey).m_tnXEnd)
		return true;
	else
		return false;
}



// Flood-fill the current region.
template <class INDEX, class SIZE>
template <class CONTROL>
void
SetRegion2D<INDEX,SIZE>::FloodFill (Status_t &a_reStatus,
	CONTROL &a_rControl, bool a_bVerify)
{
	typename CONTROL::ConstIterator itExtent;
		// An extent we're examining.
	Extent oFoundExtent;
		// An extent we found to be part of the region.

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

	// How we set up depends on whether we're to verify all existing
	// region extents.
	if (a_bVerify)
	{
		// The to-do-list becomes the current region, and we empty
		// out the current region too.
		a_rControl.m_oAlreadyDone.Clear();
		if (a_rControl.m_oToDo.CanMove (*this))
		{
			// Grab the extents right out of the current region.
			a_rControl.m_oToDo.Clear();
			a_rControl.m_oToDo.Move (*this);
		}
		else
		{
			// Copy the extents from the current region, then empty it.
			a_rControl.m_oToDo.Assign (a_reStatus, *this);
			if (a_reStatus != g_kNoError)
				return;
			Clear();
		}
	}
	else
	{
		// The already-done list starts with the region, i.e. every
		// extent already known to be in the region can avoid getting
		// tested.
		a_rControl.m_oAlreadyDone.Assign (a_reStatus, *this);
		if (a_reStatus != g_kNoError)
			return;
	
		// Start the to-do list with a border around all the extents in
		// the region.
		a_rControl.m_oToDo.MakeBorder (a_reStatus, *this);
		if (a_reStatus != g_kNoError)
			return;
	}

	// Now pull each extent out of the to-do list.  Determine which
	// sub-extents are part of the region.  Add those found extents
	// to the region.  Then add all extent surrounding the found extents
	// to the to-do-next list.
	itExtent = a_rControl.m_oToDo.Begin();
	while (itExtent != a_rControl.m_oToDo.End())
	{
		bool bStartedExtent;
			// true if we've started finding an extent.
		INDEX tnX;
			// Where we're looking for extents.

		// Get the extent, converting the type if necessary.
		Extent oExtent;
		oExtent.m_tnY = (*itExtent).m_tnY;
		oExtent.m_tnXStart = (*itExtent).m_tnXStart;
		oExtent.m_tnXEnd = (*itExtent).m_tnXEnd;

		// We're about to check this extent.  Put it in the
		// already-checked list now.
		a_rControl.m_oAlreadyDone.Union (a_reStatus, oExtent.m_tnY,
			oExtent.m_tnXStart, oExtent.m_tnXEnd);
		if (a_reStatus != g_kNoError)
			return;
	
		// If this extent shouldn't be considered, skip it.
		if (!a_rControl.ShouldUseExtent (oExtent))
			goto nextExtent;

		// Make sure our client left us with a valid extent.
		assert (oExtent.m_tnXStart < oExtent.m_tnXEnd);
		
		// Run through the pixels described by this extent, see if
		// they can be added to the region, and remember where to
		// search next.
		oFoundExtent.m_tnY = oExtent.m_tnY;
		bStartedExtent = false;
		for (tnX = oExtent.m_tnXStart; tnX <= oExtent.m_tnXEnd; ++tnX)
		{
			// Is this point in the region?
			if (tnX < oExtent.m_tnXEnd
			&& a_rControl.IsPointInRegion (tnX, oExtent.m_tnY))
			{
				// This point is in the region.  Start a new extent
				// if we didn't have one already, and add the point
				// to it.
				if (!bStartedExtent)
				{
					oFoundExtent.m_tnXStart = tnX;
					bStartedExtent = true;
				}
				oFoundExtent.m_tnXEnd = tnX + 1;
			}

			// This point is not in the region.  Any extent we're
			// building is done.
			else if (bStartedExtent)
			{
				// Add this extent to the region.
				Union (a_reStatus, oFoundExtent.m_tnY,
					oFoundExtent.m_tnXStart, oFoundExtent.m_tnXEnd);
				if (a_reStatus != g_kNoError)
					return;

				// Now add all surrounding extents to the to-do-next
				// list.
				a_rControl.m_oNextToDo.UnionSurroundingExtents
					(a_reStatus, oFoundExtent.m_tnY,
						oFoundExtent.m_tnXStart, oFoundExtent.m_tnXEnd);
				if (a_reStatus != g_kNoError)
					return;

				// Look for another extent.
				bStartedExtent = false;
			}
		}

nextExtent:
		// Move to the next extent.
		++itExtent;

		// If the to-do list needs to be replenished, do so.
		if (itExtent == a_rControl.m_oToDo.End())
		{
			// Replenish the to-do list.
			a_rControl.m_oNextToDo.Subtract (a_reStatus,
				a_rControl.m_oAlreadyDone);
			if (a_reStatus != g_kNoError)
				return;
			a_rControl.m_oToDo.Clear();
			a_rControl.m_oToDo.Merge (a_rControl.m_oNextToDo);
			
			// Start over at the beginning.
			itExtent = a_rControl.m_oToDo.Begin();
		}
	}
}



// Make the current region represent the border of the other
// region, i.e. every pixel that borders the region but isn't
// already in the region.
template <class INDEX, class SIZE>
template <class REGION>
void
SetRegion2D<INDEX,SIZE>::MakeBorder (Status_t &a_reStatus,
	const REGION &a_rOther)
{
	typename REGION::ConstIterator itExtent;
		// Used to loop through the other region's extents.

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

	// Start with an empty region.
	Clear();

	// For every extent in the other region, add every surrounding
	// extent.  That creates a region that looks like the other region,
	// but also contains the border we're after.
	for (itExtent = a_rOther.Begin();
		 itExtent != a_rOther.End();
		 ++itExtent)
	{
		UnionSurroundingExtents (a_reStatus, (*itExtent).m_tnY,
			(*itExtent).m_tnXStart, (*itExtent).m_tnXEnd);
		if (a_reStatus != g_kNoError)
			return;
	}

	// Finally, subtract the other region.  That punches a hole in us,
	// and creates the border region we're after.
	Subtract (a_reStatus, a_rOther);
	if (a_reStatus != g_kNoError)
		return;
}



// Add all extents surrounding the given extent.  Used by FloodFill().
template <class INDEX, class SIZE>
void
SetRegion2D<INDEX,SIZE>::UnionSurroundingExtents (Status_t &a_reStatus,
	INDEX a_tnY, INDEX a_tnXStart, INDEX a_tnXEnd)
{
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Add the extent above this one.
	Union (a_reStatus, a_tnY - 1, a_tnXStart, a_tnXEnd);
	if (a_reStatus != g_kNoError)
		return;

	// Add the extent in the middle.
	Union (a_reStatus, a_tnY, a_tnXStart - 1, a_tnXEnd + 1);
	if (a_reStatus != g_kNoError)
		return;

	// Add the extent below this one.
	Union (a_reStatus, a_tnY + 1, a_tnXStart, a_tnXEnd);
	if (a_reStatus != g_kNoError)
		return;
}



#ifndef NDEBUG
template <class INDEX, class SIZE>
uint32_t SetRegion2D<INDEX,SIZE>::sm_ulInstances;
#endif // NDEBUG



// Default constructor.  Must be followed by a call to Init().
template <class INDEX, class SIZE>
SetRegion2D<INDEX,SIZE>::FloodFillControl::FloodFillControl
		(Allocator &a_rAllocator)
	: m_oToDo (a_rAllocator),
	  m_oAlreadyDone (a_rAllocator),
	  m_oNextToDo (a_rAllocator)
{
	// Nothing to do.
}



// Initializing constructor.
template <class INDEX, class SIZE>
SetRegion2D<INDEX,SIZE>::FloodFillControl::FloodFillControl
		(Status_t &a_reStatus, Allocator &a_rAllocator)
	: m_oToDo (a_rAllocator),
	  m_oAlreadyDone (a_rAllocator),
	  m_oNextToDo (a_rAllocator)
{
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Initialize ourselves.
	Init (a_reStatus);
	if (a_reStatus != g_kNoError)
		return;
}



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

	// Initialize our helper regions.
	m_oToDo.Init (a_reStatus);
	if (a_reStatus != g_kNoError)
		return;
	m_oAlreadyDone.Init (a_reStatus);
	if (a_reStatus != g_kNoError)
		return;
	m_oNextToDo.Init (a_reStatus);
	if (a_reStatus != g_kNoError)
		return;
}



#endif // __SETREGION2D_H__