// © Copyright 1996-1999, Joseph Bergin.  All rights reserved. 

package cs1;

import java.util.Enumeration;
import java.util.NoSuchElementException;

// This class represents non-updatable lisp like lists.  The NIL class
// defines the empty list, but null will serve for most purposes.  
// Use cons to build up other lists.  Elements in
// a list may not be changed or removed, though functions may return new
// lists with changed/removed contents relative to their inputs.  Objects in the
// list may, however, be sent messages, which might change their state. 

// Lists hold Objects of any kind.  Enumerations over the list return 
// references to the actual objects so they may be acted on.  Hence their
// contents may be modified while they are in the list.  This is not the
// same thing as saying that the list contents change.  

// One consequence of non-updatability of lists is that two different lists
// may share contents and even share nodes out of which the lists are built.
// Non-updatability is what makes this safe. 

// Note that java.awt contains a list class, but it represents an interface
// item, not a container.  

// It is also important to note that we do not use null to represent the empty
// list.  The empty list is a true list defined in the Singleton class NIL.  

// There are three ways to manipulate these lists. First, you can use the Enumeration
// returned by elements() to access the contents. Second you can build new lists from old
// using cons(...), head(), and tail(). Third, you can pass a recursive (or other) visitor
// to the list using its accept(...). The visitor can use any public methods of the nodes 
// it visits and can control the order in which it visits them,
// so this is more flexible than Enumerations, but less flexible than cons...,
// since visitors can't change the list structure. 

// There are three design patterns used here. Null Object, Singletom, and Visitor. 
// See the desgin patterns literature for details. This design achieves a high degree
// of polymorphism as there is almost no need to to ad-hoc testing. In particular there
// are NO if statements to determine whether we are at the end of the list, either in the
// node classes or in the visitors. 
// Null Object: Bobby Wolfe, in Pattern Languages of Program Design 3, ed: Martin, 
// 	Riehle, and Buschmann, Addison-Wesley, 1998, pg 3.
// Singleton: Design Patterns, Gamma, Helm, Johnson, and Vlissides, Addison-Wesley, 
//	1995 pg 127.
// Visitor: ibid. pg 331.

class EmptyListException extends RuntimeException
{	EmptyListException(String s){super(s);}
}

public abstract class LispwVisitor implements Cloneable
{	public static LispwVisitor cons(Object h, LispwVisitor t) 
	{	if(t==null) t = NIL.val; 
		Node n = new Node(h,t); 
		return n;
	}
	// Cons is a standard abbreviation for construct.  The usage comes
	// from the language lisp, which inspired this class.  
	
	public static final NIL nil = NIL.val; // a constant.
	
	public static LispwVisitor nil(){return nil;}
	
	public abstract Object head(); // Return the head of the list or throw exception
	public abstract LispwVisitor tail();// Return the tail of the list or throw exception
	
	public interface Visitor // visit one node of the list
	{	public Object apply(Node aList);
		public Object apply(NIL empty);
	}
	// Note that apply functions on Nodes are usually recursive. Thus, the visitor can
	// control the recursion, rather than the list itself. Therefore you can recurse
	// either before or after handling the current node. 
	
	public abstract Object accept(Visitor action); // apply the action to this node.

	public abstract Enumeration elements();
	// elements is the canonical name for an enumeration over a container
	
	public void copyInto(Object[] A){}	
	// The name copyInto is also canonical for operations like this. 
	// Note that this will throw an exception if the current list object
	// has a size greater than the length of the array.  
	
	public int size(){return 0;}
	// Note that size is the canonical name for the size of a container
	// in Java.  It is the number of elements in the list.  
	
	public Object clone(){ return this;}
	// Clone is inherited from Object. 
	
	public boolean contains(Object o){return false;}
	// Contains is the canonical name for the containment relation in
	// Java container classes.
	
	public boolean isEmpty()	// Is this empty?
	{	return true;
	}
	// The name isEmpty is canonical for this test.
}

// The following two classes should be inner to the above. 
class NIL extends LispwVisitor // This is a Singleton Null Object (2 patterns) 
{	public String toString()	
	{	return "NIL" ;
	}	
	
	public Object head()
	{	throw new EmptyListException("Head"); // return null;
	}
	
	public LispwVisitor tail() 
	{	throw new EmptyListException("Tail"); // return null;
	}
	
	public Object accept(Visitor action)
	{	return action.apply(this);
	}
	
	private NIL(){}
	
	public Enumeration elements(){return Enum.e;}
	
	public static final NIL val = new NIL();

	private static class Enum implements Enumeration // A Singleton
	{	public boolean hasMoreElements()
		{	return false;
		}
		
		public Object nextElement() 
		{	return null;
		}
		
		private Enum(){}
		
		private static final Enum e = new Enum();
	}
}

class Node extends LispwVisitor
{	public Object head() // First element in this list, or null.
	{	return element;
	}
	
	public LispwVisitor tail()	// Tail (list) of this list. 
	{	return next;
	}
	
	public Object accept(Visitor action)
	{	return action.apply(this);
	}
	
	public int size()	// Length of the list.
	{	return 1 + next.size();
	}
	
	public Object clone() // returns a list like this one.
	{	return new Node (element, (LispwVisitor)next.clone());
	}
	// Clone is the canonical name for object copying in Java.  
	
	public boolean contains(Object o)	// Does this contain o?
	{	if (o == null)
		{	if(element == null) return true;
			return next.contains(null);
		}
		if(o.equals (element)) return true;
		return next.contains(o);
	}
	
	public void copyInto(Object[] A) // Copy into a preexisting array.
	{	int i = 0;
		for(Enumeration e = elements(); e.hasMoreElements();)
		{	A[i++] = e.nextElement();
		}
	}
	
	public Enumeration elements() // Return an enumeration over this. 
	{	return new LispEnum(this);
	}
	
	public boolean isEmpty()	// Is this empty?
	{	return false;
	}
	
	public String toString()	// Copy contents to a new String. 
	{	return element.toString() + " " + next.toString();
	}	
	// Most Java classes should support toString.  It is used by Java when
	// we do output by concatenating objects to strings.   
	 
	Node(Object o, LispwVisitor first) // if this were inner to LispwVisitor it could be private
	{	next = first;
		element = o;
	}
	
	// Enumerations are called Iterators in other languages. 
	// Note: java.util.Enumeration itself is an interface, not a class. 

	private class LispEnum implements Enumeration
	{	private LispwVisitor here;
		
		protected LispEnum(LispwVisitor n)
		{	here = n;
		}
		
		// The next two methods form the basis of enumerations.  
		// One way to think of enumerations is that they represent high level
		// abstractions of pointers.  Method hasMoreElements asks whether or not 
		// the pointer is "past" the end of the container.  Method nextElement
		// is the dereference operator for the pointer, except that nextElement
		// also advances the location.  It is like *(p++) in C++.  
		public boolean hasMoreElements()
		{	return here != NIL.val;
		}
		
		public Object nextElement() 
		{	if(here == NIL.val) throw new NoSuchElementException("Fail in LispwVisitor.");
			Object result = ((Node)here).element;
			here = ((Node)here).next;
			return result;
		}
	}

		private LispwVisitor next = NIL.val;
		private Object element = null;
			
}