package prax6Ott;
import java.util.*;


/**
 * @author OTTMAC
 *  Holds sub-classes like Graph, Vertex, Edge, Sageuds and Andmed and method calculatePryfer.
 */
public class GraphTask {

   public static void main (String[] args) {
      GraphTask a = new GraphTask();
      a.run();
      //throw new RuntimeException ("Nothing implemented yet!"); // delete this
   }

   /**
    * @author OTTMAC
 * @purpose: to create different graphs and call out Pryfer sequence method.
 */
public void run() {

      // TODO!!! YOUR TESTS HERE!
//	   //kahe elemendiga graafi test
//	  Graph g = new Graph ("G");
//	  Vertex kaheksa = new Vertex("8");
//	  Vertex seitse = new Vertex("7");
//	  Edge kaheksaSeitse = new Edge("87");
//	  g.first = kaheksa;
//	  kaheksa.first = kaheksaSeitse;
//	  kaheksaSeitse.target = seitse;
//	  kaheksa.next = seitse;
//	  seitse.next = null;


//	  //�he elemendiga graafi test
//	  Graph g = new Graph("G");
//	  Vertex kaheksa = new Vertex("8");
//	  g.first = kaheksa;
	   //t�htedega graafi test
     Graph g = new Graph ("G");
     Vertex kaheksa = new Vertex ("H");
     Vertex seitse = new Vertex ("G");
     Vertex kuus = new Vertex ("F");
     Vertex viis = new Vertex ("E");
     Vertex neli = new Vertex ("D");
     Vertex kolm = new Vertex ("C");
     Vertex kaks = new Vertex ("B");
     Vertex yks = new Vertex ("A");
     Edge lisaTest1 = new Edge("98");
     Vertex yheksa= new Vertex("9");;
     yheksa.first = lisaTest1;
     lisaTest1.target = kaheksa;
     g.first = yheksa;
     Edge kaheksaViis = new Edge ("85");
     Edge viisKolm = new Edge ("53");
     Edge kolmSeitse = new Edge ("37");
     Edge kolmYks = new Edge ("31");
     Edge yksNeli = new Edge ("14");
     Edge yksKaks = new Edge ("12");
     Edge kaksKuus = new Edge ("26");
     kaheksa.first = kaheksaViis;
     viis.first = viisKolm;
     kolm.first = kolmYks;
     kolmYks.next = kolmSeitse;
     yks.first = yksKaks;
     yksKaks.next = yksNeli;
     kaks.first = kaksKuus;
     kaheksaViis.target = viis;
     viisKolm.target = kolm;
     kolmYks.target = yks;
     kolmSeitse.target = seitse;
     yksKaks.target = kaks;
     yksNeli.target = neli;
     kaksKuus.target = kuus;

     //pandud n� 'arraysse'
     yheksa.next = kaheksa;
     kaheksa.next = seitse;
     seitse.next = kuus;
     kuus.next = viis;
     viis.next = neli;
     neli.next = kolm;
     kolm.next = kaks;
     kaks.next = yks;
     yks.next = null;


	   //t�htedega graaf upper-lower-segamini
//	     Graph g = new Graph ("G");
//	     Vertex kaheksa = new Vertex ("H");
//	     Vertex seitse = new Vertex ("g");
//	     Vertex kuus = new Vertex ("f");
//	     Vertex viis = new Vertex ("e");
//	     Vertex neli = new Vertex ("D");
//	     Vertex kolm = new Vertex ("c");
//	     Vertex kaks = new Vertex ("b");
//	     Vertex yks = new Vertex ("A");
//	     Edge lisaTest1 = new Edge("98");
//	     Vertex yheksa= new Vertex("9");;
//	     yheksa.first = lisaTest1;
//	     lisaTest1.target = kaheksa;
//	     g.first = yheksa;
//	     Edge kaheksaViis = new Edge ("85");
//	     Edge viisKolm = new Edge ("53");
//	     Edge kolmSeitse = new Edge ("37");
//	     Edge kolmYks = new Edge ("31");
//	     Edge yksNeli = new Edge ("14");
//	     Edge yksKaks = new Edge ("12");
//	     Edge kaksKuus = new Edge ("26");
//	     kaheksa.first = kaheksaViis;
//	     viis.first = viisKolm;
//	     kolm.first = kolmYks;
//	     kolmYks.next = kolmSeitse;
//	     yks.first = yksKaks;
//	     yksKaks.next = yksNeli;
//	     kaks.first = kaksKuus;
//	     kaheksaViis.target = viis;
//	     viisKolm.target = kolm;
//	     kolmYks.target = yks;
//	     kolmSeitse.target = seitse;
//	     yksKaks.target = kaks;
//	     yksNeli.target = neli;
//	     kaksKuus.target = kuus;
//
//	     //pandud n� 'arraysse'
//	     yheksa.next = kaheksa;
//	     kaheksa.next = seitse;
//	     seitse.next = kuus;
//	     kuus.next = viis;
//	     viis.next = neli;
//	     neli.next = kolm;
//	     kolm.next = kaks;
//	     kaks.next = yks;
//	     yks.next = null;
//
//	   //Numbriline graaf 1-st  6ni
//	   Graph g = new Graph("G");
//	   Vertex yks = new Vertex("1");
//	   Vertex kaks = new Vertex("2");
//	   Vertex kolm = new Vertex("3");
//	   Vertex neli = new Vertex("4");
//	   Vertex viis = new Vertex("5");
//	   Vertex kuus = new Vertex("6");
//	   Edge kuusViis = new Edge("65");
//	   Edge viisNeli = new Edge("54");
//	   Edge neliKolm = new Edge("43");
//	   Edge neliKaks = new Edge("42");
//	   Edge neliYks = new Edge("41");
//	   //seosed
//	   g.first = kuus;
//	   kuus.first = kuusViis;
//	   kuusViis.target = viis;
//
//	   viis.first = viisNeli;
//	   viisNeli.target = neli;
//
//	   neli.first = neliKolm;
//	   neliKolm.target = kolm;
//
//	   neliKolm.next = neliKaks;
//	   neliKaks.target = kaks;
//
//	   neliKaks.next = neliYks;
//	   neliYks.target = yks;
//
//	   kuus.next = viis;
//	   viis.next = neli;
//	   neli.next = kolm;
//	   kolm.next = kaks;
//	   kaks.next = yks;
//	   yks.next = null;

	  //numbritega graafi test
//      Graph g = new Graph ("G");
//      Vertex kaheksa = new Vertex ("8");
//      Vertex seitse = new Vertex ("7");
//      Vertex kuus = new Vertex ("6");
//      Vertex viis = new Vertex ("5");
//      Vertex neli = new Vertex ("4");
//      Vertex kolm = new Vertex ("3");
//      Vertex kaks = new Vertex ("2");
//      Vertex yks = new Vertex ("1");
//      Edge lisaTest1 = new Edge("98");
//      Vertex yheksa= new Vertex("9");;
//      yheksa.first = lisaTest1;
//      lisaTest1.target = kaheksa;
//      g.first = yheksa;
//      Edge kaheksaViis = new Edge ("85");
//      Edge viisKolm = new Edge ("53");
//      Edge kolmSeitse = new Edge ("37");
//      Edge kolmYks = new Edge ("31");
//      Edge yksNeli = new Edge ("14");
//      Edge yksKaks = new Edge ("12");
//      Edge kaksKuus = new Edge ("26");
//      kaheksa.first = kaheksaViis;
//      viis.first = viisKolm;
//      kolm.first = kolmYks;
//      kolmYks.next = kolmSeitse;
//      yks.first = yksKaks;
//      yksKaks.next = yksNeli;
//      kaks.first = kaksKuus;
//      kaheksaViis.target = viis;
//      viisKolm.target = kolm;
//      kolmYks.target = yks;
//      kolmSeitse.target = seitse;
//      yksKaks.target = kaks;
//      yksNeli.target = neli;
//      kaksKuus.target = kuus;
//
//      //pandud n� 'arraysse'
//      yheksa.next = kaheksa;
//      kaheksa.next = seitse;
//      seitse.next = kuus;
//      kuus.next = viis;
//      viis.next = neli;
//      neli.next = kolm;
//      kolm.next = kaks;
//      kaks.next = yks;
//      yks.next = null;
      ArrayList<String> andmed = calculatePryfer(g.first);
      System.out.println("Graphs Vertexes and edges connected to it.");
      System.out.println(g);
      System.out.println("Unique pryfer sequence of this graph:");
      for(int i = 0 ; i<andmed.size(); i++){ System.out.print(andmed.get(i) + "   ");}
      //System.out.println (g);
   }


