Tehtävä 2, Janne Rinta-Mänty
============================

Tarkastuksessa kiinnitettiin huomiota metodien yleisen toimivuuden
(tekeekö sitä mitä vaadittiin) lisäksi erityisesti toimintaan tyhjällä
listalla ja listan kunnossapysymiseen (alku, loppu ja lkm). Pisteitä
tehtävästä sai 8 miinus virheiden lukumäärä (tekemättä jäänyt metodi
oli arvoltaan -2 pistettä), kuitenkin vähintään nolla.
Pi(l)kkuvirheistä ei sakotettu

////////////////////////////////////////////////////////////////////////
// Tietorakenteet K2000
// 1. välikoe 3.3.2000
//
// Tehtävä 2
// Ratkaisuehdotus / Janne Rinta-Mänty 30.3.2000
////////////////////////////////////////////////////////////////////////
public class Lista { // yhteen suuntaan linkitetty tunnussolmuton lista

    private class Alkio {
	private Comparable tieto;
	private Alkio linkki;
    }

    private Alkio alku, loppu;
    private int lkm;

    // lisää alkion listaan paikkaan paikka (0 = alku)
    // jos lisäys onnistuu, palauttaa true, muuten false
    public boolean lisää(Comparable alkio, int paikka) {
	if (alkio != null && paikka >= 0 && paikka <= lkm) {
	    Alkio uusi = new Alkio(), ts = new Alkio(), p = ts;
	    uusi.tieto = alkio;
	    ts.linkki = alku;  // väliaikainen tunnussolmu

	    while (paikka > 0) { // etsitään paikka
		p = p.linkki;
		paikka--;
	    }

	    // uusi alkio paikalleen listaan
	    uusi.linkki = p.linkki;
	    p.linkki = uusi;

	    // päivitetään alku, loppu ja lkm
	    alku = ts.linkki;
	    if (p == loppu || loppu == null) { // menikö uusi viimeiseksi
		loppu = uusi;
	    }
	    lkm++;

	    return true;
	}

	return false;
    }

    // poistaa listasta arvoa pienemmät alkiot
    public void pienetPois(Comparable arvo) {
	if (arvo != null && alku != null) {
	    Alkio ts = new Alkio(), p = ts;
	    ts.linkki = alku; // väliaikainen tunnussolmu

	    while (p.linkki != null) {
		if (p.linkki.tieto.compareTo(arvo) < 0) {
		    // poistetaan p:n seuraaja
		    p.linkki = p.linkki.linkki;
		    lkm--;
		} else {
		    // siirrytään eteenpäin listassa
		    p = p.linkki;
		}
	    }

	    // päivitetään alku, loppu ja lkm
	    alku = ts.linkki;
	    if (p == ts) { // poistettiinko kaikki
		loppu = null;
	    } else {
		loppu = p;
	    }
	}
    }

    // liittää toisen tämän listan perään; toinen tyhjenee
    // palauttaa (mahdollisesti muuttuneen) tämän (this) listan
    public Lista liitä(Lista toinen) {
	if (toinen != null) {
	    if (this.alku == null) { // ensimmäinen lista on tyhjä
		// 'this' tulee samaksi kuin toinen
		// toisen 'private'-osat näkyvät tänne!
		this.alku = toinen.alku;
		this.loppu = toinen.loppu;
		this.lkm = toinen.lkm;
	    } else if (toinen.alku != null) { // kumpikaan ei ole tyhjä
		// liitetään toinen 'this':n perään
		this.loppu.linkki = toinen.alku;
		this.loppu = toinen.loppu;
		this.lkm += toinen.lkm;
	    }
	    // tyhjennetään toinen
	    toinen.alku = null;
	    toinen.loppu = null;
	    toinen.lkm = 0;
	}

	return this;
    }

    // irrottaa listasta loppuosan alkaen alkiosta alkio
    // palauttaa loppuosan tai tyhjän listan, jos alkiota ei löydy
    public Lista irroitaLoppu(Comparable alkio) {
	Lista loppuosa = new Lista();

	if (alkio != null && alku != null) {
	    Alkio ts = new Alkio(), p = ts;
	    int n = 0; // alkuosaan jäävien alkioiden lkm
	    ts.linkki = alku; // väliaikainen tunnussolmu

	    // etsitään katkaisukohta
	    while (p.linkki != null &&
		   p.linkki.tieto.compareTo(alkio) != 0) {
		p = p.linkki;
		n++;
	    }

	    if (p.linkki != null) { // jos alkio löytyi,
		// loput listasta tulee loppuosaan
		loppuosa.alku = p.linkki;
		loppuosa.loppu = this.loppu;
		loppuosa.lkm = this.lkm - n;

		// lista poikki
		p.linkki = null;

		// päivitetään alku, loppu ja lkm
		this.alku = ts.linkki; // == null, jos alkio oli ensimmäisenä
		this.lkm = n;
		if (p == ts) { // menikö kaikki loppuosaan
		    this.loppu = null;
		} else {
		    this.loppu = p;
		}
	    }
	}

	return loppuosa;
    }
}