/*****************************************************************************
 * $Id: eng_world.cc,v 1.156 2006/08/10 03:18:58 devel Exp $
 * @file
 * @author	Jim E. Brooks  http://www.jimbrooks.org
 * @brief	World, Quadrant, Locus classes.
 * @remarks If a newly-written Object doesn't appear, perhaps you should
 *          override Object::Reproducible() to return false.
 *			A Position object is 36 bytes on x86 so avoid returning by value.
 *//*
 * LEGAL:	COPYRIGHT (C) 2004 JIM E. BROOKS
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE (GPL).
 *****************************************************************************/

#define ENG_WORLD_CC 1
#include "eng.hh"
#include "eng_world.hh"
#include "gfx_random.hh"

// For World class code.
// GET_PTR() is compatible with Quadrant* or QuadrantPtr.
#if DEBUG == 2
#define ASSERT_WORLD_QUADRANT( QUADRANT ) \
{{ \
	ASSERT( (QUADRANT) != NULL ); \
    Quadrant* q_ = GET_PTR( (QUADRANT) ); \
	ASSERT( std::find( mQuadrants.begin(), mQuadrants.end(), q_ ) != mQuadrants.end() ); \
	CHECK_TYPESIG( q_, TYPESIG_QUADRANT ); \
}}
#else
#define ASSERT_WORLD_QUADRANT( QUADRANT ) \
{{ \
    CHECK_TYPESIG( (QUADRANT), TYPESIG_QUADRANT ); \
}}
#endif

////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////  World  /////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

/*****************************************************************************
 * World::Make() does the actual construction.
 *****************************************************************************/
World::World( void )
{
	// Just clear flags.
	mMade = mDimValid = false;
	mLocus = NULL;
	mObjectCnt = mObjectCntMade = 0;
}

/*****************************************************************************
 * Make the world as a set of quadrants.
 * Quadrants are divisions of the simulated world ("space partitioning").
 *
 * The world is made in phases:
 * - Derived class must define Make() then should call Make1()/Make2().
 * - World::Make1() sets the dimensions of the World.
 * - Derived class can do intermediate steps.
 * - World::Make2() builds the Quadrants and the Locus.
 *
 * @param	dimQuadrant
 *			Dimensions of the world (in quadrants).
 * @param	quadrantEdge
 *			Width of any edge of a quadrant (each edge is the same width).
 * @param	margin
 *			For when Fence() wraps a Dyna.
 * @param	dimLocus
 *			Dimensions of the Locus.  Should be smaller than dimQuadrant and
 *          each dimension should have an odd value (see Locus)
 *****************************************************************************/
void
World::Make1( const Array<3>& dimQuadrant, const fp quadrantEdge, const fp margin, const Array<3>& dimLocus )
{
	// First phase: set the world dimensions.

	mMade			= false;	// to be set by World::Make()
	mObjectCnt		= 0;
	mObjectCntMade	= 0;
	SetObjectSmallDist( WORLD(15000.0) );				// default
	SetObjectLargeDist( WORLD(quadrantEdge*0.90) );		// default

	// Set World dimensions.
	mQuadrantEdge	= quadrantEdge;
	mMargin			= margin;
	mDimQuadrant	= dimQuadrant;
	mDimWorld[XX]	= dimQuadrant[XX] * quadrantEdge;
	mDimWorld[YY]	= dimQuadrant[YY] * quadrantEdge;
	mDimWorld[ZZ]	= dimQuadrant[ZZ] * quadrantEdge;
	mDimLocus		= dimLocus;
	mCenter.x		= mDimWorld[XX] * 0.5 + quadrantEdge * 0.5;		// order-dependent!
	mCenter.y		= mDimWorld[YY] * 0.5 + quadrantEdge * 0.5;		// center of the center quadrant
	mCenter.z		= mDimWorld[ZZ] * 0.5 + quadrantEdge * 0.5;
	mDimValid		= true;
}
void
World::Make2( void )
{
ASSERT( mDimValid );

	// Second phase: make the Quadrants and the locus.

	// Make mQuadrants[].
	const uint quadrantCnt = mDimQuadrant[0] * mDimQuadrant[1] * mDimQuadrant[2];
	mQuadrants.reserve( quadrantCnt );
	Array<3> t;
	for ( t[XX] = 0; t[XX] < mDimQuadrant[XX]; ++t[XX] )
	for ( t[YY] = 0; t[YY] < mDimQuadrant[YY]; ++t[YY] )
	for ( t[ZZ] = 0; t[ZZ] < mDimQuadrant[ZZ]; ++t[ZZ] )
	{
		// Quadrants are initially empty (eQuadrantState_EMPTY).
		Quadrant* q = new Quadrant( t, mQuadrantEdge, random_ui() );
		mQuadrants.push_back( q );
	}

	// Make the Locus.
	mLocus = new Locus( mDimLocus );
}

