//////////////////////////////////////////////////////////////////////////////
//
// Asura_Classified_List.h
//
// Created by Anthony Gregson - 27/04/04
//
// Copyright (c) 2004 Rebellion. All rights reserved.
//
// Description:
//
//     Replacement to the old, obsolete Asura_Entity_List. Arranges entities
//     by classification, for improved cache efficiency when iterating
//     through. Poor lookup performance (use hashed lists for that).
//
//////////////////////////////////////////////////////////////////////////////

// B E G I N   F I L E   W R A P P E R ///////////////////////////////////////

#ifdef ASURA_USE_PRAGMA_ONCE
    #pragma once
#endif

#ifndef ___ASURA_CLASSIFIEDLIST_H___
#define ___ASURA_CLASSIFIEDLIST_H___ 1

// E N D   F I L E   W R A P P E R ///////////////////////////////////////////

// I N C L U D E S ///////////////////////////////////////////////////////////

#include "Core/Asura_ClassifiedList_System.h"
#include "Debugging/Asura_Logfile.h"
#include "Network/Asura_Guid.h"

//////////////////////////////////////////////////////////////////////////////
//
// Asura_Classified_Node, Asura_Classification_Node, Asura_Classified_List
//
//////////////////////////////////////////////////////////////////////////////

// TODO - Should we have a base List class, which people can just use without having to know what type they're using?

// TODO - Could unify this with the hashed node, as the structure is identical
template <class T> class Asura_Classified_Node
{
public:
    T* m_pxObject;
	Asura_Classified_Node<T>* m_pxNext;
	bool m_bDeleted;
};

template <class T> class Asura_Classification_Node
{
public:
	u_int m_uClassification; // Made int for 4-byte alignment
	Asura_Classification_Node<T>* m_pxNext;
	Asura_Classified_Node<T>* m_pxClassifiedList;
};

// Forward declaration
template <class T> class Asura_Classified_List_It;
template <class T> class Asura_Classified_List_Const_It;
template <class T> class Asura_Classified_List_Deleter_It;

