Tietorakenteet, 1. kurssikoe 11.3.2002
======================================

Tehtävä 1: Arvosteluperusteet ja esimerkkivastaus / Jukka Kohonen
=================================================================

Asteikko:
---------

a) 3 p: 0.5 pistettä per operaatio

	- Removessa/addissa täytyy siirtää taulukon loppuosaa
	  alaspäin/ylöspäin, tai muuten huolehtia siitä, että vektorin
	  indeksointi edelleen toimii ja järjestys säilyy. Reikien
	  jättö removessa rikkoo indeksoinnin ellei niitä huomioida
	  jollain erikoisella tavalla.

	- Addissa täytyy varata uusi taulukko ja kopioida alkiot, jos
	  vanhasta tila loppuu.

b) 3 p: 0.5 pistettä per operaatio

	- Lukuisia mahdollisia toteutustapoja: 1- tai 2-suuntainen
	  linkitys, tunnussolmu tai ei, loppuviite tai ei, lukumäärä
	  muistissa tai ei, suora tai rengaslista. Metodien
	  yksityiskohtien on täsmättävä valitun toteutustavan kanssa!

	- Jos käytetään loppu-kenttää, se on myös pidettävä kunnossa!
	- Jos käytetään lukumäärä-kenttää, se on myös pidettävä kunnossa!

c) 2 p: kolme väärin => 1 piste, kuusi väärin => 0 pistettä.

Pyöristysten takia täyteen 8 pisteeseen ei tarvittu täysin virheetöntä
vastausta.


Tarkennuksia ja huomioita
-------------------------

Indeksoinnin sai toteuttaa 0:sta tai 1:stä alkaen, kunhan teki sen
johdonmukaisesti.

Virhetilanteiden käsittelyltä ei vaadittu kovinkaan suurta tarkkuutta.
Sen sijaan *normaalien* erikoistilanteiden (tyhjä lista, listan alku
ja loppu) käsittelyn piti toimia moitteettomasti. Varsinkin b-kohdassa
erikoistilanteita tuli aika lailla, ellei käyttänyt tunnussolmullista
rengaslistaa (harva käytti).

A-kohdassa moni kävi silmukassa läpi koko taulukkoa, myös
käyttämättömiä alkioita (jotka ovat nulleja). Tämä johtaa helposti
ohjelman kaatumiseen, kun kutsutaan null-olion equals-metodia.

Alkioiden järjestyksen tuli säilyä ja indeksoinnin toimia kuten
Vectorissa, eli removessa loppuosaa siirretään alaspäin ja addissa
ylöspäin.  Näppäriä järjestyksen rikkovia kikkoja (esim. vaihdetaan
kohdealkio viimeisen alkion kanssa) ei tässä voinut käyttää. Vaikka
taulukon alkioilla ei olekaan sellaista järjestystä, jota Vectorin
*toteutuksessa* voisi hyödyntää (esim. binäärihaulla), Vectorin
*käyttäjällä* voi olla alkioille jokin tärkeä järjestys, jota toteutus
ei saa rikkoa!

B-kohdassa piti olla johdonmukainen yksityiskohtiensa kanssa.
Listan on syytä olla selkeästi joko tunnussolmullinen tai tunnussolmuton,
ei jotain siltä väliltä: jos 0-alkioiseen luodaan yksi (tunnus)solmu,
ei pitäisi sitten ottaa tuota solmua käyttöön 1-alkioisen listan
alkiota varten, vaan luoda aina uudelle alkiolle uusi solmu.

Indeksien tallettaminen itse listasolmuihin ei ole tässä kovin hyvä
idea, koska sitten niitä täytyy päivittää jos keskellä listaa lisätään
tai poistetaan alkioita. Tällainen toteutus kyllä hyväksyttiin, jos se
päivitys oli hoidettu asianmukaisesti.

B-kohdassa oli suuri houkutus ottaa käyttöön mukavia apumuuttujia
(lukumäärä, loppuviite) joidenkin operaatioiden helpottamiseksi.
Valitettavan usein tämä johti kesäkissa-ilmiöön: apumuuttujaan
kiinnitettiin huomiota vain niin kauan kuin siitä oli iloa, sitten se
jäi heitteille. Ts. sen sisältöä ei enää pidetty ajan tasalla muissa
operaatioissa, mikä johtaa myöhemmin virheelliseen toimintaan.

Tässä itse asiassa kiteytyy eräs tietorakenteiden suunnittelun
perusperiaatteista:

	Älä ota käyttöön enempää apurakenteita kuin jaksat ylläpitää!

C-kohdassa on hyväksytty esimerkistä poikkeavia vastauksia, jos ne
täsmäävät toteutuksen ja/tai uskottavan selityksen kanssa.


Eräs esimerkkivastaus:
----------------------

a) Object-taulukko, jonka koko on aluksi 10. Aina tilan loppuessa koko
kaksinkertaistetaan.

public class Vector {
    private Object taulu[];
    private int N;		// alkioiden tämänhetkinen määrä

    // 1:
    public Vector() {
	taulu = new Object[10];
	N = 0;
    }

    // 2:
    public int size() {
	return N;
    }

    // 4:
    public int indexOf(Object o) {
	for (int i=0; i<N; i++) {
	    if (taulu[i].equals(o))
		return i;
	}
	return -1;			// ei löytynyt
    }