/*****************************************************************************
 * Destroy the world.  Code smuggled out of the Death Star's central computer.
 *****************************************************************************/
void
World::Destroy( void )
{
#if DEBUG
	// Explicitly deleting these isn't strictly necessary but doing so tests
	// the destructors and helps to suppress false Valgrind warnings.
	for ( QuadrantItr itr = mQuadrants.begin(); itr != mQuadrants.end(); ++itr )
		delete *itr;
	delete mLocus;
#endif
}

/*****************************************************************************
 * Helper to invoke a callback for every object.
 *****************************************************************************/
void
World::ForEachObject( ForEachObjectCallback callback )
{
ASSERT( mMade );
	// For each quadrant.
	for ( QuadrantItr itr = mQuadrants.begin(); itr != mQuadrants.end(); ++itr )
	{
		Quadrant* q = *itr;
CHECK_TYPESIG( q, TYPESIG_QUADRANT );
		// For each object in the quadrant's object list.
		Dlist<Object>& dlist = q->GetObjectDlist();
CHECK_TYPESIG( &dlist, TYPESIG_LIB_DLIST );
		for ( const Dlink<Object>* dlink = dlist.ForStart(); dlist.ForTest(dlink); dlist.ForNext(dlink) )
		{
CHECK_TYPESIG( dlink, TYPESIG_LIB_DLINK ); CHECK_TYPESIG( dlink->mObj, TYPESIG_OBJECT );
			Object* object = dlink->mObj;
			callback( object );
		}
	}
}

/*****************************************************************************
 * Compute a cache size based on the amount of objects created.
 *****************************************************************************/
uint
World::CacheSize( void )
{
ASSERT( mMade );
	// Find the quadrant with the greatest amount of objects,
	// multiply it by the amount of quadrants in the locus,
	// and scale it up to avoid delays caused by cache evictions.
	uint size = 0;
	for ( QuadrantItr itr = mQuadrants.begin(); itr != mQuadrants.end(); ++itr )
	{
		Quadrant* q = *itr; CHECK_TYPESIG( q, TYPESIG_QUADRANT );
		size = Max( size, q->GetObjectCnt() );
	}
	size = size * mLocus->mQuadrants.size();
	size = uint( size * 1.25 );
#if DEBUG == 2
	size = 50;
#endif
	if ( gEng.GetSpeed() > eSpeed_NORMAL ) size <<= 1;
	// Cache sizes that are way too big will cause problems.
	return Min(10u*1000u,size);
}

/*****************************************************************************
 * Preload caches to avoid pauses in rendering.
 * This called for fast-mode (-fast).
 *****************************************************************************/
static void
PreloadCachesForEachObject( Object* obj )
{
//	obj->GetWorldVertexs();  // ObjectMesh now has this method, no longer Object
}
void
World::PreloadCaches( void )
{
ASSERT( mMade );
	*gEng.mStreamStatus << "preloading caches... \n";
	ForEachObject( PreloadCachesForEachObject );
}

/*****************************************************************************
 * Keep a Dyna within the world.
 * If it has gone past an edge, it is wrapped back to the opposite edge
 * (similar to Asteroids but in 3D).  A derived World class can override this behavior.
 * @return True if the Dyna's Position was corrected.
 * @remarks A derived World class can override to, eg, to force an altitude ceiling.
 * @param	dyna
 * @param	pos (IN/OUT)
 *			Position object which might be corrected.
 *          The Dyna class calls World::Fence().
 *          World::Fence() defers to the Dyna class its position.
 *****************************************************************************/
bool
World::Fence( Dyna& dyna/*unused*/, Position& pos /*IN/OUT*/ )
{
    // dyna arg is currently unused but may be used in future.

ASSERT( mDimValid );
ASSERT( mMade );

#define CODE_WORLD_FENCE_DIM( XYZ, XXYYZZ )				\
	if ( pos.XYZ < 0 )									\
	{													\
		pos.XYZ = mDimWorld[XXYYZZ] - mMargin;			\
		corrected = true;								\
	}													\
	else if ( pos.XYZ > mDimWorld[XXYYZZ] )				\
	{													\
		pos.XYZ = mMargin;								\
		corrected = true;								\
	}

	// Dyna::SetPosition() shouldn't be called, let Dyna class change its position.
	bool corrected = false;
	CODE_WORLD_FENCE_DIM( x, XX )
	CODE_WORLD_FENCE_DIM( y, YY )
	CODE_WORLD_FENCE_DIM( z, ZZ )
	return corrected;

#undef CODE_WORLD_FENCE_DIM
}

