/**
 * @file graph.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 <cassert>
#include <cstdlib>
#include <memory>
#include <vector>
#include <limits>

#include <matrix.hpp>
#include <vertex.hpp>
#include <edge.hpp>

template <class T>
class Vertex;

template <class>
class Edge;

template <class T>
class VertexIterator;

template <class T>
class const_VertexIterator;

template <class T>
class EdgeIterator;

template <class T>
class const_EdgeIterator;

/**
 * @brief Models the Weighted Graph ADT.
 * A Weighted graph is directed graph where all vertices are connected with all
 * by default with infinity weight.
 * Two vertices u,v are adjacent if the weight of the edge u->v is less than infinity.
 * @ingroup graph
 *
 * @invariant !is_empty() || order()==0
 * @invariant is_full() || order()<capacity()
 *
 */
template <class T>
class WGraph
{
public:
  /** @name Makers*/
  /** @{*/

  /**
   * @brief Makes an zero capacity Weighted Graph.
   * @post capacity() == 0
   * @post is_empty()
   * @post is_full()
   * @post order() == 0
   */
  WGraph();

  /**
   * @brief Makes a Weighted Graph with capacity vertices.
   * @param[in] capacity is the maximum number of vertices.
   * @param[in] is_directed true if the graph is directed.
   * @pre capacity > 0
   * @post is_empty()
   * @post !is_full()
   * @post order() == 0
   * @post capacity() == capacity
   * @post is_directed == is_directed()
   */
  WGraph(size_t capacity, bool is_directed);

  /**
   * @brief Destroy the Graph object
   *
   */
  ~WGraph() {}

  /** @}*/

  /** @name Observers*/
  /**@{*/

  /**
   * @brief Is a directed graph?
   *
   * @return true if is a directed graph.
   */
  bool is_directed() const;

  /**
   * @brief is the graph empty?
   * @return true if there is not any vertex.
   * @pos !is_empty() or size()==0
   */
  bool is_empty() const;

  /**
   * @brief is the graph full?
   * @return true if there is not space to add a new vertex.
   */
  bool is_full() const;

  /**
   * @brief Get the max number of vertices to be added.
   * @return return the graph's capacity.
   */
  size_t capacity() const;

  /**
   * @brief Get the current number of vertices.
   */
  size_t order() const;

  /**
   * @brief Get the number of edges with weight less than infinity.
   * @return the number of edges with weight less than infinity.
   * @post !is_directed() || ret_v <= (order()*order())
   * @post is_directed() || ret_v <= (order()*(order()+1)/2)
   */
  size_t size() const;

  /**
   * @brief is u a vertex of this graph?
   * @pre u is not nullptr.
   * @return true if u is a vertex of this graph.
   * @post !ret_v || (u->label()< size() && vertex(u->label())==u)
   */
  bool has(Vertex<T> const &u) const;

  /**
   * @brief Get the item of a vertex given its label.
   * @param label is the vertex's label.
   * @return the vertex's item.
   */
  T const &item(size_t label) const;

  /**
   * @brief Get the items.
   * @return a vector with the vertices' items.
   * @post ret_v.size()==order()
   */
  const std::vector<T> &items() const;

  /**
   * @brief get a const vertex iterator by its label.
   * @pre label< order()
   */
  const_VertexIterator<T> vertex(size_t label) const;

  /**
   * @brief get an vertex iterator by its label.
   * @pre label< order()
   */
  VertexIterator<T> vertex(size_t label);

  /**
   * @brief Get the graph's weights.
   * @return a reference to the weights matrix.
   */
  FMatrix const &weights() const;

  /**
   * @brief Get the weight of the (u->v)|(u,v) edge.
   * @param[in] u is the label of a vertex.
   * @param[in] v is the label of other vertex.
   * @return the weight of the edge (u->v)|(u,v).
   * @pre u < order()
   * @pre v < order()
   */
  float weight(size_t u, size_t v) const;

  /**
   * @brief Is vertex v adjacent to u?
   * @param[in] u is a vertex's label.
   * @param[in] v is other vertex's label.
   * @return true if the weight of the edge (u->v)|(u,v) < inf.
   * @pre u < order()
   * @pre v < order()
   */
  bool is_adjacent(size_t u, const size_t v) const;

  /**
   * @brief Is the vertex u visited?
   * @param[in] u_label is the vertex's label.
   * @return true if the vertex u is visited.
   * @pre u_label < order()
   */
  bool is_visited(size_t u_label) const;

  /**
   * @brief Get an edge iterator to the edge (u,v).
   * @param[in] u_label is the first vertex's label.
   * @param[in] v_label is the second vertex's label.
   * @return The edge iterator.
   * @pre u_label < order()
   * @pre v_label < order()
   * @post ret_v->first().label()==u_label
   * @post ret_v->second().label()==v_label
   * @post ret_v->item()==weight(u_label, v_label)
   */
  EdgeIterator<T> edge(size_t u_label, size_t v_label);

  /**
   * @brief Get an edge const iterator to the edge (u,v).
   * @param[in] u_label is the first vertex's label.
   * @param[in] v_label is the second vertex's label.
   * @return The edge iterator.
   * @pre u_label < order()
   * @pre v_label < order()
   * @post ret_v->first().label()==u_label
   * @post ret_v->second().label()==v_label
   * @post ret_v->item()==weight(u_label, v_label)
   */
  const_EdgeIterator<T> edge(size_t u_label, size_t v_label) const;

  /**
   * @brief Get an iterator to the first vertex.
   * @return an iterator to the first vertex.
   */
  VertexIterator<T> vertices_begin();

