#Importing required modules
import math
import random
import matplotlib.pyplot as plt
import numpy as np

import Users
import tool
import GDOP
import p_tool
from itertools import combinations

#计算用户平均snr
def function_snr(users,uavs_pos,c_association,power):
    sum=0
    for user_index in range(len(c_association)):
        snr=tool.cal_snr(uavs_pos[c_association[user_index]],users[user_index],power[c_association[user_index]][user_index])
        sum+=snr
    return (sum/len(users))

#计算用户平均gdop
def function_gdop(users,uavs_pos,c_association,p_association):
    # p_association=tool.get_p_association(users,uavs_pos,c_association,len(users)*2)
    sum=0
    for user_index in p_association:
        uavs=[]
        uavs.append(uavs_pos[c_association[user_index]])
        for uav_index in p_association[user_index]:
            uavs.append(uavs_pos[uav_index])
        gdop=GDOP.calculate_gdop(uavs,users[user_index])
        sum+=gdop
    return -sum/len(users)

def punish(power,p_rest):
    f = 0
    i=0
    for p in power:
        dis = sum(p) - p_rest[i]
        if dis > 0.001:
            f += 10 ** (dis * 100)
        for p_singe in p:  # 功率要大于0
            dis1 = 0 - p_singe
            if dis1>0:
                f += 10 ** max(0, dis1 * 100)
        i+=1
    return f

#Function to find index of list
def index_of(a,list):
    for i in range(0,len(list)):
        if list[i] == a:
            return i
    return -1

#Function to sort by values
def sort_by_values(list1, values):
    sorted_list = []
    while(len(sorted_list)!=len(list1)):
        if index_of(min(values),values) in list1:
            sorted_list.append(index_of(min(values),values))
        values[index_of(min(values),values)] = math.inf
    return sorted_list

#Function to carry out NSGA-II's fast non dominated sort
def fast_non_dominated_sort(values1, values2):
    #支配的节点
    S=[[] for i in range(0,len(values1))]
    front = [[]]
    n=[0 for i in range(0,len(values1))]#被支配的数量
    rank = [0 for i in range(0, len(values1))]#等级

    for p in range(0,len(values1)):
        S[p]=[]
        n[p]=0
        for q in range(0, len(values1)):
            if (values1[p] > values1[q] and values2[p] > values2[q]) or (values1[p] >= values1[q] and values2[p] > values2[q]) or (values1[p] > values1[q] and values2[p] >= values2[q]):
                if q not in S[p]:
                    S[p].append(q)
            elif (values1[q] > values1[p] and values2[q] > values2[p]) or (values1[q] >= values1[p] and values2[q] > values2[p]) or (values1[q] > values1[p] and values2[q] >= values2[p]):
                n[p] = n[p] + 1
        if n[p]==0:
            rank[p] = 0
            if p not in front[0]:
                front[0].append(p)

    i = 0
    while(front[i] != []):
        Q=[]
        for p in front[i]:
            for q in S[p]:
                n[q] =n[q] - 1
                if( n[q]==0):
                    rank[q]=i+1
                    if q not in Q:
                        Q.append(q)
        i = i+1
        front.append(Q)

    del front[len(front)-1]
    return front,rank

#Function to calculate crowding distance
def crowding_distance(values1, values2, front):
    distance = [0 for i in range(0,len(front))]
    #从小到大排序
    sorted1 = sort_by_values(front, values1[:])
    sorted2 = sort_by_values(front, values2[:])
    distance[0] = 4444444444444444
    distance[len(front) - 1] = 4444444444444444
    for k in range(1,len(front)-1):
        distance[k] = distance[k]+ (values1[sorted1[k+1]] - values1[sorted1[k-1]])/(max(values1)-min(values1))
    for k in range(1,len(front)-1):
        distance[k] = distance[k]+ (values2[sorted2[k+1]] - values2[sorted2[k-1]])/(max(values2)-min(values2))
    return distance


#初始化无人机位置
def init(pop_size,k,users):
    min_pos=0
    max_pos=1000
    pos_solution=[]
    p_solution=[]
    for i in range(pop_size):
        uavs_pos=[[min_pos+(max_pos-min_pos)*random.random(),min_pos+(max_pos-min_pos)*random.random(),100] for i in range(k)]
        p_alloc=init_p(uavs_pos,users)
        pos_solution.append(uavs_pos)
        p_solution.append(p_alloc)
    # print(pos_solution)
    return pos_solution,p_solution

