/*****************************************************************************
 * $Id: gfx_list.hh,v 1.64 2006/11/25 23:16:10 devel Exp $
 * @file
 * @author	Jim E. Brooks  http://www.jimbrooks.org
 * @brief	C++ template for a circular double-link list.
 * @remarks	"list" and "link" are reserved by C++ and UNIX resp.
 *          Why was this written instead of using STL's std::list?
 *          Because this can be compiled to do type signatue checking.
 * @verbatim
 *
 * List template class based on circular double-links with a sentinel.
 *
 * A feature of this list is that Unlink() can be safely called (but only once!)
 * inside of an iteration using the For*() methods.
 *
 * Traversing the list directly using the Dlink structure is discouraged.
 * Rather, for reliability, and in case of the list implementation is changed,
 * use the Dlist methods such as For*() and Next().
 *
 * When a list is deleted, all objects in the list are deleted by default.
 * But a constructor arg can specify to leave the linked objects allocated
 * after the list is destroyed.
 *
 * Linked objects must be allocated by the C++ new operator since
 * the list destructor uses the C++ delete operator to free linked objects
 * (in addition to the list itself).
 *
 * A sentinel is omnipresent, never unlinked, and excluded by For*().
 * A list is empty when its last remaining link is the sentinel.
 * The head pointer always points to the sentinel (head pointer is never reassigned)
 * but the tail pointer will change.
 * The first actual link follows the sentinel and is pointed to by head->next.
 *
 * For speed, a count of links isn't maintained (expected to be unused usually).
 * If a count is needed, the user of the list can track inserted/removed items.
 *
 * Usage:
 * ------
 *
 * Although Dlist is based on storing pointers to objects, a Dlist variable
 * is declared with only the user-type inside <> (don't be confused by this).
 * The Dlist itself should be declared as a pointer, eg:
 *
 *  Dlist<Class>*  mList;     // right
 *  Dlist<Class>*  mList = new Dlist<MyClass>; // right
 *  Dlist<Class*>* mList;     // wrong (would store pointer-to-pointers to MyClass)
 *  Dlist<Class>   mList;     // wrong (won't compile because of there's no default constructor)
 *
 * @endverbatim
 *//*
 * LEGAL:	COPYRIGHT (C) 2004 JIM E. BROOKS
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE (GPL).
 *****************************************************************************/

#ifndef GFX_LIST_HH
#define GFX_LIST_HH 1

namespace gfx {

template<typename T> class Dlist;

////////////////////////////////////////////////////////////////////////////////
/// @brief Class for a link in a Dlist.
/// @remarks Clients aren't allowed to delete Dlinks (caught as compile-time error).
/// Clients MUST NOT directly delete linked object: call Dlist::Unlink() to remove object.
template<typename T>
class Dlink
{
    PREVENT_COPYING(Dlink<T>)
private:
    // ctor/dtor are private: only Dlist allowed to construct/delete Dlinks.
    Dlink( void ) { SET_TYPESIG( this, TYPESIG_LIB_DLINK ); }
    ~Dlink()      { INVALIDATE_TYPESIG( this, TYPESIG_LIB_DLINK ); }
	Dlink<T>*	mPrev PACKMEMB;     // next link
	Dlink<T>*	mNext PACKMEMB;     // previous link
public:
	T*			mObj  PACKMEMB;     // pointer to actual object
	DECL_TYPESIG( TYPESIG_LIB_DLINK )
	friend class Dlist<T>;
};

////////////////////////////////////////////////////////////////////////////////
/// @brief Dlist template class.
/// @verbatim
///
/// Dlist()     Pass DESTROY/KEEP and/or SCALAR/ARRAY to control whether and how
///             linked objects are deleted when the list itself is deleted.
/// IfEmpty()	True if list is empty.
/// IfLinked()	True if object is in list.
/// Clear()     Remove all links (deletes objects depending on KEEP/DESTROY).
/// Prepend()	Prepend new link before the head of the list (new link becomes the first one).
/// Append()	Append  new link after  the tail of the list (new link becomes the last  one).
/// Unlink()	Remove link.  Never deletes the unlinked object (regardless of DESTROY).
/// First()		Return pointer to the first link or NULL if none (iterator helpers instead is recommended).
/// Last()		Return pointer to the last  link or NULL if none (iterator helpers instead is recommended).
/// Next()		Return pointer to following link or NULL if none (iterator helpers instead is recommended).
/// ForStart(), ForTest(), ForNext():
///             Iterator helpers to write a "for" loop to iterate thru the list.
///			    Can cope with loops that unlink the current link (const_cast on Dlink required to restrict doing it).
///             ForStart() returns a link pointer, ForTest() tests it, and ForNext() points it to the next link.
///	            for ( const Dlink<Class>* dlink = dlist.ForStart();
///                   dlist.ForTest(dlink);
///                   dlist.ForNext(dlink) )
///
/// @endverbatim
///
template<typename T>
class Dlist
{
    PREVENT_COPYING(Dlist<T>)

