IN1010

Cheat Sheet

Formler, begreper og oppsummering

Objektorientert programmering

eksamenssett.no

Formler

Klassehierarki

•abstract class Over { final int felt; Over(int felt) { this.felt = felt; } abstract int metode(); }
•class Under extends Over implements Grensesnitt { ... }
•Under(int a, int b) { super(a); this.egen = b; } // super() MÅ stå først
•interface Navn { returtype metode(); } // implisitt public abstract
•Deklarer felt som ikke skal endres som final - gir uttrykkelig pluss i sensurveiledningen

Polymorfi og typekonvertering

•Deklarert type bestemmer hva du KAN kalle; faktisk type bestemmer HVILKEN kode som kjører
•if (p instanceof Undertype) { Undertype u = (Undertype) p; ... }
•Oppkasting er alltid trygt; nedkasting uten instanceof gir ClassCastException
•Felt bindes statisk etter deklarert type - bare metoder bindes dynamisk
•public String toString() { return "Navn " + super.toString(); } // super. hindrer StackOverflowError

Lenket liste - pekerne ligger i dataobjektet

•Legg til sist: if (siste == null) { forste = siste = ny; } else { siste.neste = ny; ny.forrige = siste; siste = ny; }
•

Nøkkelformler per tema

Arv og polymorfisme

•abstract class Over { abstract int metode(); }
•Under(par) { super(par); this.eget = ...; } // super() først
•if (p instanceof Under) { Under u = (Under) p; ... }
•Dynamisk binding: deklarert type bestemmer hva du kan kalle, faktisk type bestemmer hva som kjører

Grensesnitt og abstrakte klasser

•class A extends B implements C, D { ... } // extends før implements
•Comparable: int compareTo(T annen) -> negativ / 0 / positiv
•Iterable: Iterator iterator(); Iterator: boolean hasNext(), T next()
•Runnable: void run()

Generics

•static > T storst(T a, T b) { ... } // generisk metode
•void les(Iterable b) / void skriv(Beholder b)
•new Beholder<>() // diamantnotasjon; new T() og new T[n] er ulovlig

Lenkede lister og datastrukturtegning

•Innsetting sist: if (siste == null) { forste = siste = ny; } else { siste.neste = ny; ny.forrige = siste; siste = ny; }

Vanlige feil å unngå

Arv og polymorfisme

•Glemmer super(...) eller plasserer det ikke først, slik at koden ikke kompilerer.
•Tror at felt bindes dynamisk - felt bindes etter deklarert type, bare metoder bindes dynamisk.
•Kaster ned uten instanceof-test og får ClassCastException.
•Lager objekter av den abstrakte toppklassen, som oppgaven eksplisitt sier ikke skal finnes.
•Tegner piler nedover fra superklassen i stedet for opp fra subklassene.

Grensesnitt og abstrakte klasser

•Glemmer public på metoden som implementerer grensesnittet.
•Prøver å legge instansvariabler i et grensesnitt - bare konstanter er lov.
•Skriver implements før extends, eller bruker extends mot et grensesnitt fra en klasse.
•Tester med instanceof inne i en metode som tar grensesnittet som parameter, i stedet for å bare kalle metoden.
•Implementerer bare noen av grensesnittets metoder uten å erklære klassen abstract.

Generics

•Skriver uten extends og prøver deretter å bruke superklassens felt inne i klassen.
•Tror at Beholder kan brukes der det står Beholder.

Eksamenstips

Arv og polymorfisme

•Oppgave 1 og 2 gir til sammen 20 av 100 poeng og er de enkleste på settet - ta dem raskt og riktig.
•super(...) må stå som første setning i konstruktøren; det er et eget poengkriterium i sensurveiledningen.
•Er superklassen abstrakt? Står det at alt materiell er enten A eller B, skal toppklassen være abstract.
•Legg neste- og forrige-pekerne i den abstrakte toppklassen, slik at hele hierarkiet kan lenkes sammen.
•På tegningen: piler oppover mot superklassen, grensesnitt tegnet som grensesnitt, alle klassene med.

Grensesnitt og abstrakte klasser

•Står det uttrykkelig at en egenskap skal programmeres som et interface, så gjør nøyaktig det - ikke lag en subklasse i stedet.
•Husk public foran metodene når du implementerer et grensesnitt; uten blir det kompileringsfeil.
•Bruk grensesnittet som parametertype og kall metoden uten instanceof - det er nettopp poenget sensor ser etter.
•En abstrakt mellomklasse kan implementere grensesnittet én gang for alle subklassene.
•Grensesnittet må tegnes som grensesnitt i oppgave 1, ikke som en vanlig klasse.

