setregion2d.hh

Motion JPEG编解码器源代码

	// Easy enough.
	m_setExtents.Clear();
	m_tnPoints = 0;
}



// Add the given horizontal extent to the region.
template <class INDEX, class SIZE>
void
SetRegion2D<INDEX,SIZE>::Union (Status_t &a_reStatus, INDEX a_tnY,
	INDEX a_tnXStart, INDEX a_tnXEnd)
{
	Extent oKey;
		// An extent being searched for.
	Extent oInserted;
		// The extent being added, modified to account for the extents
		// already present in the region.
	typename Extents::Iterator itStart, itEnd;
		// The range of existing extents that gets removed because of
		// the addition of the new extent.
	typename Extents::Iterator itHere;
		// An extent being examined and/or modified.
	
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Make sure they gave us a non-empty extent.
	assert (a_tnXStart < a_tnXEnd);

#ifdef DEBUG_SETREGION2D

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

#endif // DEBUG_SETREGION2D

	// The extent we'll be inserting starts as the extent they asked
	// to add.  That may get modified based on the nature of the extents
	// already present in the region.
	oInserted.m_tnY = a_tnY;
	oInserted.m_tnXStart = a_tnXStart;
	oInserted.m_tnXEnd = a_tnXEnd;

	// Find the first extent that may get removed because of this new
	// extent.
	// (That's the one before the first existing extent
	// that's > (y, x-start).)
	oKey.m_tnY = a_tnY;
	oKey.m_tnXStart = a_tnXStart;
	itStart = m_setExtents.UpperBound (oKey);
	--itStart;

	// Does the found extent intersect the new extent?
	if (itStart != m_setExtents.End()
	&& (*itStart).m_tnY == a_tnY
	&& (*itStart).m_tnXEnd >= a_tnXStart)
	{
		// The found extent intersects with the new extent.

		// If the found extent contains the new extent, exit now;
		// the region already contains the new extent, and no
		// modifications are necessary.
		if ((*itStart).m_tnXEnd >= a_tnXEnd)
			return;

		// The found extent will be removed, and the inserted extent
		// will start in the same location (which we know is less than
		// or equal to the inserted extent's current start, thanks to
		// the search we did earlier).
		oInserted.m_tnXStart = (*itStart).m_tnXStart;

		// If the next extent in the region doesn't intersect the one
		// being added, we can modify this extent & be done, without
		// having to do a 2nd upper-bound search.
		itEnd = itStart;
		++itEnd;
		if (itEnd == m_setExtents.End()
			|| (*itEnd).m_tnY != (*itStart).m_tnY
			|| (*itEnd).m_tnXStart > a_tnXEnd)
		{
			// We can modify this one extent & be done.  Keep the
			// largest end.
			if (oInserted.m_tnXEnd < (*itStart).m_tnXEnd)
				oInserted.m_tnXEnd = (*itStart).m_tnXEnd;

			// Adjust the number of points we contain.
			m_tnPoints += (oInserted.m_tnXEnd - oInserted.m_tnXStart)
				- ((*itStart).m_tnXEnd - (*itStart).m_tnXStart);

			// Modify the extent.
			*itStart = oInserted;

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

			// We're done.
			return;
		}
	}
	else
	{
		// The found extent doesn't intersect with the new extent.
		// Therefore, it won't get modified or removed by the addition
		// of the new extent.  Move past it.
		++itStart;
	}

	// Find the last extent that may get removed because of this new
	// extent.  Start by searching for the first existing extent
	// that's > (y, x-end), then move back one.)
	oKey.m_tnY = a_tnY;
	oKey.m_tnXStart = a_tnXEnd;
	itEnd = m_setExtents.UpperBound (oKey);
	--itEnd;

	// Does the found extent intersect the new extent?
	if (itEnd != m_setExtents.End()
	&& (*itEnd).m_tnY == a_tnY
	&& (*itEnd).m_tnXStart <= a_tnXEnd)
	{
		// Yes.  That extent will get replaced, and its endpoint may be
		// used by the inserted extent.
		if (oInserted.m_tnXEnd < (*itEnd).m_tnXEnd)
			oInserted.m_tnXEnd = (*itEnd).m_tnXEnd;
	}

	// In either case, move ahead again, to get back to the end of the
	// range we'll be removing.
	++itEnd;

	// We now have the actual extent to be inserted, and the range of
	// existing extents to be removed.

	// Run through the extents to be removed, count the number of points
	// they represent, and subtract that from our separately-maintained
	// total number of points in the region.
	for (itHere = itStart; itHere != itEnd; ++itHere)
		m_tnPoints -= (*itHere).m_tnXEnd - (*itHere).m_tnXStart;

	// If the range to be replaced has at least one existing item, then
	// move the start of the range forward by one, and overwrite the
	// old start with the extent to be inserted, i.e. avoid a memory
	// allocation if at all possible.
	if (itStart != itEnd)
	{
		// Keep track of the location of the extent to be overwritten.
		itHere = itStart;

		// Move past the extent that'll be overwritten.
		++itStart;

		// Remove all extents that were found to conflict with the one
		// being inserted.
		m_setExtents.Erase (itStart, itEnd);

		// Store the new extent.
		*itHere = oInserted;
	}

	// Otherwise, no extents are being removed, and we just insert the
	// new extent.
	else
	{
#ifndef NDEBUG
		typename Extents::InsertResult oInsertResult =
#endif // NDEBUG
			m_setExtents.Insert (a_reStatus, oInserted);
		if (a_reStatus != g_kNoError)
			return;
		assert (oInsertResult.m_bInserted);
	}

	// The region now contains this many more points.
	m_tnPoints += oInserted.m_tnXEnd - oInserted.m_tnXStart;

#ifdef DEBUG_SETREGION2D

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

#endif // DEBUG_SETREGION2D
}