/*****************************************************************************
 * Truncate/wrap quadrant[x][y][z] to stay inside the world.
 *****************************************************************************/
Array<3>
World::WrapQuadrant( const Array<3>& tuple )
{
ASSERT( mDimValid );

	Array<3> t = tuple;

	// Truncate.
	t[XX] %= mDimQuadrant[XX];
	t[YY] %= mDimQuadrant[YY];
	t[ZZ] %= mDimQuadrant[ZZ];

	// Wrap backwards if negative.
	if ( t[XX] < 0 ) t[XX] += mDimQuadrant[XX];
	if ( t[YY] < 0 ) t[YY] += mDimQuadrant[YY];
	if ( t[ZZ] < 0 ) t[ZZ] += mDimQuadrant[ZZ];

	ASSERT( t[XX] >= 0 && t[XX] < mDimQuadrant[XX] );
	ASSERT( t[YY] >= 0 && t[YY] < mDimQuadrant[YY] );
	ASSERT( t[ZZ] >= 0 && t[ZZ] < mDimQuadrant[ZZ] );

	return t;
}

/*****************************************************************************
 * @return Flat index for mQuadrants[] equivalent to mQuadrants[x][y][z].
 * Can accept negative/invalid coords.
 *****************************************************************************/
uint
World::GetQuadrantIdx( const Array<3>& tuple )
{
ASSERT( mDimValid );
ASSERT( mQuadrants.size() );

	// From the tuple [x][y][z], compute a flat index to the Quadrant vector.
	Array<3> t = WrapQuadrant( tuple );
	uint idx =   t[XX] * mDimQuadrant[YY] * mDimQuadrant[ZZ]	 // think per square of a cube
               + t[YY] * mDimQuadrant[ZZ]						 // think per row of a cube
               + t[ZZ];
	ASSERT( idx < mQuadrants.size() );
	return idx;
}

/*****************************************************************************
 * @return Return flat index for mQuadrant[] that correlates to a position
 * in world space.
 * Can handle invalid coords in vertex.
 *****************************************************************************/
uint
World::GetQuadrantIdx( const Position& pos )
{
ASSERT( mDimValid );
ASSERT( mQuadrants.size() );

	Array<3> t;
	t[XX] = int(pos.x / mQuadrantEdge);		// all quadrant edges are equal
	t[YY] = int(pos.y / mQuadrantEdge);
	t[ZZ] = int(pos.z / mQuadrantEdge);
	uint idx = GetQuadrantIdx( t );
	ASSERT( idx < mQuadrants.size() );
	return idx;
}

/*****************************************************************************
 * @return Return tuple of quadrant (mQuadrant[x][y][z]) that correlates
 * to a position in world space.
 * Can handle invalid coords in vertex.
 *****************************************************************************/
const Array<3>&
World::GetQuadrantTuple( const Position& pos )
{
	QuadrantPtrc q = GetQuadrant( pos );
	ASSERT_WORLD_QUADRANT( q );
	return q->GetTuple();
}

/*****************************************************************************
 * @return Center quadrant.
 *****************************************************************************/
QuadrantPtrc
World::GetCenterQuadrant( void )
{
ASSERT( mDimValid );
ASSERT( mQuadrants.size() );

	Array<3> t;
	t[XX] = mDimQuadrant[XX] >> 1;
	t[YY] = mDimQuadrant[YY] >> 1;
	t[ZZ] = mDimQuadrant[ZZ] >> 1;
	Quadrant* q = mQuadrants[ GetQuadrantIdx(t) ];
	ASSERT_WORLD_QUADRANT( q );
	return q;
}

/*****************************************************************************
 * @return True if this is the center quadrant.
 *****************************************************************************/
bool
World::IfCenterQuadrant( QuadrantPtrc q )
{
	ASSERT_WORLD_QUADRANT( q );
	return q == GetCenterQuadrant();
}

/*****************************************************************************
 * @return True if this an edge quadrant.
 * Edge quadrants should be (mostly) empty to avoid objects magically
 * and annoyingly appearing when the viewpoint wraps around the world.
 *****************************************************************************/
