#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/r_c_shortest_paths.hpp>
#include <iostream>
#include <limits>
#include <numeric>

const unsigned long TIME_DIURNAL = 24 * 3600;

struct Cost {
    double curr_expense;
    unsigned long time_expense;

    Cost(const double curr_expense_, const unsigned long time_expense_) : curr_expense(curr_expense_),
                                                                          time_expense(time_expense_) {}

    Cost(bool inf) : curr_expense(std::numeric_limits<double>::infinity()),
                     time_expense(std::numeric_limits<unsigned long>::max()) {}

    friend bool operator> (const Cost& first, const Cost& second) {
        if (first.time_expense > second.time_expense)
            return true;
        else if (first.time_expense == second.time_expense) {
            return first.curr_expense > second.curr_expense;
        }
        return false;
    }

    friend bool operator< (const Cost& first, const Cost& second) {
        return !(first > second);
    }

    friend bool operator==(const Cost& first, const Cost& second) {
        return (first.time_expense == second.time_expense && first.curr_expense == second.curr_expense);
    }

    friend bool operator<= (const Cost& first, const Cost& second) {
        return (first < second) || (first == second);
    }
};

struct Slot {
    size_t index;

    double cost;
    unsigned long departure;
    unsigned long duration;

    Slot(
            size_t index_,
            double cost_,
            unsigned long departure_,
            unsigned long duration_) : index(index_),
                                       cost(cost_),
                                       departure(departure_),
                                       duration(duration_) {}

    unsigned long wait(const unsigned long arrival) const {
        // Total time spent on waiting for this slot before we can depart
        auto arrival_durinal = arrival % TIME_DIURNAL;
        return (arrival_durinal > departure) ? (TIME_DIURNAL - arrival_durinal + departure) : (departure - arrival_durinal);
    }

    Cost weight(const Cost& arrival, const Cost& limits) const {
        // Total currency and time spent on choosing this slot and arriving at arrival
        // when the maximum limits for both are limits
        Cost expense{cost, wait(arrival.time_expense) + duration};

        if (expense > limits)
            expense = Cost{true};
        return expense;
    }
};

typedef boost::adjacency_list<
    boost::vecS, boost::vecS,
    boost::directedS,
    boost::property<boost::vertex_name_t, std::string>,
    Slot> Graph;

typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;

Vertex get_or_create_vertex(std::string code, Graph& graph) {
    const auto iterator = boost::vertices(graph);
    auto vertex_name_map = boost::get(boost::vertex_name, graph);
    const auto viter = std::find_if(
        iterator.first,
        iterator.second,
        [code, vertex_name_map](const Vertex vertex) {
            return get(vertex_name_map, vertex) == code;
    });

    if (viter == iterator.second) {
        Vertex vertex_d = boost::add_vertex(graph);
        boost::put(vertex_name_map, vertex_d, code);
        return vertex_d;
    }
    return *viter;
}


struct Resource {
    Cost cost;

    Resource(Cost cost_=Cost{0, 0}) : cost(cost_) {}

    Resource& operator=(Resource& other) {
        std::swap(cost, other.cost);
        return *this;
    }

    friend bool operator< (const Resource& first, const Resource& second) {
        return first.cost < second.cost;
    }
};

class ResourceExtension {
private:
    Cost max;
public:
    ResourceExtension(Cost cost=Cost{0, 0}) : max(cost) {}

    inline bool operator()(const Graph& graph, Resource& next, const Resource& prev, Edge edge) const {
        auto slot = graph[edge];
        next.cost = slot.weight(prev.cost, max);
        return (next.cost <= max);
    }
};

class ResourceDominance {
public:
    inline bool operator()(const Resource& first, const Resource& second) const {
        return first.cost < second.cost;
    }
};

typedef typename boost::r_c_shortest_paths_label<Graph, Resource> Label;

int main() {
    Graph graph;
    std::vector<std::tuple<std::string, std::string, unsigned long, double> > matrix{
        {"A", "B", 44100, 54.1},
        {"B", "A", 39300, 40.0},
        {"B", "E", 11700, 1.0},
        {"E", "B", 11700, 1.0}
    };

    for (auto const& record: matrix) {
        std::vector<int> slack(24);
        std::iota(std::begin(slack), std::end(slack), 0);

        std::string source = std::get<0>(record);
        std::string target = std::get<1>(record);
        unsigned long min_duration = std::get<2>(record);
        double cost = std::get<3>(record);

        for (int seed = 0; seed < 24; ++seed) {
            for (int duration: slack) {
                unsigned long departure = seed * 3600;
                unsigned long c_duration = duration * 3600 + min_duration;
                Slot slot{boost::num_edges(graph), cost, departure, c_duration};

                auto source_d = get_or_create_vertex(source, graph);
                auto target_d = get_or_create_vertex(target, graph);
                boost::add_edge(source_d, target_d, slot, graph);
            }
        }
    }

    std::cout << "Graph has " << boost::num_edges(graph) << " edges" << std::endl;

    auto source = get_or_create_vertex("A", graph);
    auto destination = get_or_create_vertex("B", graph);

    std::vector<std::vector<Edge> > solutions;
    std::vector<Resource> pareto_optimal_resource_container;
    Resource initial{Cost{0, 0}};
    ResourceExtension resourceExtensionFunctor{Cost{std::numeric_limits<double>::max(), 345600}};
    ResourceDominance resourceDominanceFunctor;

    boost::r_c_shortest_paths(
            graph,
            boost::get(boost::vertex_index, graph),
            boost::get(&Slot::index, graph),
            source,
            destination,
            solutions,
            pareto_optimal_resource_container,
            initial,
            resourceExtensionFunctor,
            resourceDominanceFunctor,
            std::allocator<Label>(),
            boost::default_r_c_shortest_paths_visitor()
    );

    std::cout << "Solved" << std::endl;
}