Samlinger

Java Collections API

• Java Collections API er et sett klasser som representerer ulike typer samlinger implementert på forskjellige måter.
• Grensesnitt definerer operasjonene som støttes av de forskjellige samlingene.
• Navnekonvensjon: Navnene på de konkrete klassene en kombinasjon av underliggende datastruktur og type samling. For eksempel implementerer både ArrayList og LinkedList operasjonene grensesnittet List, men underliggende datastruktur er forskjellig (henholdsvis tabell(array) og lenket liste).

Eksempel på samling: Mengde

• En mengde kan defineres som en samling elementer hvor man ikke kan ha duplikater (to eller flere like elementer),
• Innbyrdes rekkefølge ingen betydning.
• Ikkelineær samling som kan implementeres med lineær datastruktur.

Abstrakt datatyper (ADT)

• Vi kan si at en datatype er en gruppe verdier og operasjonene som er definert for disse verdiene.
• Den primitive datatypen int definerer ett sett med numeriske verdier og de operasjonene som kan utføres på disse verdiene (addisjon, multiplikasjon etc.)
• Skal vi kunne gjøre noe med heltall i en datamaskin, må vi ha en datatype som representerer heltall og operasjoner som kan utføres på datatypen.
• Tilsvarende: Skal vi kunne bruke samlingen Mengde, må vi lage en datatype som representerer samlingen.
• Dette kalles en abstrakt datatype. En abstrakt datatype er en datatype der verdiene og operasjonene i utgangspunktet ikke er definert i programmeringsspråket. Abstrakt fordi detaljer rundt implementasjon må defineres. Slike detaljer bør være skjult for brukeren.
• I Java kan en abstrakt datatype defineres i et grensesnitt. Her beskriver vi hvilke operasjoner som skal kunne utføres, men ikke hvordan operasjonene skal utføres.

Grensesnittet Mengde

• Vi starter med å definere hvilke operasjoner som skal kunne utføres på elementene.
• Vi ønsker å skille hvilke operasjoner som skal utføres fra hvordan de implementeres, og lager derfor et grensesnitt der vi definerer hvilke operasjoner (metoder) som skal kunne utføres.
• Et grensesnitt inneholder en eller flere metodesignaturer, men ingen implementasjon av metodene.
• Grensesnittet Mengde definerer en abstrakt datatype. For at vi skal kunne lage en konkret samling av type Mengde må det finnes en klasse som implementerer de abstrakte metodene definert i grensesnittet. Brukere av en klasse som implementerer Mengde har en garanti for at metodene definert i dette grensesnitt finnes, og kan bruke dem uten kjennskap til hvordan de er implementert.

package forelesning;

import mengde.*;
import java.util.Iterator;

public interface Mengde<E> extends Iterable<E> {    
    public boolean leggTil( E element) ; 
    public boolean leggTilAlle(Mengde<? extends E> mengde); 
    public Mengde<E>  union(Mengde<? extends E> mengde); 
    public Mengde<E> differanse(Mengde<? extends E> mengde) ; 
    public Mengde<E> snitt(Mengde<? extends E> mengde); 
    public E fjern (E element) ; 
    public boolean erTom(); 
    public int antall(); 
    public boolean inneholder (Object element); 
    public Iterator<E> iterator();     
    @Override
    public String toString();      
}

Datastrukturer

• En abstrakt datatype kan implementeres ved hjelp av forskjellige datastrukturer.
• En bruker/klient av en samling trenger ikke kjenne til hvordan samlingen er implementert, men forholder seg til ADT-en slik den er beskrevet i grensesnittet.
• Vi skal implementere samlingen Mengde på to forskjellige måter: ved bruk av tabell og lenket liste. Ulike implementasjoner kan ha fordeler og ulemper hva angår effektivitet og minnebruk.

Implementasjon av Mengde ved bruk av en tabell

• Vi kan nå lage en klasse som implementerer grensesnittet Mengde. En måte å gjøre dette på, er å lage en tabell som lagrer objektene som mengden inneholder.
• Senere skal vi implementere samme grensesnitt ved bruk av en lenket liste.
• Vi bruker en lineær datastruktur (tabell) til å implementere en ikke-lineær samling.
• Implementerer metodene slik at rekkefølgen elementene tilfeldigvis er lagret i tabellen ikke har betydning i forhold til operasjonene som kan utføres.