Generics

•Eksamensformen er - uten begrensningen får du ikke bruke superklassens felt.

Legg til først: ny.neste = forste; if (forste != null) forste.forrige = ny; forste = ny; if (siste == null) siste = ny;

•Ta ut (toveis), del 1: if (ut.forrige == null) forste = ut.neste; else ut.forrige.neste = ut.neste;

•Ta ut (toveis), del 2: if (ut.neste == null) siste = ut.forrige; else ut.neste.forrige = ut.forrige;

•Sett inn foran: ny.neste = gammel; ny.forrige = gammel.forrige; if (gammel.forrige == null) forste = ny; else gammel.forrige.neste = ny; gammel.forrige = ny;

•Gjennomløping: for (T p = forste; p != null; p = p.neste) { ... }

•Sammenlign identifikatorer med equals, aldri med ==

Array med instanceof og cast

•Steg 1 - tell: int n = 0; for (T p = forste; p != null; p = p.neste) if (p instanceof U) n++;
•Steg 2 - opprett: U[] ut = new U[n];
•Steg 3 - fyll: int i = 0; for (T p = forste; p != null; p = p.neste) if (p instanceof U) ut[i++] = (U) p;
•ut.length er et felt (uten parenteser); indeksene går fra 0 til length-1
•new int[n] gir n nuller; new U[n] gir n null-referanser

Iterator

•class Beholder implements Iterable { public Iterator iterator() { return new MinIt(); } }
•private class MinIt implements Iterator { T peker = forste; }
•public boolean hasNext() { return peker != null; } // må ALDRI flytte pekeren
•public T next() { if (peker == null) throw new NoSuchElementException(); T ut = peker; peker = peker.neste; return ut; }
•Filtrerende iterator: kall en finnNeste()-hjelpemetode både i konstruktøren og etter hvert framrykk
•for (T x : beholder) tilsvarer Iterator it = beholder.iterator(); while (it.hasNext()) { T x = it.next(); ... }

Generics

•class Beholder { T felt; void settInn(T t) { ... } T hentUt() { ... } }
•class KolonneG { T forste, siste; } // begrenset typeparameter
•static > T storst(T a, T b) { return a.compareTo(b) >= 0 ? a : b; }
•PECS: les fra Iterable, skriv til Beholder
•Beholder_{er IKKE en Beholder; new T() og new T[n] er ulovlig (type erasure)}

Unntak

•class MittUnntak extends Exception { MittUnntak(String m) { super(m); } } // checked, krever throws
•class MittRT extends RuntimeException { MittRT(String m) { super(m); } } // unchecked
•void m() throws MittUnntak { if (galt) throw new MittUnntak("tekst"); }
•try { ... } catch (Spesifikk e) { ... } catch (Exception e) { ... } finally { ... }
•Mest spesifikke catch først; multi-catch: catch (A | B e)
•finally kjøres alltid; kast unntaket FØR datastrukturen endres
•e.getMessage() gir teksten fra super(...); Error skal aldri fanges

Rekursjon

•I dataobjektet: int resten() { if (neste == null) return egen; return Math.max(egen, neste.resten()); }
•Startermetode i beholderen: if (forste == null) return null; return forste.resten();
•Leting: if (treff) return this; if (neste == null) return null; return neste.let(...);
•Arbeid FØR kallet gir rekkefølge framover; arbeid ETTER kallet gir baklengs
•Hjelpemetode med ekstra parameter er uttrykkelig godkjent i sensurveiledningen
•Manglende rekursjonsbunn gir StackOverflowError (en Error, ikke et Exception)

Tråder og monitor

•class Arbeider implements Runnable { public void run() { ... } }
•Thread t = new Thread(new Arbeider(...)); t.start(); ... t.join(); // start(), IKKE run()
•Lock laas = new ReentrantLock(); Condition c = laas.newCondition();
•laas.lock(); try { ... } finally { laas.unlock(); } // lock() UTENFOR try
•while (!betingelse) c.await(); // ALDRI if - betingelsen kan være usann igjen etter oppvåkning
•c.signal() vekker én ventende; c.signalAll() vekker alle
•Toveis synkronisering: to Condition-variabler på den SAMME låsen
•await() og join() kaster InterruptedException (checked)
•Eldre stil: synchronized-metode + wait() i while-løkke + notifyAll()

•Innsetting først: ny.neste = forste; if (forste != null) forste.forrige = ny; forste = ny; if (siste == null) siste = ny;

•Uttak (toveis): if (ut.forrige == null) forste = ut.neste; else ut.forrige.neste = ut.neste;

