From:        Olli P Lahti <olahti@cs.Helsinki.FI>
Subject:     Arvosteluperusteet TiRa k1t2
Date:        Thu, 19 Apr 2001 15:05:03 +0300 (EET DST)

Tietorakenteet, 1. välikoe, kevät 2001

Arvosteluperusteet, tehtävä 2.                Olli Lahti



===============================================================
ESIMERKKIVASTAUS, jonka mukainen toiminnallisuus tuli toteuttaa
===============================================================


public class Juna {

private Vaunu veturi;
private Vaunu viimeinenVaunu; // apuosoitin junan loppuun
private int junanPituus;      // junan vaunujen lukumäärä

private class Vaunu {
  // Salainen sopimus: vaunu numero 0 onkin veturi; junassa on aina veturi!
  private Vaunu edellinen;
  private String vaununNimi;
  private Vaunu seuraava;
  private Vaunu(String nimi) {
    if (nimi == null)  nimi = "?????";
    this.vaununNimi = nimi;
    // viitteet edelliseen ja seuraavaan edelleen null
  }
}

public Juna(String veturi) {
  this.veturi = new Vaunu(veturi);   // tunnussolmun luonti
  this.viimeinenVaunu = this.veturi; // pelkkä veturi on viimeinen vaunu
  this.junanPituus = 0;              // ei vielä vaunuja
}


public void lisääPerään(String vaunu) {
  // *** Tämän metodin saa toteuttaa myös selaamalla listan alusta loppuun ***

  // saamme olettaa uuden vaunun luonnin onnistuvan, ts. muisti ei lopu kesken
  this.viimeinenVaunu.seuraava = new Vaunu(vaunu);
  this.viimeinenVaunu.seuraava.edellinen = this.viimeinenVaunu;
  this.viimeinenVaunu = this.viimeinenVaunu.seuraava;
  this.junanPituus++;
}

public Juna liitä(Juna toinen) {
  // pidennetty juna on tämä sama olio eli this
  if (toinen == null)  return this;   // ei tehdä mitään
  if (toinen.veturi.seuraava == null) // ei tehdä mitään, pelkkä veturi
    return this;

  this.junanPituus+=toinen.junanPituus;
  // toiselle junalle tämän junan viimeinen vaunu ikään kuin veturiksi
  this.viimeinenVaunu.seuraava = toinen.veturi.seuraava;
  this.viimeinenVaunu.seuraava.edellinen = this.viimeinenVaunu;
  this.viimeinenVaunu = toinen.viimeinenVaunu;
  toinen.veturi.seuraava = null;         // liitettävän junan veturi jää yksin
  toinen.viimeinenVaunu = toinen.veturi; // pelkkä veturi on nyt viimeinen vaunu
  toinen.junanPituus = 0;

  return this;
}

public Juna irroitaHäntä(int moneskoVaunu, String veturi) {
  if (moneskoVaunu > this.junanPituus)
    return new Juna(veturi); // mitään ei irroteta, tulee vain uusi veturi

  Vaunu vaunuosoitin = this.veturi;
  Vaunu viimeinenVaunuApu = this.viimeinenVaunu;
  for (int i=0; i<moneskoVaunu-1; i++)
    vaunuosoitin = vaunuosoitin.seuraava;
  this.viimeinenVaunu = vaunuosoitin; // tämä vaunu (tai veturi) jää viimeiseksi
  vaunuosoitin = vaunuosoitin.seuraava; // tämä kytketään annettuun veturiin
  vaunuosoitin.edellinen.seuraava = null; // poistetaan liitos seuraavaan

  Juna irroitettuJuna = new Juna(veturi);
  irroitettuJuna.veturi.seuraava = vaunuosoitin; // veturi vetämään häntää
  vaunuosoitin.edellinen = irroitettuJuna.veturi; // 1. vaunu kiinni veturiin
  irroitettuJuna.viimeinenVaunu = viimeinenVaunuApu; // viite loppuun kohdalleen
  irroitettuJuna.junanPituus = this.junanPituus - moneskoVaunu + 1;
  this.junanPituus = moneskoVaunu - 1;

  return irroitettuJuna;
}

public int monentenako(String vaunu, int mistäEteenpäin) {
  // palauttaa ei löydy -tilanteessa -1

  if (mistäEteenpäin < 1)  mistäEteenpäin = 1;  // numerointi yhdestä alkaen
  if (mistäEteenpäin > this.junanPituus)  return -1; // juna ei ole näin pitkä
  Vaunu vaunuosoitin = this.veturi;   // aluksi veturissa
  for (int i=0; i<mistäEteenpäin; i++)
    vaunuosoitin = vaunuosoitin.seuraava;

  int vaunulaskuri = mistäEteenpäin;
  while (!vaunuosoitin.vaununNimi.equals(vaunu)) {
    vaunuosoitin = vaunuosoitin.seuraava;
    vaunulaskuri++;
    if (vaunuosoitin == null)  return -1; // juna loppui ennen kuin vaunu löytyi
  }
  return vaunulaskuri;
}

public int pituus() {         // palauta junan vaunujen lukumäärä
  return this.junanPituus;
}

public String toString() {
  String junaJono = this.junanPituus + " : <#" + this.veturi.vaununNimi + "#]";
  Vaunu vaunuosoitin = this.veturi;   // aluksi veturissa

  while ((vaunuosoitin = vaunuosoitin.seuraava) != null)
    junaJono += "|[" + vaunuosoitin.vaununNimi + "]";

  return junaJono;

// Esimerkkejä merkkijonoesityksestä:
//  0 : <#6295#]
//  1 : <#6295#]|[1. luokka]
//  5 : <#6295#]|[1. luokka]|[2. luokka]|[2. luokka]|[ravintola]|[makuuvaunu]

}

}  


 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -


