class Bilkollektiv {
    final int AB;
    Bil[] alleBilene; // arrayen er full, men vi vet ikke rekkef?lgen 
    Bil start, slutt;  // lenkeliste med ledige biler

    Bilkollektiv(int ant) {
	AB = ant;
	alleBilene = new Bil[AB];
	start = slutt = null;

    }

    // alle biler i arrayen er ledige n?r vi oppretter lenkelisten, s? alle skal med
    void lagBilPris() {
        for (int i = 0; i < AB; i++) {
            this.leggTil(alleBilene[i]); // lager en hjelpemetode for ? sette inn alle bilene sortert, slik vi har l?rt
        }
    }

    void leggTil(Bil bil) {
        if (start == null) {
            start = slutt = bil;
        }

        else if (bil.PRIS < start.PRIS) {
            bil.neste = start;
            start.forrige = bil;
            start = bil;
        }

        else if (bil.PRIS > slutt.PRIS) {
            slutt.neste = bil;
            bil.forrige = slutt;
            slutt = bil;
        }

        else {
            Bil peker = start;
            // F?rbetingelse --> bil.PRIS > peker.PRIS OG bil.PRIS < slutt.PRIS --> vi vil derfor aldri f? at peker.neste == null

            while (peker.PRIS < bil.PRIS) {
                peker = peker.neste;
            }
            // Etterbetingelsen --> peker != null OG peker.PRIS > bil.PRIS
            peker.forrige.neste = bil;
            bil.forrige = peker.forrige;
            bil.neste = peker;
            peker.forrige = bil;
        }
    }
}

abstract class Bil {
    final String BILNUMMER;
    final int PRIS; // et positivt heltall
    Bil neste, forrige = null; // pekere

    Bil (String nr, int kr) {
        BILNUMMER = nr;  
        PRIS = kr;
    }

    Bil finnBilR(Dialog dialog, boolean kunElektrisk) { // Slik kan vi gj?re det med instanceof istedet for polymorfi
        // tre basistilfeller
        if (this instanceof Elektrisk && dialog.svarJaEllerNei("Liker du " + this + "?")) {
            return this;
        }
        if (!kunElektrisk && dialog.svarJaEllerNei("Liker du " + this + "?")) {
            return this;
        }
        if (neste == null) { // m? ta h?yde for at vi ikke finner en bil som brukeren liker 
            return null;
        }
        
        // ett rekursjonssteg
        return neste.finnBilR(dialog, kunElektrisk);
    }
    
}

interface Dialog {
    boolean svarJaEllerNei (String spoersmal);
}

interface Elektrisk {
    int hentBatterikapasitet ();
}