/**
  * 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 ungueltige Referenz wird durch
 * eine spezielle Referenz repraesentiert
 * die beim Laden der Klasse erzeugt wird
 *
 * 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
 */

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

public
class LinkedList {

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

  protected static final
  LinkedList empty = new LinkedList(null, null);

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

  protected
  Object info;

  protected
  LinkedList next;

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

  protected
  LinkedList(Object info, LinkedList next)
  {
    this.info = info;
    this.next = next;
  }

  //--------------------
  //
  // mkEmptyList erzeugt kein neues Objekt
  // das Objekt fuer die leere Liste ist immer dasgleiche

  public static
  LinkedList mkEmptyList()
  {
    return
      empty;
  }

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

  public static
  LinkedList mkOne(Object info)
  {
    return
      new LinkedList(info, empty);
  }

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

  public
  LinkedList cons(Object info)
  {
    return
	new LinkedList(info, this);
  }

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

  public
  boolean isEmpty()
  {
    return
      this == empty;
  }

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

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

    return
      info;
  }

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

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

    return
      next;
  }

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

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

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

  public
  Object 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(Object o)
  {
    return
      ! isEmpty()
      &&
      ( info.equals(o)
	||
	next.isIn(o) );
  }

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

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

  public
  LinkedList insert(Object o)
  {
    if ( isIn(o) )
      return
	this;

    return
      cons(o);
  }

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

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

  public
  LinkedList remove(Object o)
  {
    if ( isEmpty() )
      return
	this;

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

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

    return
      this;
  }

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

  public
  LinkedList concat(LinkedList l2)
  {
    if ( isEmpty() )
      return
	l2;

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

    return
      this;
  }

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

  public
  LinkedList append(Object 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
  Object forall(Accumulate ac)
  {
    LinkedList l1 = this;

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

    return
      ac.getResult();
  }

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

  public
  int len1()
  {
    return
      ((Integer)
       forall(new NoOfElements())
	).intValue();
  }

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

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

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

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

  public
  int len2()
  {
    return
      ((Integer)
       forall(new LocalNoOfElements())
	).intValue();
  }

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

  static
  private
  class LocalNoOfElements
    extends Accumulate
  {
    int result;

    LocalNoOfElements() {
      result = 0;
    }

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

    public
    Object getResult()
      {
	return
	  new Integer(result);
      }
  }
}