/**
 * <p>
 * Materialien zu den zentralen NRW-Abiturpruefungen im Fach Informatik ab 2018
 * </p>
 * <p>
 * Generische Klasse Queue<ContentType>
 * </p>
 * <p>
 * Objekte der generischen Klasse Queue (Warteschlange) verwalten beliebige
 * Objekte vom Typ ContentType nach dem First-In-First-Out-Prinzip, d.h., das
 * zuerst abgelegte Objekt wird als erstes wieder entnommen. Alle Methoden haben
 * eine konstante Laufzeit, unabhaengig von der Anzahl der verwalteten Objekte.
 * </p>
 * 
 * @author Qualitaets- und UnterstuetzungsAgentur - Landesinstitut fuer Schule
 * @version Generisch_02 2014-02-21
 */
public class Queue<ContentType> {
  
  /* --------- Anfang der privaten inneren Klasse -------------- */
  
  private class QueueNode {

    private ContentType content = null;
    private QueueNode nextNode = null;

    /**
     * Ein neues Objekt vom Typ QueueNode<ContentType> wird erschaffen. 
     * Der Inhalt wird per Parameter gesetzt. Der Verweis ist leer.
     * 
     * @param pContent das Inhaltselement des Knotens vom Typ ContentType
     */
    public QueueNode(ContentType pContent) {
      content = pContent;
      nextNode = null;
    }

    /**
     * Der Verweis wird auf das Objekt, das als Parameter uebergeben wird,
     * gesetzt.
     * 
     * @param pNext der Nachfolger des Knotens
     */
    public void setNext(QueueNode pNext) {
      nextNode = pNext;
    }
    
    /**
     * Liefert das naechste Element des aktuellen Knotens.
     * 
     * @return das Objekt vom Typ QueueNode, auf das der aktuelle Verweis zeigt
     */
    public QueueNode getNext() {
      return nextNode;
    }

    /**
     * Liefert das Inhaltsobjekt des Knotens vom Typ ContentType.
     * 
     * @return das Inhaltsobjekt des Knotens
     */
    public ContentType getContent() {
      return content;
    }
    
  }
  
  /* ----------- Ende der privaten inneren Klasse -------------- */
  
  private QueueNode head;
  private QueueNode tail;

  /**
   * Eine leere Schlange wird erzeugt. 
   * Objekte, die in dieser Schlange verwaltet werden, muessen vom Typ
   * ContentType sein.
   */
  public Queue() {
    head = null;
    tail = null;
  }

  /**
   * Die Anfrage liefert den Wert true, wenn die Schlange keine Objekte enthaelt, 
   * sonst liefert sie den Wert false.
   * 
   * @return true, falls die Schlange leer ist, sonst false
   */
  public boolean isEmpty() {
    return head == null;
  }

  /**
   * Das Objekt pContentType wird an die Schlange angehaengt. 
   * Falls pContentType gleich null ist, bleibt die Schlange unveraendert.
   * 
   * @param pContent
   *            das anzuhaengende Objekt vom Typ ContentType
   */
  public void enqueue(ContentType pContent) {
    if (pContent != null) {
      QueueNode newNode = new QueueNode(pContent);
      if (this.isEmpty()) {
        head = newNode;
        tail = newNode;
      } else {
        tail.setNext(newNode);
        tail = newNode;
      }
    }
  }

  /**
   * Das erste Objekt wird aus der Schlange entfernt. 
   * Falls die Schlange leer ist, wird sie nicht veraendert.
   */
  public void dequeue() {
    if (!this.isEmpty()) {
      head = head.getNext();
      if (this.isEmpty()) {
        head = null;
        tail = null;
      }
    }
  }

  /**
   * Die Anfrage liefert das erste Objekt der Schlange. 
   * Die Schlange bleibt unveraendert. 
   * Falls die Schlange leer ist, wird null zurueckgegeben.
   *
   * @return das erste Objekt der Schlange vom Typ ContentType oder null,
   *         falls die Schlange leer ist
   */
  public ContentType front() {
    if (this.isEmpty()) {
      return null;
    } else {
      return head.getContent();
    }
  }
}