Klassen TabellMengde

• Nedenfor er tabell-implementasjonen av Mengde, som vi kom frem til i fellesskap i forelesningstimene.
• Mengdens elementer lagres i en tabell (data), som fylles opp fortløpende, d.v.s. nye elementer legges til på første ledige plass i tabellen. (Se metoden leggTil).
• Når et element fjernes (metoden fjern), fylles den ledige plassen opp med elementet som ligger til sist i tabellen. Dette er ok siden rekkefølgen ikke har noen betydning, og er mer kostnadseffektivt enn å flytte alle etterfølgende elementer ett hakk til venstre for å tette igjen hullet.
• Iterator-klassen er her laget som en lokal og privat klasse, og har tilgang til den ytre klassens variabler. Den lokale klassen er innenfor typeparameteren E sin rekkevidde, som derfor ikke skal deklareres på nytt i iterator-klassens header.
• toString-metoden gjør bruk av en StringBuilder-objekt, for å unngå arbeidsmengde av O(N²).

package forelesning;

import java.util.Iterator;

public class TabellMengde<E> implements Mengde<E> {

    private E [] data; 
    private int antall; 
    
    public TabellMengde(){
        data = (E[]) new Object[100] ;
        antall=0; 
    }
        
     public boolean leggTil(E element) {
        if (element == null) {
            throw new NullPointerException("");
        }

        // sjekke om elementet finnes fra f��r
        boolean leggesTil = !inneholder(element);

        if (leggesTil) {
            // sjekke om kapasitet m�� utvides 
            if (antall() == data.length) {
                utvidKapasitet();
            }
            data[antall++] = element;
        }
        return leggesTil;
    }

    private void utvidKapasitet() {
        E[] nyTabell =   (E[]) new Object [data.length*2];
        
        for (int i = 0; i < data.length; i++) {
            nyTabell[i] = data[i];
        }

        data = nyTabell;
    }
    public boolean leggTilAlle(Mengde<? extends E> mengde) {
        boolean r = false; 
        for(E verdi: mengde){
            if (leggTil(verdi))
                r=true; 
        }        
        return r; 
    }

    public Mengde<E> union(Mengde<? extends E> mengde) {
                
        Mengde<E> union = new TabellMengde<E>(); 
        union.leggTilAlle(mengde);
        union.leggTilAlle(this);
        
        return union; 
    }

    public Mengde<E> differanse(Mengde<? extends E> mengde) {
        Mengde<E> retur = new TabellMengde<E>(); 
        
        for (E verdi: this){
            if(!mengde.inneholder(verdi)) 
                retur.leggTil(verdi);
        }        
        return retur; 
    }

    public Mengde<E> snitt(Mengde<? extends E> mengde) {
        
        Mengde<E> retur = new TabellMengde<E>();
        
        // Iterere over verdienen i mengde
        for (E verdi: mengde){
            if(inneholder(verdi))
                retur.leggTil(verdi);
        }        
        return retur;         
    }
    
    public E fjern(E element) {

        // Sjekke om mengden er tom
        if (erTom()) {
        // Kast unntak 
        }

        // Sjekke om elementet finnes
        int funnet = -1;
        for (int i = 0; i < antall && funnet == -1; i++) {
            if (data[i].equals(element)) {
                funnet = i;
            }
        }

        if (funnet == -1) {
        //Kast unntak
        }

        E resultat = data[funnet];

        //Legger siste element i tabellen p�� plassen til elementet som skal slettes
        data[funnet] = data[antall - 1];
        data[antall - 1] = null;
        antall--;

        return resultat;
    }
    
