using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;

namespace VRPProblemAnalyzer {
  class Cluster {
    public List<double[]> Items { get; set; }
    public double[] Center { get; set; }    

    public Cluster() {
      Items = new List<double[]>();
      Center = new double[2];
    }
  }

  class KMeansClustering {
    public static List<Cluster> Cluster(double[,] vertices, int k, int restarts) {
      while (true) {
        int info = 0;
        double[,] centers = null;
        int[] xyc = null;


        Thread t = new Thread(delegate() {
          alglib.kmeansgenerate(vertices, vertices.Length / 2, 2, k, restarts + 1, out info, out centers, out xyc);
        });
        t.Start();
        if (!t.Join(1000)) {
          t.Abort();
          continue;
        }

        if (info == -3)
          return new List<Cluster>();
        else if (info == 1) {
          List<Cluster> result = new List<Cluster>();
          int count = centers.Length / 2;
          for (int i = 0; i < count; i++) {
            result.Add(new Cluster());
            result[i].Center[0] = centers[0, i];
            result[i].Center[1] = centers[1, i];
          }

          for (int i = 0; i < xyc.Length; i++) {
            double[] coords = new double[2];
            coords[0] = vertices[i, 0];
            coords[1] = vertices[i, 1];

            result[xyc[i]].Items.Add(coords);
          }

          result.RemoveAll(c => c.Items.Count == 0);

          return result;
        }
      } 
    }
  }
}