/*  EQEMu:  Everquest Server Emulator
    Copyright (C) 2001-2002  EQEMu Development Team (http://eqemu.org)

    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; version 2 of the License.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY except by those people which sell it, which
	are required to give you total support for your newly bought product;
	without even the implied warranty of MERCHANTABILITY or FITNESS FOR
	A PARTICULAR PURPOSE.  See the GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

enum direction{FORWARD,BACKWARD};

template<class TYPE> class LinkedListIterator;

template<class TYPE> 
class ListElement
{
private:

  TYPE                data;
  ListElement<TYPE>*  next;
  ListElement<TYPE>*  prev;

public:
  ListElement ();
  ListElement (const TYPE&);
  ListElement (const ListElement<TYPE>&);

  ~ListElement ();

  ListElement<TYPE>&	operator= (const ListElement<TYPE>&);

  ListElement<TYPE>*	GetLast ()
  {
	ListElement<TYPE>* tmp = this;
    while (tmp->GetNext()) {
		tmp = tmp->GetNext();
	}
	return tmp;
  }
  ListElement<TYPE>*	GetNext () const { return  next ; }
  ListElement<TYPE>*	GetPrev () const { return  prev ; }

  inline TYPE&			GetData ()			{ return  data ; }
  inline const TYPE&	GetData () const	{ return  data ; }

  void		SetData ( const TYPE& d )		    { data = d ; } // Quagmire - this may look like a mem leak, but dont change it, this behavior is expected where it's called
  void		SetLastNext ( ListElement<TYPE>* p )	
  {
	GetLast()->SetNext(p);
  } 
  void		SetNext (ListElement<TYPE>* n)	{ next = n ; } 
  void		SetPrev (ListElement<TYPE>* p)	{ prev = p ; } 

  void          ReplaceData(const TYPE&);
};

template<class TYPE> 
class LinkedList
{
private:

	ListElement<TYPE>*		first;
	bool					list_destructor_invoked;

public:

  LinkedList();
  ~LinkedList();
  bool dont_delete;
  LinkedList<TYPE>&			operator= (const LinkedList<TYPE>&);

  void Append (const TYPE&);
  void Insert (const TYPE&);
  TYPE Pop();
  TYPE PeekTop();
  void Clear();

  friend class LinkedListIterator<TYPE>;
};

template<class TYPE> 
class LinkedListIterator
{
private:
  LinkedList<TYPE>&   list;
  ListElement<TYPE>*	current_element;
  direction           dir;
 
public:
  LinkedListIterator(LinkedList<TYPE>& l,direction d = FORWARD) : list(l), dir(d) {};

  void Advance();
  const TYPE& GetData();
	bool IsFirst() 
	{
		if (current_element->GetPrev() == 0)
			return true;
		else
			return false;
	}
	bool IsLast()
	{
		if (current_element->GetNext() == 0)
			return true;
		else
			return false;
	}
  bool MoreElements();
  void MoveFirst();
  void MoveLast();
  void RemoveCurrent(bool DeleteData = true);
  void Replace(const TYPE& new_data);
  void Reset();
  void SetDir(direction);
};

template<class TYPE>
void LinkedListIterator<TYPE>::Advance()
{
	if (current_element == 0)
	{
		return;
	}
	if (dir == FORWARD)
	{
		current_element = current_element->GetNext();
	}
	else
	{
		current_element = current_element->GetPrev();
	}

	if (list.list_destructor_invoked)
	{
		while(current_element && current_element->GetData() == 0)
		{
//			if (current_element == 0)
//			{
//				return;
//			}
			if (dir == FORWARD)
			{
				current_element = current_element->GetNext();
			}
			else
			{
				current_element = current_element->GetPrev();
			}
		}
	}
}

template<class TYPE>
bool LinkedListIterator<TYPE>::MoreElements()
{
  if (current_element == 0)
    return false;
  return true;
}

template<class TYPE>
const TYPE& LinkedListIterator<TYPE>::GetData()
{
  return current_element->GetData();
}

template<class TYPE>
void LinkedListIterator<TYPE>::MoveFirst()
{
  ListElement<TYPE>* prev = current_element->GetPrev();
  ListElement<TYPE>* next = current_element->GetNext();

  if (prev == 0)
	{
		return;
	}

//  if (prev != 0)
//  {
    prev->SetNext(next);
//  }
  if (next != 0)
  {
    next->SetPrev(prev);
  }
  current_element->SetPrev(0);
  current_element->SetNext(list.first);
  list.first->SetPrev(current_element);
  list.first = current_element;
}


template<class TYPE>
void LinkedListIterator<TYPE>::MoveLast()
{
  ListElement<TYPE>* prev = current_element->GetPrev();
  ListElement<TYPE>* next = current_element->GetNext();

  if (next == 0)
	{
		return;
	}

  if (prev != 0)
  {
    prev->SetNext(next);
  }
	else
	{
    list.first = next;
	}
//  if (next != 0)
//  {
    next->SetPrev(prev);
//  }
  current_element->SetNext(0);
  current_element->SetPrev(next->GetLast());
  next->GetLast()->SetNext(current_element);
}

template<class TYPE>
void LinkedListIterator<TYPE>::RemoveCurrent(bool DeleteData)
{
  ListElement<TYPE>* save;

  if (list.first == current_element)
  {
    list.first = current_element->GetNext();
  }

  if (current_element->GetPrev() != 0)
  {
    current_element->GetPrev()->SetNext(current_element->GetNext());
  }
  if (current_element->GetNext() != 0)
  {
    current_element->GetNext()->SetPrev(current_element->GetPrev());
  }
  if (dir == FORWARD)
  {
    save = current_element->GetNext();
  }
  else
  {
    save = current_element->GetPrev();
  }
  current_element->SetNext(0);
  current_element->SetPrev(0);
  if (!DeleteData)
	  current_element->SetData(0);
  safe_delete(current_element);
  current_element = save;
}

template<class TYPE>
void LinkedListIterator<TYPE>::Replace(const TYPE& new_data)
{
    current_element->ReplaceData(new_data);
}

template<class TYPE>
void LinkedListIterator<TYPE>::Reset()
{
	if (!(&list))
	{
	  current_element=0;
	  return;
	}
	
	if (dir == FORWARD)
	{
		current_element = list.first;
	}
	else
	{
		if (list.first == 0)
		{
			current_element = 0;
		}
		else
		{
			current_element = list.first->GetLast();
		}
	}

	if (list.list_destructor_invoked)
	{
		while(current_element && current_element->GetData() == 0)
		{
//			if (current_element == 0)
//			{
//				return;
//			}
			if (dir == FORWARD)
			{
				current_element = current_element->GetNext();
			}
			else
			{
				current_element = current_element->GetPrev();
			}
		}
	}
}

template<class TYPE>
void LinkedListIterator<TYPE>::SetDir(direction d)
{
  dir = d;
}

template<class TYPE>
ListElement<TYPE>::ListElement(const TYPE& d)
{
  data = d;
  next = 0;
  prev = 0;
}

template<class TYPE>
ListElement<TYPE>::~ListElement()
{
//	cout << "ListElement<TYPE>::~ListElement()" << endl;

	if (data != 0)
		safe_delete(data);
	data = 0;
	if (next != 0)
	{
		safe_delete(next);
		next = 0;
	}
}

template<class TYPE>
void ListElement<TYPE>::ReplaceData(const TYPE& new_data)
{
	if (data != 0)
	  safe_delete(data);
	data = new_data;
}

template<class TYPE>
LinkedList<TYPE>::LinkedList()
{
	list_destructor_invoked = false;
	first = 0;
}

template<class TYPE>
LinkedList<TYPE>::~LinkedList()
{
	list_destructor_invoked = true;
	if(!dont_delete)
		Clear();
}

template<class TYPE>
void LinkedList<TYPE>::Clear() {
	while (first) {
		ListElement<TYPE>* tmp = first;
		first = tmp->GetNext();
		tmp->SetNext(0);
		safe_delete(tmp);
	}
}

template<class TYPE>
void LinkedList<TYPE>::Append(const TYPE& data)
{
  ListElement<TYPE>* new_element = new ListElement<TYPE>(data);
  
  if (first == 0)
  {
    first = new_element;
  }
  else
  {
    new_element->SetPrev(first->GetLast());
    first->SetLastNext(new_element);
  }
}

template<class TYPE>
void LinkedList<TYPE>::Insert(const TYPE& data)
{
  ListElement<TYPE>* new_element = new ListElement<TYPE>(data);

  new_element->SetNext(first);
  if (first != 0)
  {
    first->SetPrev(new_element);
  }
  first = new_element;
}

template<class TYPE>
TYPE LinkedList<TYPE>::Pop() {
	TYPE ret = 0;
	if (first) {
		ListElement<TYPE>* tmpdel = first;
		first = tmpdel->GetNext();
		if (first)
			first->SetPrev(0);
		ret = tmpdel->GetData();
		tmpdel->SetData(0);
		tmpdel->SetNext(0);
		safe_delete(tmpdel);
	}
	return ret;
}

template<class TYPE>
TYPE LinkedList<TYPE>::PeekTop() {
	if (first)
		return first->GetData();
	return 0;
}

#endif

