/**
 * AlgoDat SS00 Aufgabe 50
 * Selbstanordnende Liste
 * Elemente werden entsprechend der Zugriffshaeufigkeit sortiert
 *
 * @author Christian Semrau, 17.05.2000
 * <a href="mailto:gemrau@cs.uni-magdeburg.de">gsemrau@cs.uni-magdeburg.de</a>
 */
class FrequencyList2 {

    // Kopf der Liste
    private SingleListElement head = null;
    // Groesse der Liste
    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){
        // laststep zeigt jeweils auf das Element,
        // das den naechstgroesseren Zaehler hat,
        // prev ist der Vorgaenger von h, h ist das aktuelle Element
        SingleListElement laststep = null, prev, h = head;

        if (h == null)  // leere Liste
            return null;
        if (h.getElement().equals(x)){  // an erster Stelle gefunden
            h.incAccessCounter();
            return h.getElement();
        }
        prev = h;
        h = h.getNext();
        // h zeigt auf das zweite Element (falls es existiert)

        while (h != null){
            if (prev.getAccessCounter() != h.getAccessCounter())
                laststep = prev;
            if (h.getElement().equals(x)){  // wenn gefunden
                h.incAccessCounter();
                if (laststep==null){
                    // tritt auf, wenn das Element nach ganz vorn muss
                    prev.setNext(h.getNext());
                    h.setNext(head);
                    head = h;
                }else
                if (laststep != prev){
                    // nur umsortieren, wenn wir muessen
                    prev.setNext(h.getNext());
                    h.setNext(laststep.getNext());
                    laststep.setNext(h);
                }
                return h.getElement();
            }
            prev = h;
            h = h.getNext();
        }
        return null;  // nicht gefunden
    }

    public String toString(){
        String s = "";
        SingleListElement h = head;
        s += "size: "+size+"\n";
        while (h != null){
            s += h.getElement() + ", Zugriffe: "+h.getAccessCounter()+"\n";
            h = h.getNext();
        }
        return s;
    }    
}

/**
 * AlgoDat SS00 Aufgabe 50
 * Selbstanordnende Liste
 * Testklasse
 */
public class ChS_Aufg50c2{
    public static void main(String args[]) {
        FrequencyList2 list=new FrequencyList2();
        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);
    }
}