•Uttak (toveis, forts.): if (ut.neste == null) siste = ut.forrige; else ut.neste.forrige = ut.forrige;

Rekursjon

•int resten() { if (neste == null) return egen; return Math.max(egen, neste.resten()); }
•Startermetode: if (forste == null) return null; return forste.resten();
•Hjelpemetode: void sjekkFra(T p, int normal) { if (p == null) return; ...; sjekkFra(p.neste, normal); }
•Array: int sum(int[] a, int i) { if (i == a.length) return 0; return a[i] + sum(a, i+1); }

Unntakshåndtering

•class MittUnntak extends Exception { MittUnntak(String m) { super(m); } }
•class MittRT extends RuntimeException { MittRT(String m) { super(m); } }
•void metode() throws MittUnntak { ... throw new MittUnntak("tekst"); }
•catch (A | B e) { ... } // multi-catch; e.getMessage() gir teksten

Tråder og synkronisering

•class Arbeider implements Runnable { public void run() { ... } } -> new Thread(r).start()
•laas.lock(); try { ... } finally { laas.unlock(); }
•while (!betingelse) c.await(); // aldri if - betingelsen kan være usann igjen etter oppvåkning
•c.signal() vekker én ventende, c.signalAll() vekker alle; t.join() venter på at en tråd blir ferdig

Java grunnleggende

•class Navn { final int felt; Navn(int felt) { this.felt = felt; } }
•for (Vogn p = forste; p != null; p = p.neste) { ... }
•Type[] ut = new Type[antall]; // ut.length er lengden, uten parenteser
•if (a.equals(b)) ... // tekst og objekter; == kun for primitive typer
•public String toString() { return "X " + super.toString(); }

Iteratorer og Iterable

•class Beholder implements Iterable { public Iterator iterator() { return new MinIterator(); } }
•private class MinIterator implements Iterator { T peker = forste; ... }
•public boolean hasNext() { return peker != null; }
•for (T x : beholder) { ... } tilsvarer Iterator it = beholder.iterator(); while (it.hasNext()) { T x = it.next(); ... }

•Forsøker new T() eller new T[10] - typeparameteren finnes ikke på kjøretid.

•Glemmer typekonverteringen når en peker deklarert med supertypen tilordnes en variabel av typen T.

•Bruker rå typer uten vinkelparenteser og må så typekonvertere alt fra Object.

Lenkede lister og datastrukturtegning

•Glemmer ett av spesialtilfellene i taUt, oftest at elementet er det eneste i lista.
•Setter gammel.forrige = ny før den gamle verdien er lest av, slik at lista revner.
•Traverserer hele lista for å legge til bakerst selv om det finnes en siste-peker.
•Skriver p.neste != null etter && i stedet for før, og får NullPointerException på siste element.
•Tegner klassediagram i stedet for objekter og pekere når oppgaven ber om en datastrukturtegning.

Rekursjon

•Glemmer rekursjonsbunnen eller flytter seg ikke framover, og får StackOverflowError.
•Glemmer tom-liste-tilfellet i startermetoden og får NullPointerException.
•Kombinerer verdiene før det rekursive kallet når de skulle vært kombinert etter.
•Kaller den rekursive metoden på seg selv i stedet for på neste, slik at rekursjonen aldri kommer videre.
•Skriver løkke inne i den rekursive metoden - da er den ikke lenger rekursiv gjennomløping.

Unntakshåndtering

•Glemmer throws på metoden når unntaket arver fra Exception, slik at koden ikke kompilerer.
•Setter catch (Exception e) først, slik at de spesifikke blokkene blir uoppnåelige.
•Kaster unntaket etter at elementet er satt inn, slik at datastrukturen står igjen i ugyldig tilstand.
•Glemmer tom-liste-tilfellet og får NullPointerException i stedet for det tiltenkte unntaket.
•Skriver return i en finally-blokk og svelger unntaket som var på vei ut.

Tråder og synkronisering

•Kaller run() i stedet for start(), slik at ingen ny tråd oppstår.
•Bruker if i stedet for while rundt await(), og leser fra en beholder som er tom igjen.
•Glemmer finally rundt unlock(), slik at låsen aldri slippes hvis et unntak kastes.
•Kaller signal() eller await() uten å holde låsen og får IllegalMonitorStateException.
•Låser bare noen av monitorens metoder, slik at den kritiske regionen likevel kan nås av to tråder.

Java grunnleggende