// Merge this extent into the current region.
// The new extent can't intersect the region in any way.
template <class INDEX, class SIZE>
void
SetRegion2D<INDEX,SIZE>::Merge (Status_t &a_reStatus, INDEX a_tnY,
	INDEX a_tnXStart, INDEX a_tnXEnd)
{
	Extent oExtent;
		// The new extent being added.

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

	// Generate the new extent.
	oExtent.m_tnY = a_tnY;
	oExtent.m_tnXStart = a_tnXStart;
	oExtent.m_tnXEnd = a_tnXEnd;

	// We will contain this many more points.
	m_tnPoints += a_tnXEnd - a_tnXStart;

	// Add this extent to the current region.
#ifndef NDEBUG
	typename Extents::InsertResult oInsertResult =
#endif // NDEBUG
		m_setExtents.Insert (a_reStatus, oExtent);
	if (a_reStatus != g_kNoError)
		return;
	assert (oInsertResult.m_bInserted);
	
#ifndef NDEBUG
	// Make sure the new extent is not contiguous with the extent
	// in front of & behind it.
	{
		typename Extents::Iterator itNew, itOther;

		// Get the location of the newly moved extent.
		itNew = oInsertResult.m_itPosition;

		// Make sure it's not contiguous with the extent before it.
		itOther = itNew;
		--itOther;
		assert (itOther == m_setExtents.End()
			|| (*itOther).m_tnY != (*itNew).m_tnY
			|| (*itOther).m_tnXEnd < (*itNew).m_tnXStart);

		// Make sure it's not contiguous with the extent after it.
		itOther = itNew;
		++itOther;
		assert (itOther == m_setExtents.End()
			|| (*itNew).m_tnY != (*itOther).m_tnY
			|| (*itNew).m_tnXEnd < (*itOther).m_tnXStart);
	}
#endif // NDEBUG
}



// Merge the other region into ourselves, emptying the other region.
template <class INDEX, class SIZE>
void
SetRegion2D<INDEX,SIZE>::Merge (SetRegion2D<INDEX,SIZE> &a_rOther)
{
	// Make sure we can move extents between regions.
	assert (CanMove (a_rOther));

	// If the current region is empty, just move all the other region's
	// extents over at once.
	if (m_tnPoints == 0)
	{
		Move (a_rOther);
	}
	else
	{
		typename Extents::Iterator itHere, itNext;
			// Where we are in the other region's extents.
	
		// Run through the extents in the other region, move them to the
		// current region, and make sure the new extent isn't contiguous
		// with any of our existing extents.
		for (itHere = a_rOther.m_setExtents.Begin();
			 itHere != a_rOther.m_setExtents.End();
			 itHere = itNext)
		{
			// Get the location of the next extent.  (We have to do this
			// because, after we call Move(), itHere isn't valid any
			// more.)
			itNext = itHere;
			++itNext;
	
			// We will contain this many more points.
			m_tnPoints += (*itHere).m_tnXEnd - (*itHere).m_tnXStart;
	
			// Move this extent to the current region.
#ifndef NDEBUG
			typename Extents::InsertResult oInsertResult =
#endif // NDEBUG
				m_setExtents.Move (a_rOther.m_setExtents, itHere);
			assert (oInsertResult.m_bInserted);
			
#ifndef NDEBUG
			// Make sure the new extent is not contiguous with the
			// extent in front of & behind it.
			{
				typename Extents::Iterator itNew, itOther;
	
				// Get the location of the newly moved extent.
				itNew = oInsertResult.m_itPosition;
	
				// Make sure it's not contiguous with the extent before
				// it.
				itOther = itNew;
				--itOther;
				assert (itOther == m_setExtents.End()
					|| (*itOther).m_tnY != (*itNew).m_tnY
					|| (*itOther).m_tnXEnd < (*itNew).m_tnXStart);
	
				// Make sure it's not contiguous with the extent after
				// it.
				itOther = itNew;
				++itOther;
				assert (itOther == m_setExtents.End()
					|| (*itNew).m_tnY != (*itOther).m_tnY
					|| (*itNew).m_tnXEnd < (*itOther).m_tnXStart);
			}
#endif // NDEBUG
		}
	}

	// Now the other region is empty.
	a_rOther.m_tnPoints = 0;
}