    // 7:
    // tarkennus: indeksin oltava välillä 0...N-1
    public Object set(int index, Object o) {
	if (index < 0 || index > N-1)
	    return null;
	Object vanha = taulu[index];
	taulu[index] = o;
	return vanha;		// palauttaa paikan vanhan sisällön
    }

    // 9:
    public boolean remove(Object o) {
	int index = indexOf(o);
	if (index == -1)
	    return false;		// ei löytynyt
	else {
	    for (int i=index; i<N-1; i++)
		taulu[i] = taulu[i+1];	// loppuosan siirto
	    taulu[N-1] = null;
	    N--;
	    return true;
	}
    }

    // 10:
    // tarkennus: indeksin oltava välillä 0...N
    public void add(int index, Object o) {
	if (index < 0 || index > N)
	    return;		// voisi myös heittää poikkeuksen
	if (N >= taulu.length)
	    grow();		// tilan kasvatus
	for (int i=N-1; i>=index; i--)
	    taulu[i+1] = taulu[i];	// loppuosan siirto
	taulu[index] = o;
	N++;
    }

    private void grow() {
        Object uusitaulu[] = new Object[taulu.length * 2];
        for (int i=0; i<N; i++)
            uusitaulu[i] = taulu[i];
	taulu = uusitaulu;
    }
}



b) Jotta operaatioista saadaan lyhyitä ja yksinkertaisia, käytetään
2-suuntaista tunnussolmullista rengaslistaa. Lisäksi pidetään
alkioiden lukumäärä tallessa muuttujassa N. Lukumäärämuuttuja on
tietysti pidettävä ajan tasalla kun alkoita lisätään tai poistetaan.

public class Vector {
    private class Solmu {
	private Object alkio;
	private Solmu edel;
	private Solmu seur;
    }

    Solmu tunnus;		// tunnussolmu (ei sisällä alkiota)
    int N;			// alkioiden lukumäärä

    // 1:
    public Vector() {
	tunnus = new Solmu();
	tunnus.alkio = null;
	tunnus.edel = tunnus;	// rengas kuntoon!
	tunnus.seur = tunnus;	// rengas kuntoon!
	N = 0;
    }

    // 2:
    public int size() {
	return N;
    }

    // 5:
    // tarkennus: palauttaa -1 jos alkiota ei löydy
    public int lastIndexOf(Object o) {
	Solmu s = tunnus.edel;	// viimeinen alkio
	int index = N-1;
	while (s!=tunnus && !s.alkio.equals(o)) {
	    s = s.edel;
	    index--;
	}
	return index;
    }

    // 6:
    // tarkennus: indeksin oltava välillä 0...N-1
    public Object get(int index) {
	if (index<0 || index>N-1)
	    return null;
	Solmu s = tunnus.seur;	// ensimmäinen alkio
	for (int i=0; i<index; i++)
	    s = s.seur;
	return s.alkio;
    }

    // 6, "tehoversio": aloitetaan loppupäästä jos matka sieltä on
    // lyhyempi kuin alkupäästä. Tällaista ei toki vaadittu!
    public Object get2(int index) {
	if (index<0 || index>N-1)
	    return null;
	Solmu s;
	if (index < N/2) {
	    s = tunnus.seur;
	    for (int i=0; i<index; i++)
		s = s.seur;
	}
	else {
	    s = tunnus.edel;
	    for (int i=N-1; i>index; i--)
		s = s.edel;
	}
	return s.alkio;
    }

    // 8:
    public boolean add(Object o) {
	Solmu uusi = new Solmu();
	uusi.alkio = o;
	uusi.edel = tunnus.edel;
	uusi.seur = tunnus;
	uusi.edel.seur = uusi;
	uusi.seur.edel = uusi;
	N++;
	return true;
    }	    

    // 11:
    // tarkennus: indeksin oltava välillä 0...N-1
    public Object remove(int index) {
	if (index < 0 || index > N-1)
	    return null;
	Solmu s = tunnus.seur;	// ensimmäinen alkio
	for (int i=0; i<index; i++)
	    s = s.seur;
	s.edel.seur = s.seur;
	s.seur.edel = s.edel;
	N--;
	return s.alkio;
    }
}


c)

Taulukkototeutuksella:
4	O(N)	(alkion etsintä silmukalla)
5	O(N)	(alkion etsintä silmukalla)
6	O(1)
7	O(1)
8	O(N)	(kopiointi uuteen taulukkoon, jos tila loppui)
9	O(N)	(alkion etsintä silmukalla, ja taulukon loppupätkän siirto)
10	O(N)	(taulukon loppupätkän siirto / kopiointi uuteen)
11	O(N)	(taulukon loppupätkän siirto)

Linkitetyllä listalla:
4	O(N)	(alkion etsintä silmukalla)
5	O(N)	(alkion etsintä silmukalla)
6	O(N)	(paikan haku silmukalla)
7	O(N)	(paikan haku silmukalla)
8	O(1)
9	O(N)	(etsintä silmukalla)
10	O(N)	(paikan haku silmukalla)
11	O(N)	(paikan haku silmukalla)

Huom: jos b-kohdassa 6-operaatio tehdään tehokkaammalla toteutuksella
(ks. b-kohta), silti alkioita voidaan joutua käymään läpi N/2 = O(N)
kappaletta.

Huom: b-kohdan 8-operaatio vie ajan O(N), jos lista ei ole rengas eikä
erillistä loppuviitettä ole.

======================================