import sys
import time

import numpy as np

from util import get_random_point_100


class Point:
    def __init__(self, p, val):
        self.p = p
        self.val = val


class DL:
    def __init__(self, d, L):
        # d is a distance |v_i-v_j|
        self.d = d
        # L is Lipschitz value |f(v_i)-f(v_j)|/|v_i-v_j|)
        self.L = L


class LipoLD:
    def __init__(self, cec2017, fn_number, population_size_global, population_size, initial_sample_count, limit, dim,
                 break_when_found_good_estimate):
        self.cec2017 = cec2017
        self.min_so_far = sys.float_info.max
        self.fn_number = fn_number
        self.population_size = population_size
        self.population_size_global = population_size_global
        self.break_when_found_good_estimate = break_when_found_good_estimate
        self.limit = limit
        self.dim = dim
        self.initial_sample_count = initial_sample_count

        self.history = self.init_history(initial_sample_count)
        self.lip_list = self.init_lip_list()

    def init_history(self, initial_sample_count):
        initial_points_set = [get_random_point_100(self.dim) for _ in range(initial_sample_count)]

        def evaluate_points_set(l):
            return [Point(el, self.cec2017(self.fn_number, np.array(el))[0]) for el in l]

        # create a list of Points
        return evaluate_points_set(initial_points_set)

    def init_lip_list(self):
        def get_list_of_distances_and_slopes_with_itself(l):
            vals = []
            for i1, p1 in enumerate(l):
                for p2 in l[i1 + 1:]:
                    d = np.linalg.norm(p1.p - p2.p)
                    if d > 0:
                        vals.append(DL(d, abs(p1.val - p2.val) / d))
            return vals

        def sort_by_distance(l):
            return sorted(l, key=lambda p: p.d)

        # create a list generated by different pair of the list above: list of DL
        # sort by distance (descending order)
        distances_with_slopes = get_list_of_distances_and_slopes_with_itself(self.history)
        sorted_by_dist = sort_by_distance(distances_with_slopes)

        # create first Lipschitz list by merging an empty list with sorted_evaluated
        return self.merge([], sorted_by_dist)

    def get_list_of_distances_and_slopes_with_point(self, l, point):
        vals = []
        for h_point in l:
            if (h_point.p == point.p).all():
                continue
            d = np.linalg.norm(h_point.p - point.p)
            vals.append(DL(d, np.abs(h_point.val - point.val) / d))

        return vals

    # estimates value of function at unknown point using multiple Lipschitz ratios
    def estimate_max_min(self, p, min_this_iteration):
        old_point = self.history[0]  # old point

        d = np.linalg.norm(p - old_point.p)
        est = old_point.val - self.slope_estimate(d) * d
        for i, old_point in enumerate(self.history[1:]):
            d = np.linalg.norm(p - old_point.p)
            est = old_point.val - self.slope_estimate(d) * d
            if est >= min_this_iteration:
                return None
            # TODO try pruning more with minimum value
        return est

    def optimize_min(self):
        frequency = 100
        for iteration in range(self.limit - self.initial_sample_count):
            if iteration % frequency == 0:
                print('lip_list length ', len(self.lip_list))
                print('iteration ', iteration)
                print('best point', self.min_so_far)
                print('theoretical best', 100. * self.fn_number)
                tt = time.time()

            best_point = Point(np.zeros(self.dim), np.infty)

            for _ in range(self.population_size_global):
                x = get_random_point_100(self.dim)
                estimated_val = self.estimate_max_min(x, self.min_so_far)
                if estimated_val is not None and estimated_val < best_point.val:
                    best_point.val = estimated_val
                    best_point.p = x
                    if self.break_when_found_good_estimate:
                        break

            if best_point.val == np.infty:
                for _ in range(self.population_size):
                    x = get_random_point_100(self.dim)
                    estimated_val = self.estimate_max_min(x, best_point.val)
                    # TODO ola mark each v_{argmax_i{ f(v_i) - L(|x-v_i|)*|x-v_i|}} with current loop id/number (label it as fresh)
                    # TODO kazimierz: is above TODO still relevant?
                    if estimated_val is not None and estimated_val < best_point.val:
                        best_point.val = estimated_val
                        best_point.p = x

            # choose the probe point with minimum estimated value to be evaluated (say, p_opt)
            # evaluate f at this optimal point p_opt
            best_point.val = self.cec2017(self.fn_number, np.array(best_point.p))[0]
            if best_point.val < self.min_so_far:
                self.min_so_far = best_point.val
            sorted_dls = self.get_list_of_distances_and_slopes_with_point(self.history, best_point)

            self.history.append(best_point)

            # build a sorted list of tuples (|v_i - p_opt|, |f(v_i)-f(p_opt)|/|v_i-p_opt|), sort by key descending
            # merge Lipschitz list with the list of tuples you just built
            self.lip_list = self.merge(self.lip_list, sorted_dls)

            # TODO below comment
            # if evaluation_step mod s == 0
            # discard the least fresh points so that there is at most [s] surviving freshest
            # recompute Lipschitz list
            if iteration % frequency == 0:
                print('elapsed:', time.time() - tt)
                print()
        # TODO someday: perhaps cma-es algorithm will fine-tune the remaining local optimum we have found?

    def slope_estimate(self, d):
        list_length = len(self.lip_list)
        lower = 0
        upper = list_length
        # element is inside [lower, upper)
        # lower is always < upper - 1
        while lower < upper:  # use < instead of <=
            # if lower == upper - 1, x should be lower
            x = lower + (upper - lower) // 2
            # x is inside [lower, upper - 1]
            distance_at_x = self.lip_list[x].d
            if d > distance_at_x:
                # should look to the left for the element
                #
                # if lower == x:   # these two are the actual lines
                # return         # you're looking for
                upper = x
                if upper == 0:
                    return self.lip_list[0].L
            elif d < distance_at_x:
                # should look to the right for the element
                lower = x + 1
                if lower == list_length:
                    return self.lip_list[-1].L
            elif d == distance_at_x:
                return x
        # lower == upper
        return self.lip_list[lower].L

    # merges two sorted lists descending by first element
    # returns a new list with ascending second element and sorted descending by first element
    def merge(self, L1, L2):
        nL = []
        r1 = r2 = 0
        pL = -np.infty
        pd = np.infty
        while r1 < len(L1) or r2 < len(L2):
            if (r1 < len(L1) and r2 < len(L2) and L1[r1].d >= L2[r2].d) or r2 == len(L2):
                # consider element from L1 list
                if L1[r1].L > pL:
                    if pd == L1[r1].d:
                        nL.pop()
                    nL.append(L1[r1])
                    pd = L1[r1].d
                    pL = L1[r1].L
                # in either case skip the element
                r1 += 1
            else:
                # consider element from L2 list
                if L2[r2].L > pL:
                    if pd == L2[r2].d:
                        nL.pop()
                    nL.append(L2[r2])
                    pd = L2[r2].d
                    pL = L2[r2].L
                # in either case skip the element
                r2 += 1

        return nL
