import java.util.*;
/**
 * AlgoDat SS00 Aufgabe 49
 * Datentyp Deque, Testklasse
 * 
 * @author Christian Semrau, 29.04.2000
 * <a href="mailto:Christian.Semrau@student.uni-magdeburg.de">
 * Christian.Semrau@student.uni-magdeburg.de</a>
 */
class ChS_Aufg49 {
    static Deque deque;
/**
 * Starts the application.
 * @param args an array of command-line arguments
 */
public static void main(java.lang.String[] args) {
    deque = new ListDeque();
//    deque = new ArrayDeque();

    String[] sa = new String[]{"A", "B", "C", "D"};
    Integer[] ia = new Integer[30];
    for (int i = 0; i<ia.length; i++) ia[i] = new Integer(i);

    System.out.println("Beginn: "+deque);

    System.out.println("Iterator: Laenge "+deque.size());
    for (Iterator i = deque.iterator(); i.hasNext(); )
        System.out.print(i.next()+", ");
    System.out.println();

    for (int i=0; i<sa.length; i++){
        deque.insertFirst(sa[i]);
    }
    System.out.println("Nach Einfuegen: "+deque);

    System.out.println("Gepoppt: "+deque.removeLast()+", Rest:"+ deque);

    System.out.println("Iterator: Laenge "+deque.size());
    for (Iterator i = deque.iterator(); i.hasNext(); )
        System.out.print(i.next()+", ");
    System.out.println();
    System.out.println("Enumeration:");
    for (Enumeration e = deque.elements(); e.hasMoreElements(); )
        System.out.print(e.nextElement()+", ");
    System.out.println();
}
}

    // -------------------------
    // -- DAS INTERFACE Deque --
    // -------------------------

//import java.util.*;
/**
 * AlgoDat SS00 Aufgabe 49
 * Interface fuer Deque
 * 
 * @author Christian Semrau, 29.04.2000
 * <a href="mailto:Christian.Semrau@student.uni-magdeburg.de">
 * Christian.Semrau@student.uni-magdeburg.de</a>
 */
interface Deque {
/** Leert die Deque. */
public void clear();
/** Liefert eine Enumeration fuer die Deque. */
public Enumeration elements();
/** Liefert true, wenn die Deque leer ist. */
boolean empty();
/** Liefert das erste Element ohne es zu entfernen. */
public Object getFirst();
/** Liefert das letzte Element ohne es zu entfernen. */
public Object getLast();
/** Fuegt das Objekt vorn an die Deque an. */
public void insertFirst(Object o);
/** Fuegt das Objekt hinten an die Deque an. */
public void insertLast(Object o);
/** Liefert einen Iterator fuer die Deque. */
public Iterator iterator();
/** Liefert das erste Element und entfernt es. */
public Object removeFirst();
/** Liefert das letzte Element und entfernt es. */
public Object removeLast();
/** Liefert die Anzahl der Elemente in der Deque. */
public int size();
}

    // ------------------------------------
    // -- IMPLEMENTIERUNG ALS ArrayDeque --
    // ------------------------------------

//import java.util.*;
/**
 * AlgoDat SS00 Aufgabe 49
 * Datentyp Deque
 * implementiert mit einem Array unbegrenzter Groesse
 * 
 * @author Christian Semrau, 29.04.2000
 * <a href="mailto:Christian.Semrau@student.uni-magdeburg.de">
 * Christian.Semrau@student.uni-magdeburg.de</a>
 */