	// Sentinel never has an object, but use a different address than NULL
	// to distinguish from other dlinks that may have NULL pointers.
#define DLIST_SENTINEL_NULL_OBJ  (reinterpret_cast<T*>(ILLEGAL_PTR))

	// mHead should always point to sentinel.  Sentinel should never have an object.
#define CHECK_DLIST_HEAD_TAIL() \
	ASSERT( mHead->mObj == DLIST_SENTINEL_NULL_OBJ ); \
	CHECK_TYPESIG( mHead, TYPESIG_LIB_DLINK ); \
	CHECK_TYPESIG( mTail, TYPESIG_LIB_DLINK );

public:
    enum eDestroy { DESTROY, KEEP };
    enum eDeletor { SCALAR, ARRAY };
			            Dlist( void );  // default is DESTROY,SCALAR
	explicit			Dlist( eDestroy destroy, eDeletor deletor = SCALAR );
	explicit			Dlist( eDeletor deletor, eDestroy destroy = DESTROY );  // swapped
						~Dlist();
	inline bool			IfEmpty( void ) const;
	inline bool			IfLinked( const T* obj ) const;
	inline void			Clear( void );
	inline Dlink<T>*	Prepend( T* obj );
	inline Dlink<T>*	Append( T* obj );
	inline void			Unlink( Dlink<T>* dlink );
	inline Dlink<T>*	First( void ) const;
	inline Dlink<T>*	Last( void ) const;
	inline Dlink<T>*	Next( Dlink<T>* dlink ) const;
	inline const Dlink<T>*	ForStart( void ) const;
	inline bool				ForTest( const Dlink<T>*& dlink ) const;
	inline void				ForNext( const Dlink<T>*& dlink ) const;

private:
    inline void         Init( eDestroy destroy, eDeletor deletor );

