/**
 * AlgoDat SS00 Aufgabe 50
 * Selbstanordnende Liste
 * Gefundenes Element wird mit Vorgaenger vertauscht
 *
 * @author Laura Marnitz, Christian Semrau, 16.05.2000
 * <a href="mailto:gemrau@cs.uni-magdeburg.de">gsemrau@cs.uni-magdeburg.de</a>
 */
class TransposeList {

    private SingleListElement head = null;
    private int size = 0;

    // kein Konstruktor --> parameterloser Standardkonstruktor wird
    // automatisch erzeugt

    public void insert(Object x){
        SingleListElement y = new SingleListElement(x, head);
        head = y;
        size++;
    }

    public Object findElement(Object x){
        SingleListElement preprev, prev, h = head;
        if (h == null)  // leere Liste
            return null;
        // die Liste ist nicht leer
        if (h.getElement().equals(x))  // an erster Stelle gefunden
           return h.getElement();
        h = h.getNext();
        if (h == null)  // schon am Ende der Liste und nicht gefunden
            return null;
        // das erste Element wars nicht, h zeigt auf das existierende zweite
        if (h.getElement().equals(x)){  // gefunden an zweiter Stelle
            transpose(null, head, h);  // mit erstem Element tauschen
            return h.getElement();
        }
        preprev = head;
        prev = h;
        h = h.getNext();
        // noch nicht gefunden, h zeigt auf das dritte
        while (h != null){  // solange h auf ein Element zeigt
            if (h.getElement().equals(x)){
                transpose(preprev, prev, h);
                return h.getElement();
            }
            preprev = prev;
            prev = h;
            h = h.getNext();  // schrittweise mit allen drei Zeigern...
            // die Liste durchwandern
        }
        return null; //nicht gefunden
    }

    // Vertauscht prev und h miteinander.
    // Falls preprev==null, wird angenommen, dass prev==head
    private void transpose(SingleListElement preprev,
    SingleListElement prev, SingleListElement h){
        prev.setNext(h.getNext());
        h.setNext(prev);
        if (preprev == null)
            head = h;
        else           
            preprev.setNext(h);
    }
  
    public String toString(){
        String s = "";
        SingleListElement h = head;
        s += "size: "+size+"\n";
        while (h != null){
            s += h.getElement()+"\n";
            h = h.getNext();
        }
        return s;
    }    
}

/**
 * AlgoDat SS00 Aufgabe 50
 * Selbstanordnende Liste
 * Testklasse
 */
public class ChS_Aufg50b{
    public static void main(String args[]) {
        TransposeList list=new TransposeList();
        list.insert(new Integer(4));
        list.insert(new Integer(3));
        list.insert(new Integer(2));
        list.insert(new Integer(1));
        list.findElement(new Integer(4));
        list.findElement(new Integer(2));
        System.out.println(list);
    }
}