///////////////////////////////////////////////////////////////////
// Oppgave 1
//

/* Stakkoperasjoner:
 * - lese et tall: push
 * - lese en av de fire operasjonene: 2*topAndPop + push
 * - hente ut svaret til slutt: topAndPop
 */

/* OPPGAVE 1.B */
class Beregn {
  FloatStakk stakk;

  Beregn() {
    stakk = new FloatStakk();
  }

  void tall(float t) {
    stakk.push(t);
  }

  float resultat() {
    return stakk.topAndPop();
  }

  void add() {
    stakk.push(stakk.topAndPop() + stakk.topAndPop());
  }

  void sub() {
    stakk.push(-stakk.topAndPop() + stakk.topAndPop());
  }

  void mult() {
    stakk.push(stakk.topAndPop() * stakk.topAndPop());
  }

  void div() {
    stakk.push((1 / stakk.topAndPop()) * stakk.topAndPop());
  }
}
//////////////////////////////

/* OPPGAVE 1.C */
class BeregnDirekte {
  int n;
  float[] stakk;
  int ant;

  void BeregnDirekte(int i) {
    n = i;
    stakk = new float[i];
  }

  void tall(float t) {
    if (ant == n) {
      System.out.println("Ikke mer plass!");
      System.exit(1);
    } else stakk[ant++] = t;
  }

  void add() {
    if (ant < 2) {
      System.out.println("For få tall!");
      System.exit(2);
    } else stakk[ant - 2] += stakk[--ant];
  }

  void sub() {
    if (ant < 2) {
      System.out.println("For få tall!");
      System.exit(2);
    } else stakk[ant - 2] -= stakk[--ant];
  }

  void mult() {
    if (ant < 2) {
      System.out.println("For få tall!");
      System.exit(2);
    } else stakk[ant - 2] *= stakk[--ant];
  }

  void div() {
    if (ant < 2) {
      System.out.println("For få tall!");
      System.exit(2);
    } else stakk[ant - 2] /= stakk[--ant];
  }

  float resultat() {
    if (ant != 1) {
      System.out.println("Ikke ferdig uttrykk!");
      System.exit(3);
    }
    return stakk[0];
  }
}




///////////////////////////////////////////////////////////////////
// Oppgave 2
//

public class LagTre {
// Har ikke tatt med sjekk på at input er feil.
/* 
 * OPPGAVE 2.A
 * Rekursiv metode: 
 * (Antar at vi har en metode nesteTall() som gir oss det neste tallet
 * i sekvensen.)
 */

// Kall: rot = lagTreA();
Node lagTreA() {
  Node n = new Node(nesteTall());
  // Sjekker om vi har venstre og/eller høyre subtre.
  // Merk at begge disse må være lest før vi kan gjøre et rekursivt kall.
  boolean v = (nesteTall() == 1);
  boolean h = (nesteTall() == 1);
  if (v) n.venstre = lagTreA();
  if (h) n.hoyre =   lagTreA();
  return n;
}

/* 
 * OPPGAVE B
 * Node-stakk:
 */
Node lagTreB() {
  Stakk stakk = new Stakk();
  Node rot = new Node(nesteTall());
  boolean v = (nesteTall() == 1);
  boolean h = (nesteTall() == 1);

  Node n = rot;
  while (n != null) {
    if (!v && !h) {// Bladnode
      if (stakk.isEmpty()) return rot; // Ferdig med å bygge opp treet
      // Skal generere høyre subtre til pop-noden
	n = (Node)stakk.topAndPop();
	v = false;
	h = true;
    }

    if (v) {
	if (h) stakk.push(n);
	n.venstre = new Node(nesteTall());
	n = n.venstre;
    } else { // Her er h true
	n.hoyre = new Node(nesteTall());
	n = n.hoyre;
    }

    v = (nesteTall() == 1);
    h = (nesteTall() == 1);
  }
  return rot;
}

/* 
 * OPPGAVE C
 * Forenklet rekursiv metode.
 * Merk: Operasjoner har alltid både h og v true
 *       Operander (verdier) har alltid både h og v false
 */
Node lagTreC() {
  Node n = new Node(nesteTall());
  if (n.data < 0) {  // Operator-node
    n.venstre = lagTreC();
    n.hoyre = lagTreC();
  }
  return n;
}

/* 
 * OPPGAVE D
 * Direkte beregning
 */
int beregn() {
  int i = nesteTall();
  if (i >= 0) return i;
  else if (i == -1) return beregn() + beregn();
  else if (i == -2) return beregn() - beregn();
  else if (i == -3) return beregn() * beregn();
  else if (i == -4) return beregn() / beregn();
  else {
    System.out.println("Feil i input!");
    return 0;
  }
}

int nesteTall () {
  // TOBE written
  return 0;
}

}


