/**
 * @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());
    vertex_items_.reserve(capacity_);
    visited_vertices_.reserve(capacity_);

    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 vertex_items_.empty();
}

template <class T>
bool WGraph<T>::is_full() const
{
    return vertex_items_.size() >= weights_.rows();
}

template <class T>
size_t WGraph<T>::size() const
{
    size_t ret_v = 0;

    for (size_t u = 0; u < order(); ++u)
        for (size_t v = 0; v < order(); ++v)
        {
            if (!is_directed() && u >= v)
                continue;
            if (weights_[u][v] < std::numeric_limits<float>::infinity())
                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
{
    bool ret_v = (u.graph_ == this && u.label_ < order());
    return ret_v;
}

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

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

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_[u][v];
}

template <class T>
bool WGraph<T>::is_adjacent(size_t u, size_t v) const
{
    assert(u < order());
    assert(v < order());
    return (weight(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());

    Edge<T> e(u_label, v_label, this);
    EdgeIterator<T> ret_v(e);

    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());

    Edge<T> e(u_label, v_label, const_cast<WGraph<T> *>(this));
    EdgeIterator<T> ret_v(e);

    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)
{
    for (size_t i = 0; i < visited_vertices_.size(); ++i)
        visited_vertices_[i] = 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_[u_label][v_label] = new_w;
    if (!is_directed())
        weights_[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
    vertex_items_.push_back(v);
    visited_vertices_.push_back(false);
    Vertex<T> vx(order() - 1, this);
    VertexIterator<T> ret_v(vx);

    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_begin();
    while (iter != vertices_end() && iter->item() != item)
        ++iter;
    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_begin();
    while (iter != vertices_end() && iter->item() != item)
        ++iter;
    assert(iter == vertices_end() || iter->item() == item);
    return iter;
};

template <class T>
VertexIterator<T>
WGraph<T>::vertices_begin()
{
    Vertex<T> v(0, this);
    return VertexIterator<T>(v);
}

template <class T>
const_VertexIterator<T>
WGraph<T>::vertices_begin() const
{
    Vertex<T> v(0, const_cast<WGraph<T> *>(this));
    return const_VertexIterator<T>(v);
}

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

template <class T>
const_VertexIterator<T>
WGraph<T>::vertices_end() const
{
    Vertex<T> v(order(), const_cast<WGraph<T> *>(this));
    return const_VertexIterator<T>(v);
}

template <class T>
EdgeIterator<T>
WGraph<T>::edges_begin(const VertexIterator<T> &v)
{
    assert(has(*v));
    size_t u = v->label();
    size_t j = 0;
    while (j < order() && weights_[u][j] == std::numeric_limits<float>::infinity())
        ++j;
    Edge<T> e(u, j, this);
    return EdgeIterator<T>(e);
}

template <class T>
const_EdgeIterator<T>
WGraph<T>::edges_begin(const const_VertexIterator<T> &v) const
{
    assert(has(*v));
    size_t u = v->label();
    size_t j = 0;
    while (j < order() && weights_[u][j] == std::numeric_limits<float>::infinity())
        ++j;
    Edge<T> e(u, j, const_cast<WGraph<T> *>(this));
    return const_EdgeIterator<T>(e);
}

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

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

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

template <class T>
std::istream &
operator>>(std::istream &input, WGraph<T> &g) noexcept(false)
{
    std::string token;
    input >> token;
    bool directed;
    if (token == "DIRECTED")
        directed = true;
    else if (token == "UNDIRECTED")
        directed = false;
    else
        throw std::runtime_error("Wrong WGraph");

    size_t order;
    input >> order;
    g = WGraph<T>(order, directed);

    for (size_t i = 0; i < order; ++i)
    {
        T item;
        input >> item;
        g.add_vertex(item);
    }

    size_t num_edges;
    input >> num_edges;

    for (size_t i = 0; i < num_edges; ++i)
    {
        typename T::key_t u_key, v_key;
        float w;
        input >> u_key >> v_key >> w;

        size_t u_label = 0, v_label = 0;
        for (size_t j = 0; j < g.order(); ++j)
        {
            if (g.item(j).key() == u_key)
                u_label = j;
            if (g.item(j).key() == v_key)
                v_label = j;
        }
        g.set_weight(u_label, v_label, w);
    }

    return input;
}