class ArrayDeque implements Deque{
  private Object[] feld;  // das Feld das die Daten enthaelt
  private int offset, length;  // Beginn und Laenge des Datenbereichs
  private int loadstep;  // Schrittweite der Vergroesserung
  private int modCount = 0;  // zaehlt die Veraenderungen der Deque,
  // macht den Iterator "sicher", indem der Iterator beim Feststellen
  // einer Veraenderung mit einer ConcurrentModificationException abbricht

/**
 * Legt eine leere Deque an.
 */
public ArrayDeque() {
    loadstep=10; feld=new Object[2*loadstep];
    offset=loadstep; length=0;
}

/**
 * Leert die Deque.
 */
public void clear(){
    modCount++;
    offset = feld.length/2; length = 0;
    for (int i=0; i<feld.length; )
          feld[i++] = null;  // gibt die Objekte frei fuer den GC
}

private void del(int I){
    if (I<0 || I>=length)
        throw new IllegalArgumentException(I+" ausserhalb des Bereichs");
    if (I==0){ feld[offset++] = null; length--;
    }else
    if (I==length-1){ feld[offset+(--length)] = null;
    }else{
        // dieser Fall tritt in dieser Klasse nicht auf,
        // die Methode stammt in dieser Form aus der Sequenz-Klasse
        System.arraycopy(feld,offset+I+1, feld,offset+I, length-I-1);
        feld[offset+(--length)] = null;
    }
}

/**
 * Liefert eine Enumeration fuer dieses Objekt.
 * Waehrend der Verwendung einer Enumeration darf das Objekt
 * nicht veraendert werden - das Verhalten ist sonst undefiniert.
 */
public Enumeration elements() {
    return new Enumeration(){
        int count = 0;
        public boolean hasMoreElements(){
            return count < length;
        }
        public Object nextElement(){
            if (count < length)
                return feld[offset+count++];
            else
                throw new NoSuchElementException();
        }
    };
}

/**
 * 
 */
public boolean empty() {
    return size()<=0;
}

/**
 * Liefert das erste Objekt der Deque.
 */
public Object getFirst() {
    if (length==0)
        throw new NoSuchElementException();
    return feld[offset];
}

/**
 * Liefert das letzte Objekt der Deque.
 */
public Object getLast() {
    if (length==0)
        throw new NoSuchElementException();
    return feld[offset+length-1];
}

/**
 * Fuegt das Objekt vorn an die Deque an.
 */
public void insertFirst(Object x){
    modCount++;
    if (offset<=0) resize();
    feld[--offset] = x; length++;
}

/**
 * Fuegt das Objekt hinten an die Deque an.
 */
public void insertLast(Object x){
    modCount++;
    if (offset+length>=feld.length) resize();
    feld[offset+(length++)] = x;
}

/**
 * Liefert einen Iterator fuer dieses Objekt.
 * Wird waehrend der Verwendung eines Iterators das Objekt veraendert,
 * dann bricht der Iterator beim naechsten Aufruf von next mit einer
 * ConcurrentModificationException ab.
 */
public Iterator iterator() {
    return new Iterator(){
        int count = 0;
        int expectedModCount = modCount;
        public boolean hasNext(){
            return count < length;
        }
        public Object next(){
            if (count < length){
                try{
                    Object obj = feld[offset+count++];
                    checkForComodification();
                    return obj;
                } catch(IndexOutOfBoundsException e) {
                    checkForComodification();
                    throw new NoSuchElementException();
                }
            }else{
                checkForComodification();
                throw new NoSuchElementException();
            }
        }
        public void remove(){
            throw new UnsupportedOperationException();
        }
        final void checkForComodification() {
            if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        }
    };
}

/**
 * Liefert das erste Element und entfernt es aus der Deque.
 */
public Object removeFirst() {
    modCount++;
    Object obj = getFirst();
    del(0);
    return obj;
}

/**
 * Liefert das letzte Element und entfernt es aus der Deque.
 */
public Object removeLast() {
    modCount++;
    Object obj = getLast();
    del(length-1);
    return obj;
}

private void resize() {
    int l = loadstep>0 ? loadstep : (length+2);
    Object[] feld2 = new Object[length+2*l];
    System.arraycopy(feld,offset, feld2,l, length);
    feld = feld2; offset=l;
}

/**
 * Liefert die Anzahl der Elemente in der Deque.
 */
public int size() {
    return length;
}

/**
 * Liefert eine Stringdarstellung der Deque.
 */
public String toString() {
    StringBuffer sb = new StringBuffer();
    sb.append("[");
    if (length>0) sb.append(feld[offset]);
    for (int i=offset+1; i<offset+length; i++)
        sb.append(",").append(feld[i]);
    sb.append("]");
//    sb.append("-(").append(offset+","+length+","+feld.length).append(")");
    return sb.toString();
}
}

    // -----------------------------------
    // -- IMPLEMENTIERUNG ALS ListDeque --
    // -----------------------------------

