/***************************************************************************
                           clist.h  -  description
                             -------------------
    begin                : Sat Mai 5 2002
    copyright            : (C) 2002-2003 by Mathias Küster
    email                : mathen@users.berlios.de
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

#ifndef CLIST_H
#define CLIST_H

 /**
  *@author Mathias Küster
  *
  * A pointer based linked list with auto delete.
  */

#include <dclib/dcos.h>

typedef int (*CompareFunc) (void*, void*);

template<class type> class CListObject {
public:
	/** */
	CListObject() {};
	/** */
	~CListObject() {};

	/** */
	CListObject<type> * prev;
	/** */
	CListObject<type> * next;
	/** */
	type * Object;
};

template<class type> class CList {
public:
	/** */
	CList();
	/** */
	~CList();

	/** */
	int Add( type * Object );
	/** */
	int Del( type * Object );
	/** */
	void Clear();
	/** */
	int Remove( type * Object );
	/** */
	int InsertSorted( type * Object, CompareFunc func );
	/** */
	type * Prev( type * Object );
	/** */
	type * Next( type * Object );
	/** */
	long Count() const;

private:
	/** */
	long size;
	/** */
	CListObject<type> * pFirst;
	/** */
	CListObject<type> * pLast;
	/** */
	CListObject<type> * pCache;
	/** */
	CListObject<type> * FindListObject( type * Object );
};

/** */
template<class type> inline long CList<type>::Count() const
{ return size; }

/** */
template<class type> inline CList<type>::CList()
{
	pFirst = 0;
	pLast  = 0;
	pCache = 0;
	size   = 0;
}

/** */
template<class type> inline CList<type>::~CList()
{
	Clear();
}

/** */
template<class type> inline int CList<type>::InsertSorted( type * Object, CompareFunc func )
{
	CListObject<type> * lb, *lb1;

	if (!Object)
		return -1;

	if (!pFirst)
	{
		Add(Object);
		return 0;
	}
	
	lb  = pFirst;
	lb1 = 0;

	while(lb!=0)
	{
		if (func(Object,lb->Object)==-1)
		{
			lb1 = new CListObject<type>();
			lb1->Object = Object;
			lb1->prev = lb->prev;
			lb->prev = lb1;
			lb1->next = lb;
			if (pFirst==lb)
				pFirst=lb1;
			else
				lb1->prev->next = lb1;
			size++;
			pCache = 0;

			return 0;
		}

		lb = lb->next;
	}

	if ( lb1 == 0 )
	{
	    Add(Object);
	}
	return 0;
}

/** */
template<class type> inline int CList<type>::Add( type * Object )
{
	if ( Object == 0 )
	{
		return -1;
	}

	if ( pFirst == 0 )
	{
		pFirst = pLast = new CListObject<type>();
		pFirst->prev   = 0;
		pFirst->next   = 0;
		pFirst->Object = Object;
	}
	else if ( pLast != 0 )
	{
		pLast->next = new CListObject<type>();
		pLast->next->prev = pLast;
		pLast->next->next = 0;
		pLast->next->Object = Object;
		pLast = pLast->next;
	}
	else
	{
		// error
	}

	size++;

	pCache = 0;

	return 0;
}

/** */
template<class type> inline int CList<type>::Del( type * Object )
{
	CListObject<type> * lb = FindListObject( Object );

	if ( lb == 0 )
		return -1;

	delete lb->Object;

	if ( lb->prev != 0 )
		lb->prev->next = lb->next;
	if ( lb->next != 0 )
		lb->next->prev = lb->prev;
	if ( lb == pFirst )
		pFirst = lb->next;
	if ( lb == pLast )
		pLast = lb->prev;

	delete lb;

	size--;

	pCache = 0;

	return 0;
}

/** */
template<class type> inline void CList<type>::Clear()
{
	CListObject<type> * lb = pFirst;

	while(lb!=0)
	{
		delete lb->Object;
		pLast = lb->next;
		delete lb;
		lb = pLast;
	}

	pFirst = 0;
	pLast  = 0;
	pCache = 0;
	size   = 0;
}

/** */
template<class type> inline int CList<type>::Remove( type * Object )
{
	CListObject<type> * lb = FindListObject( Object );

	if ( lb == 0 )
		return -1;

	if ( lb->prev != 0 )
		lb->prev->next = lb->next;
	if ( lb->next != 0 )
		lb->next->prev = lb->prev;
	if ( lb == pFirst )
		pFirst = lb->next;
	if ( lb == pLast )
		pLast = lb->prev;

	delete lb;

	size--;

	pCache = 0;

	return 0;
}

/** */
template<class type> inline type * CList<type>::Prev( type * Object )
{
	CListObject<type> * lb = 0;

	if (pLast==0)
		return 0;

	if ( Object == 0 )
	{
		pCache = pLast;
		return pCache->Object;
	}

	if ( pCache != 0 )
		if ( pCache->Object == Object )
			lb = pCache;

	if ( lb == 0 )
		if ( (lb = FindListObject( Object )) == 0 )
		{
			pCache = 0;
			return 0;
		}

	pCache = lb->prev;

	if ( pCache == 0 )
		return 0;

	return pCache->Object;
}

/** */
template<class type> inline type * CList<type>::Next( type * Object )
{
	CListObject<type> * lb = 0;

	if (pFirst==0)
		return 0;

	if ( Object == 0 )
	{
		pCache = pFirst;
		return pCache->Object;
	}

	if ( pCache != 0 )
		if ( pCache->Object == Object )
			lb = pCache;

	if ( lb == 0 )
		if ( (lb = FindListObject( Object )) == 0 )
		{
			pCache = 0;
			return 0;
		}

	pCache = lb->next;

	if ( pCache == 0 )
		return 0;

	return pCache->Object;
}

/** */
template<class type> inline CListObject<type> * CList<type>::FindListObject( type * Object )
{
	CListObject<type> * lb = pFirst;

	while(lb!=0)
	{
		if (lb->Object == Object )
		{
			return lb;
		}

		lb = lb->next;
	}

	return lb;
}

#endif