def get_dis(i,uavs_pos,users,uav_to_user):
    dis=[]
    for k in uav_to_user[i]:
        dis.append(tool.calculate_3d_distance(uavs_pos[i],users[k]))
    return dis

def init_p(uavs_pos,users):
    uavs_initial = [i for i in range(len(uavs_pos))]
    combination = list(combinations(uavs_initial, 3))
    c_association, p_association = p_tool.get_p_association_first(users, uavs_pos,
                                                                  math.ceil(len(users) / len(combination)),
                                                                  math.ceil(len(users) / len(uavs_pos)))
    uav_to_user=tool.get_uav_to_user(c_association,uavs_pos)
    print(uav_to_user)
    p_rest=tool.get_rest_p(users,uavs_pos,p_association)
    # print(p_rest)
    p_alloc=[]
    for i in range(len(uavs_pos)):
        #归一化生成 功率
        dis=get_dis(i,uavs_pos,users,uav_to_user)
        # p=[random.randint(1,len(uav_to_user[i])) for i in range(len(uav_to_user[i]))]
        p_new=[0 for i in range(len(users))]
        for j in range(len(uav_to_user[i])):
            p_new[uav_to_user[i][j]]=dis[j]/sum(dis)*p_rest[i]
            # p_new.append(p[j]/sum(p)*p_rest[i])
        p_alloc.append(p_new)
        # p_alloc.append(np.random.uniform(0, p_rest[i] / len(uav_to_user[i]), (len(uav_to_user[i]))))
    return p_alloc

#交叉 pos_solution1=[[],[],[]]
def cross_over(pos_solution1,pos_solution2):
    child1=[]
    child2=[]
    for i in range(len(pos_solution1)):
        pos1 = []
        pos2=[]
        beta = get_beta()
        for j in range(len(pos_solution1[i])):
            if j<len(pos_solution1[i])-1:
                x1 = (pos_solution1[i][j] + pos_solution2[i][j]) / 2
                x2 = abs((pos_solution1[i][j] - pos_solution2[i][j]) / 2)
                x1=x1 + beta * x2
                x2=abs(x1 - beta * x2)
                pos1.append(x1)
                pos2.append(x2)
            else:
                pos1.append(100)
                pos2.append(100)
        child1.append(pos1)
        child2.append(pos2)
    return child1,child2

def cross_over_p(p_solution1,p_solution2):
    child1 = []
    child2 = []
    for i in range(len(p_solution1)):
        p1 = []
        p2 = []
        beta = get_beta()
        for j in range(len(p_solution1[i])):
            x1 = (p_solution1[i][j] + p_solution2[i][j]) / 2
            x2 = abs((p_solution1[i][j] - p_solution2[i][j]) / 2)
            x1 = x1 + beta * x2
            x2 = abs(x1 - beta * x2)
            p1.append(x1)
            p2.append(x2)

        child1.append(p1)
        child2.append(p2)
    return child1,child2


def get_beta(crossover_param=2):
    u = random.random()
    if u <= 0.5:
        return (2 * u) ** (1 / (crossover_param + 1))
    return (2 * (1 - u)) ** (-1 / (crossover_param + 1))

def mutate(child,variables_range):
    u, delta = get_delta()
    child_new=[]
    if u < 0.5:
        for i in range(len(child)):
            pos=[]
            for j in range(len(child[i])):
                if j < len(child[i]) - 1:
                    x=child[i][j]+ delta * (child[i][j] - variables_range[0])
                    pos.append(x)
                else:
                    pos.append(100)
            child_new.append(pos)
    else:
        for i in range(len(child)):
            pos = []
            for j in range(len(child[i])):
                if j<len(child[i])-1:
                    x= child[i][j] +delta * (variables_range[1] - child[i][j])
                    pos.append(x)
                else:
                    pos.append(100)
            child_new.append(pos)
    for i in range(len(child_new)):
        for j in range(len(child_new[i])):
            if j<len(child_new[i])-1:
                if child_new[i][j] < variables_range[0]:
                    child_new[i][j] = variables_range[0]
                elif child_new[i][j] > variables_range[1]:
                    child_new[i][j] = variables_range[1]
    return child_new

def mutate_p(child,variables_range):
    return