//import java.util.*;
/**
 * AlgoDat SS00 Aufgabe 49
 * Datentyp Deque
 * implementiert mit einer doppelt verketteten Liste
 * 
 * @author Christian Semrau, 29.04.2000
 * <a href="mailto:Christian.Semrau@student.uni-magdeburg.de">
 * Christian.Semrau@student.uni-magdeburg.de</a>
 */
class ListDeque implements Deque {
    private ListElement begin;  // Anfang der Deque
    private ListElement end;    // Ende der Deque
    private int elementCount;   // Anzahl der Elemente
    private int modCount = 0;   // Anzahl der Veraenderungen

/**
 * Erzeugt eine leere Deque.
 */
public ListDeque() {
    begin = end = null; elementCount = 0;
}

/**
 * Leert die Deque.
 */
public void clear() {
    modCount++;
    begin = end = null; elementCount = 0;
}

/**
 * Liefert eine Enumeration.
 * Veraenderung des Objekts waehrend der Verwendung einer Enumeration
 * fuehrt zu undefiniertem Verhalten!
 */
public Enumeration elements() {
    return new Enumeration(){
        ListElement theNext = begin;
        public boolean hasMoreElements(){
            return theNext!=null;
        }
        public Object nextElement(){
            if (theNext==null)
                throw new NoSuchElementException();
            Object obj = theNext.data;
            theNext = theNext.next;
            return obj;
        }
    };
}

/**
 * 
 */
public boolean empty() {
    return size()<=0;
}

/**
 * Liefert das erste Element der Deque ohne es zu entfernen.
 */
public Object getFirst() {
    if (begin==null)
        throw new NoSuchElementException();
    return begin.data;
}

/**
 * Liefert das letzte Element der Deque ohne es zu entfernen.
 */
public Object getLast() {
    if (end==null)
        throw new NoSuchElementException();
    return end.data;
}

/**
 * Fuegt das Objekt an den Anfang der Deque.
 */
public void insertFirst(Object o) {
    modCount++;
    if (begin != null)
        begin = begin.createPre(o);
    else
        begin = end = new ListElement(o);
    elementCount++;
}

/**
 * Fuegt das Objekt ans Ende der Deque.
 */
public void insertLast(Object o) {
    modCount++;
    if (end != null)
        end = end.createNext(o);
    else
        begin = end = new ListElement(o);
    elementCount++;
}

/**
 * Wird waehrend der Verwendung eines Iterators das Objekt veraendert,
 * dann bricht der Iterator beim naechsten Aufruf von next mit einer
 * ConcurrentModificationException ab.
 */
public Iterator iterator() {
    return new Iterator(){
        ListElement theNext = begin;
        int expectedModCount = modCount;
        public boolean hasNext(){
            return theNext!=null;
        }
        public Object next(){
            if (theNext!=null){
                try{
                    Object obj = theNext.data;
                    theNext = theNext.next;
                    checkForComodification();
                    return obj;
                } catch(NullPointerException e) {
                    checkForComodification();
                    throw new NoSuchElementException();
                }
            }else{
                checkForComodification();
                throw new NoSuchElementException();
            }
        }
        public void remove(){
            throw new UnsupportedOperationException();
        }
        final void checkForComodification() {
            if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        }
    };
}

/**
 * Liefert das erste Element der Deque und entfernt es.
 */
public Object removeFirst() {
    modCount++;
    Object obj = getFirst();
    begin = begin.next;
    if (begin!=null)
        begin.pre = null;
    else
        end = null;
    elementCount--;
    return obj;
}

/**
 * Liefert das letzte Element der Deque und entfernt es.
 */
public Object removeLast() {
    modCount++;
    Object obj = getLast();
    end = end.pre;
    if (end!=null)
        end.next = null;
    else
        begin = null;
    elementCount--;
    return obj;
}

/**
 * Liefert die Anzahl der Elemente.
 */
public int size() {
    return elementCount;
}

/**
 * Returns a String that represents the value of this object.
 */
public String toString() {
    StringBuffer sb = new StringBuffer("[");
    if (begin!=null){
        for (ListElement e = begin; e!=null; e = e.next){
            sb.append(e.toString());
            if (e.next!=null)
                sb.append(",");
        }
    }
    sb.append("]");
//    sb.append("-(").append(size()).append(")");
    return sb.toString();
}
}

    // -----------------------------
    // -- HILFSKLASSE ListElement --
    // -----------------------------