bool
World::IfEdgeQuadrant( QuadrantPtrc q )
{
ASSERT( mDimValid );
ASSERT_WORLD_QUADRANT( q );

	// Ignore one-quadrant-wide dimensions.
	// Otherwise, in a (n,1,n) world, every quadrant is an edge.
	#define RETURN_TRUE_IF_EDGE_QUADRANT( DIM )							\
		if (    (mDimQuadrant[DIM] > 1)									\
			 && (  (q->GetTuple()[DIM] == 0)							\
	            || (q->GetTuple()[DIM] == mDimQuadrant[DIM] - 1) ) )	\
			return true;
	RETURN_TRUE_IF_EDGE_QUADRANT( XX )
	RETURN_TRUE_IF_EDGE_QUADRANT( YY )
	RETURN_TRUE_IF_EDGE_QUADRANT( ZZ )
	return false;
}

/*****************************************************************************
 * Return amount of objects in the center/current quadrant.
 *****************************************************************************/
uint
World::GetObjectCntInCenterQuadrant( void ) const
{
	return gEng.mEye.GetQuadrant()->GetObjectCnt();
}

/*****************************************************************************
 * Set distances for when a small/large object is considered too distant to be visible.
 *****************************************************************************/
void
World::SetObjectSmallDist( fp dist )
{
	mObjectSmallDist  = dist;
	mObjectSmallDist2 = SQUARE(dist);
}
void
World::SetObjectLargeDist ( fp dist )
{
	mObjectLargeDist  = dist;
	mObjectLargeDist2 = SQUARE(dist);
}

/*****************************************************************************
 * In the future, this could consult some sort of terrain map (canyons, plateaus).
 *****************************************************************************/
bool
World::IfBelowGround( const Position& pos )
{
	return pos.y < 0;
}
bool
World::IfBelowGround( const MatrixExt& m )
{
	return ABS( m[Oy] ) < 0;	// absolute in case of negative Eye origin
}

/*****************************************************************************
 * @return A distance from the world's center that it's outside the world.
 *****************************************************************************/
