/**
  * 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 einen speziellen
 * Endeknoten repraesentiert, bei dem die info-Komponente
 * nie genutzt wird, die next-Komponente enthaelt die
 * ungueltige Referenz.
 *
 * 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

  protected
  E info;

  protected
  LinkedList<E> next;

  //--------------------
  //
  // Objekte werden nur in der Klasse erzeugt
  // die eigentlichen Konstruktoren sind
  // mkEmptyList und mkOne

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

  //--------------------
  //
  // mkEmptyList erzeugt immer ein neues Objekt.
  // Dieses wird durch die schwache Implementierung von
  // generics in Java notwendig.
  // Dieser Nachteil kann nur mit "unsave conversions"
  // umgangen werden.

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

  //--------------------
  //
  // mkOne ist in Analogie zu mkEmptyList
  // definiert worden

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

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

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

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

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

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

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

    return
      info;
  }

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

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

    return
      next;
  }

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

  public
  int len()
  {
    return
      isEmpty()
      ? 0
      : 1 + next.len();
  }

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

  public
  E at(int i)
    throws IndexOutOfBoundsException
  {
    if ( i < 0 || isEmpty() )
      throw
	new IndexOutOfBoundsException("illegal index into linked list");

    return
      ( i == 0 )
      ? hd()
      : next.at(i - 1);
  }

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

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

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

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

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

    return
      cons(o);
  }

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

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

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

    if ( info.equals(o) )
      return
	next;

    next = next.remove(o);
    // !!! Seiteneffekt
    // Liste wird veraendert

    return
      this;
  }

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

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

    if ( next.isEmpty() ) {
      next = l2;
    } else {
      next = next.concat(l2);
    }

    return
      this;
  }

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

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

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

  public
  String toString()
  {
    if ( isEmpty() )
      return
	"[]";

    return
      "[" + info.toString() + next.toString0();


  }

  private
  String toString0()
  {
    String s = "";
    if ( isEmpty() )
      return
	"]";

    return
      "," + info.toString() + next.toString0();
  }

  //--------------------
  // forall zur Verarbeitung aller Werte einer Liste

  public
  <Result> Result forall(Accumulate <E, Result> ac)
  {
    LinkedList<E> l1 = this;

    while ( ! l1.isEmpty() ) {
      ac.process(l1.info);
      l1 = l1.next;
    }

    return
      ac.getResult();
  }

  //--------------------
  // len implementiert mit forall

  public
  int len1()
  {
    // auto unboxing
    return
      forall(new NoOfElements<E>());
  }

  //--------------------
  // toString implementiert mit forall

  public
  String toString1()
  {
    return
      forall(new ToString <E>("[", ",", "]"));
  }

  //--------------------
  // len implementiert mit forall
  // und einer statischen lokalen Klasse
  // fuer das Kommando

  // Ziel:
  // Vermeidung von globalen Namen
  // fuer lokale Hilfsklassen

  public
  int len2()
  {
    return
      forall(new LocalNoOfElements <E> ());
  }

  //--------------------
  // Quelle hier nur aus Demozwecken aus der
  // globalen Klasse NoOfElements uebernommen

  static
  private
  class LocalNoOfElements <E>
    extends Accumulate <E, Integer>
  {
    int result = 0;

    public
    void process(E element)
      {
	++result;
      }

    public
    Integer getResult()
      {
	return
	  result;
      }
  }

  /*---------------------------------------------------------*/

}