///////////////////////////////////////////////////////////////////
// Oppgave 4
//
public class Traverser {
  public static void main(String[] args) {
    Node rot = new Node("A",
		  new Node("B", 
    new Node("D", null,
		   new Node("E", // søsken til D
	  new Node("F", null, null), null)), //slutt F, E og D
			       new Node("C", // søsken til B
		        new Node("G", null, null), null)), null); //slutt G, B og A

    traverser(rot, 0);
    rot.skrivUt();
  }

  static void traverser(Node tre, int db) {
    Node barn;
    
    // Dybden kan umiddelbart gis riktig verdi.
    tre.dybde = db;
    
    // Antall og høyde settes foreløpig som om det er en bladnode.
    tre.antall = 1;
    tre.hoyde = 0;
    
    if (tre.forsteBarn == null) {
      // Dette er en bladnode
      tre.bladAvstand = 0;
    } else {
      // Skal finne MINSTE avstand til en bladnode,
      // denne er i hvert fall mindre enn MAX_VALUE.
      tre.bladAvstand = Integer.MAX_VALUE;
    }
    
    barn = tre.forsteBarn;
    while (barn != null) {
      traverser(barn, db + 1);     
      tre.antall += barn.antall;
      if (barn.hoyde + 1 > tre.hoyde) {
	    tre.hoyde = barn.hoyde + 1;
      }
      if (barn.bladAvstand + 1 < tre.bladAvstand) {
	    tre.bladAvstand = barn.bladAvstand + 1;
      }      
      barn = barn.nesteSosken;
    }   
  }
}

//////////////////////////////
class Node {
  String navn;
  Node forsteBarn, nesteSosken;
  int dybde, hoyde, antall, bladAvstand;

  Node(String s, Node f, Node n) {
    navn = s;
    forsteBarn = f;
    nesteSosken = n;
  }

  void skrivUt() {
    System.out.println(navn + ": ");
    System.out.println("   Dybde: " + dybde);
    System.out.println("   Høyde: " + hoyde);
    System.out.println("   Antall: " + antall);
    System.out.println("   BladAvstand: " + bladAvstand);
    System.out.print("");
    if (forsteBarn != null) {
      forsteBarn.skrivUt();
    }
    if (nesteSosken != null) {
      nesteSosken.skrivUt();
    }
  }
}


///////////////////////////////////////////////////////////////////
// Oppgave 5
//

// Programmet består av en vanlig permutasjonsgenerator, en forenklet
// treinnsetting (like verdier forekommer ikke), samt en del
// statistikkberegninger.

public class Soketre {
  public static void main(String[] args) {
    Gen g = new Gen(Integer.parseInt(args[0]));
    g.gen(0);
    g.skrivResultat();
  }
}

//  Om vi kjører dette får vi resultatet under (Kolonnene er altså:
//  node-antall, gjennomsnittlig høyde og gjennomsnittlig søkelengde for
//  trærne). Det virker ikke urimelig ut fra denne tabellen at både
//  kolonne to og tre stiger logaritmisk med node-antallet, og dette er
//  altså nettopp hva teorien sier.
//    1   0.00   0.00
//    2   1.00   0.50
//    3   1.67   0.89
//    4   2.33   1.21
//    5   2.80   1.48
//    6   3.27   1.72
//    7   3.67   1.93
//    8   4.02   2.12
//    9   4.34   2.29


//////////////////////////////

class Gen {
  int n;
  boolean[] brukt;
  int[] p;
  int antTre = 0;
  int sumHoyde = 0;
  float sumGjLengde;

  Gen(int i) {
    n = i;
    brukt = new boolean[n];
    p = new int[n];
  }

  void gen(int i) {   // Som vanlig, se notatet.
    for (int siff = 0; siff < n; siff++) {
      if (!brukt[siff]) {
	    brukt[siff] = true;
	    p[i] = siff;
	    if (i < n - 1) {
	      gen(i + 1);
	    } else {
	      lagTre();
	    }
	    brukt[siff] = false;
      }
    }
  }

  void skrivResultat() {
    System.out.print(n + " ");
    System.out.print(((float)sumHoyde)/antTre + "    ");
    System.out.println(sumGjLengde/antTre);
  }

  void lagTre() {
    Node t;
    int niv, v;

    Node rot = new Node(p[0]);   // Antar n > 0
    int hoyde = 0;
    int nivsum = 0;

    for (int i = 1; i < n; i++) {   // Sett inn i treet
      t = rot;
      niv = 0;
      v = p[i];
      while (t.data != v) {
	    if (v < t.data) {
	      if (t.venstre == null) {
	        t.venstre = new Node(v);
	      }
	      t = t.venstre;
	    } else {   // Ingen er like!
	      if (t.hoyre == null) {
	        t.hoyre = new Node(v);
	      }
	      t = t.hoyre;
	    }
	    niv++;
      }
      nivsum += niv;
      if (hoyde < niv) {
	    hoyde = niv;
      }
    }
    antTre++;
    sumHoyde += hoyde;
    sumGjLengde += (float)nivsum/n;
  }
}