//
// Created by brand on 4/11/2018.
//

#include "Grid.h"
#include<iostream>
#include<queue>
#include "Grid.h"
#include <iostream>
#include <vector>
#include <string>
#include <list>

#include <limits> // for numeric_limits

#include <set>
#include <utility> // for pair
#include <algorithm>
#include <iterator>

using namespace std;

typedef int vertex_t;
typedef double weight_t;
struct neighbor {
    vertex_t target;
    weight_t weight;
    neighbor(vertex_t arg_target, weight_t arg_weight)
            : target(arg_target), weight(arg_weight) { }
};

Grid::Grid() {

    const weight_t max_weight = std::numeric_limits<double>::infinity();
    this->generate_grid();

}


Grid::Grid(uint8_t width, uint8_t length) {
    this->width = width;
    this->length = length;
    this->generate_grid();
}
void Grid::DijkstraComputePaths(vertex_t source,
                          const adjacency_list_t &adjacency_list,
                          std::vector<weight_t> &min_distance,
                          std::vector<vertex_t> &previous)
{
    int n = adjacency_list.size();
    min_distance.clear();
    min_distance.resize(n, max_weight);
    min_distance[source] = 0;
    previous.clear();
    previous.resize(n, -1);
    std::set<std::pair<weight_t, vertex_t> > vertex_queue;
    vertex_queue.insert(std::make_pair(min_distance[source], source));

    while (!vertex_queue.empty())
    {
        weight_t dist = vertex_queue.begin()->first;
        vertex_t u = vertex_queue.begin()->second;
        vertex_queue.erase(vertex_queue.begin());

        // Visit each edge exiting u
        const std::vector<neighbor> &neighbors = adjacency_list[u];
        for (std::vector<neighbor>::const_iterator neighbor_iter = neighbors.begin();
             neighbor_iter != neighbors.end();
             neighbor_iter++)
        {
            vertex_t v = neighbor_iter->target;
            weight_t weight = neighbor_iter->weight;
            weight_t distance_through_u = dist + weight;
            if (distance_through_u < min_distance[v]) {
                vertex_queue.erase(std::make_pair(min_distance[v], v));

                min_distance[v] = distance_through_u;
                previous[v] = u;
                vertex_queue.insert(std::make_pair(min_distance[v], v));

            }

        }
    }
}

/*
 *
 * Caller
            std::vector<weight_t> min_distance;
        std::vector<vertex_t> previous;
        DijkstraComputePaths(0, adjacency_list, min_distance, previous);
        std::cout << "Distance from 0 to 4: " << min_distance[4] << std::endl;
        std::list<vertex_t> path = DijkstraGetShortestPathTo(4, previous);
        std::cout << "Path : ";
        std::copy(path.begin(), path.end(), std::ostream_iterator<vertex_t>(std::cout, " "));
        std::cout << std::endl;

        return 0;

 */



void Grid::generate_grid() {
    // Define grid and storing in member variable






    typedef std::vector<std::vector<neighbor> > adjacency_list_t;



    std::list<vertex_t> DijkstraGetShortestPathTo(
            vertex_t vertex, const std::vector<vertex_t> &previous)
    {
        std::list<vertex_t> path;
        for ( ; vertex != -1; vertex = previous[vertex])
            path.push_front(vertex);
        return path;
    }



    // remember to insert edges both ways for an undirected graph
    adjacency_list_t adjacency_list(25);
    // 0 = a
    adjacency_list[0].push_back(neighbor(1, 7));
    adjacency_list[0].push_back(neighbor(2, 9));
    adjacency_list[0].push_back(neighbor(5, 14));
    // 1 = b
    adjacency_list[1].push_back(neighbor(0, 7));
    adjacency_list[1].push_back(neighbor(2, 10));
    adjacency_list[1].push_back(neighbor(3, 15));
    // 2 = c
    adjacency_list[2].push_back(neighbor(0, 9));
    adjacency_list[2].push_back(neighbor(1, 10));
    adjacency_list[2].push_back(neighbor(3, 11));
    adjacency_list[2].push_back(neighbor(5, 2));
    // 3 = d
    adjacency_list[3].push_back(neighbor(1, 15));
    adjacency_list[3].push_back(neighbor(2, 11));
    adjacency_list[3].push_back(neighbor(4, 6));
    // 4 = e
    adjacency_list[4].push_back(neighbor(3, 6));
    adjacency_list[4].push_back(neighbor(5, 9));
    // 5 = f
    adjacency_list[5].push_back(neighbor(0, 14));
    adjacency_list[5].push_back(neighbor(2, 2));
    adjacency_list[5].push_back(neighbor(4, 9));


    1, 2 , 1);
    1, 8 , 1);

    2, 3 , 1);
    2, 9 , 1);

    3, 4 , 1);
    3, 10 , 1);

    4, 5 , 1);
    4, 11 , 1);

    5, 6 , 1);
    5, 12 , 1);

    6, 7 , 1);
    6, 13 , 1);

    7, 14 , 1);

    8, 9 , 1);
    8, 15 , 1);
    8, 1 , 1);
    9, 10 , 1);
    9, 16 , 1);
    9, 2 , 1);
    10, 11 , 1);
    10, 17 , 1);
    10, 3 , 1);
    11, 12 , 1);
    11, 18 , 1);
    11, 4 , 1);
    12, 13 , 1);
    12, 19 , 1);
    12, 5 , 1);
    13, 14 , 1);
    13, 20 , 1);
    13, 6 , 1);
    14, 21 , 1);
    14, 7 , 1);
    15, 16 , 1);
    15, 22 , 1);
    15, 8 , 1);
    16, 17 , 1);
    16, 23 , 1);
    16, 9 , 1);
    17, 18 , 1);
    17, 24 , 1);
    17, 10 , 1);
    18, 19 , 1);
    18, 25 , 1);
    18, 11 , 1);
    19, 20 , 1);
    19, 26 , 1);
    19, 12 , 1);
    20, 21 , 1);
    20, 27 , 1);
    20, 13 , 1);
    21, 14 , 1);
    22, 23 , 1);
    22, 29 , 1);
    22, 15 , 1);
    23, 24 , 1);
    23, 30 , 1);
    23, 16 , 1);
    24, 25 , 1);
    24, 31 , 1);
    24, 17 , 1);
    25, 26 , 1);
    25, 32 , 1);
    25, 18 , 1);


    2, 1 , 1);
    3, 2 , 1);
    4, 3 , 1);
    5, 4 , 1);
    6, 5 , 1);
    9, 8 , 1);
    10, 9 , 1);
    11, 10 , 1);
    12, 11 , 1);
    13, 12 , 1);
    16, 15 , 1);
    17, 16 , 1);
    18, 17 , 1);
    19, 18 , 1);
    20, 19 , 1);
    23, 22 , 1);
    24, 23 , 1);
    25, 24 , 1);



}



}


/**
 *
 * @param width used to know which width coordinate
 * @param length used to know which length coordinate
 */
void Grid::addObstacle(unsigned int width, unsigned int length) {
    this->grid[]

}

vector<int> Grid::pathFinding() {
    // generating a path which is returned in a series of ints inside a vector
    // pathfinder will avoid obstacles

}