// © Copyright 1997, Joseph Bergin. All rights reserved.

import java.util.Enumeration;
import algo.*;

/** LList implements a circularly, doubly linked list of Objects.  It has an associated
*	Iterator type that also functions as an Enumeration.
* The Iterator and Enumeration references are to a type 
* <a href = LListIterator.html> LListIterator</a>
*/
public class LList implements Cloneable
{	/** Create an empty list. */
	public LList()
	{	tail = new LListNode(null, null, null); 
		tail.next = tail;
		tail.previous = tail;
	}	// The tail is a trailer node. 
	
	/** Insert the object before this location and move the iterator to this location.
	* @param i the location at which to insert
	* @param o the object to be inserted (not null)
	*/
	public synchronized void insert(Iterator i, Object o)
	{	if(o == null)return;
		LListIterator ii = (LListIterator)i;
		LListNode node = new LListNode(o, ii.here, ii.here.previous);
		LListNode temp = ii.here;
		ii.here.previous.next = node;
		temp.previous = node;
		ii.here = node;;
		count++;
	}
	
	/** Return true if the list is empty. */
	public synchronized boolean isEmpty(){ return tail.next == tail; }
	
	/** Remove the object a the location of an iterator. The iterator is advanced at the end.
	* @param i the location to remove
	* @return the original item at the location of i (may be null)
	*/
	public synchronized Object remove(Iterator i)
	{	Object result = i.get();
		LListIterator ii = (LListIterator)i;
		if(ii.here != tail)
		{	LListNode n = ii.here;
			n.next.previous = n.previous;
			n.previous.next = n.next;
			ii.here = n.next;
			n = null;
		}
		count--;
		return result;
	}
	
	/** Returns the length of the list.
	* @return the number of elements
	*/
	public synchronized long size() {return count;}
	
	/** Return an iterator to the first element of the list if any.
	* @return the location of the beginning of the list
	*/
	public synchronized Iterator begin(){return new LListIterator(this);}
	
	/** Return an iterator to the location following the last element of the list.
	* @return an iterator to the location "after" the list
	*/
	public synchronized Iterator end()
	{ 	LListIterator result = (LListIterator)begin();
		result.here = tail;
		return result;
	}
	
	/** Return a space separated list of elements of the list.
	* @return a string representation of the list
	*/
	public synchronized String toString()
	{	String result = "< ";
		for(Iterator i = begin(); !i.equals(end()); i.advance())
			result += i.get().toString()+' ';
		return result + '>';
	}
	
	/** Return an Enumeration over all of the list.
	* @return an enumeration over the list
	*/
	public synchronized  Enumeration elements(){ return (Enumeration)begin(); }
	
	/** Return a faithful copy of this list
	* @return a new list with the same elements in the same order.
	*/
	public synchronized Object clone()
	{	LList result = new LList();
		Enumeration e = elements();
		while(e.hasMoreElements())
			result.insert(result.end(), e.nextElement());
		return result;
	}
	
	private LListNode tail;
	private long count = 0;
	
	/** Both an Enumeration and BidirectionalIterator over LLists.  There is no public constructor as these
	* are always created from lists. 
	*/
	class LListIterator implements BidirectionalIterator, Enumeration
	{	
		/** Create an iterator initialized to the beginning of the list.
		* @param the list
		*/
		LListIterator(LList l){here = l.tail.next; list = l;}

		/** Does this reference the same location in the container?
		* @param i the iterator to be compared with
		*/
		public boolean equals(Iterator i){ return here == ((LListIterator)i).here; }

		/** Move this to the position of i.
		* @param the position to move to
		*/
		public void moveTo(Iterator i){ here = ((LListIterator)i).here;}
		
		/**
		* Advance to the next element in the list, but not past the tail. 
		* @return the new location
		*/
		public Iterator advance()	// C++,  ++this
		{	if(here != list.tail)here = here.next;
			return this;
		}

		/** Move the location back one item. Does not move back past head.
		* @return the new location
		*/
		public Iterator retreat()	// C++, --this 
		{	if(here.previous != list.tail)here = here.previous;
			return this;
		}

		/**
		* Return the current element of the list.
		* @return the current element
		*/
		public Object get() { return here.get(); }

		/**
		* Set the current element to the list
		* @param o the new value at this location
		*/
		public void set(Object o) { here.set(o); }
		
		/** Return true if the list has more elements
		* @return does the list have more elements
		*/
		public boolean hasMoreElements(){ return here != list.tail; }
		
		/** Return the current element of the list and advance
		* @return the current element
		*/
		public Object nextElement()
		{	Object result = get();
			advance();
			return result;
		}
		
		/** Return a new iterator to the same location. 
		* @return a copy of the iterator
		*/
		public Object clone()
		{ 	LListIterator result = new LListIterator(list);
			result.here = here;
			return result;
		}

		private LList list;
		private LListNode here;
		
	}

	class LListNode
	{	LListNode(Object o){this(o,null,null);}

		LListNode(Object o, LListNode next){this(o,next,null);}
		
		LListNode(Object o, LListNode next, LListNode prev)
		{	value = o; 
			this.next = next; 
			previous = prev;
		}
		
		public Object get(){return value;}
		
		public void set(Object o){value = o;}
		
		private LListNode previous;
		private LListNode next;
		private Object value;
	}
}