  /**
   * @brief Get an iterator to the first vertex.
   * @return an iterator to the first vertex.
   */
  const_VertexIterator<T> vertices_begin() const;

  /**
   * @brief Get an iterator to the end of the vertex list.
   * @return an iterator to the end of the vertex list.
   */
  VertexIterator<T> vertices_end();

  /**
   * @brief Get an iterator to the end of the vertex list.
   * @return an iterator to the end of the vertex list.
   */
  const_VertexIterator<T> vertices_end() const;

  /**
   * @brief Get an iterator to the first edge incident to the given vertex
   *
   * @param v is the vertex to get the incident edges.
   * @return an iterator to first edge incident to the vertex.
   * @pre has(v).
   */
  EdgeIterator<T> edges_begin(const VertexIterator<T> &v);

  /**
   * @brief Get a const iterator to the first edge incident to the given vertex
   *
   * @param v is the vertex to get the incident edges.
   * @return an iterator to first edge incident to the vertex.
   * @pre has(v).
   */
  const_EdgeIterator<T> edges_begin(const const_VertexIterator<T> &v) const;

  /**
   * @brief Get an interator to the end of the edge list incident to the given vertex
   *
   * @param v is the vertex to get the incident edges.
   * @return an iterator to the end of the edge list incident to the vertex.
   * @pre has(v).
   */
  EdgeIterator<T> edges_end(const VertexIterator<T> &v);

  /**
   * @brief Get an interator to the end of the edge list incident to the given vertex
   *
   * @param v is the vertex to get the incident edges.
   * @return an iterator to the end of the edge list incident to the vertex.
   * @pre has(v).
   */
  const_EdgeIterator<T> edges_end(const const_VertexIterator<T> &v) const;

  /**
   * @brief Find a vertex with the given item.
   * @param item is the item to find.
   * @return an iterator to a vertex with the given item or vertices_end() if there is not any.
   */
  VertexIterator<T> find_vertex(const T &item);

  /**
   * @brief Find a vertex with the given item.
   * @param item is the item to find.
   * @return an const iterator to a vertex with the given item or vertices_end() if there is not any.
   */
  const_VertexIterator<T> find_vertex(const T &item) const;

  /** @}*/

  /** @name Modifiers*/
  /** @{*/

  /**
   * @brief Set the visited state of all vertices.
   * @param visited_state is the new visited state.
   * @post is_visited(u_label)==visited_state for all u_label < order()
   */
  void reset(bool visited_state = false);

  /**
   * @brief Add a new vertex.
   * @param[in] v is the data item to be save in the new vertex.
   * @pre !is_full()
   * @post order()==(old.order()+1)
   * @post has(ret_v)
   * @post ret_v.item() == v
   * @post ret_v.is_visited() == false
   */
  VertexIterator<T> add_vertex(T const &v);

  /**
   * @brief Set the visited state of a vertex.
   *
   * @param v_label is the vertex's label.
   * @param new_item is the new item.
   * @pre v_label < order()
   * @post item(v_label)==new_item
   */
  void set_item(size_t v_label, const T &new_item);

  /**
   * @brief Set the weight of (u->v)|(u,v) edge.
   * @param[in] u_label u vertex's label.
   * @param[in] v_label v vertex's label.
   * @param[in] new_w the new weight value.
   * @pre u_label < order()
   * @pre v_label < order()
   * @post weight(u_label, v_label)==new_w
   * @post is_directed() || weight(v_label, u_label)==new_w)
   */
  void set_weight(size_t u_label, size_t v_label, float new_w);

  /**
   * @brief Set the visited state of a vertex.
   *
   * @param u_label is the vertex's label.
   * @param new_state is the new visited state.
   * @pre u_label < order()
   * @post is_visited(u_label)=new_state
   */
  void set_visited(size_t u_label, bool new_state);

  /** @} */

protected:
  friend class VertexIterator<T>;
  friend class EdgeIterator<T>;
  friend class const_VertexIterator<T>;
  friend class const_EdgeIterator<T>;
  bool is_directed_;                   /**< is a directed graph?*/
  std::vector<T> vertex_items_;        /**< the vector of vertices' items.*/
  std::vector<bool> visited_vertices_; /**< the vector of vertices visited state.*/
  FMatrix weights_;                    /**< the weight matrix.*/
};

/**
 * @brief Fold a weighted graph to an output stream.
 * Grammar:
 *
 * 'DIRECTED'|'UNDIRECTED'
 * <NUM. NODES>
 * <NODE_0_ITEM>
 * ...
 * <NODE_N-1_ITEM>
 * <NUM_EDGES>
 * <U_KEY_0> <V_KEY_0> <EDGE_WEIGHT_0>
 * ...
 * <U_KEY_num_edges-1> <V_KEY_num_edges-1> <EDGE_WEIGHT_num_edges-1>
 *
 * where only edges with weight < inf are stored.
 *
 * @param out is the output stream.
 * @param g is the graph to fold.
 * @return the output stream.
 */
template <class T>
std::ostream &operator<<(std::ostream &out, const WGraph<T> &g) noexcept;

/**
 * @brief Unfold a Weighted graph from an input stream.
 *
 * See operator<< for the input format.
 *
 * where only edges with weight < inf are stored.
 * @param in is the input stream.
 * @param g is the graph to unfold.
 * @return the input stream.
 * @throw std::runtime_error("Wrong WGraph") if the input format is wrong.
 * @post is_full()
 */
template <class T>
std::istream &operator>>(std::istream &input, WGraph<T> &g) noexcept(false);

#include <graph_imp.hpp>