var unionfind = require('union-find');
var hamming = require('compute-hamming');

function goeBURST_krustal(profiles, identifiers, callback) {
  
  var lvs = profiles.map(function(x){
    return x.map(function(x){return 0;});
  });

  var edges = [];

  for (var i = 0; i < profiles.length-1; i++) {
    for (var j = i+1; j < profiles.length; j++) {
      var diff = hamming(profiles[i], profiles[j]) - 1;
      lvs[i][diff] ++;
      lvs[j][diff] ++;

      edges.push([i, j]);
    }
  }
  var countComp = 0;

  function edgecmp(e, f) {
    countComp +=1;
    
    //console.log(countComp);
    var elevel = hamming(profiles[e[0]], profiles[e[1]]);
    var flevel = hamming(profiles[f[0]], profiles[f[1]]);
    var n = lvs[e[0]].length;

    if (elevel != flevel)
      return elevel - flevel;

    for (var l = 0; l < n; l++) {
      maxe = Math.max(lvs[e[0]][l], lvs[e[1]][l]);
      maxf = Math.max(lvs[f[0]][l], lvs[f[1]][l]);

      if (maxe != maxf)
        return maxf - maxe;

      mine = Math.min(lvs[e[0]][l], lvs[e[1]][l]);
      minf = Math.min(lvs[f[0]][l], lvs[f[1]][l]);

      if (mine != minf)
        return minf - mine;
    }

    maxe = Math.max(e[0], e[1]);
    maxf = Math.max(f[0], f[1]);

    if (maxe != maxf)
      return maxe - maxf;

    mine = Math.min(e[0], e[1]);
    minf = Math.min(f[0], f[1]);

    return minf - mine;
  }

  edges.sort(edgecmp);

  tree = [];
  values = [];

  var sets = new unionfind(profiles.length);

  for (var k = 0; k < edges.length && tree.length < profiles.length - 1; k++) {
    if (sets.find(edges[k][0]) != sets.find(edges[k][1])) {
      
      sets.link(edges[k][0], edges[k][1]);

      var value = hamming(profiles[edges[k][0]], profiles[edges[k][1]]);
      tree.push({source: identifiers[edges[k][0]], target: identifiers[edges[k][1]], value: value});

    }
  }

  callback(tree);
}

module.exports = goeBURST_krustal;