template <class T> class Asura_Classified_List
{
	friend class Asura_Classified_List_It<T>;
	friend class Asura_Classified_List_Const_It<T>;
	friend class Asura_Classified_List_Deleter_It<T>;

public:
	Asura_Classified_List()
	{
		m_pxUnclassifiedList = NULL;
		m_pxClassificationList = NULL;
		m_uNumObjects = 0;
		m_uNumIterationsInProgress = 0;
	}

	~Asura_Classified_List()
	{
		Asura_Assert( (m_uNumIterationsInProgress == 0), "Destroying list with iterator still active. There's a fair chance this will cause a crash." );
	}

	bool AddToList(T* pxObject)
	{
		// Check this objects GUID isn't already in the list?
		// First call ClassifyList() to minimise differences between ASSERT and non-ASSERT builds.
		ClassifyList();

		if( FindObject(pxObject->GetGuid()) )
		{
			Asura_Assertf( false, ("Object (GUID %u) already exists in classified list", pxObject->GetGuid()) );
			return(false);
		}

		// The entity classification might not be set yet, so just add this entity to the list of entities to be classified
		Asura_Classified_Node<T>* pxNode = static_cast<Asura_Classified_Node<T>*>(Asura_ClassifiedList_System::AllocateClassifiedNode());
		
		// Add this entity to this classification list
		pxNode->m_pxNext   = m_pxUnclassifiedList;		
		pxNode->m_pxObject = pxObject;
		pxNode->m_bDeleted = false;

		m_pxUnclassifiedList = pxNode;

		m_uNumObjects++;
		return(true);
	}

	// KOR - 23/03/2006 - added bShouldAlwaysBePresent parameter.
	// This is for the Asura_Entity_Server updateable list, where it is not
	// known if an entity is already in the list, so we shouldn't assert if it isn't.
	bool RemoveFromList(const T* pxObject, bool bShouldAlwaysBePresent = true)
	{
		// Find the right classification
		const u_int uClassId = pxObject->GetClassification();
		Asura_Classification_Node<T>* pxPrevClassificationNode = NULL;
		Asura_Classification_Node<T>* pxClassificationNode = m_pxClassificationList;

		while (pxClassificationNode)
		{
			if (pxClassificationNode->m_uClassification >= uClassId)
			{
				break;
			}
			pxPrevClassificationNode = pxClassificationNode;
			pxClassificationNode	 = pxClassificationNode->m_pxNext;
		}
		if (pxClassificationNode)
		{
			// Found the classification, now find the node in the classification list
			Asura_Classified_Node<T>* pxPrevNode = NULL;
			Asura_Classified_Node<T>* pxNode	 = pxClassificationNode->m_pxClassifiedList;
			while (pxNode && (pxNode->m_pxObject != pxObject))
			{
				pxPrevNode = pxNode;
				pxNode	   = pxNode->m_pxNext;
			}
			if ( pxNode )
			{
				// if there's an iteration in progress, we can't delete nodes willy-nilly. Instead,
				// flag the node as deleted: it will be removed later when FlushDeletedNodes is called
				if( m_uNumIterationsInProgress > 0 )
				{
					pxNode->m_bDeleted = true;
				}
				else
				{
					// Remove the node
					if ( pxPrevNode )
					{
						// Patch previous nodes next pointer.
						pxPrevNode->m_pxNext = pxNode->m_pxNext;
					}
					else
					{
						// No previous node - so it's the start of the list
						if ( pxNode->m_pxNext )
						{
							pxClassificationNode->m_pxClassifiedList = pxNode->m_pxNext;
						}
						else
						{
							// Infact this classification list is empty now
							// Remove the classification from the list
							if (pxPrevClassificationNode)
							{
								// Patch previous nodes next pointer.
								pxPrevClassificationNode->m_pxNext = pxClassificationNode->m_pxNext;
							}
							else
							{
								// No previous node - so it's the start of the list
								m_pxClassificationList = pxClassificationNode->m_pxNext;
							}
							// return the classification node to the pool
							Asura_ClassifiedList_System::FreeClassificationNode(pxClassificationNode);
						}
					}
					// Return this entity node to the pool
					Asura_ClassifiedList_System::FreeClassifiedNode(pxNode);
					Asura_Assert((m_uNumObjects > 0), "Classified-list count has reached zero - something has gone wrong.");
					m_uNumObjects--;
				}

				// Done
				return(true);
			}
		}

		// Didn't find the object in the classified list... it must be in the new list, and never been classified
		// Seeing as we never iterate through the unclassified list, we don't have to worry about iterators here
		Asura_Classified_Node<T>* pxPrevNode = NULL;
		Asura_Classified_Node<T>* pxNode = m_pxUnclassifiedList;
		while (pxNode && (pxNode->m_pxObject != pxObject))
		{
			pxPrevNode = pxNode;
			pxNode = pxNode->m_pxNext;
		}
		if (pxNode)
		{
			if (pxPrevNode)
			{
				pxPrevNode->m_pxNext = pxNode->m_pxNext;
			}
			else
			{
				// First element of the new list
				m_pxUnclassifiedList = pxNode->m_pxNext;
			}
			// Return this entity node to the pool
			Asura_ClassifiedList_System::FreeClassifiedNode(pxNode);
			Asura_Assert((m_uNumObjects > 0), "Classified-list count has reached zero - something has gone wrong.");
			m_uNumObjects--;
			return(true);
		}
		else
		{
			if(bShouldAlwaysBePresent)
			{
				Asura_Assert(false, "Trying to remove object, but we don't know about it?");
			}
			return(false);
		}
	}

	void ClassifyList()
	{
		// Go though the list of unclassified objects
		Asura_Classified_Node<T>* pxNode = m_pxUnclassifiedList;
		// we build a new list of "still unclassified" objects so clear the head of the old list
		m_pxUnclassifiedList = NULL;
		// To speed up insertion to the tail of the new "still unclassified" list, store the tail as we go.
		Asura_Classified_Node<T>* pxUnclassifiedListTail = NULL;
		while (pxNode)
		{	
			// Dig out the next new object
			Asura_Classified_Node<T>* pxNextNode = pxNode->m_pxNext;
			// Find the right classification (if any)
			const u_int uClassId = pxNode->m_pxObject->GetClassification();

			// JAT 20/07/06 - only classify entities which have a valid classification
			if ( uClassId != 0 ) // AsuraEntityClass_NotSet is 0
			{
				Asura_Classification_Node<T>* pxClassificationNode = NULL;

				// Check for insertion at the start of the list
				if (!m_pxClassificationList || m_pxClassificationList->m_uClassification > uClassId )
				{
					// Empty list, or insertion at start of list
					pxClassificationNode = static_cast<Asura_Classification_Node<T>*>(Asura_ClassifiedList_System::AllocateClassificationNode());
					// Add this classification to the list
					pxClassificationNode->m_uClassification = uClassId;
					pxClassificationNode->m_pxClassifiedList = NULL;
					pxClassificationNode->m_pxNext = m_pxClassificationList;
					m_pxClassificationList = pxClassificationNode;
				}
				else
				{
					// Non empty list, find classification or insertion point
					Asura_Classification_Node<T>* pxPrevNode = NULL;
					pxClassificationNode = m_pxClassificationList;
					while (pxClassificationNode)
					{
						if ( pxClassificationNode->m_uClassification >= uClassId )
						{
							break;
						}
						pxPrevNode = pxClassificationNode;
						pxClassificationNode = pxClassificationNode->m_pxNext;
					}
	
					// If we didn't find the right classification - add it
					if ( !pxClassificationNode || pxClassificationNode->m_uClassification > uClassId )
					{
						// Allocate new classification node
						pxClassificationNode = static_cast<Asura_Classification_Node<T>*>(Asura_ClassifiedList_System::AllocateClassificationNode());
						// and Add it to this classification list
						pxClassificationNode->m_pxClassifiedList = NULL;
						if ( pxPrevNode )
						{
							pxClassificationNode->m_pxNext = pxPrevNode->m_pxNext;
							pxPrevNode->m_pxNext = pxClassificationNode;
						}
						else
						{
							// Insert at start
							pxClassificationNode->m_pxNext = m_pxClassificationList;
							m_pxClassificationList = pxClassificationNode;
						}
						pxClassificationNode->m_uClassification = uClassId;
					}
				}
				// Put this node at the head of the classified list
				Asura_Assert( pxClassificationNode->m_uClassification == uClassId, "No correct classification?" );
				pxNode->m_pxNext = pxClassificationNode->m_pxClassifiedList;
				pxClassificationNode->m_pxClassifiedList = pxNode;
			}
			else
			{
				if ( pxUnclassifiedListTail )
				{
					// link this node to the end of the "still unclassified" list
					pxUnclassifiedListTail->m_pxNext = pxNode;
				}
				else
				{
					// this is the first node we've found without valid classification
					// Therefore this node becomes the new head of the unclassified list.
					m_pxUnclassifiedList = pxNode;
				}
				// set the tail of the unclassified list to be this node.
				pxUnclassifiedListTail = pxNode;
			}
			// On to the next
			pxNode = pxNextNode;
		}
	}

	// TODO - Would it be worth adding a FindObject with guid and classification? (Would reduce search time when used)
	// Unavoidably linear. Avoid using if possible
	inline T* FindObject( Asura_Guid uGuid, bool bIgnoreDestroyed = true )
    {
        if (uGuid == ASURA_GUID_UNREGISTERED)
        {
            return NULL;
        }

		// KOR - 22/03/2006 - ensure list has been classified.
		ClassifyList();

		Asura_Classification_Node<T>* pxClassificationNode = m_pxClassificationList;

		while (pxClassificationNode)
		{
			Asura_Classified_Node<T>* pxClassifiedNode = pxClassificationNode->m_pxClassifiedList;

			while(pxClassifiedNode)
			{
				if( !pxClassifiedNode->m_bDeleted && (pxClassifiedNode->m_pxObject->GetGuid() == uGuid) )
				{
					if( !bIgnoreDestroyed || !pxClassifiedNode->m_pxObject->IsDestroyed() )
					{
						return pxClassifiedNode->m_pxObject;
					}
				}
				pxClassifiedNode = pxClassifiedNode->m_pxNext;
			}
			pxClassificationNode = pxClassificationNode->m_pxNext;
		}

		// JAT 20/07/06 - search the unclassified list as well
		// Didn't find the object in the classified list... it must be in the new list, and never been classified
		Asura_Classified_Node<T>* pxNode = m_pxUnclassifiedList;
		while ( pxNode )
		{
			if( !pxNode->m_bDeleted && ( pxNode->m_pxObject->GetGuid() == uGuid ) )
			{
				if( !bIgnoreDestroyed || !pxNode->m_pxObject->IsDestroyed() )
				{
					return pxNode->m_pxObject;
				}
			}
			pxNode = pxNode->m_pxNext;
		}

	    return NULL;
    }

	// Should we really have this? Makes this less generic (although we already use GetClassification, GetGuid and IsDestroyed)
    inline T* FindEntity(Asura_Guid uGuid)
    {
        return FindObject(uGuid);
    }

	void DestroyAllObjects()
	{
		// Call PreDestructionShutdown on everything first, to allow entities to access other entities during this phase.
		for ( Asura_Classified_List_It< T > xIt( this ); !xIt.Done(); xIt.Next() )
		{
			xIt.GetCurrent()->PreDestructionShutdown();
		}

		// Now go through and delete the necessary entities.
		for( Asura_Classified_List_Deleter_It< T > xIt( this ); !xIt.Done(); )
		{
			xIt.DeleteCurrent( false );
		}

		Asura_Assert((m_uNumObjects == 0), "Not all entries have been removed during destruction.");
	}

	void StartIteration( void )
	{
		m_uNumIterationsInProgress++;
	}
	
	void FinishIteration( void )
	{
		Asura_Assert( (m_uNumIterationsInProgress > 0), "FinishIteration called but no iterations in progress?" );
		
		m_uNumIterationsInProgress--;
		if( m_uNumIterationsInProgress == 0 )
		{
			FlushDeletedNodes();
		}
	}

	void FlushDeletedNodes( void )
	{
		// Find the right classification
		Asura_Classification_Node<T>* pxPrevClassificationNode = NULL;
		Asura_Classification_Node<T>* pxClassificationNode = m_pxClassificationList;

		while( pxClassificationNode )
		{			
			// Found the classification, now find the node in the classification list
			Asura_Classified_Node<T>* pxPrevNode = NULL;
			Asura_Classified_Node<T>* pxNode	 = pxClassificationNode->m_pxClassifiedList;
			while( pxNode )
			{
				if( pxNode->m_bDeleted )
				{
					// Remove the node
					if( pxPrevNode )
					{
						// Patch previous nodes next pointer.
						pxPrevNode->m_pxNext = pxNode->m_pxNext;
					}
					else
					{
						// No previous node - so it's the start of the list
						pxClassificationNode->m_pxClassifiedList = pxNode->m_pxNext;
					}

					// Return this entity node to the pool
					Asura_Classified_Node<T>* pxTempNode = pxNode;
					pxNode = pxNode->m_pxNext;

					Asura_ClassifiedList_System::FreeClassifiedNode(pxTempNode);
					Asura_Assert((m_uNumObjects > 0), "Reached zero classified-list entries - cannot remove any more.");
					m_uNumObjects--;
				}
				else
				{
					pxPrevNode = pxNode;
					pxNode	   = pxNode->m_pxNext;
				}
			}

			// check whether this classification node is now empty. If so, delete the classification node
			if( !pxClassificationNode->m_pxClassifiedList )
			{
				if( pxPrevClassificationNode )
				{
					// Patch previous nodes next pointer.
					pxPrevClassificationNode->m_pxNext = pxClassificationNode->m_pxNext;
				}
				else
				{
					// No previous node - so it's the start of the list
					m_pxClassificationList = pxClassificationNode->m_pxNext;
				}

				Asura_Classification_Node<T>* pxTempNode = pxClassificationNode;
				pxClassificationNode = pxTempNode->m_pxNext;

				// return the classification node to the pool
				Asura_ClassifiedList_System::FreeClassificationNode(pxTempNode);
			}
			else
			{
				pxPrevClassificationNode = pxClassificationNode;
				pxClassificationNode	 = pxClassificationNode->m_pxNext;
			}
		}
	}

	void OutputToDebugger (const char* szTitle)
	{
		Asura_Classification_Node<T>*	pxNode	= m_pxClassificationList;

		Asura_OutputToDebugger(("\n"));
		Asura_OutputToDebugger(("--------------------------------------------------------------------------------\n"));
		Asura_OutputToDebugger(("Asura_Classified_List::OutputToDebugger(): \"%s\"\n", szTitle));
		Asura_OutputToDebugger(("--------------------------------------------------------------------------------\n"));

		while(pxNode != NULL)
		{
			Asura_Classified_Node<T>*	pxClassifiedNode	= pxNode->m_pxClassifiedList;
			int							iCount				= 0;

			// Count the number of entries in this classification...
			while(pxClassifiedNode != NULL)
			{
				pxClassifiedNode = pxClassifiedNode->m_pxNext;
				iCount++;
			}

			// Output the count...
			Asura_OutputToDebugger(("Classification = %u, Count = %d\n", pxNode->m_uClassification, iCount));

			// Step onto the next node...
			pxNode	= pxNode->m_pxNext;
		}

		Asura_OutputToDebugger(("--------------------------------------------------------------------------------\n"));
		Asura_OutputToDebugger(("\n"));
	}

    const Asura_Classified_Node<T>* GetUnclassifiedList( void ) const { return m_pxUnclassifiedList; } 
	u_int GetNumEntries(void) const	{ return(m_uNumObjects); }

private:
	Asura_Classification_Node<T>* m_pxClassificationList; // Classification sorted entities
	Asura_Classified_Node<T>* m_pxUnclassifiedList; // New entities waiting to be classified on their first update

	u_int m_uNumObjects;
	u_int m_uNumIterationsInProgress;
};

