# import Pkg
#Pkg.add("DataFrames")
#Pkg.add("CSV")

using Distributed
using DataFrames
using CSV
using LinearAlgebra
@everywhere using Random

#set up extra processes for parallel runs
println(nprocs())
println(nworkers())

addprocs(Sys.CPU_THREADS - 1);
println(nworkers())

st70 = CSV.read("data/st70.csv");

head(st70, 10)

"""
    euclidean_distance_matrix(cities)

Compute a matrix of euclidean distances between
city x, y coordinate pairs

# Arguments
- cities::Array: n x 2 matrix of x, y coordinates

"""
function euclidean_distance_matrix(cities)
    nrows = size(cities)[1]
    matrix = zeros(nrows, nrows)
    
    row = 1
    
    for city1 in 1:nrows
        col = 1
        for city2 in 1:nrows
            matrix[row, col] = norm(cities[city1, 1:2]-cities[city2, 1:2])
            col+=1
        end
        row +=1
    end
        
    return matrix
end

trim_cities(df, ncities) = Array(df[2:end])[1:ncities, :]

"""
    tour_cost(tour, matrix)

Compute the travel cost of tour using
the cost matrix
"""
function tour_cost(tour, matrix)
    cost = 0.0
    for i in 1:size(tour)[1] - 1
        cost += matrix[tour[i], tour[i+1]]
    end
    
    cost += matrix[tour[end], tour[1]]
    
    return cost
end

@everywhere begin
"""
    simple_tweak!(tour)

Simple swap of elemements in an array
Note this modifies the input array
This is more efficient than returning a copy.
"""
function simple_tweak!(tour, i, j)
    tour[i], tour[j] = tour[j], tour[i]
end
    
end

@everywhere function tweak_two_opt!(tour, i, j)
    reverse!(tour, i, j)
end

@everywhere begin
"""
    steepest_ascent(init_solution, matrix; time_limit=2.0, tweak!=simple_tweak!)

First improvement local search

Iteratively test candidate solutions in the neigbourhood
of the best solution and adopt the first improvement found.
Executes until time_limit is reached (default 2 seconds) or no improvements
found.

# Arguments

- intial_solution::Array: initial tour
- matrix::Array 2x2. costs of travel
- time_limit::int64: maximum run time
- tweak::func(tour::Array, i::Int, j::Int): tweak function modifies tour in place
    default = simple_tweak!

# Returns
- Tuple (best_cost, best_solution)

"""
function steepest_ascent(init_solution, matrix; time_limit=2.0, tweak=simple_tweak!)
        
    best = copy(init_solution)
    best_cost = -tour_cost(init_solution, matrix)
    n_cities = size(init_solution)[1]
    
    #candidate solution
    candidate = copy(init_solution)
    
    start = time()
    improvement = true
    best_city_i = 1
    best_city_j = 2
    
    while improvement && (time() - start) < time_limit
        improvement = false
    
        for city_i in 1:n_cities
            for city_j in city_i+1:n_cities
                tweak(candidate, city_i, city_j)
                cost = -tour_cost(candidate, matrix)
                
                if cost > best_cost
                    best_cost = cost
                    best_city_i = city_i
                    best_city_j = city_j
                    improvement = true
                end
                
                #reverse swap and continue search
                tweak(candidate, city_i, city_j)
                            
            #revert to best found
            tweak(candidate, best_city_i, best_city_j)
            
            best_solution = copy(candidate)        
                    
            end
        end
    end
    
    return -best_cost, best
end
   
#end @everywhere
end

Random.seed!(42);

coords = trim_cities(st70, 20);
matrix = euclidean_distance_matrix(coords)
tour = [i for i in 1:size(coords)[1]]

# add solution code
@time results1  = steepest_ascent(shuffle(tour), matrix)

@time results2 = steepest_ascent(shuffle(tour), matrix, tweak=tweak_two_opt!)

println(results1)
println(results2)