/**
 * @file graph_utils_imp.hpp
 *
 * CopyRight F. J. Madrid-Cuevas <fjmadrid@uco.es>
 *
 * Sólo se permite el uso de este código en la docencia de las asignaturas sobre
 * Estructuras de Datos de la Universidad de Córdoba.
 *
 * Está prohibido su uso para cualquier otro objetivo.
 */
#pragma once

#include <string>

#include <graph.hpp>
#include <graph_iterators.hpp>

template <class T>
WGraph<T>::WGraph()
{
    assert(capacity() == 0);
    assert(is_empty());
    assert(is_full());
    assert(order() == 0);
}

template <class T>
WGraph<T>::WGraph(size_t capacity_, bool directed)
{
    assert(capacity_ > 0);
    is_directed_ = directed;
    weights_.resize(capacity_, capacity_, std::numeric_limits<float>::infinity());
    assert(is_empty());
    assert(!is_full());
    assert(order() == 0);
    assert(capacity() == capacity_);
    assert(is_directed() == directed);
}

template <class T>
size_t WGraph<T>::capacity() const
{
    return weights_.rows();
}

template <class T>
bool WGraph<T>::is_directed() const
{
    assert(capacity() > 0);
    return is_directed_;
}
template <class T>
size_t WGraph<T>::order() const
{
    return vertex_items_.size();
}

template <class T>
bool WGraph<T>::is_empty() const
{
    return order() == 0;
}

template <class T>
bool WGraph<T>::is_full() const
{
    return order() == capacity();
}

template <class T>
size_t WGraph<T>::size() const
{
    size_t ret_v = 0;
    float inf = std::numeric_limits<float>::infinity();
    for (size_t u = 0; u < order(); ++u) {
        size_t start_v = is_directed() ? 0 : u + 1;
        for (size_t v = start_v; v < order(); ++v) {
            if (weights_.get(u, v) < inf) {
                ret_v++;
            }
        }
    }
    assert(!is_directed() || ret_v <= (order() * order()));
    assert(is_directed() || ret_v <= ((order() * (order() + 1)) / 2));
    return ret_v;
}

template <class T>
bool WGraph<T>::has(Vertex<T> const &u) const
{
    return u.graph_ == this && u.label_ < order();
}

template <class T>
VertexIterator<T> WGraph<T>::vertex(size_t label)
{
    assert(label < order());
    return VertexIterator<T>(Vertex<T>(label, this));
}

template <class T>
const_VertexIterator<T> WGraph<T>::vertex(size_t label) const
{
    assert(label < order());
    return const_VertexIterator<T>(const_cast<WGraph<T>*>(this)->vertex(label));
}

template <class T>
T const &WGraph<T>::item(size_t label) const
{
    assert(label < order());
    return vertex_items_[label];
}

template <class T>
std::vector<T> const &WGraph<T>::items() const
{
    return vertex_items_;
}

template <class T>
FMatrix const &WGraph<T>::weights() const
{
    return weights_;
}

template <class T>
float WGraph<T>::weight(size_t u, size_t v) const
{
    assert(u < order());
    assert(v < order());
    return weights_.get(u, v);
}

template <class T>
bool WGraph<T>::is_adjacent(size_t u, size_t v) const
{
    assert(u < order());
    assert(v < order());
    return weights_.get(u, v) < std::numeric_limits<float>::infinity();
}

template <class T>
bool WGraph<T>::is_visited(size_t u_label) const
{
    assert(u_label < order());
    return visited_vertices_[u_label];
}

template <class T>
EdgeIterator<T> WGraph<T>::edge(size_t u_label, size_t v_label)
{
    assert(u_label < order());
    assert(v_label < order());
    EdgeIterator<T> ret_v = EdgeIterator<T>(Edge<T>(u_label, v_label, this));
    assert(ret_v->first()->label() == u_label);
    assert(ret_v->second()->label() == v_label);
    assert(ret_v->item() == weight(u_label, v_label));
    return ret_v;
}

template <class T>
const_EdgeIterator<T> WGraph<T>::edge(size_t u_label, size_t v_label) const
{
    assert(u_label < order());
    assert(v_label < order());
    const_EdgeIterator<T> ret_v = const_EdgeIterator<T>(const_cast<WGraph<T>*>(this)->edge(u_label, v_label));
    assert(ret_v->first().label() == u_label);
    assert(ret_v->second().label() == v_label);
    assert(ret_v->item() == weight(u_label, v_label));
    return ret_v;
}

template <class T>
void WGraph<T>::reset(bool state)
{
    std::fill(visited_vertices_.begin(), visited_vertices_.end(), state);
#ifndef NDEBUG
    for (size_t u = 0; u < order(); ++u)
        assert(is_visited(u) == state);
#endif
}

template <class T>
void WGraph<T>::set_item(size_t v_label, const T &new_item)
{
    assert(v_label < order());
    vertex_items_[v_label] = new_item;
    assert(new_item == item(v_label));
}

template <class T>
void WGraph<T>::set_weight(size_t u_label, size_t v_label, float new_w)
{
    assert(u_label < order());
    assert(v_label < order());
    weights_.set(u_label, v_label, new_w);
    if (!is_directed()) {
        weights_.set(v_label, u_label, new_w);
    }
    assert(new_w == weight(u_label, v_label));
    assert(is_directed() || new_w == weight(v_label, u_label));
}

