From:        Mikko J Rauhala <mjrauhal@cc.helsinki.fi>
Date:        Tue, 17 Apr 2001 14:25:58 +0300 (EEST)

12.3.2001 tehtävä 4

/* Yleiset arvostelukriteerit: Jokaisesta kohdasta on annettu maksimissaan
   2 pistettä. Lisäksi 1 piste on annettu siitä, että ylipäätään osaa käydä
   puuta läpi.

   Yleisesti ottaen kohdasta on saanut täydet pisteet, jos ohjelman logiikka
   pelaa eikä siinä ole ihan kamalia syntaktisiakaan virheitä. Oikeaa ideaa
   sisältävistä mutta toimimattomista ratkaisuista on saanut yhden pisteen.
   Samaten virhetarkistusten puutteesta on sakotettu; sitähän vaadittiin
   tehtävänannossakin.

   Jos on tehnyt saman yksinkertaisen virheen useammassa osatehtävässä,
   on siitä voitu sakottaa vain kerran.

   Esimerkkiratkaisut käyttävät puun läpikäyntiin rekursiota. Jos on
   käyttänyt rekursion sijaan jotain muuta läpikäyntitapaa, niin on toki
   voinut saada täydet pisteet, kunhan kaikki asiaan liittyvä koodi on
   näkyvillä ja ohjelma toimii.
*/

public class Sukupuu {

    private class Sukulainen {
	private String nimi;
	private int syntymävuosi;
	private Sukulainen äiti, isä;
    }

    private Sukulainen juuri;

    public Sukupuu() {
	juuri = null;
    }

    /* kaukaisinEsivanhempi - yksinkertainen rekursiivinen haku, ottaen aina
       suuremman alipuiden korkeuksista ja lisäten yhden. Tyhjä puu palauttaa
       -1.
    */

    public int kaukaisinEsivanhempi() {
	return kaukaisinEsivanhempi(juuri);
    }

    private int kaukaisinEsivanhempi(Sukulainen juuri) {
	int isäkorkeus, äitikorkeus;

	if (juuri == null) return -1;

	isäkorkeus = kaukaisinEsivanhempi(juuri.isä);
	äitikorkeus = kaukaisinEsivanhempi(juuri.äiti);

	if (isäkorkeus > äitikorkeus) return isäkorkeus + 1;
	else return äitikorkeus + 1;
    }

    /* Rekursiivinen haku. Sukulaisuuskuvaus muodostetaan return-ketjulla
       siten, että jokainen rekursiotaso lisää oman määreensä löydetyn
       jonon alkuun ja palauttaa tuloksen. */

    public String sukulaisuus(String nimi) {
	if (juuri == null || nimi == null) return null;
	if (juuri.nimi.equals(nimi)) return "minä";
	return sukulaisuus(nimi, juuri);
    }

    private String sukulaisuus(String nimi, Sukulainen juuri) {
	if (juuri.äiti != null) {
	    if (juuri.äiti.nimi.equals(nimi)) {
		return "äiti";
	    } else {
		String nimitys = sukulaisuus(nimi, juuri.äiti);
		if (nimitys != null) return "äidin " + nimitys;
	    }
	}
	if (juuri.isä != null) {
	    if (juuri.isä.nimi.equals(nimi)) {
		return "isä";
	    } else {
		String nimitys = sukulaisuus(nimi, juuri.isä);
		if (nimitys != null) return "isän " + nimitys;
	    }
	}
	return null;
    }

    /* Puu käydään läpi kaksi kertaa: Ensin haetaan suurin synnytysikä,
       ja sitten erikseen kaikki tässä iässä synnyttäneet ja tulostetaan ne.
       Homma hoituisi myös yhdellä läpikäynnillä hieman monimutkaisemmin.
    */       

    public void tulostaVanhinSynnyttäjä() {
        int ikä = this.suurinSynnytysikä(juuri);
	System.out.println("Ikä " + ikä + ": " +
			   this.ikäisetSynnyttäjät(juuri, ikä));
    }

    /* Rekursiivinen läpikäynti, palautetaan -1 jos ei löytynyt äitejä. */

    private int suurinSynnytysikä(Sukulainen juuri) {
	int saatu = -1, vanhempisaatu;

	if (juuri == null) return -1;
	if (juuri.äiti != null) {
	    saatu = juuri.syntymävuosi - juuri.äiti.syntymävuosi;
	    if ((vanhempisaatu = suurinSynnytysikä(juuri.äiti)) > saatu) {
		saatu = vanhempisaatu;
	    }
	}
	if (juuri.isä != null) {
	    if ((vanhempisaatu = suurinSynnytysikä(juuri.isä)) > saatu) {
		saatu = vanhempisaatu;
	    }
	}
	return saatu;
    }

    /* Rekursiivinen läpikäynti, palautetaan null jos ei puuta,
       tyhjä merkkijono jos ei pyydetynikäisiä äitejä. */

    private String ikäisetSynnyttäjät(Sukulainen juuri, int ikä) {
	String lisäys = "";

	if (juuri == null) return null;
	if (juuri.äiti != null) {
	    if (juuri.syntymävuosi - juuri.äiti.syntymävuosi == ikä) {
		lisäys = juuri.äiti.nimi + " ";
	    }
	    lisäys += ikäisetSynnyttäjät(juuri.äiti, ikä);
	}
	if (juuri.isä != null) {
	    lisäys += ikäisetSynnyttäjät(juuri.isä, ikä);
	}
	return lisäys;
    }
}