///////////////////////////////////////////////////////
// LinkedListDeque.java
// 
// Written By Geoff Knagge (9806135)
// last modified 14/8/1999
//
// implements a Deque using a linked list of ListNodes
///////////////////////////////////////////////////////

public class LinkedListDeque implements Deque
{
	private int dequeSize;
	private ListNode head, tail;

	/////////////////////////////////// Constructor

	public LinkedListDeque()
	{
		head = new ListNode(null,null,null);
		tail = new ListNode(null,null,head); // head is prev node
		head.setNext(tail);
		dequeSize = 0;
	}

	/////////////////////////////////// Mutator Methods

	public void insertFirst(Object o)
	// places a new ListNode containing o between the head sentinel
	// and the node that the head was originally linked to.
	{
		ListNode newNode = new ListNode(o,head.getNext(),head);
		head.getNext().setPrev(newNode);
		head.setNext(newNode);
		dequeSize++;
	}

	public void insertLast(Object o)
	// places a new ListNode containing o between the tail sentinel
	// and the node that the tail was originally linked to.
	{
		ListNode newNode = new ListNode(o,tail,tail.getPrev());
		tail.getPrev().setNext(newNode);
		tail.setPrev(newNode);
		dequeSize++;
	}

	public Object removeFirst() throws EmptyDequeException
	// returns the object in the node linked to the head of the list,
	// and removes that node.
	{
		if (isEmpty())
			throw new EmptyDequeException();
		ListNode node = head.getNext();
		head.setNext(node.getNext());
		node.getNext().setPrev(head);
		dequeSize--;
		return node.getElement();
	}

	public Object removeLast() throws EmptyDequeException
	// returns the object in the node linked to the tail of the list,
	// and removes that node.
	{
		if (isEmpty())
			throw new EmptyDequeException();
		ListNode node = tail.getPrev();
		tail.setPrev(node.getPrev());
		node.getPrev().setNext(head);
		dequeSize--;
		return node.getElement();
	}

	public Object firstElement() throws EmptyDequeException
	// returns the object in the node linked to the head of the list
	{
		if (isEmpty())
			throw new EmptyDequeException();
		return head.getNext().getElement();
	}

	public Object lastElement() throws EmptyDequeException
	// returns the object in the node linked to the tail of the list
	{
		if (isEmpty())
			throw new EmptyDequeException();
		return tail.getPrev().getElement();
	}

	/////////////////////////////////// Access Methods

	public boolean isEmpty()
	// returns true if there are no nodes between the head and tail
	{
		return (dequeSize == 0);
	}

	public int size()
	// returns the number of nodes between the head and the tail
	{
		return dequeSize;
	}
}