    public boolean erTom() {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    public int antall() {
        return antall; 
    }


    public boolean inneholder(Object element) {

        boolean funnet = false; 
        for (int i = 0; i < antall && !funnet; i++) {
            if (data[i].equals(element)) {
                funnet = true;
            }
        }
        return funnet; 
    }

    
    public Iterator<E> iterator() {
        return new TabellMengdeIterator();
    }
    
    @Override
    public String toString() {

        StringBuilder sb = new StringBuilder("");

        for (int i = 0; i < antall; i++) {
            sb.append(data[i].toString() + " ");
        }

        return sb.toString();
    }

    private class TabellMengdeIterator implements Iterator<E> {

        private int pos;

        public boolean hasNext() {
            return (pos < antall);
        }

        public E next() {
            return data[pos++];
        }

        public void remove() {
            throw new UnsupportedOperationException("Not supported yet.");
        }
    }
        
}

Klassen LenketMengde

• Nedenfor er en lenket-liste-implementasjon av Mengde.
• Nye elementer legges til på begynnelsen av den lenkede listen (metoden leggTil).
• Node-klassen er en privat og lokal klasse. Et Node-objekt har en verdi (elementet som skal lagres i listen) og en referanse til neste node i den lenkede listen. Den ytre klassen har tilgang til Node-klassens variabler selv om de er deklarert som private.
• Metodene for å utføre mengde-operasjoner (union, differanse og snitt) er ikke implementert, men ved bruk av iteratoren kan de implementeres på samme måte som for tabell-implementasjonen.

package forelesning;

import mengde.*;
import java.util.Iterator;

public class LenketMengde<E> implements Mengde<E> {

    private Node start; 
    private int antall; 
    
    
    public boolean leggTil(E element) {
        
        boolean leggesTil = !inneholder(element); 
                
        if (leggesTil){
            start = new Node(element,start);
            antall++; 
        }        
        return leggesTil; 
    }

    public boolean leggTilAlle(Mengde<? extends E> mengde) {
        
        int antallLagtTil = 0; 
        
        for (E e : mengde ){
            if(leggTil(e))
                antall++; 
        }
        
        return (antallLagtTil > 0); 
    }

    public Mengde<E> union(Mengde<? extends E> mengde) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    public Mengde<E> differanse(Mengde<? extends E> mengde) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    public Mengde<E> snitt(Mengde<? extends E> mengde) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    public E fjern(E element) {
        
        E retur = null; 
        Node p, q; 
        boolean funnet = false; 
        if (erTom()){
            //Kast unntak
        }
        
        //er det f��rste element i listen som skal slettes?
        if (start.verdi.equals(element)){
            retur = start.verdi; 
            start = start.neste; 
        }
        else {
            // hvis ikke m�� vi lete oss frem til noden  som skal slettes, og ta
            // vare p�� referansen til noden _f��r_ den som skal slettes. 
            q = start; 
            p = start.neste; 
            while(p != null && !funnet ){
                if (p.verdi.equals(element))
                    funnet = true; 
                else {
                    q = p; 
                    p = p.neste; 
                }
            }
            if (!funnet ){
                // kast unntak 
            }
            
            retur = p.verdi; 
            q.neste = p.neste;                         
        }
        
        return retur;         
    }

    public boolean erTom() {
        return (antall == 0); 
    }

    public int antall() {
        return antall; 
    }

    public boolean inneholder(Object element) {
        boolean funnet = false; 
        Iterator<E> it = iterator(); 
        while (it.hasNext() && !funnet){
            E verdi = it.next(); 
            if (verdi.equals(element))
                funnet = true; 
        }
        return funnet; 
    }

    public Iterator<E> iterator() {
        return new LenketMengdeIterator(); 
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder(); 
        for (E element : this ){
            sb.append(element.toString() + " "); 
        }
        
        return sb.toString(); 
    }
    
    private class Node {
        private E verdi; 
        private Node neste; 
        
        private Node(E verdi, Node neste){
            this.verdi = verdi;
            this.neste = neste; 
        }
    }
    
    private class LenketMengdeIterator implements Iterator<E> {

        private Node p; 
        
        public LenketMengdeIterator(){
            p = start; 
        }
        
        public boolean hasNext() {
            return (p != null); 
        }

        public E next() {
            E verdi = p.verdi; 
            p = p.neste; 
            return verdi; 
        }

        public void remove() {
            throw new UnsupportedOperationException("Not supported yet.");
        }
        
    }  
    
    
}