   /**
 * @author OTTMAC
 * @purpose: to hold a Graph's Vertex information. Vertex name (id), next vertex (next) and first 'child' of the current vertex (edge first)
 * @variable Vertex id: Vertex name.
 * @variable Edge first : First Edge of this Vertex. Allows to describe a child of current Vertex.
 * @variable Vertex next : Next Vertex. Used to hold all Graphs Vertexes in a Graph.
 */
class Vertex {

      String id;
      Vertex next;
      Edge first;
      /**
       * Class constructor with three inputs. Creates a Vertex object.
       */
      Vertex (String s, Vertex v, Edge e) {
         id = s;
         next = v;
         first = e;
      }
      /**
       * Class constructor with one input. Creates a Vertex object
       */
      Vertex (String s) {
         this (s, null, null);
      }

      @Override
      public String toString() {
         return id;
      }

      // TODO!!! Your Vertex methods here!

   } // Vertex


   /**
 * @author OTTMAC
 * @purpose to create an edge with according data - id, target (another vertex) and 'next' edge, which is an edge on the same level.
 * @variable String id : Edge name.
 * @variable Vertex target : Edge target Vertex
 * @variable Edge next : An Edge on the same level.
 */
class Edge {

      String id;
      Vertex target;
      Edge next;
      /**
       * Class constructor with three inputs. Creates a Edge object.
       */param konstruktoril
      Edge (String s, Vertex v, Edge e) {
         id = s;
         target = v;
         next = e;
      }
      /**
       * Class constructor with one input. Creates a Edge object.
       */
      Edge (String s) {
         this (s, null, null);
      }