fp
World::DistanceOutside( void )
{
	fp edgeGreatest = MAX( MAX( mDimWorld[0], mDimWorld[1] ), mDimWorld[2] );
	return edgeGreatest;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////  Quadrant  ////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

fp Quadrant::mEdge;		// all Quadrant edges are the same size

/*****************************************************************************
 * Construct a quadrant.
 * @param	tuple
 *			Tuple for mQuadrants[x,y,z].
 * @param	edge
 *			Edge of any quadrant (world coord).  Each edge is the same width.
 * @param	seed
 *			Random seed used for populating this Quadrant.
 * @param   shadow
 *			True if this is to be a shadow quadrant.
 *****************************************************************************/
Quadrant::Quadrant( const Array<3>& tuple,
                    const fp edge,
                    const uint seed,
                    bool shadow )
:
	mObjectDlist( Dlist<Object>::KEEP ),		// Keep as the global Eye can't be deleted.
	mOmniDlist( Dlist<Omni>::KEEP ),			// List of always-rendered objects.
	mDetectorDlist( Dlist<Detector>::KEEP )		// ~Object() deletes Detectors.
{
	// Keep this self-contained to simplify program initialization.
	SET_TYPESIG( this, TYPESIG_QUADRANT );
	mState			= eQuadrantState_EMPTY;
	// Create a shadow quadrant (unless this _is_ a shadow quadrant).
	mShadow			= shadow ? NULL : new Quadrant( tuple, edge, seed, true );
	mEdge			= edge;
	mSeed			= seed;									// this seeds random objects
	mTuple[XX]		= tuple[XX];
	mTuple[YY]		= tuple[YY];
	mTuple[ZZ]		= tuple[ZZ];
	mCube.x1		=  tuple[XX]    * edge;
	mCube.x2		= (tuple[XX]+1) * edge - 1;
	mCube.y1		=  tuple[YY]    * edge;
	mCube.y2		= (tuple[YY]+1) * edge - 1;
	mCube.z1		=  tuple[ZZ]    * edge;
	mCube.z2		= (tuple[ZZ]+1) * edge - 1;
	mPosition.Set( mCube.x1,								// order-dependent!
                   mCube.y1,
                   mCube.z1 );								// origin, equals Cube::x1,y1,z1
	mCenter.Set( mPosition.x + (mCube.x2 - mCube.x1) * 0.5,
                 mPosition.y + (mCube.y2 - mCube.y1) * 0.5,
                 mPosition.z + (mCube.z2 - mCube.z1) * 0.5 );  // order-dependent!
	mObjectCnt		= 0;
   	// QuadrantObject depends on Quadrant being constructed (can't be in ctor's init list).
    // ~Quadrant() deletes QuadrantObject indirectly by deleting Object dlist.
	mQuadrantObject	= new QuadrantObject( this );			// used for visibility tests
}

/*****************************************************************************
 * Quadrant destructor.
 *****************************************************************************/
Quadrant::~Quadrant()
{
//	if ( gExiting ) return;		// unnecessary unless a Quadrant is static

CHECK_TYPESIG(this,TYPESIG_QUADRANT);
	// Delete all Objects in this Quadrant.
	// ~Dlist() (of mObjectList) is told by Keep() to not delete Objects
	// because the global Eye (which is the only global Object) can't be deleted.
	for ( const Dlink<Object>* dlink = mObjectDlist.ForStart();
          mObjectDlist.ForTest(dlink);
          mObjectDlist.ForNext(dlink) )
	{
		Object* obj = dlink->mObj;
		CHECK_TYPESIG(obj,TYPESIG_OBJECT);
		// Indeed, ~Object() will unlink itself from the same Dlist this loop
		// is iterating thru but the For*() helpers can handle it.
		if ( obj != &gEng.mEye ) delete obj;  // don't delete static Eye
	}
	DELETE_NULL( mShadow );
	//DELETE_NULL( mQuadrantObject );  // deleted by "delete obj" above
	INVALIDATE_TYPESIG( this, TYPESIG_QUADRANT );
}

/*****************************************************************************
 * Populate this Quadrant with objects.
 *****************************************************************************/
void
Quadrant::Populate( void )
{
	if ( mState != eQuadrantState_POPULATED )
	{
		gWorld.PopulateQuadrant( this );	// defer specifics to some module
		mState = eQuadrantState_POPULATED;	// afterwards
	}
}

/*****************************************************************************
 * Delete most objects in this Quadrant.
 * This conserves memory and is called when the quadrant is no longer in the locus.
 *****************************************************************************/
void
Quadrant::Shrink( void )
{
	// Already shrunk?
	if (   mState == eQuadrantState_EMPTY	// don't change state from empty to shrunk
        || mState == eQuadrantState_SHRUNK
        || gEng.GetSpeed() == eSpeed_FASTEST )
		return;

	// For each object in the quadrant's object list.
	CHECK_TYPESIG( &mObjectDlist, TYPESIG_LIB_DLIST ); 
	for ( const Dlink<Object>* dlink = mObjectDlist.ForStart();
          mObjectDlist.ForTest(dlink);
          mObjectDlist.ForNext(dlink) )
	{
CHECK_TYPESIG( dlink, TYPESIG_LIB_DLINK );
CHECK_TYPESIG( dlink->mObj, TYPESIG_OBJECT );
		Object* object = dlink->mObj;
		if ( object->Reproducible() )
		{
			// This object can be reproduced (reconstructed).
			// Indeed, ~Object() will unlink itself from the same list this
			// loop is iterating on but the For*() helpers can handle it.
			delete object;
			//mObjectDlist.Unlink( dlink );	~Object() will unlink it
		}
	}

	mState = eQuadrantState_SHRUNK;
}

/*****************************************************************************
 * @return True if a Position is inside this Quadrant.
 *****************************************************************************/
bool
Quadrant::IfInside( const Position& pos ) const
{
	return mCube.IfInside( pos );
}

/*****************************************************************************
 * @return True if an object fits inside this Quadrant.
 * Returns false if it overlaps into another Quadrant(s).
 * @remarks Cube::IfInside() measures all three dimensions.
 * False would be undesirably returned for a Posrad of a Fixed object
 * at land altitude because the radius would extend below ground (Y dim).
 *****************************************************************************/
bool
Quadrant::IfInside( const Posrad& posrad ) const
{
	if ( gWorld.GetDimQuadrant()[YY] > 1 )
	{
		return mCube.IfInside( posrad );
	}
	else
	{
		// For a (n,1,n) World, ignore the Y dimension to allow
		// placement of Objects which otherwise extended below ground.
		return    posrad.x - posrad.mRadius >= mCube.x1
		       && posrad.x + posrad.mRadius <= mCube.x2
		     //&& posrad.y - posrad.mRadius >= y1				// ignore Y
	         //&& posrad.y + posrad.mRadius <= y2
		       && posrad.z - posrad.mRadius >= mCube.z1
	           && posrad.z + posrad.mRadius <= mCube.z2;
	}
}

/*****************************************************************************
 * Quadrant::DynaMoved() must be called after a Dyna object is moved
 * in case it has moved from one Quadrant into another.
 * Movement can occur by translation, changing position, or changing matrix.
 *****************************************************************************/
void
Quadrant::DynaMoved( Dyna& dyna )
{
	DynaMoved( dyna, dyna.GetPosition() );
}
void
Quadrant::DynaMoved( Dyna& dyna, const Position& pos )
{
ASSERT( gWorld.IfMade() );
CHECK_TYPESIG( &dyna, TYPESIG_OBJECT );

	// Is Dyna outside this quadrant?
	if ( ! mCube.IfInside( pos ) )
	{
		// Give this object to the quadrant the object has entered.
		QuadrantPtrc taker = gWorld.GetQuadrant( pos );
		taker->Take( dyna, this );
	}
}

/*****************************************************************************
 * Take an object from another Quadrant.
 * A consequence of moving a Dyna object across quadrants.
 *****************************************************************************/
void
Quadrant::Take( Object& object, QuadrantPtrc giver )
{
ASSERT( gWorld.IfMade() );
CHECK_TYPESIG( &object, TYPESIG_OBJECT );
CHECK_TYPESIG( giver, TYPESIG_QUADRANT );

	// Unlink object out of giver's quadrant.
	giver->RemoveObject( object.GetLink() );

	// Link object into this quadrant.
	object.SetLink( AddObject( &object ) );

	// Migrate this object's Detector object (if it has one).
	object.MoveDetector( giver, this );

	// Update object's quadrant pointer.
	object.SetQuadrant( this );
}
// Although this is an ObjectMesh method, it's part of the implementation of Quadrant::Take().
void
ObjectMesh::MoveDetector( QuadrantPtrc giver, QuadrantPtrc taker )
{
	if ( mLinkDetector != NULL )
	{
		Detector* detector = mLinkDetector->mObj;
		giver->RemoveDetector( mLinkDetector );
		mLinkDetector = taker->AddDetector( detector );
	}
}

/*****************************************************************************
 * Add/remove object to this Quadrant.
 *****************************************************************************/
Dlink<Object>*
Quadrant::AddObject( Object* obj )
{
	++mObjectCnt;
	return mObjectDlist.Append( obj );
}
void
Quadrant::RemoveObject( Dlink<Object>* dlink )
{
	--mObjectCnt;
	mObjectDlist.Unlink( dlink );
}

/*****************************************************************************
 * Add/remove Omni object to this Quadrant.
 *****************************************************************************/
Dlink<Omni>*
Quadrant::AddOmni( Omni* omni )
{
	++mObjectCnt;					// an Omni is an Object
	return mOmniDlist.Append( omni );
}
void
Quadrant::RemoveOmni( Dlink<Omni>* dlink )
{
	--mObjectCnt;					// an Omni is an Object
	mOmniDlist.Unlink( dlink );
}

/*****************************************************************************
 * Add/remove a Detector to this Quadrant.
 *****************************************************************************/
Dlink<Detector>*
Quadrant::AddDetector( Detector* detector )
{
	return mDetectorDlist.Append( detector );
}
// Does not free the unlinked object (caller should free it).
void
Quadrant::RemoveDetector( Dlink<Detector>* dlink )
{
	mDetectorDlist.Unlink( dlink );
}

/*****************************************************************************
 * @return True if Quadrant is visible (approximation).
 * This is used for speed to skip rendering most Objects in rear-facing Quadrants.
 * @remarks In a 3x1x3 Locus, up to 8 Quadrants can normally be visible.
 * Eg, when the Eye is nearly at one of the corners of the center Quadrant,
 * all Quadrants except the one at the corner are facing.
 *****************************************************************************/
bool
Quadrant::IfVisible( void ) const
{
	return mQuadrantObject->Visible();
}

/*****************************************************************************
 * Return a random position in this Quadrant.
 *****************************************************************************/
void
Quadrant::RandomPosition( Position& pos ) const
{
	pos.x = mCube.x1 + random_f( mEdge );
	pos.y = mCube.y1 + random_f( mEdge );
	pos.z = mCube.z1 + random_f( mEdge );
}

/*****************************************************************************
 * Return amount of objects in this quadrant.
 *****************************************************************************/
uint
Quadrant::GetObjectCnt( void ) const
{
	// If this quadrant has a shadow, include the shadow's count.
	// Shadow quadrants are used by ObjectGroup.
	if ( mShadow != NULL )
		return mObjectCnt + mShadow->mObjectCnt;
	else
		return mObjectCnt;	// either quadrant has no shadow or is a shadow
}

/*****************************************************************************
 * Output Quadrant to stream.
 *****************************************************************************/
ostream&
operator<<( ostream& strm, const Quadrant& o )
{
	strm << "quadrant["
         << o.GetTuple()[XX] << ','
         << o.GetTuple()[YY] << ','
         << o.GetTuple()[ZZ] << ']' << ' ';
	switch ( o.GetState() )
	{
		case eQuadrantState_EMPTY:
		strm << "EMPTY ";
		break;

		case eQuadrantState_SHRUNK:
		strm << "SHRUNK ";
		break;

		case eQuadrantState_POPULATED:
		strm << "POPULATED ";
		break;

		default:
		strm << "INVALID "; ASSERT(0);
		break;
	}
    strm << endl << "  "
         << "seed=" << o.mSeed << ' '
         << "pos=" << o.GetPosition() << ' '
         << endl << "  "
         << "cube= " << o.GetCube() << ' ' << endl;
	return strm;
}

////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////  Locus  /////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

/*****************************************************************************
 * An overhead view a 3x3x1 locus of quadrants.
 * @verbatim
 *	 +------+------+------+
 *	 |      |      |      |
 *	 |      |      |      |
 *	 +------+------+------+
 *	 |      |  .   |      |
 *	 |      | eye  |      |
 *	 +------+------+------+
 *	 |      |      |      |
 *	 |      |      |      |
 *	 +------+------+------+
 * @endverbatim
 *****************************************************************************/

/*****************************************************************************
 * Locus constructor.
 * @param	dim
 *			Dimensions must have odd values (see comments at Locus class).
 *****************************************************************************/
Locus::Locus( const Array<3>& dim )
{
	mDim = dim;
	mDim[XX] |= 1;		// ensure odd values
	mDim[YY] |= 1;
	mDim[ZZ] |= 1;
	mDimHalf[XX] = mDim[XX] >> 1;
	mDimHalf[YY] = mDim[YY] >> 1;
	mDimHalf[ZZ] = mDim[ZZ] >> 1;
	mCenterTuple = mDimHalf;		// equivalent
}
Locus::~Locus()
{
    // nothing
}

/*****************************************************************************
 * Update the locus of quadrants to the position of the viewpoint.
 * To conserve memory, quadrants are shrunk where the locus has moved away from.
 * A quadrant is shrunk by deleting objects that can be easily reconstructed.
 * When the locus is moved over shrunk quadrants, Quadrant::Populate()
 * is called to reconstruct the delete objects.
 *****************************************************************************/
// Move Locus to where the Eye is.
void
Locus::Update( void )
{
ASSERT( gEng.mEye.mInitialized );

	// Bypass if Eye is still in the same Quadrant.
	static QuadrantPtr prevQuadrant;
	if ( prevQuadrant != gEng.mEye.GetQuadrant() )
	{
		prevQuadrant = gEng.mEye.GetQuadrant();
		Update( gEng.mEye.GetPosition() );
#if DEBUG
		// Eye's quadrant should be included in the Locus and at its center quadrant.
		ASSERT( std::find( mQuadrants.begin(), mQuadrants.end(), GET_PTR(gEng.mEye.GetQuadrant()) ) != mQuadrants.end() );
		ASSERT( gEng.mEye.GetQuadrant() == GetCenterQuadrant() );
#endif
	}
}
void
Locus::Update( const Position& pos )
{
ASSERT( gWorld.mQuadrants.size() );

	static vector<Quadrant*> prevQuadrants;		// quadrants of previous locus
	static Array<3>          prevCenter(-1);	// tuple of center quadrant

	// The new locus shall surround the given position
	// (the given position is the center of the new locus).
	Array<3> center = gWorld.GetQuadrantTuple( pos );	// tuple of center quadrant

	// Unless viewpoint is still in the same quadrant.
	if ( center != prevCenter )
	{
		prevQuadrants = mQuadrants;		// current locus becomes the previous
		prevCenter    = center;

		// Move the locus over another set of quadrants.
		// Refill mQuadrants[].
		// As the locus moves away from quadrants, they will be shrunk.
		// Conversely, as the locus moves over quadrants, shrunk ones wiil be repopulated.
		mQuadrants.clear();
		Array<3> t;
		for ( t[XX] = center[XX]-mDimHalf[XX]; t[XX] <= center[XX]+mDimHalf[XX]; ++t[XX] )
		for ( t[YY] = center[YY]-mDimHalf[YY]; t[YY] <= center[YY]+mDimHalf[YY]; ++t[YY] )
		for ( t[ZZ] = center[ZZ]-mDimHalf[ZZ]; t[ZZ] <= center[ZZ]+mDimHalf[ZZ]; ++t[ZZ] )
		{
			Quadrant* q = GET_PTR( gWorld.GetQuadrant(t) );
			DEBUG2_CODE( if ( q ) { CHECK_TYPESIG( q, TYPESIG_QUADRANT ); } )
			mQuadrants.push_back( q );
			if ( q->GetState() != eQuadrantState_POPULATED ) q->Populate();
		}

		// To conserve memory, shrink any quadrant in the previous locus
		// but not in the current.
		for ( QuadrantItr itr = prevQuadrants.begin(); itr != prevQuadrants.end(); ++itr )
		{
			// Only shrink populated quadrants (not empty ones).
			Quadrant* qPrev = *itr;		// quadrant in previous locus
			DEBUG2_CODE( if ( qPrev ) { CHECK_TYPESIG( qPrev, TYPESIG_QUADRANT ); } )
			if ( std::find( mQuadrants.begin(), mQuadrants.end(), qPrev ) == mQuadrants.end() )
				if ( qPrev->GetState() == eQuadrantState_POPULATED ) qPrev->Shrink();
		}
	}
}

/*****************************************************************************
 * Return center Quadrant in the Locus.
 *****************************************************************************/
QuadrantPtrc
Locus::GetCenterQuadrant( void ) const
{
	uint idxCenter = GetQuadrantIdx( mCenterTuple );
	ASSERT( idxCenter < mQuadrants.size() );
	return mQuadrants[idxCenter];
}

/*****************************************************************************
 * @return Flat index for mQuadrants[] equivalent to mQuadrants[x][y][z].
 * Unlike World's counterpart, does NOT accept an invalid tuple.
 *****************************************************************************/
uint
Locus::GetQuadrantIdx( const Array<3>& tuple ) const
{
	// From the tuple [x][y][z], compute a flat index to the Quadrant vector.
	uint idx =   tuple[XX] * mDim[YY] * mDim[ZZ]	 // think per square of a cube
               + tuple[YY] * mDim[ZZ]				 // think per row of a cube
               + tuple[ZZ];
	ASSERT( idx < mQuadrants.size() );
	return idx;
}

/*****************************************************************************
 * @return Amount of Objects in locus.
 *****************************************************************************/
uint
Locus::GetObjectCnt( void ) const
{
	uint cnt = 0;
	for ( ConstQuadrantItr itr = mQuadrants.begin();
          itr != mQuadrants.end();
          ++itr )
	{
		cnt += (*itr)->GetObjectCnt();
	}
	return cnt;
}

/*****************************************************************************
 * Output Locus to stream.
 *****************************************************************************/
ostream&
operator<<( ostream& strm, const Locus& o )
{
	strm << "Locus["
         << o.mDim[XX] << ','
         << o.mDim[YY] << ','
         << o.mDim[ZZ] << ']' << endl;
	for ( ConstQuadrantItr itr = o.mQuadrants.begin();
          itr != o.mQuadrants.end();
          ++itr )
	{
		strm << **itr;	// print quadrants
	}
	return strm;
}

////////////////////////////////////////////////////////////////////////////////
//////////////////////////  QuadrantObject class  //////////////////////////////
////////////////////////////////////////////////////////////////////////////////

/*****************************************************************************
 * The purpose of this object is to test the visibility of an entire Quadrant.
 * For speed, if not visible, rendering bypasses all of its Objects.
 *****************************************************************************/
QuadrantObject::QuadrantObject( QuadrantPtrc q )
: Parent(q)
{
	SetPosition( q->GetCenter() );
	SetRadius( gWorld.GetQuadrantEdge() * 0.707 ); // sqrt(0.5 + 0.5)

	// The corners of the quadrants.
	fp y  = q->GetCube().y1;
	fp yi = (q->GetCube().y2 - q->GetCube().y1) / GetPolygonCnt();

	for ( uint i = 0; i < GetVertexCnt(); i += 4 )
	{
		mWorldVertexs[i+0].x = q->GetCube().x1;
		mWorldVertexs[i+0].y = y;
		mWorldVertexs[i+0].z = q->GetCube().z1;

		mWorldVertexs[i+1].x = q->GetCube().x2;
		mWorldVertexs[i+1].y = y;
		mWorldVertexs[i+1].z = q->GetCube().z1;

		mWorldVertexs[i+2].x = q->GetCube().x1;
		mWorldVertexs[i+2].y = y;
		mWorldVertexs[i+2].z = q->GetCube().z2;

		mWorldVertexs[i+3].x = q->GetCube().x2;
		mWorldVertexs[i+3].y = y;
		mWorldVertexs[i+3].z = q->GetCube().z2;

		y += yi;
	}

	FinalConstruction();
}
QuadrantObject::~QuadrantObject()
{
	// ~Object() does it.
}

/*****************************************************************************
 * The regular Object::Visible() isn't appropriate for extremely large objects
 * such as QuadrantObject.
 *****************************************************************************/
int
QuadrantObject::Visible( void )
{
	// Returns true unless all Z coords are behind viewpoint.
	return VisibleSimple();
}
