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

    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 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
        while (h != null){
            if (h.getElement().equals(x)){  // wenn gefunden
                h.incAccessCounter();
                if (prev.getAccessCounter() < h.getAccessCounter()){
                // nur sortieren, wenn es noetig ist
                    prev.setNext(h.getNext());  // h aus Liste entfernen
                    insertion(h);  // h sortiert einfuegen
                }
                return h.getElement();
            }
            prev = h;
            h = h.getNext();
        }
        return null;  // nicht gefunden
    }

    // fuegt h nach accessCounter sortiert in die Liste ein
    private void insertion(SingleListElement h){
        SingleListElement x = head, xnext;
        if (head.getAccessCounter() <= h.getAccessCounter()){
            // h muss oder kann vor head eingefuegt werden
            h.setNext(head);
            head = h;
            return;
        }
        while (x != null){
            xnext = x.getNext();  // Nachfolger bestimmen und merken
            if (xnext == null ||
            xnext.getAccessCounter() <= h.getAccessCounter()){
                // einfuegen, wenn kein Nachfolger mehr existiert, oder
                // die Zugriffszaehler passen
                h.setNext(xnext);
                x.setNext(h);
                return;
            }
            x = xnext;  // mit x weiterwandern
        }
    }

    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_Aufg50c{
    public static void main(String args[]) {
        FrequencyList list=new FrequencyList();
        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);
    }
}