/* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  * Copyright (C) 2017

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #ifndef LEMON_COMPACT_GRAPH_H

 #define LEMON_COMPACT_GRAPH_H

 ///\ingroup graphs

 ///\file

 ///\brief CompactDigraph class.

 #include <lemon/core.h>

 #include <lemon/bits/graph_extender.h>

 #include <algorithm>

 namespace lemon {

   class CompactDigraphBase {

   public:

     CompactDigraphBase()

       : built(false), node_num(0), arc_num(0),

         node_first_out(NULL),

         arc_target(NULL) {}

     ~CompactDigraphBase() {

       if (built) {

         delete[] node_first_out;

         delete[] arc_target;

       }

     }

     class Node {

       friend class CompactDigraphBase;

     protected:

       int id;

       Node(int _id) : id(_id) {}

     public:

       Node() {}

       Node (Invalid) : id(-1) {}

       bool operator==(const Node& node) const { return id == node.id; }

       bool operator!=(const Node& node) const { return id != node.id; }

       bool operator<(const Node& node) const { return id < node.id; }

     };

     class Arc {

       friend class CompactDigraphBase;

     protected:

       int id;

       int source;

       Arc(int _id, int _source) : id(_id), source(_source) {}

     public:

       Arc() { }

       Arc (Invalid) : id(-1), source(-1) {}

       bool operator==(const Arc& arc) const { return id == arc.id; }

       bool operator!=(const Arc& arc) const { return id != arc.id; }

       bool operator<(const Arc& arc) const { return id < arc.id; }

     };

     Node source(const Arc& e) const { return Node(e.source); }

     Node target(const Arc& e) const { return Node(arc_target[e.id]); }

     void first(Node& n) const { n.id = node_num - 1; }

     static void next(Node& n) { --n.id; }

   private:

     void nextSource(Arc& e) const {

       if (e.id == -1) return;

       int last = node_first_out[e.source] - 1;

       while (e.id == last) {

         --e.source;

         last = node_first_out[e.source] - 1;

       }

     }

   public:

     void first(Arc& e) const {

       e.id = arc_num - 1;

       e.source = node_num - 1;

       nextSource(e);

     }

     void next(Arc& e) const {

       --e.id;

       nextSource(e);

     }

     void firstOut(Arc& e, const Node& n) const {

       e.source = n.id;

       e.id = node_first_out[n.id];

       if (e.id == node_first_out[n.id + 1]) e = INVALID;

     }

     void nextOut(Arc& e) const {

       ++e.id;

       if (e.id == node_first_out[e.source + 1]) e = INVALID;

     }

     void firstIn(Arc& e, const Node& n) const {

       first(e);

       while(e != INVALID && target(e) != n) {

         next(e);

       }

     }

     void nextIn(Arc& e) const {

       Node arcTarget = target(e);

       do {

         next(e);

       } while(e != INVALID && target(e) != arcTarget);

     }

     static int id(const Node& n) { return n.id; }

     static Node nodeFromId(int id) { return Node(id); }

     int maxNodeId() const { return node_num - 1; }

     static int id(const Arc& e) { return e.id; }

     Arc arcFromId(int id) const {

       int *l = std::upper_bound(node_first_out, node_first_out + node_num, id) - 1;

       int src = l - node_first_out;

       return Arc(id, src);

     }

     int maxArcId() const { return arc_num - 1; }

     typedef True NodeNumTag;

     typedef True ArcNumTag;

     int nodeNum() const { return node_num; }

     int arcNum() const { return arc_num; }

   private:

     template <typename Digraph, typename NodeRefMap>

     class ArcLess {

     public:

       typedef typename Digraph::Arc Arc;

       ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef)

         : digraph(_graph), nodeRef(_nodeRef) {}

       bool operator()(const Arc& left, const Arc& right) const {

         return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];

       }

     private:

       const Digraph& digraph;

       const NodeRefMap& nodeRef;

     };

   public:

     typedef True BuildTag;

     void clear() {

       if (built) {

         delete[] node_first_out;

         delete[] arc_target;

       }

       built = false;

       node_num = 0;

       arc_num = 0;

     }

     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>

     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {

       typedef typename Digraph::Node GNode;

       typedef typename Digraph::Arc GArc;

       built = true;

       node_num = countNodes(digraph);

       arc_num = countArcs(digraph);

       node_first_out = new int[node_num + 1];

       arc_target = new int[arc_num];

       int node_index = 0;

       for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {

         nodeRef[n] = Node(node_index);

         ++node_index;

       }

       ArcLess<Digraph, NodeRefMap> arcLess(digraph, nodeRef);

       int arc_index = 0;

       for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {

         int source = nodeRef[n].id;

         std::vector<GArc> arcs;

         for (typename Digraph::OutArcIt e(digraph, n); e != INVALID; ++e) {

           arcs.push_back(e);

         }

         if (!arcs.empty()) {

           node_first_out[source] = arc_index;

           std::sort(arcs.begin(), arcs.end(), arcLess);

           for (typename std::vector<GArc>::iterator it = arcs.begin();

                it != arcs.end(); ++it) {

             int target = nodeRef[digraph.target(*it)].id;

             arcRef[*it] = Arc(arc_index, source);

             arc_target[arc_index] = target;

             ++arc_index;

           }

         } else {

           node_first_out[source] = arc_index;

         }

       }

       node_first_out[node_num] = arc_num;

     }

     template <typename ArcListIterator>

     void build(int n, ArcListIterator first, ArcListIterator last) {

       built = true;

       node_num = n;

       arc_num = static_cast<int>(std::distance(first, last));

       node_first_out = new int[node_num + 1];

       arc_target = new int[arc_num];

       int arc_index = 0;

       for (int i = 0; i != node_num; ++i) {

         node_first_out[i] = arc_index;

         for ( ; first != last && (*first).first == i; ++first) {

           int j = (*first).second;

           LEMON_ASSERT(j >= 0 && j < node_num,

             "Wrong arc list for CompactDigraph::build()");

           arc_target[arc_index] = j;

           ++arc_index;

         }

       }

       LEMON_ASSERT(first == last,

         "Wrong arc list for CompactDigraph::build()");

       node_first_out[node_num] = arc_num;

     }

   protected:

     bool built;

     int node_num;

     int arc_num;

     int *node_first_out;

     int *arc_target;

   };

   typedef DigraphExtender<CompactDigraphBase> ExtendedCompactDigraphBase;

   /// \ingroup graphs

   ///

   /// \brief A static directed graph class.

   ///

   /// \ref CompactDigraph is a highly efficient digraph implementation

   /// similar to \ref StaticDigraph. It is more memory efficient but does

   /// not provide efficient iteration over incoming arcs.

   ///

   /// It stores only one \c int values for each node and one \c int value

   /// for each arc. Its \ref InArcIt implementation is inefficient and

   /// provided only for compatibility with the \ref concepts::Digraph "Digraph concept".

   ///

   /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".

   /// Most of its member functions and nested classes are documented

   /// only in the concept class.

   ///

   /// \sa concepts::Digraph

   class CompactDigraph : public ExtendedCompactDigraphBase {

   private:

     /// Graphs are \e not copy constructible. Use DigraphCopy instead.

     CompactDigraph(const CompactDigraph &) : ExtendedCompactDigraphBase() {};

     /// \brief Assignment of a graph to another one is \e not allowed.

     /// Use DigraphCopy instead.

     void operator=(const CompactDigraph&) {}

   public:

     typedef ExtendedCompactDigraphBase Parent;

   public:

     /// \brief Constructor

     ///

     /// Default constructor.

     CompactDigraph() : Parent() {}

     /// \brief The node with the given index.

     ///

     /// This function returns the node with the given index.

     /// \sa index()

     static Node node(int ix) { return Parent::nodeFromId(ix); }

     /// \brief The arc with the given index.

     ///

     /// This function returns the arc with the given index.

     /// \sa index()

     Arc arc(int ix) { return arcFromId(ix); }

     /// \brief The index of the given node.

     ///

     /// This function returns the index of the the given node.

     /// \sa node()

     static int index(Node node) { return Parent::id(node); }

     /// \brief The index of the given arc.

     ///

     /// This function returns the index of the the given arc.

     /// \sa arc()

     static int index(Arc arc) { return Parent::id(arc); }

     /// \brief Number of nodes.

     ///

     /// This function returns the number of nodes.

     int nodeNum() const { return node_num; }

     /// \brief Number of arcs.

     ///

     /// This function returns the number of arcs.

     int arcNum() const { return arc_num; }

     /// \brief Build the digraph copying another digraph.

     ///

     /// This function builds the digraph copying another digraph of any

     /// kind. It can be called more than once, but in such case, the whole

     /// structure and all maps will be cleared and rebuilt.

     ///

     /// This method also makes possible to copy a digraph to a CompactDigraph

     /// structure using \ref DigraphCopy.

     ///

     /// \param digraph An existing digraph to be copied.

     /// \param nodeRef The node references will be copied into this map.

     /// Its key type must be \c Digraph::Node and its value type must be

     /// \c CompactDigraph::Node.

     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"

     /// concept.

     /// \param arcRef The arc references will be copied into this map.

     /// Its key type must be \c Digraph::Arc and its value type must be

     /// \c CompactDigraph::Arc.

     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

     ///

     /// \note If you do not need the arc references, then you could use

     /// \ref NullMap for the last parameter. However the node references

     /// are required by the function itself, thus they must be readable

     /// from the map.

     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>

     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {

       if (built) Parent::clear();

       Parent::build(digraph, nodeRef, arcRef);

     }

     /// \brief Build the digraph from an arc list.

     ///

     /// This function builds the digraph from the given arc list.

     /// It can be called more than once, but in such case, the whole

     /// structure and all maps will be cleared and rebuilt.

     ///

     /// The list of the arcs must be given in the range <tt>[begin, end)</tt>

     /// specified by STL compatible itartors whose \c value_type must be

     /// <tt>std::pair<int,int></tt>.

     /// Each arc must be specified by a pair of integer indices

     /// from the range <tt>[0..n-1]</tt>. <i>The pairs must be in a

     /// non-decreasing order with respect to their first values.</i>

     /// If the k-th pair in the list is <tt>(i,j)</tt>, then

     /// <tt>arc(k-1)</tt> will connect <tt>node(i)</tt> to <tt>node(j)</tt>.

     ///

     /// \param n The number of nodes.

     /// \param begin An iterator pointing to the beginning of the arc list.

     /// \param end An iterator pointing to the end of the arc list.

     ///

     /// For example, a simple digraph can be constructed like this.

     /// \code

     ///   std::vector<std::pair<int,int> > arcs;

     ///   arcs.push_back(std::make_pair(0,1));

     ///   arcs.push_back(std::make_pair(0,2));

     ///   arcs.push_back(std::make_pair(1,3));

     ///   arcs.push_back(std::make_pair(1,2));

     ///   arcs.push_back(std::make_pair(3,0));

     ///   CompactDigraph gr;

     ///   gr.build(4, arcs.begin(), arcs.end());

     /// \endcode

     template <typename ArcListIterator>

     void build(int n, ArcListIterator begin, ArcListIterator end) {

       if (built) Parent::clear();

       CompactDigraphBase::build(n, begin, end);

       notifier(Node()).build();

       notifier(Arc()).build();

     }

     /// \brief Clear the digraph.

     ///

     /// This function erases all nodes and arcs from the digraph.

     void clear() {

       Parent::clear();

     }

   public:

     Node baseNode(const OutArcIt &arc) const {

       return Parent::source(static_cast<const Arc&>(arc));

     }

     Node runningNode(const OutArcIt &arc) const {

       return Parent::target(static_cast<const Arc&>(arc));

     }

     Node baseNode(const InArcIt &arc) const {

       return Parent::target(static_cast<const Arc&>(arc));

     }

     Node runningNode(const InArcIt &arc) const {

       return Parent::source(static_cast<const Arc&>(arc));

     }

   };

 }

 #endif