//////////////////////////////////////////////////////////////////////////////
//
// Asura_Classified_List_It, Asura_Classified_List_Const_It, Asura_Classified_List_Deleter_It
//
//////////////////////////////////////////////////////////////////////////////

template <class T> class Asura_Classified_List_It
{

public:

	// Constructor for iterator, also classifies the list (if any unclassifieds still exist) and starts the iteration
	Asura_Classified_List_It<T>(Asura_Classified_List<T>* pxList)
	{
		Asura_Assert(pxList,"");
		pxList->StartIteration();
		pxList->ClassifyList();

		m_pxList = pxList;
		Restart();
	}

	~Asura_Classified_List_It<T>(void)
	{
		m_pxList->FinishIteration();
	}

	//gets the current entity in the iteration
	T* GetCurrent() const
	{
		Asura_Assert(m_pxCurrentObjectNode,"");
		return m_pxCurrentObjectNode->m_pxObject;
	}

	T* operator()( void ) const { return GetCurrent(); }

	//advance to the next entity in the list
	void Next()
	{
		while (m_pxCurrentClassificationNode)
		{
			if (m_pxCurrentObjectNode)
			{
				m_pxCurrentObjectNode = m_pxCurrentObjectNode->m_pxNext;
				if (!m_pxCurrentObjectNode)
				{
					m_pxCurrentClassificationNode = m_pxCurrentClassificationNode->m_pxNext;
					// Continue looping
				}
				else
				{
					return;
				}
			}
			else
			{
				m_pxCurrentObjectNode = m_pxCurrentClassificationNode->m_pxClassifiedList;
				return;
			}
		}
	}

	//indicates whether the iteration has finished
	bool Done() const {return m_pxCurrentObjectNode == NULL;}

	//restarts the iteration
	void Restart()
	{
		//reset values
		m_pxCurrentClassificationNode = m_pxList->m_pxClassificationList;
		m_pxCurrentObjectNode = NULL;
		//and find the first entry
		Next();
	}

protected:

	Asura_Classified_List<T>* m_pxList;
	const Asura_Classification_Node<T>* m_pxCurrentClassificationNode;
	const Asura_Classified_Node<T>* m_pxCurrentObjectNode;

private:

    // Prevent copies being made, since currently it's unsafe.
    Asura_Classified_List_It<T>( const Asura_Classified_List_It<T>& xOtherIt );
    Asura_Classified_List_It<T>& operator=( const Asura_Classified_List_It<T>& xOtherIt );

};