	eDestroy            mDestroy;   ///< controls whether list destructor will delete linked objects
	eDeletor			mDeletor;   ///< controls whether to use delete or delete[] on linked objects
	Dlink<T>*			mHead;		///< always points to the sentinel
	Dlink<T>*			mTail;		///< points to last link or sentinel if empty
	mutable Dlink<T>*	mDlinkNext;	///< used by For*()

public:
	DECL_TYPESIG( TYPESIG_LIB_DLIST )
	friend bool TestList( void );
};

/*****************************************************************************
 * Constructor.
 *****************************************************************************/
template<typename T>
Dlist<T>::Dlist( void )
{
    Init( DESTROY, SCALAR );
}
template<typename T>
Dlist<T>::Dlist( eDestroy destroy, eDeletor deletor )
{
    Init( destroy, deletor );
}
template<typename T>
Dlist<T>::Dlist( eDeletor deletor, eDestroy destroy )
{
    Init( destroy, deletor );
}
template<typename T>
void Dlist<T>::Init( eDestroy destroy, eDeletor deletor )
{
	SET_TYPESIG( this, TYPESIG_LIB_DLIST );

	mDestroy = destroy;
	mDeletor = deletor;

	// Make the sentinel which points to itself.
	mHead = mTail = new Dlink<T>;
	mHead->mObj = DLIST_SENTINEL_NULL_OBJ;  // sentinel never has an object
	mHead->mPrev = mHead->mNext = mTail->mPrev = mTail->mNext = mHead;
}

/*****************************************************************************
 * Delete all links (and optionally the linked objects).
 * Sentinel must remain in case new links are added.
 *****************************************************************************/
template<typename T>
void Dlist<T>::Clear( void )
{
	// Delete links (and optionally the linked objects) but keep the sentinel.
	// Sentinel is needed if after clearing, new links are added.
	Dlink<T>* dlink = mHead->mNext;
	while ( dlink != dlink->mNext )
	{
//ASSERT( dlink->mObj != NULL );  // allow client to assign NULL object
CHECK_TYPESIG(dlink,TYPESIG_LIB_DLINK);
CHECK_TYPESIG(dlink->mNext,TYPESIG_LIB_DLINK);
		Dlink<T>* next = dlink->mNext;  // before dlink is unlinked (don't saw off branch)
		if ( mDestroy == DESTROY )
		{
			if ( mDeletor == ARRAY )  // delete the object pointed to by this link
				delete[] dlink->mObj;
			else
				delete   dlink->mObj;
		}
		Unlink( dlink );  // delete the link struct itself
		dlink = next;
	}
ASSERT( mHead == mTail );  // head==tail==sentinel
CHECK_DLIST_HEAD_TAIL();
}

/*****************************************************************************
 * Destructor.
 * Delete all objects in the list (unless KEEP) then the list itself.
 *****************************************************************************/
template<typename T>
Dlist<T>::~Dlist()
{
	Clear();       // delete linked objects
	delete mHead;  // delete hidden sentinel (Clear() kept it)
	INVALIDATE_TYPESIG( this, TYPESIG_LIB_DLIST );
}

/*****************************************************************************
 * Make new link for object and prepend link to list.
 * The new link will be inserted immediately after the head/sentinel.
 * But effectively the new link is the first link as the loop helper ForStart()
 * will start an iteration at the link following the head.
 *****************************************************************************/
template<typename T>
Dlink<T>*
Dlist<T>::Prepend( T* obj )
{
CHECK_DLIST_HEAD_TAIL();

	// As a sentinel is used, head/tail always point to something,
	// and there is always a previous and a next link.

	// New link struct for this object.
	Dlink<T>* dlink = new Dlink<T>;

	// Insert new link between head/sentinel link and second link.
	if ( UX(mHead == mTail) ) mTail = dlink; // if list is empty, new link is the tail
	dlink->mNext = mHead->mNext;
	dlink->mPrev = mHead;
	dlink->mObj  = obj;
	mHead->mNext = dlink->mNext->mPrev = dlink;
CHECK_TYPESIG(dlink->mNext,TYPESIG_LIB_DLINK);
CHECK_TYPESIG(dlink->mPrev,TYPESIG_LIB_DLINK);
CHECK_DLIST_HEAD_TAIL();
	return dlink;
}

/*****************************************************************************
 * Make new link for object and append link to list.
 *****************************************************************************/
template<typename T>
Dlink<T>*
Dlist<T>::Append( T* obj )
{
CHECK_DLIST_HEAD_TAIL();

	// As a sentinel is used, head/tail always point to something,
	// and there is always a previous and a next link.

	// New link struct for this object.
	Dlink<T>* dlink = new Dlink<T>;

	// Link to tail and supplant it.
	dlink->mPrev = mTail;
	dlink->mNext = mTail->mNext;  // mTail->mNext = mHead = sentinel
	dlink->mObj  = obj;
	mTail->mNext = dlink;
	mTail        = dlink;
CHECK_TYPESIG(dlink->mNext,TYPESIG_LIB_DLINK);
CHECK_TYPESIG(dlink->mPrev,TYPESIG_LIB_DLINK);
CHECK_DLIST_HEAD_TAIL();
	return dlink;
}

/*****************************************************************************
 * Unlink object's link out of list.
 * NEVER deletes the object (regardless of DESTROY ctor arg).
 * @remarks This design decision was for flexibility, the caller
 * can link and unlink an object in a list that auto-destroys its objects.
 *****************************************************************************/
template<typename T>
void
Dlist<T>::Unlink( Dlink<T>* dlink )
{
CHECK_TYPESIG( dlink, TYPESIG_LIB_DLINK );
CHECK_DLIST_HEAD_TAIL();

	// As a sentinel is used, head/tail always point to something,
	// and there is always a previous and a next link.
	if ( UX(mTail == dlink) ) mTail = dlink->mPrev;  // update tail if unlinking it
CHECK_TYPESIG(dlink->mNext,TYPESIG_LIB_DLINK);
CHECK_TYPESIG(dlink->mPrev,TYPESIG_LIB_DLINK);
	dlink->mPrev->mNext = dlink->mNext;  // preceding --> following
	dlink->mNext->mPrev = dlink->mPrev;  // following --> preceding
	delete dlink;
CHECK_DLIST_HEAD_TAIL();
}

/*****************************************************************************
 * @return True if list is empty.
 *****************************************************************************/
template<typename T>
bool
Dlist<T>::IfEmpty( void ) const
{
CHECK_DLIST_HEAD_TAIL();
	return mHead == mTail;  // empty if sentinel is the only link
}

/*****************************************************************************
 * @return True if list contains object.
 *****************************************************************************/
template<typename T>
bool
Dlist<T>::IfLinked( const T* obj ) const
{
CHECK_DLIST_HEAD_TAIL();
	for ( const Dlink<T>* dlink = ForStart(); ForTest(dlink); ForNext(dlink) )
	{
		if ( dlink->mObj == obj ) return true;
	}
	return false;
}

/*****************************************************************************
 * @return The first link (or NULL if list empty).
 *****************************************************************************/
template<typename T>
Dlink<T>*
Dlist<T>::First( void ) const
{
CHECK_DLIST_HEAD_TAIL();
CHECK_TYPESIG(mHead->mNext,TYPESIG_LIB_DLINK);  // works either way
	return mHead == mTail ? NULL : mHead->mNext;
}
/*****************************************************************************
 * @return The last link (or NULL if list empty).
 *****************************************************************************/
template<typename T>
Dlink<T>*
Dlist<T>::Last( void ) const
{
CHECK_DLIST_HEAD_TAIL();
	return mHead == mTail ? NULL : mTail;
}

/*****************************************************************************
 * @return The following link (or NULL if link was the last).
 *****************************************************************************/
template<typename T>
Dlink<T>*
Dlist<T>::Next( Dlink<T>* dlink ) const
{
CHECK_DLIST_HEAD_TAIL();
CHECK_TYPESIG(dlink,TYPESIG_LIB_DLINK);
CHECK_TYPESIG(dlink->mNext,TYPESIG_LIB_DLINK);
	return dlink->mNext != mHead ? dlink->mNext : NULL;
}

/*****************************************************************************
 * ForTest() is why Unlink() can be called (only once) inside an iteration (const_cast on Dlink required).
 * mDlinkNext remembers the next link in case code inside the loop unlinks the current link.
 *****************************************************************************/
template<typename T>
const Dlink<T>*
Dlist<T>::ForStart( void ) const
{
CHECK_DLIST_HEAD_TAIL();
CHECK_TYPESIG(mHead->mNext,TYPESIG_LIB_DLINK);
	return mHead->mNext;
}
template<typename T>
bool
Dlist<T>::ForTest( const Dlink<T>*& dlink ) const
{
CHECK_DLIST_HEAD_TAIL();
CHECK_TYPESIG(dlink,TYPESIG_LIB_DLINK);
CHECK_TYPESIG(dlink->mNext,TYPESIG_LIB_DLINK);
	mDlinkNext = dlink->mNext;
	return dlink != mHead;
}
template<typename T>
void
Dlist<T>::ForNext( const Dlink<T>*& dlink ) const
{
CHECK_DLIST_HEAD_TAIL();
//CHECK_TYPESIG(dlink,TYPESIG_LIB_DLINK);  // yes, dlink arg is allowed to point to a deleted link
CHECK_TYPESIG(mDlinkNext,TYPESIG_LIB_DLINK);
	dlink = mDlinkNext;
}

} // namespace gfx

#endif // GFX_LIST_HH
