/**
  * Copyright (c): Uwe Schmidt, FH Wedel
  *
  * You may study, modify and distribute this source code
  * FOR NON-COMMERCIAL PURPOSES ONLY.
  * This copyright message has to remain unchanged.
  *
  * Note that this document is provided 'as is',
  * WITHOUT WARRANTY of any kind either expressed or implied.
  */

package ds.persistent.list;

/** Implementation of single linked lists.
    The element type is the example class E
    In real world java progs, this would be a
    generic type parameter.

    This implementation is a PERSISTENT one.
*/

import ds.interfaces.List;
import ds.util.E;
import java.util.Iterator;

import static ds.util.Undef.undefined;

public abstract class LinkedList
    implements List {

    //----------------------------------------
    // the smart constructors

    // empty list
    public static
	LinkedList empty() {

	return
	    EMPTY;
    }

    // singleton list
    public static
	LinkedList singleton(E e) {
	return
	    EMPTY.cons(e);
    }

    // list from iterator
    public static
	LinkedList fromIterator(Iterator<E> elems) {

        if ( elems.hasNext() ) {
            E info = elems.next();
            return
                fromIterator(elems).cons(info);
        }
        return
            empty();
    }

    //----------------------------------------
    // public methods

    public boolean inv() {
	return true;
    }

    public abstract LinkedList init();
    public abstract LinkedList tail();

    public abstract LinkedList concat(List l2);

    public LinkedList append(E e) {
        return
            concat(singleton(e));
    }

    public Node cons(E e) {
        return
            new Node(e, this);
    }

    public LinkedList reverse() {
	return
	    reverse1(empty());
    }
    abstract protected LinkedList reverse1(LinkedList res);

    // default impementation for copy
    public LinkedList copy() {
	return
	    this;
    }

    public Iterator<E> iterator() {
        return
            new ListIterator(this);
    }

    public String toString() {
        return
            (new ListIterator(this)).toString();
    }

    //----------------------------------------
    // the empty list

    // the "generic" empty list object, (the singleton has a raw type)

    private static final LinkedList EMPTY
	= new Empty();

    // the singleton class for the empty list object

    private static final
	class Empty
	extends LinkedList {

	public boolean isEmpty() {
	    return true;
	}
	public boolean member(E e) {
	    return false;
	}
	public int     length() {
	    return 0;
	}
	public E head() {
            return
		undefined("head of empty list");
	}
	public LinkedList tail() {
            return
		undefined("tail of empty list");
	}
	public E last() {
            return
		undefined("last of empty list");
	}
	public LinkedList init() {
            return
		undefined("init of empty list");
	}
	public E at(int i) {
            return
		undefined("at of empty list");
	}
	public LinkedList concat(List l2) {
	    return
		(LinkedList)l2;
	}

	//----------------------------------------
	// not public stuff

	Empty() { }

	protected LinkedList reverse1(LinkedList acc) {
	    return
		acc;
	}
    }

    //----------------------------------------
    // the none empty list class

    private static final
	class Node
	extends LinkedList {

	public boolean isEmpty() {
	    return
		false;
	}

	public boolean member(E e) {
	    return
		e.equalTo(info)
		||
		next.member(e);
	}

	public int length() {
	    return
		1 + next.length();
	}

	public E head() {
	    return
		info;
	}

	public LinkedList tail() {
	    return
		next;
	}

	public E last() {
	    if ( next.isEmpty() )
		return
		    info;
	    return
		next.last();
	}

	public LinkedList init() {
	    if ( next.isEmpty() )
		return
		    empty();
	    return
		setNext(next.init());
	}

	public E at(int i) {
	    if ( i == 0 )
		return
		    info;
	    return
		next.at(i - 1);
	}

	public LinkedList concat(List l2) {
	    return
		setNext(next.concat(l2));
	}

	/* destructive *
	public LinkedList copy() { // duplicate all nodes
	    return
		next.copy().cons(info);
	}
	/**/

	//----------------------------------------
	// not public stuff

        private final E             info;
        private
	    /* persistent */ final /**/
	    LinkedList next;

        Node(E i, LinkedList n) {
            info = i;
            next = n;
            ++cntNode;
        }

	protected LinkedList reverse1(LinkedList acc) {
	    return
		next.reverse1(setNext(acc));
	}

	Node setNext(LinkedList l2) {
	    /* persistent */
	    if ( l2 == next )
		return
		    this;
	    return
		l2.cons(info);

	    /* destructive *
	    next = l2;
	    return
		this;
	    /**/
	}
    }

    //----------------------------------------
    // iterator class

    private static
	class ListIterator
	extends ds.util.Iterator<E> {

        List cur;

        ListIterator(List l) {
            cur = l;
            ++cntIter;
        }

        public boolean hasNext() {
            return
                ! cur.isEmpty();
        }

        public E next() {
            if ( cur.isEmpty() )
                return
		    undefined("iterator exhausted");

	    E res = cur.head();
	    cur   = cur.tail();
	    return
		res;
        }
    }

    //----------------------------------------
    // profiling

    private static int cntNode = 0;
    private static int cntIter = 0;

    public static String stats() {
        return
            "stats for ds.persistent.list.List:\n" +
            "# new Node()         : " + cntNode + "\n" +
            "# new ListIterator() : " + cntIter + "\n";
    }
}