// L?sningsforslag, inf110, uke 11a.

// ------------------------------------------------------------------
public class Aktiviteter {

    // Variabel som brukes til nummerering av hendelsene.
    // Egentlig ikke n?dvendig, men gj?r kanskje testingen lettere?
    static int antall = 0;

    // Total (minste) gjennomf?ringstid for prosjektet
    static int totalTid = 0;

    /* Testprogram */
    public static void main(String[] args) {
	AktivitetsNode startAktivitet;
	HendelsesNode startHendelse;
    
	// START EKSEMPEL hentet fra forelesningen 26/3:

	startAktivitet = new AktivitetsNode("Vann/kloakk", 4);
    
	AktivitetsNode grunnmur = new AktivitetsNode("Grunnmur", 4);
	startAktivitet.utkanter = new AktivitetsKant(grunnmur, null);
    
	AktivitetsNode gulv = new AktivitetsNode("Gulv", 4);
	grunnmur.utkanter = new AktivitetsKant(gulv, null);
    
	AktivitetsNode vegger = new AktivitetsNode("Vegger", 5);
	grunnmur.utkanter = new AktivitetsKant(vegger, grunnmur.utkanter);

	AktivitetsNode vindu = new AktivitetsNode("Vindu", 2);
	vegger.utkanter = new AktivitetsKant(vindu, null);

	AktivitetsNode tak = new AktivitetsNode("Tak", 3);
	vegger.utkanter = new AktivitetsKant(tak, vegger.utkanter);

	AktivitetsNode takrenner = new AktivitetsNode("Takrenner", 1);
	tak.utkanter = new AktivitetsKant(takrenner, null);

	AktivitetsNode elanlegg = new AktivitetsNode("Elektisk anlegg", 2);
	vegger.utkanter = new AktivitetsKant(elanlegg, vegger.utkanter);
	tak.utkanter = new AktivitetsKant(elanlegg, tak.utkanter);
	gulv.utkanter = new AktivitetsKant(elanlegg, gulv.utkanter);

	// SLUTT EKSEMPEL

	startHendelse = new HendelsesNode(antall++);
	startHendelse.utkanter = konverter(startAktivitet);

	tidligsteAvslutning(startHendelse, 0);
	senesteAvslutning(startHendelse);
	slakk(startHendelse);
    }


// ------------------------------------------------------------------
    /* Oppgave b):
     *  Metode for ? konvertere en aktivitetsnode (akt) til en hendelseskant.
     *  Lager ogs? hendelsesnoden kanten g?r til.
     *  Hendelsesnoden kanten skal g? fra antas laget der denne metoden kalles.
     *  Returnerer derfor hendelseskanten som ble laget.
     */
    static HendelsesKant konverter(AktivitetsNode akt) {
	// "Flytter" informasjonen fra noden ut p? kanten.
	HendelsesKant h = new HendelsesKant(akt.navn, akt.tid);
	h.til = new HendelsesNode(antall++);

	// NB! ?delegger akt.utkanter underveis!
	// Ikke pent, men trenger da ikke ? sette noe merke :)
	while (akt.utkanter != null) {
	    // Kaller rekursivt videre for konvertering.
	    // Hjelpekanten k hjelper til ? huske utkanter
	    // som allerede er laget.
	    HendelsesKant k = h.til.utkanter;
	    h.til.utkanter = konverter(akt.utkanter.til);
	    h.til.utkanter.neste = k;
	    akt.utkanter = akt.utkanter.neste;
	}

	// Hvis en aktivitet har flere innkanter, m? vi lage en dummy-node
	// som samler disse. For enkelthets skyld huskes denne dummy-noden
	// av aktiviteten selv (variabelen s.husk).
	if (akt.innKanter > 1) {
	    if (akt.husk != null) {
		h = new HendelsesKant("Dummy", 0);
		h.til = akt.husk;
	    } else {
		// F?rste gangen lager vi selv dummy-noden kanten g?r fra,
		// og setter utkantene.
		HendelsesNode n = new HendelsesNode(antall++);
		n.utkanter = h;
		akt.husk = n;
	
		// Lager s? en dummy-kant som er den som returneres.
		h = new HendelsesKant("Dummy", 0);
		h.til = n;
	    }
	}
    
	return h;
    }






// ------------------------------------------------------------------
  /* Oppgave c): Tre metoder som m? til for ? beregne slakk. */

    static void tidligsteAvslutning(HendelsesNode h, int t) {
	if (t > h.tidligsteAvslutning) {
	    h.tidligsteAvslutning = t;
	    HendelsesKant k = h.utkanter;
	    if (k == null && t > totalTid) {
		totalTid = t;
	    }
	    while (k != null) {
		tidligsteAvslutning(k.til, t + k.tid);
		k = k.neste;
	    }
	}
    }
  
    static int senesteAvslutning(HendelsesNode h) {
	HendelsesKant k = h.utkanter;
	h.senesteAvslutning = totalTid;
	while (k != null) {
	    int retur = senesteAvslutning(k.til);
	    if (retur - k.tid < h.senesteAvslutning) {
		h.senesteAvslutning = retur - k.tid;
	    }
	    k = k.neste;
	}
	return h.senesteAvslutning;
    }
  
    static void slakk(HendelsesNode h) {
	HendelsesKant k = h.utkanter;
	while (k != null) {
	    if (k.slakk == -1) {
		k.slakk = k.til.senesteAvslutning - h.tidligsteAvslutning - k.tid;
		slakk(k.til);
	    }
	    k = k.neste;
	}
    }
  
} // end class Aktiviteter














/* Datastruktur for Aktivitetsgraf (gitt i oppgaveteksten) */

class AktivitetsNode {
    String navn;
    int tid;
    AktivitetsKant utkanter;
    int innKanter = 0;
    HendelsesNode husk;

    AktivitetsNode(String s, int i) {
	navn = s;
	tid = i;
    }
  
}


class AktivitetsKant {
    AktivitetsNode til;
    AktivitetsKant neste;

    AktivitetsKant(AktivitetsNode a, AktivitetsKant k) {
	til = a;
	neste = k;
	// Trenger ? vite antall innkanter for ? kunne lage hendelsesgrafen.
	til.innKanter++;
    }
  
}


/* Datastruktur for hendelsesgrafen. Svar p? oppgave a). /* 

class HendelsesNode {
    int nummer;
    HendelsesKant utkanter;
    int tidligsteAvslutning = Integer.MIN_VALUE;
    int senesteAvslutning = Integer.MAX_VALUE;

    HendelsesNode(int i) {
	nummer = i;
    }
}

class HendelsesKant {
    HendelsesNode til;
    HendelsesKant neste;
    String navn;
    int tid;
    int slakk = -1;

    HendelsesKant(String s, int i) {
	navn = s;
	tid = i;
    }
}