/* -*- C++ -*-

  * src/lemon/smart_graph.h - Part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Combinatorial Optimization Research Group, 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_SMART_GRAPH_H

 #define LEMON_SMART_GRAPH_H

 ///\ingroup graphs

 ///\file

 ///\brief SmartGraph and SymSmartGraph classes.

 #include <vector>

 #include <lemon/invalid.h>

 #include <lemon/erasable_graph_extender.h>

 #include <lemon/clearable_graph_extender.h>

 #include <lemon/extendable_graph_extender.h>

 #include <lemon/idmappable_graph_extender.h>

 #include <lemon/iterable_graph_extender.h>

 #include <lemon/alteration_observer_registry.h>

 #include <lemon/default_map.h>

 #include <lemon/graph_utils.h>

 namespace lemon {

   /// \addtogroup graphs

   /// @{

   ///Base of SmartGraph

   ///Base of SmartGraph

   ///

   class SmartGraphBase {

     struct NodeT 

     {

       int first_in,first_out;      

       NodeT() : first_in(-1), first_out(-1) {}

     };

     struct EdgeT 

     {

       int head, tail, next_in, next_out;      

       //FIXME: is this necessary?

       EdgeT() : next_in(-1), next_out(-1) {}  

     };

     std::vector<NodeT> nodes;

     std::vector<EdgeT> edges;

   public:

     typedef SmartGraphBase Graph;

     class Node;

     class Edge;

   public:

     SmartGraphBase() : nodes(), edges() { }

     SmartGraphBase(const SmartGraphBase &_g) : nodes(_g.nodes), edges(_g.edges) { }

     ///Number of nodes.

     int nodeNum() const { return nodes.size(); }

     ///Number of edges.

     int edgeNum() const { return edges.size(); }

     /// Maximum node ID.

     /// Maximum node ID.

     ///\sa id(Node)

     int maxNodeId() const { return nodes.size()-1; }

     /// Maximum edge ID.

     /// Maximum edge ID.

     ///\sa id(Edge)

     int maxEdgeId() const { return edges.size()-1; }

     Node tail(Edge e) const { return edges[e.n].tail; }

     Node head(Edge e) const { return edges[e.n].head; }

     /// Node ID.

     /// The ID of a valid Node is a nonnegative integer not greater than

     /// \ref maxNodeId(). The range of the ID's is not surely continuous

     /// and the greatest node ID can be actually less then \ref maxNodeId().

     ///

     /// The ID of the \ref INVALID node is -1.

     ///\return The ID of the node \c v. 

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

     /// Edge ID.

     /// The ID of a valid Edge is a nonnegative integer not greater than

     /// \ref maxEdgeId(). The range of the ID's is not surely continuous

     /// and the greatest edge ID can be actually less then \ref maxEdgeId().

     ///

     /// The ID of the \ref INVALID edge is -1.

     ///\return The ID of the edge \c e. 

     static int id(Edge e) { return e.n; }

     Node addNode() {

       Node n; n.n=nodes.size();

       nodes.push_back(NodeT()); //FIXME: Hmmm...

       return n;

     }

     Edge addEdge(Node u, Node v) {

       Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...

       edges[e.n].tail=u.n; edges[e.n].head=v.n;

       edges[e.n].next_out=nodes[u.n].first_out;

       edges[e.n].next_in=nodes[v.n].first_in;

       nodes[u.n].first_out=nodes[v.n].first_in=e.n;

       return e;

     }

     void clear() {

       edges.clear();

       nodes.clear();

     }

     class Node {

       friend class SmartGraphBase;

     protected:

       int n;

       Node(int nn) {n=nn;}

     public:

       Node() {}

       Node (Invalid) { n=-1; }

       bool operator==(const Node i) const {return n==i.n;}

       bool operator!=(const Node i) const {return n!=i.n;}

       bool operator<(const Node i) const {return n<i.n;}

     };

     class Edge {

       friend class SmartGraphBase;

     protected:

       int n;

       Edge(int nn) {n=nn;}

     public:

       Edge() { }

       Edge (Invalid) { n=-1; }

       bool operator==(const Edge i) const {return n==i.n;}

       bool operator!=(const Edge i) const {return n!=i.n;}

       bool operator<(const Edge i) const {return n<i.n;}

     };

     void first(Node& node) const {

       node.n = nodes.size() - 1;

     }

     static void next(Node& node) {

       --node.n;

     }

     void first(Edge& edge) const {

       edge.n = edges.size() - 1;

     }

     static void next(Edge& edge) {

       --edge.n;

     }

     void firstOut(Edge& edge, const Node& node) const {

       edge.n = nodes[node.n].first_out;

     }

     void nextOut(Edge& edge) const {

       edge.n = edges[edge.n].next_out;

     }

     void firstIn(Edge& edge, const Node& node) const {

       edge.n = nodes[node.n].first_in;

     }

     void nextIn(Edge& edge) const {

       edge.n = edges[edge.n].next_in;

     }

     Edge _findEdge(Node u,Node v, Edge prev = INVALID) 

     {

       int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;

       while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;

       prev.n=e;

       return prev;

     }

   };

   typedef AlterableGraphExtender<SmartGraphBase> AlterableSmartGraphBase;

   typedef IterableGraphExtender<AlterableSmartGraphBase> IterableSmartGraphBase;

   typedef IdMappableGraphExtender<IterableSmartGraphBase> IdMappableSmartGraphBase;

   typedef DefaultMappableGraphExtender<IdMappableSmartGraphBase> MappableSmartGraphBase;

   typedef ExtendableGraphExtender<MappableSmartGraphBase> ExtendableSmartGraphBase;

   typedef ClearableGraphExtender<ExtendableSmartGraphBase> ClearableSmartGraphBase;

   ///A smart graph class.

   ///This is a simple and fast graph implementation.

   ///It is also quite memory efficient, but at the price

   ///that <b> it does not support node and edge deletion</b>.

   ///It conforms to 

   ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.

   ///\sa concept::ExtendableGraph.

   ///

   ///\todo Some member functions could be \c static.

   ///

   ///\todo A possibly useful functionality: a function saveState()

   ///(or snapshot() ) would

   ///give back a data sturcture X and then the function restoreState(X)

   ///(or rollBack() )

   ///would remove the nodes and edges added after the call of saveState().

   ///Of course it should be used as a stack. (Maybe X is not necessary.)

   ///

   ///\author Alpar Juttner

   class SmartGraph :public ClearableSmartGraphBase {

   public:

     /// Finds an edge between two nodes.

     /// Finds an edge from node \c u to node \c v.

     ///

     /// If \c prev is \ref INVALID (this is the default value), then

     /// it finds the first edge from \c u to \c v. Otherwise it looks for

     /// the next edge from \c u to \c v after \c prev.

     /// \return The found edge or \ref INVALID if there is no such an edge.

     ///

     /// Thus you can iterate through each edge from \c u to \c v as it follows.

     /// \code

     /// for(Edge e=G.findEdge(u,v);e!=INVALID;e=G.findEdge(u,v,e)) {

     ///   ...

     /// }

     /// \endcode

     /// \todo Possibly it should be a global function.

     Edge findEdge(Node u,Node v, Edge prev = INVALID) 

     {

       return _findEdge(u,v,prev);

     }

 };

   template <>

   int countNodes<SmartGraph>(const SmartGraph& graph) {

     return graph.nodeNum();

   }

   template <>

   int countEdges<SmartGraph>(const SmartGraph& graph) {

     return graph.edgeNum();

   }

   /// @}  

 } //namespace lemon

 #endif //LEMON_SMART_GRAPH_H