// Move the contents of the other region into the current region.
// The current region must be empty.
template <class INDEX, class SIZE>
void
SetRegion2D<INDEX,SIZE>::Move (SetRegion2D<INDEX,SIZE> &a_rOther)
{
	// Make sure we're allowed to do this.
	assert (CanMove (a_rOther));

	// Make sure the current region is empty.
	assert (m_tnPoints == 0);

	// Move the extents.
	m_setExtents.Move (a_rOther.m_setExtents);

	// Now we have all their points.
	m_tnPoints = a_rOther.m_tnPoints;
	a_rOther.m_tnPoints = 0;
}



// Returns true if the other region's contents can be moved
// into the current region.
template <class INDEX, class SIZE>
bool
SetRegion2D<INDEX,SIZE>::CanMove
	(const SetRegion2D<INDEX,SIZE> &a_rOther) const
{
	// Return whether our extents can be moved.
	return m_setExtents.CanMove (a_rOther.m_setExtents);
}



// Make the current region represent the intersection between
// itself and the other given region.
template <class INDEX, class SIZE>
void
SetRegion2D<INDEX,SIZE>::Intersection (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);

	// Not implemented yet.
	assert (false);
	a_reStatus = g_kInternalError;
}



// 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,
	const SetRegion2D<INDEX,SIZE> &a_rOther,
	typename Extents::ConstIterator &a_ritHere)
{
	Extent oKey;
		// Used to search through the existing extents.
	typename Extents::Iterator itStart, itEnd;
		// The range of existing extents that gets removed because of
		// the subtraction of the new extent.

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

	// Make sure they gave us a non-empty extent.
	assert (a_tnXStart < a_tnXEnd);

#ifdef DEBUG_SETREGION2D

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

#endif // DEBUG_SETREGION2D

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

	// Figure out if no existing extents intersect with the beginning
	// of the extent we're trying to subtract.
	if (itStart == m_setExtents.End()
	|| (*itStart).m_tnY != a_tnY
	|| (*itStart).m_tnXStart > a_tnXStart)
	{
		// The found extent is past any extent that the beginning would
		// intersect with.  Move back one.
		--itStart;

		// See if this extent intersects the beginning of the range
		// we're trying to subtract.
		if (itStart == m_setExtents.End()
		|| (*itStart).m_tnY != a_tnY
		|| (*itStart).m_tnXEnd <= a_tnXStart)
		{
			// Move forward again.  If that extent is on a different
			// line, or it starts after the removed range ends, then
			// leave: there's nothing to subtract.
			++itStart;
			if (itStart == m_setExtents.End()
			|| (*itStart).m_tnY != a_tnY
			|| (*itStart).m_tnXStart >= a_tnXEnd)
			{
				// There's nothing to subtract.  Find the first extent
				// in a_rOther that may intersect with one of our
				// extents.
				if (a_ritHere != a_rOther.m_setExtents.End()
					&& itStart != m_setExtents.End())
				{
					a_ritHere = a_rOther.m_setExtents.UpperBound
						(*itStart);
					--a_ritHere;
				}
				return;
			}
		}
	}

	// We found the first extent that may intersect with the range we're
	// trying to subtract.

	// Sanity check: make sure the found extent is on the same line as
	// the range we're trying to subtract.
	assert (itStart != m_setExtents.End() && (*itStart).m_tnY == a_tnY);

	// We have 4 cases: that extent has its beginning chopped off,
	// its end chopped off, gets removed completely, or gets broken in
	// half.
	if ((*itStart).m_tnXStart >= a_tnXStart)
	{
		if ((*itStart).m_tnXEnd > a_tnXEnd)
		{
			// The found extent gets its beginning cut off, and then
			// we're done.
			m_tnPoints -= a_tnXEnd - (*itStart).m_tnXStart;
			(*itStart).m_tnXStart = a_tnXEnd;
			return;
		}
		else
		{
			// The found extent gets removed completely.
			// Fall through to deal with the end of the range being
			// subtracted.
		}
	}
	else
	{
		if ((*itStart).m_tnXEnd > a_tnXEnd)
		{
			// The found extent gets broken in half.

			Extent oInserted;
				// The second half of the broken extent.

			// Prepare to break the extent in half, by generating the
			// second half of the extent.
			oInserted.m_tnY = a_tnY;
			oInserted.m_tnXStart = a_tnXEnd;
			oInserted.m_tnXEnd = (*itStart).m_tnXEnd;

			// Insert the second half of the broken extent.  Note that
			// if this succeeds, this creates an inconsistent region
			// temporarily, but it'll be fixed by the next statement.
			{
#ifndef NDEBUG
				typename Extents::InsertResult oInsertResult =
#endif // NDEBUG
					m_setExtents.Insert (a_reStatus, oInserted);
				if (a_reStatus != g_kNoError)
					return;
				assert (oInsertResult.m_bInserted);
			}

			// Now modify the found extent so that it becomes the first
			// half of the broken extent.  The region is consistent
			// again.
			(*itStart).m_tnXEnd = a_tnXStart;

			// We removed this many points.
			m_tnPoints -= a_tnXEnd - a_tnXStart;

			// We're done.