•Glemmer this. i konstruktøren når parameteren heter det samme som feltet, slik at feltet forblir null eller 0.
•Bruker == på String i stedet for equals, slik at erMed alltid returnerer false.
•Skriver while (p.neste != null) og mister siste element, eller får NullPointerException på tom liste.
•Kaller toString() i stedet for super.toString() i subklassen og får StackOverflowError.
•Skriver ut.length() med parenteser (det er et felt for arrayer, en metode for String).

Iteratorer og Iterable

•Flytter pekeren før elementet returneres, slik at første element hoppes over.
•Lar hasNext() flytte pekeren, slik at annethvert element forsvinner.
•Returnerer den samme iteratoren hver gang fra iterator(), slik at lista bare kan gjennomløpes én gang.
•Glemmer å kalle finnNeste i konstruktøren i en filtrerende iterator, slik at det første elementet blir feil.
•Deklarerer letevariabelen med undertypen i stedet for supertypen i en filtrerende iterator.

•Husk typekonverteringen når du leser neste/forrige tilbake: de er deklarert med supertypen i dataklassen.

•Ved bruk av den generiske klassen er selve deklarasjonen KolonneG det viktigste poenget.

•PECS: skal du lese ut, bruk ? extends; skal du legge inn, bruk ? super.

•Beholder er ikke en Beholder - generiske typer er ikke kovariante.

Lenkede lister og datastrukturtegning

•Sensorveiledningen sier eksplisitt: ingen Node-objekter når pekerne skal ligge i dataobjektene.
•Bruk siste-pekeren for innsetting bakerst - traverserer du lista, taper du poeng selv med riktig resultat.
•Skriv opp de fire spesialtilfellene (eneste, først, sist, midten) på kladd før du koder taUt.
•Koble den nye noden på først, koble om de gamle etterpå - ellers mister du en referanse.
•Første- og siste-pekerne skal ha supertypen som deklarert type, ikke en subtype.

Rekursjon

•Øv på rekursjon gjennom lenket liste, ikke på fakultet og Fibonacci - det siste finnes ikke på disse eksamenene.
•Legg den rekursive metoden inne i dataobjektet og la den kalle seg selv på neste; beholderen får en startermetode.
•Startermetoden må håndtere tom liste; flere sett ber uttrykkelig om at den returnerer null da.
•Skal du kombinere verdier (maks, sum), gjør arbeidet ETTER det rekursive kallet.
•En rekursiv hjelpemetode med ekstra parametere er uttrykkelig godkjent i sensurveiledningen.

Unntakshåndtering

•Unntaksklassen er tre linjer: extends Exception og en konstruktør som kaller super(melding).
•Én unntaksklasse med String-parameter for å skille feilsituasjoner er ofte bedre svar enn mange nesten like klasser.
•Kast unntaket FØR du endrer datastrukturen, ellers står lista igjen i ugyldig tilstand.
•Husk å spesialbehandle tom liste - sensorveiledningen nevner det hvert år.
•Arver du fra RuntimeException, slipper du throws overalt; les oppgaveteksten, den sier ofte hvilken variant.

Tråder og synkronisering

•Lær monitormalen utenat: lock() utenfor try, unlock() i finally, await() i while-løkke, signal() ved tilstandsendring.
•start() lager ny tråd, run() gjør det ikke - dette er den vanligste feilen på hele oppgaven.
•All informasjon tråden trenger, må inn gjennom konstruktøren; run() har verken parametere eller returverdi.
•Nyere sett ber uttrykkelig om ReentrantLock og Condition - ikke bruk synchronized da.
•To parter som begge kan vente, trenger to Condition-variabler på den samme låsen.

Java grunnleggende

•Sensorveiledningene sier at import-setninger, kommentarer og tilgangsmodifikatorer ikke vektlegges - bruk ikke tid på dem.
•Deklarer felt som ikke skal endres som final; det gir uttrykkelig pluss i sensurveiledningen.
•Sammenlign identifikatorer med equals, aldri med ==.
•Bruk while (p != null) og flytt pekeren sist i løkkekroppen, ikke while (p.neste != null).
•Ved array-oppgaver: tell først, opprett arrayen med riktig lengde, fyll deretter.

Iteratorer og Iterable

•Skriv standardmalen fra hukommelsen: Iterable på beholderen, indre klasse med hasNext og next.
•next() skal ta vare på elementet, flytte pekeren og så returnere - aldri flytte først.
•hasNext() må aldri flytte pekeren; den skal kunne kalles flere ganger på rad.
•Filtrerende iterator: kall en finnNeste-hjelpemetode både i konstruktøren og etter hvert framrykk.
•La iterator() lage et nytt objekt hver gang, slik at to løkker kan gå samtidig.