/**
 * AlgoDat SS00 Aufgabe 49
 * die Elemente der doppelt verketteten Liste
 * 
 * @author Christian Semrau, 16.05.2000
 * <a href="mailto:Christian.Semrau@student.uni-magdeburg.de">
 * Christian.Semrau@student.uni-magdeburg.de</a>
 */
class ListElement {

    // einfache oder detaillierte toString()-Methode
    static boolean verbose = false;
    private static int counter = 0;
    // identifiziert die Elemente fuer die ausfuehrliche Darstellung
    private int myIndex;

    // die Daten des Elements
    Object data;
    // Vorgaenger
    ListElement pre;
    // Nachfolger
    ListElement next;

/**
 * Erzeugt ein neues ListElement.
 * pre und next werden auf null gesetzt.
 * @param o die Daten des neuen Elements
 */
public ListElement(Object o) {
    this(o, null, null);
}

/**
 * Erzeugt ein neues ListElement.
 * @param d die Daten des neuen Elements
 * @param p der Vorgaenger
 * @param n der Nachfolger
 */
public ListElement(Object d, ListElement p, ListElement n){
    myIndex = ++counter;
    data = d;
    pre = p;
    next = n;
}

/**
 * Erzeugt ein neues ListElement, das als next an dieses angehaengt wird.
 * Der Vorgaender des neu erzeugten Elements wird auf this gesetzt.
 * @return das neu erzeugte ListElement, also this.next
 * @param d das Daten-Object
 */
public ListElement createNext(Object o) {
    ListElement n = new ListElement(o, this, null);
    next = n;
    return n;
}

/**
 * Erzeugt ein neues ListElement, das als pre an dieses angehaengt wird.
 * Der Nachfolger des neu erzeugten Elements wird auf this gesetzt.
 * @return das neu erzeugte ListElement, also this.pre
 * @param d das Daten-Object
 */
public ListElement createPre(Object o) {
    ListElement p = new ListElement(o, null, this);
    pre = p;
    return p;
}

public void setNext(ListElement e){
    next = e;
}
public void setPre(ListElement e){
    pre = e;
}
public ListElement getNext(){
    return next;
}
public ListElement getPre(){
    return pre;
}
public Object getElement(){
    return data;
}
public void setElement(Object o){
    data = o;
}

/**
 * Liefert eine String-Repraesentation dieses Objekts.
 * Wenn verbose==true, werden zusaetzlich interne Daten angezeigt.
 */
public String toString(){
    StringBuffer sb = new StringBuffer();
    if (verbose) sb.append("[").append(myIndex).append(",(");
    sb.append(data.toString());
    if (verbose){
        sb.append(")");
        if (pre!=null) sb.append(",pre:").append(pre.myIndex);
        if (next!=null) sb.append(",next:").append(next.myIndex);
        sb.append("]");
    }
    return sb.toString();
}
}