// Doubly Linked List
//
// Douglas Thrift
//
// $Id$

#ifndef _DoublyLinkedList_hpp_
#define _DoublyLinkedList_hpp_

#include "NullNode.hpp"
#include "Iterator.hpp"

template<typename Type>
class DoublyLinkedList
{
private:
	NullNode<Type> front;
	NullNode<Type> back;
public:
	DoublyLinkedList() { front.setNext(&back); back.setPrevious(&front); }
	~DoublyLinkedList() { while (front.getNext() != &back) front.removeNext(); }
	void addFront(const Type& value) { front.addNext(value); }
	void addBack(const Type& value) { back.addPrevious(value); }
	bool contains(const Type& value);
	void removeFirst(const Type& value);
	void removeLast(const Type& value);
	Iterator<Type> iterator(void) { return Iterator<Type>(&front, &back); }
	void accept(Visitor<Type>* visitor);
};

template<typename Type>
bool DoublyLinkedList<Type>::contains(const Type& value)
{
	return front.contains(value, dynamic_cast<Node<Type>*>(&back), true);
}

template<typename Type>
void DoublyLinkedList<Type>::removeFirst(const Type& value)
{
	front.remove(value, dynamic_cast<Node<Type>*>(&back), true);
}

template<typename Type>
void DoublyLinkedList<Type>::removeLast(const Type& value)
{
	back.remove(value, dynamic_cast<Node<Type>*>(&front), false);
}

template<typename Type>
void DoublyLinkedList<Type>::accept(Visitor<Type>* visitor)
{
	front.accept(visitor, dynamic_cast<Node<Type>*>(&back), true);
}

#endif // _DoublyLinkedList_hpp_