template <class T>
void WGraph<T>::set_visited(size_t u_label, bool new_state)
{
    assert(u_label < order());
    visited_vertices_[u_label] = new_state;
    assert(new_state == is_visited(u_label));
}

template <class T>
VertexIterator<T> WGraph<T>::add_vertex(T const &v)
{
    assert(!is_full());
#ifndef NDEBUG
    size_t old_order = order();
#endif
    size_t new_label = order();
    vertex_items_.push_back(v);
    visited_vertices_.push_back(false);
    VertexIterator<T> ret_v = vertex(new_label);
    assert(order() == old_order + 1);
    assert(has(*ret_v));
    assert(ret_v->item() == v);
    assert(!ret_v->is_visited());
    return ret_v;
}

template <class T>
VertexIterator<T>
WGraph<T>::find_vertex(const T &item)
{
    VertexIterator<T> iter = vertices_end();
    for (size_t i = 0; i < order(); ++i) {
        if (vertex_items_[i] == item) {
            iter = vertex(i);
            break;
        }
    }
    assert(iter == vertices_end() || iter->item() == item);
    return iter;
}

template <class T>
const_VertexIterator<T>
WGraph<T>::find_vertex(const T &item) const
{
    const_VertexIterator<T> iter = vertices_end();
    for (size_t i = 0; i < order(); ++i) {
        if (vertex_items_[i] == item) {
            iter = vertex(i);
            break;
        }
    }
    assert(iter == vertices_end() || iter->item() == item);
    return iter;
}

template <class T>
VertexIterator<T>
WGraph<T>::vertices_begin()
{
    if (order() > 0)
        return vertex(0);
    return vertices_end();
}

template <class T>
const_VertexIterator<T>
WGraph<T>::vertices_begin() const
{
    if (order() > 0)
        return vertex(0);
    return vertices_end();
}

template <class T>
VertexIterator<T>
WGraph<T>::vertices_end()
{
    return VertexIterator<T>(Vertex<T>(order(), this));
}

template <class T>
const_VertexIterator<T>
WGraph<T>::vertices_end() const
{
    return const_VertexIterator<T>(const_cast<WGraph<T>*>(this)->vertices_end());
}

template <class T>
EdgeIterator<T>
WGraph<T>::edges_begin(const VertexIterator<T> &v)
{
    assert(has(*v));
    size_t u = v->label();
    float inf = std::numeric_limits<float>::infinity();
    for (size_t adj = 0; adj < order(); ++adj) {
        if (weights_.get(u, adj) < inf) {
            return edge(u, adj);
        }
    }
    return edges_end(v);
}

template <class T>
const_EdgeIterator<T>
WGraph<T>::edges_begin(const const_VertexIterator<T> &v) const
{
    assert(has(*v));
    return const_EdgeIterator<T>(const_cast<WGraph<T>*>(this)->edges_begin(const_cast<WGraph<T>*>(this)->vertex(v->label())));
}

template <class T>
EdgeIterator<T>
WGraph<T>::edges_end(const VertexIterator<T> &v)
{
    assert(has(*v));
    return EdgeIterator<T>(Edge<T>(v->label(), order(), this));
}

template <class T>
const_EdgeIterator<T>
WGraph<T>::edges_end(const const_VertexIterator<T> &v) const
{
    assert(has(*v));
    return const_EdgeIterator<T>(const_cast<WGraph<T>*>(this)->edges_end(const_cast<WGraph<T>*>(this)->vertex(v->label())));
}

template <class T>
std::ostream &
operator<<(std::ostream &out, const WGraph<T> &g) noexcept
{
    out << (g.is_directed() ? "DIRECTED" : "UNDIRECTED") << "\n";
    out << g.order() << "\n";
    for (size_t i = 0; i < g.order(); ++i) {
        out << g.item(i) << "\n";
    }
    out << g.size() << "\n";
    float inf = std::numeric_limits<float>::infinity();
    for (size_t u = 0; u < g.order(); ++u) {
        size_t start_v = g.is_directed() ? 0 : u + 1;
        for (size_t v = start_v; v < g.order(); ++v) {
            if (g.weight(u, v) < inf) {
                out << g.item(u).key() << " " << g.item(v).key() << " " << g.weight(u, v) << "\n";
            }
        }
    }
    return out;
}

template <class T>
std::istream &
operator>>(std::istream &input, WGraph<T> &g) noexcept(false)
{
    std::string dir_str;
    if (!(input >> dir_str)) {
        return input;
    }
    bool directed = (dir_str == "DIRECTED");
    size_t order;
    if (!(input >> order)) {
        throw std::runtime_error("Wrong WGraph");
    }
    g = WGraph<T>(order, directed);
    for (size_t i = 0; i < order; ++i) {
        T item;
        if (!(input >> item)) {
            throw std::runtime_error("Wrong WGraph");
        }
        g.add_vertex(item);
    }
    size_t size;
    if (!(input >> size)) {
        throw std::runtime_error("Wrong WGraph");
    }
    for (size_t i = 0; i < size; ++i) {
        typename T::key_t u_key, v_key;
        float w;
        if (!(input >> u_key >> v_key >> w)) {
            throw std::runtime_error("Wrong WGraph");
        }
        auto u_it = g.find_vertex(u_key);
        auto v_it = g.find_vertex(v_key);
        if (u_it == g.vertices_end() || v_it == g.vertices_end()) {
            throw std::runtime_error("Wrong WGraph");
        }
        g.set_weight(u_it->label(), v_it->label(), w);
    }
    return input;
}