/* Author: Jeff Dalton <J.Dalton@ed.ac.uk>
 * Updated: Tue Jun 12 16:49:06 2001 by Jeff Dalton
 */

package ix.util.lisp;

import java.io.Serializable;
import java.util.*;

import ix.util.*;


/** 
 * Lisp-style lists. <p>
 *
 * An LList can be treated as a Collection that is sequential,
 * fixed-size, and modifiable.  However, the linked structure
 * is visible; and that allows them to be used in ways that 
 * typical Java collections cannot.  Two LLists can share structure
 * by having a common tail.  Moreover, an LList is not constructed
 * by creating an empty LList and then adding elements; instead it
 * is typically made from a single element, which becomes the first
 * element of the LList, plus an existing LList that contains the
 * rest.  This supports a different style of programming closer to
 * what is used in functional languages, Lisp, and Prolog. <p>
 *
 * For a Collection based on LLists that works in the more usual
 * Java manner, use an LListCollector. <p>
 *
 * The class structure is like that in Common Lisp -- there is an
 * abstract class List with two subclasses, Cons and Null -- but 
 * only proper lists are allowed.  The car of a Cons can be any
 * Object, but the cdr must be a List.<p>
 *
 * The empty list is the value of Lisp.NIL and is the only instance
 * of the class Null.<p>
 *
 * An important goal was that all lists, including the empty list,
 * could be enumerated.  That's one reason for having a List subclass
 * for the empty list, rather than just using a unique Object or
 * <tt>null</tt>.  The subclass also allows a number of other
 * methods to be defined for all lists.  (A plausible alternative,
 * however, would be to have just one class, LList, and have the empty
 * list be a unique instance of that class.)
 *
 * @see LListCollector
 * @see Lisp
 * @see Cons
 * @see Null
 */

// "LList" because "List" conflicts with an AWT class and with java.util.List.

public abstract class LList extends AbstractSequentialList
implements LispObject, Serializable {

    // Methods needed to complete AbstractSequentialList

    public ListIterator listIterator(int index) {
	return new LListListIterator(this, index);
    }

    public int size() {
	return length();
    }

    // Inherited methods we need to override because they're inefficient.

    /**
     * Returns an interator over the elements of the list.
     * Note that the result is a plain Iterator, not a ListIterator,
     * because Iterators require less state and can be implemented
     * more efficiently.
     */
    public Iterator iterator() {
	return new LListIterator(this);
    }

    public boolean isEmpty() {
	return this == Lisp.NIL;
    }

    public int lastIndexOf(Object o) {
	// The inherited method iterates backwards over the list
	// which would be very slow.
	int i = -1, max = -1;
	for (LList at = this; at != Lisp.NIL; at = at.cdr()) {
	    i++;
	    Object e = at.car();
	    if (e == o || o.equals(e)) 	// e might be null
		max = i;
	}
	return max;
    }

    // The abstract methods are implemented differently in Cons and Null.
    // In some cases, a Cons method can be simpler than an inherited List
    // method, because it does not have to test for the list being null.

    public abstract boolean isNull();

    public abstract Object car();
    public abstract LList cdr();

    public abstract int length();

    public abstract Object elementAt(int i);

    public abstract Enumeration elements();

    public abstract boolean equal(LList list);
    public abstract boolean find(Object a);

    public abstract LList append(LList tail);
    // public abstract LList nconc(LList tail);


    // But it's simpler to define LList methods that are inherited.

    public Object clone() {
	return Lisp.NIL;	// overridden in Cons
    }

    public LList reverse() {
	LList r = Lisp.NIL;
	for (LList at = this; at != Lisp.NIL; at = at.cdr()) {
	    r = new Cons(at.car(), r);
	}
	return r;
    }

    public Object get(Object propname) {
	for (LList at = this; at != Lisp.NIL; at = at.cdr().cdr()) {
	    if (at.car() == propname)
		return at.cdr().car();
	}
	return null;
    }

    public Cons lastCons() {
	Cons tail = (Cons)this;
	for (; tail.cdr() != Lisp.NIL; tail = (Cons)tail.cdr()) {
	}
	return tail;
    }

    public LList take(int n) {
	if (n <= 0 || isNull())
	    return Lisp.NIL;
	else
	    return new Cons(car(), cdr().take(n - 1));
    }

    public LList drop(int n) {
	LList tail = this;
	for (int i = 0; i < n; i++) {
	    tail = tail.cdr();
	}
	return tail;
    }

    public LList without(Object e) { // Collection remove returns boolean
	if (isNull()) return this;
	else if (car() == e) return this.cdr();
	else return new Cons(car(), cdr().without(e));
    }

    public LList delete(Object e) {
	if (isNull()) return this;
	else if (car() == e) return cdr();
	else 
	    for (LList back = this, at = this.cdr();
		 at != Lisp.NIL;
		 back = at, at = at.cdr()) {
		if (at.car() == e) {
		    ((Cons)back).setCdr(at.cdr());
		    break;
		}
	}
	return this;
    }

    public LList insert(Object e, Predicate2 lessp) {
	// The new element goes before the first that's greater than it is.
	if (isNull())
	    return new Cons(e, Lisp.NIL);
	else if (lessp.trueOf(e, car()))
	    return new Cons(e, this);
	else
	    return new Cons(car(), cdr().insert(e, lessp));
    }

    public LList replaceAll(final Object old, final Object neu) {
	return mapcar(new Function1() {
	    public Object funcall(Object e) {
		return e == old ? neu : e;
	    }
	});
    }

    public LList mapc(Function1 f) {
	for (LList tail = this; !tail.isNull(); tail = tail.cdr()) {
	    f.funcall(tail.car());
	}
	return this;
    }

    public LList mapcar(Function1 f) {
	if (isNull())
	    return Lisp.NIL;
	else
	    return new Cons(f.funcall(car()), cdr().mapcar(f));
    }

    public LList flatmap(Function1 f) {
	if (isNull())
	    return Lisp.NIL;
	else
	    return ((LList)f.funcall(car())).append(cdr().flatmap(f));
    }

    public void walkTree(Function1 f) {
	for (LList tail = this; !tail.isNull(); tail = tail.cdr()) {
	    Object elt = tail.car();
	    if (elt instanceof LList)
		((LList)elt).walkTree(f);
	    else
		f.funcall(elt);
	}
    }

    public LList intersect(LList set) {
	LListCollector result = new LListCollector();
	for (LList tail = this; !tail.isNull(); tail = tail.cdr()) {
	    Object elt = tail.car();
	    if (set.find(elt))
		result.addElement(elt);
	}
	return result.contents();
    }

    public LList permute() {
	return
	    Seq.toLList
	        (Seq.shuffleVector(Seq.toVector(elements())).elements());
    }

}