public final class Tyokalut {

  private Tyokalut() { }

  public static int laskeNimisetVaunut(Juna juna, String vaunu) {
          // *** toString-merkkijonosta etsintä kelpuutetaan myös ***
    int lkm = 0;
    int nykypaikka = 1;            // monennessako vaunussa laskenta etenee
    int uusipaikka;
    while ((uusipaikka = juna.monentenako(vaunu, nykypaikka)) > -1) {
      lkm++;
      nykypaikka = uusipaikka+1;   // jatka etsintää löytyneen seuraajasta
    }
    return lkm;
  }

  public static void poistaNimisetVaunut(Juna juna, String vaunu) {
          // HUOM: Yksittäisiin vaunuihin ei voida pitää viitteitä muutoin kuin
          //       itsenäisinä junina vetureineen, sillä Juna-luokan sisäinen
          //       rakenne ei näy luokan ulkopuolelle.
          // *** (Rekursiivinen poisto loppujunien suhteen kävisi myös; ***
          // ***  tällöin tarvittaisiin useita apuvetureita yhtäaikaa.) ***
    int nykypaikka = 1;              // monennessako vaunussa karsiminen etenee
    int poistopaikka;
    while ((poistopaikka = juna.monentenako(vaunu, nykypaikka)) > -1) {
      Juna loppujuna = juna.irroitaHäntä(poistopaikka+1, "----");
      juna.irroitaHäntä(poistopaikka, "pois"); // tämä vaunu irrotetaan roskaksi
      juna.liitä(loppujuna);               // yhdistä loppujuna takaisin kiinni
      // jatka etsintää samasta liitoskohdasta
    }
  }

  public static void käännäYmpäri(Juna juna) {
          // *** häntien asettaminen hetkeksi taulukkoon hyväksyttiin myös ***
    Juna vaunut = juna.irroitaHäntä(1, "0000"); // irrota vaunut alkuperäisestä
    while (vaunut.pituus() > 0)        // siirrä vaunut takaisin lopusta alkaen
      juna.liitä(vaunut.irroitaHäntä(vaunut.pituus(), "----"));
  }

}


 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -


==========
PISTEYTYS:
==========

- luokan Juna rakenne mukaanluettuna (sisä)luokka Vaunu
  sekä näiden konstruktorit                                1 p.

- metodi lisääPerään                                      1/2 p.

- metodi liitä                                             1 p.

- metodi irroitaHäntä                                    1 1/2 p.

- metodi monentenako                                      1/2 p.

- metodit pituus ja toString                              1/2 p.

                                                         --------
                                                           5 p.
kirjastoluokka Tyokalut

- annetun nimisten vaunujen määrä                         1/2 p.

- annetun nimisten vaunujen poistaminen                    1 p.

- junan vaunujen järjestys päinvastaiseksi                1/2 p.

                                                         --------
                                                           2 p.

                                                         ========
                                              yhteensä     7 p.


Vähäisistä koodaus- tai ajatusvirheistä ei vähennetty pisteitä, ellei
tällaisia virheitä ollut huomattavan useita.