package com.data.struct;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

import com.data.struct.GraphicDepthFirstSort.Node;


public class Kruskal {
  private Node[] list;
  private List<Edge> edges=new ArrayList<Edge>();
  
  public Kruskal(int v,int e){
    System.out.println("v:"+v+" e:"+e);
    list=new Node[v];
    for(int i=0;i<v;i++){
      Node node=new Node();
      node.id=i;
      list[i]=node;
    }
    System.out.print("weight:");
    for(int i=0;i<e;i++){
      int v1=new Random().nextInt(v);
      int v2=new Random().nextInt(v);
      if(v1==v2){
        continue;
      }
      while(true){
        Node node=list[v1];
        Node x=node;
        boolean already=false;
        while(node.next!=null){
          if(node.next.id==v2){
            already=true;
            break;
          }
          node=node.next;
        }
        if(already==true){
          break;
        }
        Node ex=new Node();
        ex.id=v2;
        ex.w=new Random().nextInt(e);
        System.out.print(ex.w+" ");
        node.next=ex;
        Edge edge=new Edge();
        edge.start=x;
        edge.end=list[ex.id];
        edge.w=ex.w;
        edges.add(edge);
        break;
      }
    }
    System.out.println();
    Collections.sort(edges, new Comparator<Edge>() {

      @Override
      public int compare(Edge o1, Edge o2) {
        if(o1.w>o2.w){
          return 1;
        }else if(o1.w<o2.w){
          return -1;
        }else{
          return 0;
        }
      }
      
    });
  }
  
  public void printG(){
    for(int i=0;i<list.length;i++){
      Node node=list[i];
      System.out.print(node.id+"=>");
      while(node.next!=null){
        System.out.print(node.next.id+"("+node.next.w+")=>");
        node=node.next;
      }
      System.out.println();
    }
    
  }
  public void print(){
          Node h = list[0];
          while(h.treeParent!=null){
            h=h.treeParent;
          }
          this.print(0, h);
   }
       
   private void print(int level, Node node){
       for (int i = 0; i < level; i++) {
           System.out.format(" ");
       }
       System.out.format("|");
       for (int i = 0; i < level; i++) {
           System.out.format("-");
       }
       
       System.out.format("%d%n", node.id);
       List<Node> child = node.children;
       for(int i=0;i<child.size();i++){   
         Node c=child.get(i);
           print(level + 1, c);
       }           
   }
  
  public int kruskal(){
    for(int i=0;i<list.length;i++){
      makeSet(list[i]);
    }
    int w=0;
    for(int i=0;i<edges.size();i++){
      Edge edge=edges.get(i);
      if(findSet(edge.start)!=findSet(edge.end)){
        union(edge.start,edge.end);
        edge.end.children.add(edge.start);
        edge.start.treeParent=edge.end;
        w+=edge.w;
      }
    }
    return w;
    
  }
  
  public void makeSet(Node x){
    x.parent=x;
    x.rank=0;
  }
  public void union(Node x,Node y){
     link(findSet(x),findSet(y));
  }
  private void link(Node x,Node y){
    if(x.rank>y.rank){
      y.parent=x;
    }else{
      x.parent=y;
      if(x.rank==y.rank){
        y.rank++;
      }
    }
    
  }
  public Node findSet(Node x){
    if(x.parent!=x){
      x.parent=findSet(x.parent);
    }
    return x.parent;
  }
  
  public static class Node{
    private int id;
    private Node next;
    private int w;
    private int rank;
    private Node parent;
    private Node treeParent;
    private List<Node> children=new ArrayList<Node>();
  }
  private class Edge{
    private Node start;
    private Node end;
    private int w;
  }
  public static void main(String[] args) {
    Kruskal k=new Kruskal(5,10);
    k.printG();
    System.out.println("total weight:"+k.kruskal());
    k.print();

  }

}