def get_delta(mutation_param=5):
    u = random.random()
    if u < 0.5:
        return u, (2 * u) ** (1 / (mutation_param + 1)) - 1
    return u, 1 - (2 * (1 - u)) ** (1 / (mutation_param + 1))

def get_function_values(pop_size,pos_solution,p_solution):
    function1_values = []
    function2_values = []
    punish_values = []
    for i in range(pop_size):
        uavs_pos = pos_solution[i]
        uavs_initial = [i for i in range(len(uavs_pos))]
        combination = list(combinations(uavs_initial, 3))
        c_association,p_association=p_tool.get_p_association_first(users, uavs_pos, math.ceil(len(users) / len(combination)),
                                math.ceil(len(users) / len(uavs_pos)))
        # c_association = tool.get_c_association(users, uavs_pos, math.ceil(len(users) / len(uavs_pos)))
        # p_association = tool.get_p_association(users, uavs_pos, c_association, len(users) * 2 / len(uavs_pos))
        p_rest = tool.get_rest_p(users, uavs_pos, p_association)
        function1_values.append(function_snr(users, pos_solution[i], c_association, p_solution[i]))
        function2_values.append(function_gdop(users, uavs_pos, c_association, p_association, ))
        punish_values.append(punish(p_solution[i], p_rest))
    return function1_values,function2_values,punish_values


def tournament(pos_solution,non_dominated_sorted_solution,rank,distance):
    a1 = random.randint(0, len(pos_solution) - 1)
    b1=a1
    while b1==a1:
        b1 = random.randint(0, len(pos_solution) - 1)
    participants = [pos_solution[a1],pos_solution[b1]]
    best = None
    for participant in participants:
        if best is None or crowding_operator(a1,b1,non_dominated_sorted_solution,rank,distance) == 1:
            best = participant
    return best

def get_f_by_pos(pos):
    c_association = tool.get_c_association(users, pos, math.ceil(len(users) / len(pos)))
    p_association = tool.get_p_association(users, pos, c_association, len(users) * 2 / len(pos))
    p = init_p(pos, users)
    function1_value=function_snr(users, pos, c_association, p)
    function2_value=function_gdop(users, pos, c_association, p, )
    return function1_value,function2_value

def crowding_operator(index1,index2,non_dominated_sorted_solution,rank,distance):
    rank1=rank[index1]#index1的等级
    rank2=rank[index2]
    distance1=0
    distance2=0
    for i in range(len(non_dominated_sorted_solution[rank1])):
        if non_dominated_sorted_solution[rank1][i]==index1:
            distance1=distance[rank1][i]
    for i in range(len(non_dominated_sorted_solution[rank2])):
        if non_dominated_sorted_solution[rank2][i]==index2:
            distance2=distance[rank2][i]
    if rank1<rank2 or (rank1==rank2 and distance1>distance2):
        return 1
    else:
        return 0