      @Override
      public String toString() {
         return id;
      }

      // TODO!!! Your Edge methods here!

   } // Edge


   /**
 * @author OTTMAC
 * @purpose: to hold graph id and 'root' Vertex
 * @variable String id: Graph name.
 * @variable Vertex first : First Vertex of a Graph.
 */
static class Graph {

      String id;
      Vertex first;
      /**
       * Class constructor with two inputs. Creates a Graph object.
       * @param  s +desc
       * @ param v + desc
       */
      Graph (String s, Vertex v) {
         id = s;
         first = v;
      }
      /**
       * Class constructor with one input. Creates a Graph object.
       */
      Graph (String s) {
         this (s, null);
      }

      @Override
      public String toString() {
          String nl = System.getProperty ("line.separator");
          StringBuffer sb = new StringBuffer (nl);
          sb.append (id + nl);
          Vertex v = first;
          while (v != null) {
             sb.append (v.toString() + " --> ");
             Edge e = v.first;
             while (e != null) {
                sb.append (e.toString());
                sb.append ("(" + v.toString() + "->"
                   + e.target.toString() + ") ");
                e = e.next;
             }
             sb.append (nl);
             v = v.next;
          }
          return sb.toString();
       }

      // TODO!!! Your Graph methods here!
   } // Graph

