// Konteeksamen i IN1010 og INF1010 v?ren 2019
// L?sningsforslag og sensorveiledning oppgave 9-10


// Svaret p? oppgave 9 m? inneholde tegning av arrayen og de riktige objektene.


class Prio<E extends Comparable<E>> {
    Object[] alleO;
     // Om studenten deklarerer E[] alle0, b?r dette v?re like bra.
    int iBruk;
    int maxP, minP;
    
    Prio(int n) {
	// Dette er dessverre ikke lov:  alleO = new E[n];
	// og de b?r f? litt trekk for det siden akkurat dette har v?rt forelest.
        // Det er heller ikke lov ? skrive  (E[])new Object[n]
        // men dette b?r gi full uttelling fordi de har l?rt ? gj?re det s?nn, 
	// og det er m?ten ? gj?re det p? n?r E ikke er restriktert.
	// At dette ikke er lov, kan ikke studenten vite.

	// Studenter som har deklarert alleO av typen E[] vil naturlig nok 
	// ikke typekonvertere fra Object til E ved tilordning.
	// Dette er markert i l?sningsforslaget der typekonvertering er gjort.

	alleO = new Object[n];

	iBruk = 0;
	maxP = minP = 0; 
    }

    private int bak(int p) {
	if (p == alleO.length-1) return 0;
	return p+1;
    }

    private int foran(int p) {
	if (p == 0) return alleO.length-1;
	return p-1;
    }

    int antall() {
	return iBruk;
    }

    // Det er viktig at taUt returnerer elementet som maxP peker p?
    // og at det ikke gj?res noe flytting her.

    E taUt() {
	// NB! Helt greit ? anta at iBruk>0.
	E res = (E)alleO[maxP];   // For studenter som har typen E[] p? alleO,
	                          // er denne typekonverteringen ikke n?dvendig.
	iBruk--;
	maxP = bak(maxP);
	return res;
    }


    // settInn skal v?re en metode som flytter sm? elementer og 
    // setter det nye elementet inn p? riktig sted.

    void settInn(E e) {
	if (iBruk == 0) {
	    // Spesialbehandling av tom struktur:
	    alleO[0] = e;  iBruk = 1;
	    maxP = minP = 0;
	    return;
	}

	if (iBruk == alleO.length) {
	    // Beholderen er full:
	    if (e.compareTo((E)alleO[minP]) <= 0) { 
		// (Ikke typekonvertering hvis E[]-array.)
		// Det nye elementet er mindre enn alle i beholderen;
		// da er det ingenting ? gj?re.
		return;
	    }

	    // Ellers, fjern det minste elementet i beholderen:
	    minP = foran(minP);  iBruk--;
	}
	
	int p = minP;
	minP = bak(minP);
	while (true) {
	    if (p == foran(maxP)) {
		// Det nye elementet er st?rre enn alle i beholderen:
		alleO[bak(p)] = e;  iBruk++;
		return;
	    }

	    if (e.compareTo((E)alleO[p]) <= 0) { 
		// (Ikke typekonvertering hvis E[]-array.)
		// Det nye elementet skal bak p (og vi vet det er ledig plass):
		alleO[bak(p)] = e;  iBruk++;
		return;
	    }

	    // Flytt ned:
	    alleO[bak(p)] = alleO[p];
	    p = foran(p);
	}
    }


    // Det resterende er kun for testform?l.

    private void dump() {
	System.out.print(antall() + ":  ");
	for (int i = 0;  i < alleO.length;  i++) {
	    if (i == maxP) System.out.print("M:");
	    if (i == minP) System.out.print("m:");
	    System.out.print(alleO[i] + "  ");
	}
	System.out.println();
    }

    public static void main(String[] arg) {
	Prio<Integer> tab = new Prio<>(6);
	tab.dump();

	tab.settInn(17);  // tab.dump();
	tab.settInn(11);  // tab.dump();
	tab.settInn(11);
	tab.settInn(9);  tab.settInn(1);  tab.settInn(7);
	tab.dump();

	System.out.println("Ut: " + tab.taUt());
	System.out.println("Ut: " + tab.taUt());
	tab.dump();

	tab.settInn(0);   tab.dump();
	tab.settInn(10);  tab.dump();
	tab.settInn(20);  tab.dump();
	tab.settInn(-1);  tab.dump();
    }
}