// Project Identifier: 9B734EC0C043C5A836EA0EBE4BEFEA164490B2C7
#include <map>
#include <cmath>
#include <vector>
#include <string>
#include <limits>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <getopt.h>
#include <algorithm>
#include <unordered_map>
#include "MST.h"

// VERTEX //////////////////////////////////////////////////////////////////////////////
class Vertex{
    public:
    size_t id;
    double x;
    double y;
    double distance;
    bool visited;
    size_t prev;
    bool operator<(const Vertex& v1) const {
        return (id < v1.id);
    }
    Vertex(size_t &id_num, double &x_coord, double&y_coord): id(id_num), x(x_coord), y(y_coord), distance(std::numeric_limits<double>::infinity()), visited(false), prev(0){}
};

class OPT{
    public:
    std::vector<std::vector<double> > distance_matrix;
    std::vector<Vertex> container;
    std::vector<Vertex> path;
    std::vector<Vertex> best_path;
    double current_distance;
    double best_distance;
    OPT(): current_distance(0), best_distance(0){}
};

// UTILITIES //////////////////////////////////////////////////////////////////////////////
// set all vertices as not visited
void set_unvisited(std::vector<Vertex> & container);

// get vertices
void get_vertices(std::vector<Vertex> &container);

// returns weight from two vertices
double find_weight_v(Vertex &vertex_a, Vertex &vertex_b);

// add up all edges to get path length
double calc_path_length(std::vector<Vertex> &container);

// returns edge value (dik + dkj - dij)
double calc_edge(Vertex &vertex, std::vector<Vertex> &path, size_t &index);


// PART B //////////////////////////////////////////////////////////////////////////////
// finds nearest location to last inserted element in path
size_t nearest_location(size_t &last_inserted, std::vector<Vertex> &path, std::vector<Vertex> &container);

// returns insertion index that would cause the smallest increase in path length
size_t insert_position(std::vector<Vertex> &path, Vertex &vertex);

// run fasttsp
void run_fasttsp(std::vector<Vertex> &container);

// PART C //////////////////////////////////////////////////////////////////////////////
// create distance matrix
void construct_matrix(OPT &opt);

// get upper bound info from FASTTSP calculation
void get_upper_bound(OPT &opt);

// construct mst for gen_perms
double construct_mst(OPT &opt, size_t permLength);

// promising
bool promising(OPT &opt, size_t permLength);

// gen perms
void gen_perms(OPT &opt, size_t permLength);

// run opttsp
void run_opttsp(OPT &opt);


// TESTING /////////////////////////////////////////////////////////
// init path
void init_path(OPT &opt);

// reassign path
void reassign_path(OPT &opt);

// print path for testing
void print_path(std::vector<Vertex> &path);

// test container
void test_perm_container(std::vector<std::vector<Vertex> > &perm_container);

// test perms
void test_perms(std::vector<std::vector<Vertex> > &perm_container, std::vector<Vertex> &v_container, size_t permLength, size_t h);

// test opttsp
void test_run_opttsp(std::vector<Vertex> &v_container);