import pandas as pd
import math
from sklearn import cluster, datasets
from operator import itemgetter
import collections
import adj
import csv
import copy
import matplotlib.pyplot as plt
import plt123
import TSP123


def test123(fname1):
    #from matplotlib import pyplot as plt
    data = pd.read_csv(fname1)
    f1 = data['X'].tolist()
    f2 = data['Y'].tolist()
    f3 = data['capacity'].tolist()
    VC = data['vehicle_capacity'].tolist()
    VC = VC[0]

    item = [0]*len(f1)
    for i in range(0,len(f1)):
        item[i] = [i-1,f1[i],f2[i],f3[i],0]

    depot = item.pop(0)
    G =[0]*2
    for i in range(0,len(item)):
        G[0] = item[i][1]/len(item) + G[0]
        G[1] = item[i][2]/len(item) + G[1]



    def Get_Distance_Reverse(list1 , point):

        for i in range(0,len(list1)):
            list1[i][4] = (math.sqrt((list1[i][1]-point[0])**2 + (list1[i][2]-point[1])**2))

        list2 = sorted(list1 , key=lambda tup: tup[4], reverse = True)

        return list2

    def Get_Distance(list1 , point):
        for i in range(0,len(list1)):
            list1[i][4] = (math.sqrt((list1[i][1]-point[0])**2 + (list1[i][2]-point[1])**2))

        #print(list1)
        list2 = sorted(list1 , key=lambda tup: tup[4])

        return list2

    def Get_Gravity(list1):
        Grav = [0]*2
        for i in range(0 , len(list1)):
            Grav[0] = list1[i][1]/len(list1) + Grav[0]
            Grav[1] = list1[i][2]/len(list1) + Grav[1]
        return Grav


    def get_Gravity1(list1):
        grav = [[],[]]
        for i in range(0,len(list1)):
            temp = 0
            temp1 = 0
            for j in range(0,len(list1[i])):
                temp = list1[i][j][1]/len(list1[i]) + temp
                temp1 = list1[i][j][2]/len(list1[i]) + temp1
            grav[0].append(temp)
            grav[1].append(temp1)

        return grav

    def OneDistance(node1,x,y):
        return math.sqrt((node1[1]-x)**2 + (node1[2]-y)**2)

    def get_AllDistance(list1 , grav):                    #找出每個需求點與所有重心的距離
        Q=[]
        for i in range(0,len(list1)):
                for j in range(0,len(grav[1])):
                    Q.append(math.sqrt((list1[i][1]-grav[0][j])**2 + (list1[i][2]-grav[1][j])**2))

        distance = [(Q[i:i+len(grav[1])])  for i in range(0,len(Q),len(grav[1]))]
        sort = []
        for i in range(0,len(distance)):
            sort.append(sorted(range(len(distance[i])), key=lambda k: distance[i][k]))

        return(distance,sort)
    def get_FinalGravity(list1):
        grav = [[],[]]
        for i in range(0,len(list1)):
            temp = 0
            temp1 = 0
            for j in range(1,len(list1[i])):
                temp = list1[i][j][1]/(len(list1[i])-1) + temp
                temp1 = list1[i][j][2]/(len(list1[i])-1) + temp1
            grav[0].append(temp)
            grav[1].append(temp1)

        return grav

    count = 0
    cluster_list = []
    G_list = []
    Distance_list  = Get_Distance_Reverse(item , depot)
    while len(Distance_list) != 0:
        cap = Distance_list[0][3]
        G_list.append(Distance_list.pop(0))
        G1 = [0]*2
        G1[0] = G_list[count][1]
        G1[1] = G_list[count][2]


        if(len(Distance_list)== 0):
            break
        Distance_list1 = Get_Distance(Distance_list,G1)
        temp_list = []
        temp_list.append(G_list[count])

        while cap + Distance_list1[0][3] <= VC:

            cap = cap + Distance_list1[0][3]
            temp_list.append(Distance_list1.pop(0))
            G1 = Get_Gravity(temp_list)
            Distance_list1 = Get_Distance(Distance_list1,G1)
            if(len(Distance_list1) == 0):
                break

        cluster_list.append(temp_list)

        if(len(Distance_list1)==0):
            break

        Distance_list = Get_Distance_Reverse(Distance_list1,depot)


        count = count+1

    G1 = get_Gravity1(cluster_list)
    init_cluster = copy.deepcopy(cluster_list)
    cap = [0]*len(cluster_list)
    for i in range(len(cluster_list)):
        for j in range(len(cluster_list[i])):
            cap[i] = cluster_list[i][j][3] + cap[i]


    for i in range(0,len(cluster_list)):
        for j in range(0,len(cluster_list[i])):

            for k in range(0,len(cluster_list)):
                if (j >= len(cluster_list[i])):
                    break
                if (k != i):
                    init_Distance = OneDistance(cluster_list[i][j] , G1[0][i] , G1[1][i])
                    new_Distance = OneDistance(cluster_list[i][j] ,  G1[0][k] , G1[1][k])
                    if(cap[k] + cluster_list[i][j][3] <= VC and new_Distance < init_Distance):
                        cap[k] = cap[k] + cluster_list[i][j][3]
                        cap[i] = cap[i] - cluster_list[i][j][3]
                        temp = cluster_list[i].pop(j)
                        cluster_list[k].append(temp)
                        G1 = get_Gravity1(cluster_list)



    for i in range(0,len(cluster_list)):
        cluster_list[i].insert(0,depot)
        init_cluster[i].insert(0,depot)

    final_grav1 = get_FinalGravity(cluster_list)
    init_grav1 = get_FinalGravity(init_cluster)
    final_tsp, init_tsp = TSP123.get_tsp(cluster_list,init_cluster)
    plt123.cluster_plt(cluster_list, final_grav1 ,init_cluster,init_grav1,final_tsp, init_tsp, fname1 , depot)
    return final_tsp, init_tsp


import os
items = os.listdir(".")
newlist = []
for names in items:
        if names.endswith(".csv"):
                newlist.append(names)

result = []
name1 = []
mylist = ['good_P-n20-k2.csv', 'good_P-n21-k2.csv']
for i in range(0,len(newlist)):
        print(newlist[i],i)
        temp1,temp2 = test123(newlist[i])
        result.append([temp1,temp2,newlist[i]])

df2 = pd.DataFrame(data=result)
df2.to_csv('out.csv')
d = 1000
c = 1000