/**
  * 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
 *
 * int dieser Klasse, die mit Generics arbeitet,
 * wird die eigentliche Liste durch eine Kette von
 * Knoten repraesentiert.Fuer die Knoten wird eine
 * lokale Klasse definiert, mit der wie in C mit Records
 * und Zeiger gearbeitet wird.
 *
 * die LinkedList-Klasse dient nur als Wrapper,
 * um die eigentliche C-aehnliche Implementierung zu
 * kapseln.
 *
 * Es wird also int einem C-Stil int Java programmiert.
 * Dieses ist bei Verwendung von Generics int Java auch
 * notwendig, da die leere Liste durch die null-Referenz
 * dargestellt wird.
 *
 * Dieser Ansatz wird fuer die Realisierung von
 * Baeumen aus Performanzgruenden noch viel wichtiger
 * als fuer Listen.
 *
 * die Routinen sind alle in rekursiver Form
 * die meisten Rekursionen sind Endrekursionen
 * oder lineare, koennen also einfach in Schleifen
 * transformiert werden
 *
 * in der Routine remove wird mit Seiteneffekten
 * gearbeitet, hier wird also der rein funktionale
 * Stil verlassen, um Kopieroperationen zu vermeiden
 *
 * die Konstruktoren sind nicht oeffentlich,
 * sie sind durch statische Methoden ersetzt
 *
 */

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

public class LinkedList<E> {

    //--------------------
    //
    // protected als Zugriffsattribut
    // erlaubt die schrittweise Erweiterung
    // der Menge der Methoden

    // die lokale Hilfsklasse fuer
    // die Knoten-Records

    protected static class Node<E> {
	protected E info;
	protected Node<E> next;

	protected Node(E e, Node<E> l) {
	    info = e;
	    next = l;
	}
    }

    protected Node<E> data;

    protected LinkedList () {
	data = null;
    }

    //--------------------
    //
    // mkEmptyList erzeugt immer ein neues Objekt
    // das Objekt fuer die leere Liste ist immer ein neues
    // Das Singleton Muster ist nicht anwendbar

    public static
	<E> LinkedList<E> mkEmptyList()
    {
	return
	    new LinkedList<E> ();
    }

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

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

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

    public
	boolean isEmpty()
    {
	return
	    data == null;
    }

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

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

	return
	    data.info;
    }

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

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

	data = data.next;
	return
	    this;
    }

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

    private
	int len(Node<E> l) {
	return
	    l == null
	    ? 0
	    : 1 + len(l.next);
    }

    public
	int len () {
	return
	    len(data);
    }

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

    private
	E at(Node<E> l, int i)
	throws IndexOutOfBoundsException
    {
	if (i < 0 || l == null)
	    throw
		new IndexOutOfBoundsException
		    ("illegal index into linked list");
	return
	    ( i == 0 )
	    ? l.info
	    : at(l.next, i - 1);
    }

    public
	E at(int i)
	throws IndexOutOfBoundsException
    {
	return
	    at(data, i);
    }

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

    private
	boolean isIn(E e, Node<E> l) {
	return
	    ( l != null )
	    &&
	    ( l.info.equals(e)
	      ||
	      isIn(e, l.next) );
    }

    public
	boolean isIn(E e) {
	return
	    isIn(e, data);
    }

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

    /**
     * erzeugt eine neue Liste
     * die das Objekt o enthaelt
     */

    public
	LinkedList<E> insert(E e)
    {
	if ( isIn(e) )
	    return
		this;
	return
	    cons(e);
    }

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

    /**
     * erzeugt eine neue Liste
     * die das Objekt e nicht mehr enthaelt
     */

    private
	Node<E> remove(E e, Node<E> l) {
	if ( l == null )
	    return
		l;

	if ( l.info.equals(e) )
	    return
		l.next;

	l.next = remove(e, l.next);

	// !!! Seiteneffekt
	// Liste wird veraendert

	return
	    l;
    }

    public
	LinkedList<E> remove(E e) {
	data = remove(e,data);
	return
	    this;
    }
}