def main(users,pop_size,max_gen,k=3):
    pos_solution,p_solution=init(pop_size,k,users)
    print(p_solution)
    # max_gen = 100
    gen_no = 0
    pos_range=[0,1000]
    best_pos=[]
    best_p=[]
    f1_best=[]
    f2_best=[]
    while(gen_no<max_gen):
        function1_values,function2_values,punish_values=get_function_values(pop_size,pos_solution,p_solution)
        # for i in range(pop_size):
        #     uavs_pos=pos_solution[i]
        #     c_association = tool.get_c_association(users, uavs_pos, math.ceil(len(users) / len(uavs_pos)))
        #     p_association=tool.get_p_association(users,uavs_pos,c_association,len(users)*2/len(uavs_pos))
        #     p_rest=tool.get_rest_p(users, uavs_pos, p_association)
        #     function1_values.append(function_snr(users,pos_solution[i],c_association,p_solution[i]))
        #     function2_values.append(function_gdop(users,uavs_pos,c_association,p_association,))
        #     punish_values.append(punish(p_solution[i],p_rest))
        print(function1_values)
        print(function2_values)
        print(punish_values)
        non_dominated_sorted_solution,rank = fast_non_dominated_sort(function1_values[:], function2_values[:])
        print(non_dominated_sorted_solution)
        print("等级")
        print(rank)
        crowding_distance_values=[]
        for i in range(0,len(non_dominated_sorted_solution)):
            crowding_distance_values.append(crowding_distance(function1_values[:],function2_values[:],non_dominated_sorted_solution[i][:]))
        pos_solution2 = pos_solution[:]
        p_solution2=p_solution[:]
        #排序要考虑惩罚项
        #交叉变异生成子代
        while (len(pos_solution2) != 2 * pop_size):
            #锦标赛选择
            parent1 = tournament(pos_solution,non_dominated_sorted_solution,rank,crowding_distance_values)
            parent2 = parent1
            while parent1== parent2:
                parent2 = tournament(pos_solution,non_dominated_sorted_solution,rank,crowding_distance_values)
            #交叉变异
            child1,child2=cross_over(parent1,parent2)

            child1_mute=mutate(child1,pos_range)
            child2_mute=mutate(child2,pos_range)
            child1_p=init_p(child1_mute,users)
            child2_p=init_p(child2_mute,users)
            pos_solution2.append(child1_mute)
            pos_solution2.append(child2_mute)
            p_solution2.append(child1_p)
            p_solution2.append(child2_p)
        function1_values2, function2_values2, punish_values2 = get_function_values(2*pop_size, pos_solution2, p_solution2)
        print(function1_values2)
        print(function2_values2)
        print(punish_values2)
        non_dominated_sorted_solution2,rank2 = fast_non_dominated_sort(function1_values2[:], function2_values2[:])
        print(non_dominated_sorted_solution2)
        print(rank2)
        crowding_distance_values2 = []
        for i in range(0, len(non_dominated_sorted_solution2)):
            crowding_distance_values2.append(
                crowding_distance(function1_values2[:], function2_values2[:], non_dominated_sorted_solution2[i][:]))
        new_solution = []
        for i in range(0, len(non_dominated_sorted_solution2)):
            non_dominated_sorted_solution2_1 = [
                index_of(non_dominated_sorted_solution2[i][j], non_dominated_sorted_solution2[i]) for j in
                range(0, len(non_dominated_sorted_solution2[i]))]
            front22 = sort_by_values(non_dominated_sorted_solution2_1[:], crowding_distance_values2[i][:])
            front = [non_dominated_sorted_solution2[i][front22[j]] for j in
                     range(0, len(non_dominated_sorted_solution2[i]))]
            front.reverse()
            for value in front:
                new_solution.append(value)
                if (len(new_solution) == pop_size):
                    break
            if (len(new_solution) == pop_size):
                break
        pos_solution = [pos_solution2[i] for i in new_solution]
        p_solution=[p_solution2[i] for i in new_solution]
        # function1_last, function2_last, _ = get_function_values(len(solution), solution,
        #                                                         p_solution_)
        # non_dominated_sorted_solution = fast_non_dominated_sort(function1_last[:], function2_last[:])
        # print(non_dominated_sorted_solution[0])
        # pos_now=[solution[i] for i in non_dominated_sorted_solution[0]]
        # p_now=[p_solution_[i] for i in non_dominated_sorted_solution[0]]
        # best_pos.append(pos_now)
        # best_p.append(p_now)
        function1_best,function2_best,_=get_function_values(len(pos_solution),pos_solution,
                                                                p_solution)
        non_dominated_sorted_solution3,_ = fast_non_dominated_sort(function1_best[:], function2_best[:])
        function1_best1=[]
        function2_best1 = []
        for i in range(len(non_dominated_sorted_solution3[0])):
            # print(i)
            function1_best1.append(function1_best[non_dominated_sorted_solution3[0][i]])
            function2_best1.append(function2_best[non_dominated_sorted_solution3[0][i]])

        # f1_best.extend(function1_best1)
        # f2_best.extend(function2_best1)
        f1_best=function1_best1
        f2_best=function2_best1
        gen_no+=1

    # plt.xlabel('average snr', fontsize=15)
    # plt.ylabel('average 1/gdop', fontsize=15)
    # plt.scatter(function1_best, function2_best)
    # plt.show()
    return f1_best,f2_best,best_pos,best_p




if __name__ == '__main__':
    users = Users.getUsers("./data.csv")
    f1,f2,_,_=main(users,60,500,4)
    print(f1, f2)
    plt.xlabel('average snr', fontsize=12)
    plt.ylabel('average -gdop', fontsize=12)

    plt.scatter(f1, f2,)
    plt.show()

