EQ2EMu/EQ2/source/common/linked_list.h

/*  
    EQ2Emulator:  Everquest II Server Emulator
    Copyright (C) 2007  EQ2EMulator Development Team (http://www.eq2emulator.net)

    This file is part of EQ2Emulator.

    EQ2Emulator 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 3 of the License, or
    (at your option) any later version.

    EQ2Emulator is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; 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 EQ2Emulator.  If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include "types.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:
	int32				    count;
	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();
  void LCount() { count--; }
  void ResetCount() { count=0; }
  int32	Count() { return count; }
  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;
  list.LCount();
}

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;
	count = 0;
	dont_delete = false;
}

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);
	}
	ResetCount();
}

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);
  }
  count++;
}

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;
  count++;
}

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);
		count--;
	}
	return ret;
}

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

#endif