   /**
    * @author OTTMAC
 * @param first Vertex: input Vertex object, contains the first element of the tree.
 * @purpose Creates two matrixes and starts to delete the smallest leaf from the given tree
 * until two Vertexes are left. The deleted leafs fathers compose an unique Pr�fer sequence
 * which is then printed onto the screen along with the given tree.
 * @return array containing Pryfer elements
 */
public ArrayList<String> calculatePryfer(Vertex first){
 	  ArrayList<Andmed> andmed = new ArrayList<Andmed>();
 	  ArrayList<Sagedus> sagedus = new ArrayList<Sagedus>();
 	  Vertex tmp = first;
	  Sagedus neueAlgus = new Sagedus();
	  neueAlgus.nimi = tmp.id;
	  neueAlgus.sagedus = -1;
	  sagedus.add(neueAlgus);
	  tmp = tmp.next;
	  //maatriksi p�hi valmis, k�ik vertexid kirja.
 	  while(tmp != null){
			  Sagedus neue = new Sagedus();
			  neue.nimi = tmp.id;
			  neue.sagedus = 0;
			  sagedus.add(neue);
			  tmp = tmp.next;
 	  }
 	  //Sagedustele
 	  while(first != null){
 		  if(first.first != null){
 			  Andmed uus = new Andmed(first.first.target.id, first.id);
 			  for(int i = 0; i<sagedus.size() ; i++){
 				  //kui on kellegi laps, pane sagedus k�rgemale
 				  if(sagedus.get(i).nimi.equals(first.first.target.id )){
 					  sagedus.get(i).sagedus ++;
 					  }
 				  //Kui on olemas, t�sta sagedust
 				  if(sagedus.get(i).nimi.equals(first.id)){
 					  sagedus.get(i).sagedus ++;
 					  }
 			  }
 			  //Lisa isa ja poja nimi
 			  andmed.add(uus);
 			  //kui isal on veel poegi, otsi nad k�ik �les ja pane kirja isa-poja paarid.
 			  //T�sta ka sagedust iga kord kui n�ed.
 			  if(first.first.next != null){
 				  Edge edgeTmp = first.first.next;
 				  while(edgeTmp != null){
 					  Andmed newBrotha = new Andmed(edgeTmp.target.id, first.id);
 					  andmed.add(newBrotha);
 		 			  for(int i = 0; i<sagedus.size() ; i++){
 		 				  if(sagedus.get(i).nimi.equals(edgeTmp.target.id)){
 		 					  sagedus.get(i).sagedus ++;
 		 					  }
 		 				  if(sagedus.get(i).nimi.equals(first.id)){
 		 					  sagedus.get(i).sagedus ++;
 		 					  }
 		 			  }
 					  edgeTmp = edgeTmp.next;
 				  }
 			  }
 		  }
 		  first = first.next;
 	  }
 	  //Kahe maatriksi p�hjal pr�feri arvutamine
 	  //olemas on sagedustabel ja isa-poja tabel
 	  //Hakkame otsima lehti, ehk siis neid kelle sagedus = 1

 	  ArrayList<String> pryfer = new ArrayList<String>();
 	  while(andmed.size()!=1){
 		  if(andmed.size()==0){break;}
 		  Sagedus min = null;
 		  for(int i = 0; i<sagedus.size(); i++){
 			  if(sagedus.get(i).sagedus ==1){
 				  //Kui oleme esimese leidnud, paneme kirja  selle miinimumLeheks
 				  if (min == null){
 					  min = sagedus.get(i);
 				  }
 				  //Kui leht on v�iksem kui miinimum, pane see min-iks
 				  else if (min.nimi.compareTo(sagedus.get(i).nimi) >0){
 					  min = sagedus.get(i);
 				  }
 			  }
 		  }
 		  //eemalda sagedustabelist miinimum
 		  sagedus.remove(min);
 		  //Leia andmemaatriksist miinimumi isa ja pane pr�feri massiivi isa v��rtus
 		  String isa = "";
 		  for(int i = 0 ; i<andmed.size() ; i++){
 			  if(andmed.get(i).nimi.equals(min.nimi)){
 				  isa = andmed.get(i).isa;
 				  pryfer.add(isa);
 				  andmed.remove(i);
 				  break;
 			  }
 		  }
 		  //Leia isa �les sagedustabelist ja v�henda tema sagedust 1 v�rra.
 		  for(int i = 0; i<sagedus.size(); i++){
 			  if(sagedus.get(i).nimi.equals(isa)){
 				  sagedus.get(i).sagedus --;
 			  }
 		  }
 		  //J�tka algoritmi kuni sagedusTabelisse on j��nud 1 element.
 	  }

 	  return pryfer;
   }
   //sagedusmaatriksi loomiseks vajalik objekt
   /**
 * @author OTTMAC
 *	@purpose for creating Vertex frequency table
 *@variable String nimi : Vertex name.
 *@variable int sagedus : According frequency
 */
public class Sagedus{
	   String nimi;
	   int sagedus;
   }
   //isa-poja objekt.
   /**
 * @author OTTMAC
 * @purpose to hold father-son pairs.
 * @variable String nimi: Vertex child.
 * @variable String isa : Vertex father.
 */
public class Andmed{
	      String nimi;
	      String isa;
	      /**
	       * Class constructor with two inputs. Creates an 'Andmed' object.
	       */
	      Andmed (String _nimi, String _isa) {
	         nimi = _nimi;
	         isa = _isa;
	      }
   }
}