/* Author: Jeff Dalton <J.Dalton@ed.ac.uk>
 * Updated: Sun May 27 05:34:46 2001 by Jeff Dalton
 */

package ix.util.lisp;

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

/**
 * A Collector that uses an LList to hold the elements and that provides
 * a number of different ways to add elements. <p>
 *
 * As a Java Collection, it is sequential, variable-sized, and modifiable. <p>
 *
 * Unlike Java's LinkedList class, which uses a doubly-linked list
 * internally, this class uses a list that is only forward-linked;
 * but it maintains a pointer to the last cell in the list to allow
 * elements to be added efficiently at either the beginning or end.
 * However, deleting the last element takes time proportional to
 * the length of the list.  LListCollectors can therefore be used
 * efficiently as stacks or queues, but not as double-ended queues
 * (deques). <p>
 *
 * The ListIterator for this class can efficiently add or remove
 * at any point in the list except for deleting the last element,
 * which again requires time proportional to the length.  Note
 * that some of these operations may change a car as well as a cdr.
 */

public class LListCollector extends AbstractSequentialList 
implements Collector, Serializable {

    transient Cons head = new Cons(Lisp.NIL, Lisp.NIL);
    Cons tail = head;

    public LListCollector() {
    }

    // 2nd constructor expected for Collections

    public LListCollector(Collection initialContents) {
	addAll(initialContents);
    }

    // Methods needed to complete AbstractSequentialList

    public ListIterator listIterator(int index) {
	return new LListCollectorListIterator(index);
    }

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

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

    // For public boolean isEmpty(), see below.

    public boolean add(Object o) {
	// Put at end.  The inherited methods does it by add(size(), o).
	addElement(o);
	return true;
    }

    public void clear() {
	setContents(Lisp.NIL);
    }

    public int lastIndexOf(Object o) {
	// The inherited method iterates backwards over the list
	// which is very slow.
	return contents().lastIndexOf(o);
    }

    // Our own methods

    public void addElement(Object e) {
	tail.cdr = new Cons(e, Lisp.NIL);
	tail = (Cons)tail.cdr;
    }

    public void deleteElement(Object e) {
	setContents(head.cdr.delete(e));
    }

    public void pushElement(Object e) {
	head.cdr = new Cons(e, head.cdr);
	if (tail == head)		// was empty
	    tail = (Cons)tail.cdr;
    }

    public Object popElement() {
	Debug.assert(head.cdr instanceof Cons, "popElement() when empty");
	Object result = (head.cdr).car();
	if (tail == head.cdr) {		// popping final element
	    Debug.assert(tail.cdr == Lisp.NIL, "bogus tail");
	    tail = head;
	}
	head.cdr = ((Cons)head.cdr).cdr;
	return result;
    }

    public void insertElement(Object e, Predicate2 lessp) {
	setContents(head.cdr.insert(e, lessp));
    }

    public Enumeration elements() {
	return head.cdr.elements();
    }

    public LList contents() {
	return head.cdr;
    }

    public Object result () {	// for Collector interface
	return head.cdr;
    }

    public void setContents(LList newContents) {
	head.cdr = newContents;
	tail = head;
	if (newContents instanceof Cons)
	    tail = tail.lastCons();
    }

    public boolean isEmpty() {
	return (tail == head);
    }

    public int length() {
	return (head.cdr).length();
    }

    public void concLList(LList l) {
	tail.cdr = l;
	if (l instanceof Cons)
	    tail = tail.lastCons();
    }

    public void appendLList(LList l) {
	concLList((LList)l.clone());
    }

    public void pushLList(LList l) { 		// prefixLList()?  /\/
	setContents(l.append(head.cdr));
    }

    public Function1 elementAdder() {
	return new adderFunction() {
	    public Object funcall(Object e) {
		addElement(e);
		return null;
	    }
	};
    }

    public Function1 elementPusher() {
	return new adderFunction() {
	    public Object funcall(Object e) {
		pushElement(e);
		return null;
	    }
	};
    }

    public Function1 llistAppender() {
	return new adderFunction() {
	    public Object funcall(Object l) {
		appendLList((LList)l);
		return null;
	    }
	};
    }

    public Function1 llistConcer() {
	return new adderFunction() {
	    public Object funcall(Object l) {
		concLList((LList)l);
		return null;
	    }
	};
    }

    protected static interface adderFunction extends Function1 {
    }

    // Serialization and deserialization methods that should be more
    // efficient than the default.

    private void writeObject(java.io.ObjectOutputStream out)
        throws java.io.IOException {
        
	// Write tail and any "hidden" stuff produced by serialization.
        out.defaultWriteObject();

	// Write length.
	out.writeInt(length());

	// Write out elements, ensuring that the last Cons is written
	// as a Cons so it will match tail.
	if (head != tail) {	// not empty
	    Cons at;
	    for (at = (Cons)head.cdr; at.cdr != Lisp.NIL; at = (Cons)at.cdr) {
		out.writeObject(at.car);
	    }
	    Debug.assert(at instanceof Cons);
	    out.writeObject(at);
	}
    }

    private void readObject(java.io.ObjectInputStream in)
        throws ClassNotFoundException, java.io.IOException {

	// Read tail and any "hidden" stuff
	in.defaultReadObject();

	// Read length
	int len = in.readInt();

	if (len == 0)
	    head = tail;
	else {
	    head = new Cons(Lisp.NIL, Lisp.NIL);
	    Cons at = head;
	    for (int i = 0; i < len-1; i++) {
		Cons e = new Cons(in.readObject(), Lisp.NIL);
		at.cdr = e;
		at = e;
	    }
	    Cons t = (Cons)in.readObject();
	    Debug.assert(t == tail);
	    at.cdr = t;
	}

    }

    /**
     * ListIterator for ListCollectors
     */
    class LListCollectorListIterator extends LListListIterator {

	public LListCollectorListIterator(int index) {
	     super(contents(), index);
	}

	public void set(Object o) {
	    // Different from the inherited method just to have a different
	    // error message.
	    if (setPoint == null)
		throw new IllegalStateException
		    ("set without next or previous, " +
		     "or after remove or add called");
	    else
		setPoint.setCar(o);
	}

	public void remove() {
	    // Removes the last element returned by next or previous.
	    if (setPoint == null)
		throw new IllegalStateException
		    ("remove without next or previous, or after add");
	    // The list is not empty.
	    Debug.assert(!isEmpty());
	    Debug.assert(setPoint instanceof Cons);
	    // Three cases:
	    if (setPoint == head.cdr) {
		// Deleting the first element (which might also be the last)
		Debug.assert(index == 0);
		popElement();
		list = head.cdr;
		at = list;
	    }
	    if (setPoint == tail) {
		// Deleting the last element when it's not the first.
		// This is a pain.
		Debug.assert(setPoint.cdr == Lisp.NIL);
		Cons back = (Cons)list.drop(index - 1); // linear
		Debug.assert(back.cdr == setPoint);
		back.setCdr(Lisp.NIL);
		tail = back;
		Debug.assert(!isEmpty());
	    }
	    else {
		// Deleting in the middle of the list.
		// This is the only case where we change a car.
		Cons nextCons = (Cons)setPoint.cdr;
		setPoint.setCar(nextCons.car);
		setPoint.setCdr(nextCons.cdr);
		if (nextCons == tail)
		    tail = setPoint;
		Debug.assert(!isEmpty());
	    }
	    Debug.assert(list == head.cdr);
	    setPoint = null;
	}

	public void add(Object o) {
	    // Inserts before the elt next would return.
	    // This is annoyingly tricky.
	    if (head == tail) {
		// Adding to empty list
		Debug.assert(index == 0);
		Debug.assert(head.cdr == Lisp.NIL);
		addElement(o);
		list = head.cdr;
		at = list.cdr();
	    }
	    else if (at == Lisp.NIL) {
		// Adding at end of non-empty list
		addElement(o);
		at = at.cdr();
	    }
	    else if (at == head.cdr) {
		// Adding at start of non-empty list
		Debug.assert(index == 0);
		pushElement(o);
		list = head.cdr;
		at = list.cdr();
	    }
	    else {
		// Adding somewhere in the middle of a non-empty list
		// This is the only case where we change a car.
		Debug.assert(at instanceof Cons);
		Object movedElt = at.car();
		Cons cat = (Cons)at;
		cat.setCar(o);
		cat.setCdr(new Cons(movedElt, cat.cdr()));
		at = cat.cdr();
	    }
	    Debug.assert(list == head.cdr);
	    setPoint = null;
	    index++;
	}

    }

}