template <typename T> class Asura_Classified_List_Const_It : public Asura_Classified_List_It<T>
{

public:

	Asura_Classified_List_Const_It<T>(Asura_Classified_List<T>* pxList) : Asura_Classified_List_It<T>(pxList) {}

	const T* GetCurrent(void) const { return Asura_Classified_List_It<T>::GetCurrent(); }
	const T* operator()(void) const { return GetCurrent(); }

private:

    // Prevent copies being made, since currently it's unsafe.
    Asura_Classified_List_Const_It<T>( const Asura_Classified_List_Const_It<T>& xOtherIt );
    Asura_Classified_List_Const_It<T>& operator=( const Asura_Classified_List_Const_It<T>& xOtherIt );

};

template <class T> class Asura_Classified_List_Deleter_It : public Asura_Classified_List_It<T>
{

public:

	Asura_Classified_List_Deleter_It<T>(Asura_Classified_List<T>* pxList) : Asura_Classified_List_It<T>(pxList) {}

    // Permanently deletes the current entity and moves to the next in the list.
	// Note this assumes that the destructor will remove the object from the list.
	void DeleteCurrent( bool bIncludePreDestructionShutdown = true )
	{
		Asura_Assert(this->m_pxCurrentObjectNode,"");
		const Asura_Classified_Node<T>* pxToDelete = this->m_pxCurrentObjectNode;
		this->Next();
		if ( bIncludePreDestructionShutdown )
		{
			pxToDelete->m_pxObject->PreDestructionShutdown();
		}
		delete pxToDelete->m_pxObject; // This should remove it from the list too.
	}

private:

    // Prevent copies being made, since currently it's unsafe.
    Asura_Classified_List_Deleter_It<T>( const Asura_Classified_List_Deleter_It<T>& xOtherIt );
    Asura_Classified_List_Deleter_It<T>& operator=( const Asura_Classified_List_Deleter_It<T>& xOtherIt );

};

#endif // #ifndef ___ASURA_CLASSIFIEDLIST_H___
