/**
  * 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.
  */

/**
 * @author Uwe Schmidt
 *
 * Eine Klasse fuer verkettete Listen
 *
 * Die leere Liste wird durch das einzige aus der Klasse Empty
 * erzeugte Objekt repraesentiert, dessen Referenz int der
 * statischen Variablen empty gespeichert wird.
 *
 * Diese Referenz muss aber int der erzeugenden statischen
 * Funktion mkEmpty int eine Referenz des jeweils erforderlichen
 * Listentyps knvertiert werden.
 *
 * Dieses geht nur mit einer ungeprueften Konversion,
 * ist aber moeglich, da die Resultate der Empty-Methoden nicht von
 * dem Typparameter E abhaengen
 *
 * Die Hilfsklassen Empty und Node und die Konstruktoren
 * sind nicht oeffentlich,
 * Sie werden nur ueber die statischen Methoden aus LinkedList
 * aufgerufen.
 *
 */

//--------------------

public abstract
class LinkedList<E> {

    //--------------------
    //
    // die leere Liste wird durch die Referenz
    // in der Variablen empty repraesentiert

    protected static final
    LinkedList<Object> empty = new Empty<Object>();

    //--------------------

    @SuppressWarnings("unchecked")
    public static
    <E> LinkedList<E> mkEmptyList() {
	return
	    (LinkedList<E>)empty; // unchecked cast
    }

    public static
    <E> LinkedList<E> mkOne(E info) {
	LinkedList<E> r = mkEmptyList();
	return
	    r.cons(info);
    }

    //--------------------

    public
    LinkedList<E> cons(E info)
    {
	return
	    new Node<E>(info, this);
    }

    public
    boolean isEmpty() {
	return
	    false;
    }

    public
    E hd()
	throws IndexOutOfBoundsException
    {
	throw
	    new IndexOutOfBoundsException("hd of empty list");
    }

    public
    LinkedList<E> tl()
	throws IndexOutOfBoundsException
    {
	throw
	    new IndexOutOfBoundsException("tl of empty list");
    }

    public abstract
    int len();

    public
    E at(int i)
	throws IndexOutOfBoundsException
    {
	throw
	    new IndexOutOfBoundsException("illegal index into linked list");
    }

    public abstract
    boolean isIn(E o);

    public
    LinkedList<E> insert(E o) {
	if ( isIn(o) )
	    return
		this;

	return
	    cons(o);
    }

    public abstract
    LinkedList<E> remove(E o);


    public abstract
    LinkedList<E> concat(LinkedList<E> l2);

    public
    LinkedList<E> append(E o) {
	return
	    concat(mkOne(o));
    }
}

//--------------------
//
// Keine Methode in Empty besitzt als Resultat E, daher
// ist die Typkonversion in mkEmpty in der Klasse List harmlos

class Empty<E> extends LinkedList<E> {
    // nicht public
    Empty() {
    }

    public
    boolean isEmpty() {
	return
	    true;
    }

    public
    int len() {
	return 0;
    }

    public
    boolean isIn(E o) {
	return
	    false;
    }

    public
    LinkedList<E> remove(E o) {
	return
	    this;
    }

    public
    LinkedList<E> concat(LinkedList<E> l2) {
	return l2;
    }
}

//--------------------

class Node<E> extends LinkedList<E> {
    private
    E info;

    private
    LinkedList<E> next;

    Node(E info, LinkedList<E> next) {
	this.info = info;
	this.next = next;
    }

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

    public
    boolean isIn(E o) {
	return
	    info.equals(o)
	    ||
	    next.isIn(o);
    }

    public
    LinkedList<E> remove(E o) {
	if (info.equals(o))
	    return next;
	next = next.remove(o);
	return
	    this;
    }

    public
    LinkedList<E> concat(LinkedList<E> l2) {
	if (next.isEmpty())
	    next = l2;
	else
	    next = next.concat(l2);
	return
	    this;
    }
}

//--------------------