// -*- c++ -*-

#ifndef LEMON_BIPARTITE_GRAPH_WRAPPER_H

#define LEMON_BIPARTITE_GRAPH_WRAPPER_H

///\ingroup gwrappers

///\file

///\brief Several graph wrappers.

///

///This file contains several useful graph wrapper functions.

///

///\author Marton Makai

#include <lemon/invalid.h>

#include <iter_map.h>

#include <lemon/graph_wrapper.h>

#include <for_each_macros.h>

namespace lemon {

  /// \brief A wrapper for composing a bipartite graph from a graph 

  /// and from a node-map showing for any node which color class it belongs to.

  ///

  /// A wrapper for composing a bipartite graph.

  /// \c _graph have to be a reference to a graph of type \c Graph 

  /// and \c _s_false_t_true_map is an \c IterableBoolMap 

  /// reference containing the elements for the 

  /// color classes S and T. \c _graph is to be referred to an undirected 

  /// graph or a directed graph with edges oriented from S to T.

  ///

  /// \author Marton Makai

  template<typename Graph> 

  class BipartiteGraphWrapper : public GraphWrapper<Graph> {

  public:

    typedef IterableBoolMap< typename Graph::template NodeMap<int> > 

    SFalseTTrueMap;

  protected:

    SFalseTTrueMap* s_false_t_true_map;

    BipartiteGraphWrapper() : GraphWrapper<Graph>()/*, 

						     S_CLASS(false), T_CLASS(true)*/ { }

    void setSFalseTTrueMap(SFalseTTrueMap& _s_false_t_true_map) { 

      s_false_t_true_map=&_s_false_t_true_map;

    }

  public:

    //marci

    //FIXME vhogy igy kellene, csak az en forditom nem eszi meg

    static const bool S_CLASS;

    static const bool T_CLASS;

    /// This method is to reach the iterable maps of the bipartite graph or 

    /// bipartite graph wrapper.

    const SFalseTTrueMap& sFalseTTrueMap() const { 

      return *s_false_t_true_map; 

    }

    //bool S_CLASS;

    //bool T_CLASS;

    BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) 

      : GraphWrapper<Graph>(_graph), 

	s_false_t_true_map(&_s_false_t_true_map)/*, 

						  S_CLASS(false), T_CLASS(true)*/ { }

    typedef typename GraphWrapper<Graph>::Node Node;

    //using GraphWrapper<Graph>::NodeIt;

    typedef typename GraphWrapper<Graph>::Edge Edge;

    //using GraphWrapper<Graph>::EdgeIt;

    class ClassNodeIt;

    friend class ClassNodeIt;

    class OutEdgeIt;

    friend class OutEdgeIt;

    class InEdgeIt;

    friend class InEdgeIt;

    class ClassNodeIt : public Node {

      friend class BipartiteGraphWrapper<Graph>;

    protected:

      const BipartiteGraphWrapper<Graph>* gw;

    public:

      ClassNodeIt() { }

      ClassNodeIt(Invalid i) : Node(i) { }

      ClassNodeIt(const BipartiteGraphWrapper<Graph>& _gw, bool _class) : 

	Node(), gw(&_gw) { 

	_gw.s_false_t_true_map->first(*this, _class); 

      }

      //FIXME needed in new concept, important here

      ClassNodeIt(const BipartiteGraphWrapper<Graph>& _gw, const Node& n) : 

	Node(n), gw(&_gw) { }

      ClassNodeIt& operator++() { 

	gw->s_false_t_true_map->next(*this);

	return *this; 

      }

    };

//     class SNodeIt {

//       Node n;

//     public:

//       SNodeIt() { }

//       SNodeIt(const Invalid& i) : n(i) { }

//       SNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 

// 	_G.s_false_t_true_map->first(n, false); 

//       }

//       operator Node() const { return n; }

//     };

//     class TNodeIt {

//       Node n;

//     public:

//       TNodeIt() { }

//       TNodeIt(const Invalid& i) : n(i) { }

//       TNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 

// 	_G.s_false_t_true_map->first(n, true); 

//       }

//       operator Node() const { return n; }

//     };

//     class OutEdgeIt { 

//       friend class BipartiteGraphWrapper<Graph>;

//     protected:

//       typename Graph::OutEdgeIt e;

//     public:

//       OutEdgeIt() { }

//       OutEdgeIt(const Invalid& i) : e(i) { }

//       OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {

// 	if (!(*(_G.s_false_t_true_map))[_n]) 

// 	  e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));

// 	else 

// 	  e=INVALID;

//       }

//       operator Edge() const { return Edge(typename Graph::Edge(e)); }

//     };

//     class InEdgeIt { 

//       friend class BipartiteGraphWrapper<Graph>;

//     protected:

//       typename Graph::InEdgeIt e;

//     public:

//       InEdgeIt() { }

//       InEdgeIt(const Invalid& i) : e(i) { }

//       InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {

// 	if ((*(_G.s_false_t_true_map))[_n]) 

// 	  e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));

// 	else 

// 	  e=INVALID;

//       }

//       operator Edge() const { return Edge(typename Graph::Edge(e)); }

//     };

    using GraphWrapper<Graph>::first;

    ClassNodeIt& first(ClassNodeIt& n, bool _class) const { 

      n=ClassNodeIt(*this, _class); return n;

    }

//    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }

//    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }

//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 

//       i=OutEdgeIt(*this, p); return i;

//     }

//     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 

//       i=InEdgeIt(*this, p); return i;

//     }

//     using GraphWrapper<Graph>::next;

//     ClassNodeIt& next(ClassNodeIt& n) const { 

//       this->s_false_t_true_map->next(n.n); return n; 

//     }

//     SNodeIt& next(SNodeIt& n) const { 

//       this->s_false_t_true_map->next(n); return n; 

//     }

//     TNodeIt& next(TNodeIt& n) const { 

//       this->s_false_t_true_map->next(n); return n; 

//     }

//     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }

//     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }

//     Node tail(const Edge& e) { 

//       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 

// 	return Node(this->graph->tail(e));

//       else

// 	return Node(this->graph->head(e));	

//     }

//     Node head(const Edge& e) { 

//       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 

// 	return Node(this->graph->head(e));

//       else

// 	return Node(this->graph->tail(e));	

//     }

//     Node aNode(const OutEdgeIt& e) const { 

//       return Node(this->graph->aNode(e.e)); 

//     }

//     Node aNode(const InEdgeIt& e) const { 

//       return Node(this->graph->aNode(e.e)); 

//     }

//     Node bNode(const OutEdgeIt& e) const { 

//       return Node(this->graph->bNode(e.e)); 

//     }

//     Node bNode(const InEdgeIt& e) const { 

//       return Node(this->graph->bNode(e.e)); 

//     }

    /// Returns true iff \c n is in S.

    bool inSClass(const Node& n) const {

      return !(*(this->s_false_t_true_map))[n];

    }

    /// Returns true iff \c n is in T.

    bool inTClass(const Node& n) const {

      return (*(this->s_false_t_true_map))[n];

    }

  };

  template<typename G>

  const bool BipartiteGraphWrapper<G>::S_CLASS=false;

  template<typename G>

  const bool BipartiteGraphWrapper<G>::T_CLASS=true;

  /// \brief A bipartite graph template class

  ///

  /// This class composes a bipartite graph over a directed or undirected 

  /// graph structure of type \c Graph.

  /// \c _graph have to be a reference to a graph of type \c Graph 

  /// and \c _s_false_t_true_map is an \c IterableBoolMap 

  /// reference containing the elements for the 

  /// color classes S and T. \c _graph is to be referred to an undirected 

  /// graph or a directed graph with edges oriented from S to T.

  ///

  ///\bug experimental. Do not use this while the bipartitemap augmentation 

  /// does not work well.

  template<typename Graph>

  class BipartiteGraph : public BipartiteGraphWrapper<Graph> {

//     typedef IterableBoolMap< typename Graph::template NodeMap<int> > 

//     SFalseTTrueMap;

    typedef BipartiteGraphWrapper<Graph> Parent;

  protected:

    Graph gr;

    typename Graph::template NodeMap<int> bipartite_map;

    typename Parent::SFalseTTrueMap s_false_t_true_map;

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Edge Edge;

    BipartiteGraph() : BipartiteGraphWrapper<Graph>(), 

		       gr(), bipartite_map(gr, -1), 

		       s_false_t_true_map(bipartite_map) { 

      Parent::setGraph(gr); 

      Parent::setSFalseTTrueMap(s_false_t_true_map);

    }

    /// the \c bool parameter which can be \c S_Class or \c T_Class shows 

    /// the color class where the new node is to be inserted.

    Node addNode(bool b) {

      Node n=Parent::graph->addNode();

      bipartite_map.update();

      //bipartite_map.set(n, -1);

      s_false_t_true_map.insert(n, b);

      return n;

    }

    /// A new edge is inserted.

    ///\pre \c tail have to be in \c S_Class and \c head in \c T_Class.

    Edge addEdge(const Node& tail, const Node& head) {

      return Parent::graph->addEdge(tail, head);

    }

    void erase(const Node& n) {

      s_false_t_true_map.remove(n);

      Parent::graph->erase(n);

    }

    void erase(const Edge& e) {

      Parent::graph->erase(e);

    }

    void clear() {

      FOR_EACH_LOC(typename Parent::EdgeIt, e, *this) erase(e);

      FOR_EACH_LOC(typename Parent::NodeIt, n, *this) erase(n);

    }

  };

  template<typename Graph, typename sIterableMap, typename tIterableMap>

  class stGraphWrapper;

  /// Easier stuff for bipartite graphs.

  template<typename Graph>

  class stBipartiteGraphWrapper : public 

  stGraphWrapper<Graph, typename Graph::SFalseTTrueMap, 

		 typename Graph::SFalseTTrueMap> {

  public:

    typedef stGraphWrapper<Graph, typename Graph::SFalseTTrueMap, 

			   typename Graph::SFalseTTrueMap> Parent;

    stBipartiteGraphWrapper(Graph& _graph) : 

      Parent(_graph, _graph.sFalseTTrueMap(), _graph.sFalseTTrueMap()) { }

  };

//   template<typename Graph> 

//   std::ostream& 

//   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Node& i) { 

//     os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; 

//     return os; 

//   }

//   template<typename Graph> 

//   std::ostream& 

//   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Edge& i) { 

//     os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << 

//       " node: " << i.n << ")"; 

//     return os; 

//   }

  /// \brief A wrapper for adding extra nodes s and t to a bipartite graph

  /// and edges from s to each node of S and form each node of T to t.

  /// 

  /// A wrapper for adding extra nodes s and t to a bipartite graph

  /// and edges from s to each node of S and form each node of T to t.

  /// This class is very useful to reduce some matching or more

  /// generally, capacitataed b-matching problem to a flow problem.

  /// According to the bipartite graph concepts the bipartite 

  /// graph have to be oriented from S to T.

  ///

  /// \author Marton Makai

  template<typename Graph, typename sIterableMap, typename tIterableMap>

  class stGraphWrapper : public GraphWrapper<Graph> {

  protected:    

    const sIterableMap* s_iterable_map;

    const tIterableMap* t_iterable_map;

  public:

    class Node; 

    friend class Node;

//GN, int

//0 normalis, 1 s, 2 t, ez az iteralasi sorrend, 

//es a vege a false azaz (invalid, 3)    

    class NodeIt;

    friend class NodeIt;

//GNI, int

    class Edge;

    friend class Edge;

//GE, int, GN

//0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,

//invalid: (invalid, 3, invalid)

    class OutEdgeIt;

    friend class OutEdgeIt;

//GO, int, GNI

//normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)

//s-bol (invalid, 1, first), ... (invalid, 3, invalid)

//t-bol (invalid, 3, invalid)

    class InEdgeIt;

    friend class InEdgeIt;

//GI, int, GNI

//normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)

//s-be (invalid, 3, invalid)

//t-be (invalid, 2, first), ... (invalid, 3, invalid)

    class EdgeIt;

    friend class EdgeIt;

//(first, 0, invalid) ...

//(invalid, 1, vmi)

//(invalid, 2, vmi)

//invalid, 3, invalid)

    template <typename T> class NodeMap;

    template <typename T> class EdgeMap;

//    template <typename T> friend class NodeMap;

//    template <typename T> friend class EdgeMap;

    ///\todo FIXME ezt majd static-ra kell javitani

    const Node S_NODE;

    const Node T_NODE;

    static const bool S_CLASS=false;

    static const bool T_CLASS=true;

    // \bug not too nice constructor.

    stGraphWrapper(Graph& _graph, 

		   const sIterableMap& _s_iterable_map, 

		   const tIterableMap& _t_iterable_map) : 

      GraphWrapper<Graph>(_graph), 

      s_iterable_map(&_s_iterable_map), 

      t_iterable_map(&_t_iterable_map), 

      S_NODE(INVALID, 1), 

      T_NODE(INVALID, 2) { }

//    std::ostream& 

//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);

//    friend std::ostream& 

//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);

//    friend std::ostream& 

//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i);

    class Node : public Graph::Node {

    protected:

      friend class GraphWrapper<Graph>;

      friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;

      template <typename T> friend class NodeMap;

      friend class Edge;

      friend class OutEdgeIt;

      friend class InEdgeIt;

      friend class EdgeIt;

      int spec; 

    public:

      Node() { }

      Node(const typename Graph::Node& _n, int _spec=0) : 

	Graph::Node(_n), spec(_spec) { }

      Node(const Invalid& i) : Graph::Node(i), spec(3) { }

      friend bool operator==(const Node& u, const Node& v) { 

	return (u.spec==v.spec && 

		static_cast<typename Graph::Node>(u)==

		static_cast<typename Graph::Node>(v));

      } 

      friend bool operator!=(const Node& u, const Node& v) { 

	return (v.spec!=u.spec || 

		static_cast<typename Graph::Node>(u)!=

		static_cast<typename Graph::Node>(v));

      }

//      template<typename G> 

//      friend std::ostream& 

//      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Node& i); 

      friend std::ostream& operator<< (std::ostream& os, const Node& i);

      int getSpec() const { return spec; }

    };

    class NodeIt { 

      friend class GraphWrapper<Graph>;

      friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;

      typename Graph::NodeIt n;

      int spec; 

     public:

      NodeIt() { }

      NodeIt(const typename Graph::NodeIt& _n, int _spec) : 

	n(_n), spec(_spec) { }

      NodeIt(const Invalid& i) : n(i), spec(3) { }

      NodeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) 

	: n(*(_G.graph)), spec(0) { 

	if (!_G.graph->valid(n)) spec=1;

      }

      operator Node() const { return Node(n, spec); }

    };

    class Edge : public Graph::Edge {

      friend class GraphWrapper<Graph>;

      friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;

      template <typename T> friend class EdgeMap;

      int spec;

      typename Graph::Node n;

    public:

      Edge() { }

      Edge(const typename Graph::Edge& _e, int _spec, 

	   const typename Graph::Node& _n) : 

	Graph::Edge(_e), spec(_spec), n(_n) { 

      }

      Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }

      friend bool operator==(const Edge& u, const Edge& v) { 

	return (u.spec==v.spec && 

		static_cast<typename Graph::Edge>(u)==

		static_cast<typename Graph::Edge>(v) && 

		u.n==v.n);

      } 

      friend bool operator!=(const Edge& u, const Edge& v) { 

	return (v.spec!=u.spec || 

		static_cast<typename Graph::Edge>(u)!=

		static_cast<typename Graph::Edge>(v) || 

		u.n!=v.n);

      } 

//      template<typename G> 

//      friend std::ostream& 

//      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Edge& i); 

      friend std::ostream& operator<< (std::ostream& os, const Edge& i);

      int getSpec() const { return spec; }

      typename Graph::Node getNode() const { return n; }

    };

    class OutEdgeIt { 

      friend class GraphWrapper<Graph>;

      friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;

      typename Graph::OutEdgeIt e;

      int spec;

      typename Graph::ClassNodeIt n;

    public:

      OutEdgeIt() { }

      OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec, 

		const typename Graph::ClassNodeIt& _n) : 

	e(_e), spec(_spec), n(_n) { 

      }

      OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }

      OutEdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, 

		const Node& _n) {

	switch (_n.spec) {

	  case 0 : 

	    if (_G.graph->inSClass(_n)) { //S, van normalis kiel 

	      e=typename Graph::OutEdgeIt(*(_G.graph), 

					  typename Graph::Node(_n)); 

	      spec=0;

	      n=INVALID;

	      if (!_G.graph->valid(e)) spec=3;

	    } else { //T, specko kiel van

	      e=INVALID;

	      spec=2;

	      n=_n;

	    }

	    break;

	  case 1:

	    e=INVALID;

	    spec=1;

	    _G.graph->first(n, S_CLASS); //s->vmi;

	    if (!_G.graph->valid(n)) spec=3; //Ha S ures

	    break;

	  case 2:

	    e=INVALID;

	    spec=3;

	    n=INVALID;

	    break;

	}

      }

      operator Edge() const { return Edge(e, spec, n); }

    };

    class InEdgeIt { 

      friend class GraphWrapper<Graph>;

      friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;

      typename Graph::InEdgeIt e;

      int spec;

      typename Graph::ClassNodeIt n;

    public:

      InEdgeIt() { }

      InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec, 

	       const typename Graph::ClassNodeIt& _n) : 

	e(_e), spec(_spec), n(_n) { 

      }

      InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }

      InEdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, 

	       const Node& _n) {

	switch (_n.spec) {

	  case 0 : 

	    if (_G.graph->inTClass(_n)) { //T, van normalis beel 

	      e=typename Graph::InEdgeIt(*(_G.graph), 

					 typename Graph::Node(_n)); 

	      spec=0;

	      n=INVALID;

	      if (!_G.graph->valid(e)) spec=3;

	    } else { //S, specko beel van

	      e=INVALID;

	      spec=1;

	      n=_n;

	    }

	    break;

	  case 1:

	    e=INVALID;

	    spec=3;

	    n=INVALID;

	    break;

	  case 2:

	    e=INVALID;

	    spec=2;

	    _G.graph->first(n, T_CLASS); //vmi->t;

	    if (!_G.graph->valid(n)) spec=3; //Ha T ures

	    break;

	}

      }

      operator Edge() const { return Edge(e, spec, n); }

    };

    class EdgeIt { 

      friend class GraphWrapper<Graph>;

      friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;

      typename Graph::EdgeIt e;

      int spec;

      typename Graph::ClassNodeIt n;

    public:

      EdgeIt() { }

      EdgeIt(const typename Graph::EdgeIt& _e, int _spec, 

	     const typename Graph::ClassNodeIt& _n) : 

	e(_e), spec(_spec), n(_n) { }

      EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }

      EdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) : 

	e(*(_G.graph)), spec(0), n(INVALID) { 

	if (!_G.graph->valid(e)) {

	  spec=1;

	  _G.graph->first(n, S_CLASS);

	  if (!_G.graph->valid(n)) { //Ha S ures

	    spec=2;

	    _G.graph->first(n, T_CLASS);

	    if (!_G.graph->valid(n)) { //Ha T ures

	      spec=3;

	    }

	  }

	}

      }

      operator Edge() const { return Edge(e, spec, n); }

    };

    NodeIt& first(NodeIt& i) const { 

      i=NodeIt(*this); return i;

    }

    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 

      i=OutEdgeIt(*this, p); return i;

    }

    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 

      i=InEdgeIt(*this, p); return i;

    }

    EdgeIt& first(EdgeIt& i) const { 

      i=EdgeIt(*this); return i;

    }

    NodeIt& next(NodeIt& i) const { 

      switch (i.spec) {

	case 0:

	  this->graph->next(i.n);

	  if (!this->graph->valid(i.n)) {

	    i.spec=1;

	  }

	  break;

	case 1:

	  i.spec=2;

	  break;

	case 2:

	  i.spec=3;

	  break;

      }

      return i; 

    }

    OutEdgeIt& next(OutEdgeIt& i) const { 

      typename Graph::Node v;

      switch (i.spec) {

	case 0: //normal edge

	  v=this->graph->aNode(i.e);

	  this->graph->next(i.e);

	  if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk

	    if (this->graph->inSClass(v)) { //S, nincs kiel

	      i.spec=3;

	      i.n=INVALID;

	    } else { //T, van kiel

	      i.spec=2; 

	      i.n=v;

	    }

	  }

	  break;

	case 1: //s->vmi

	  this->graph->next(i.n);

	  if (!this->graph->valid(i.n)) i.spec=3;

	  break;

	case 2: //vmi->t

	  i.spec=3;

	  i.n=INVALID;

	  break;

      }

      return i; 

    }

    InEdgeIt& next(InEdgeIt& i) const { 

      typename Graph::Node v;

      switch (i.spec) {

	case 0: //normal edge

	  v=this->graph->aNode(i.e);

	  this->graph->next(i.e);

	  if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk

	    if (this->graph->inTClass(v)) { //S, nincs beel

	      i.spec=3;

	      i.n=INVALID;

	    } else { //S, van beel

	      i.spec=1; 

	      i.n=v;

	    }

	  }

	  break;

	case 1: //s->vmi

	  i.spec=3;

	  i.n=INVALID;

	  break;

	case 2: //vmi->t

	  this->graph->next(i.n);

	  if (!this->graph->valid(i.n)) i.spec=3;

	  break;

      }

      return i; 

    }

    EdgeIt& next(EdgeIt& i) const { 

      switch (i.spec) {

	case 0:

	  this->graph->next(i.e);

	  if (!this->graph->valid(i.e)) { 

	    i.spec=1;

	    this->graph->first(i.n, S_CLASS);

	    if (!this->graph->valid(i.n)) {

	      i.spec=2;

	      this->graph->first(i.n, T_CLASS);

	      if (!this->graph->valid(i.n)) i.spec=3;

	    }

	  }

	  break;

	case 1:

	  this->graph->next(i.n);

	  if (!this->graph->valid(i.n)) {

	    i.spec=2;

	    this->graph->first(i.n, T_CLASS);

	    if (!this->graph->valid(i.n)) i.spec=3;

	  }

	  break;

	case 2:

	  this->graph->next(i.n);

	  if (!this->graph->valid(i.n)) i.spec=3;

	  break;

      }

      return i; 

    }    

    Node tail(const Edge& e) const { 

      switch (e.spec) {

      case 0: 

	return Node(this->graph->tail(e));

	break;

      case 1:

	return S_NODE;

	break;

      case 2:

      default:

	return Node(e.n);

	break;

      }

    }

    Node head(const Edge& e) const { 

      switch (e.spec) {

      case 0: 

	return Node(this->graph->head(e));

	break;

      case 1:

	return Node(e.n);

	break;

      case 2:

      default:

	return T_NODE;

	break;

      }

    }

    bool valid(const Node& n) const { return (n.spec<3); }

    bool valid(const Edge& e) const { return (e.spec<3); }

    int nodeNum() const { return this->graph->nodeNum()+2; }

    int edgeNum() const { 

      return this->graph->edgeNum()+this->graph->nodeNum(); 

    }

    Node aNode(const OutEdgeIt& e) const { return tail(e); }

    Node aNode(const InEdgeIt& e) const { return head(e); }

    Node bNode(const OutEdgeIt& e) const { return head(e); }

    Node bNode(const InEdgeIt& e) const { return tail(e); }

    void addNode() const { }

    void addEdge() const { }

//    Node addNode() const { return Node(this->graph->addNode()); }

//    Edge addEdge(const Node& tail, const Node& head) const { 

//      return Edge(this->graph->addEdge(tail, head)); }

//    void erase(const Node& i) const { this->graph->erase(i); }

//    void erase(const Edge& i) const { this->graph->erase(i); }

//    void clear() const { this->graph->clear(); }

    template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> { 

      typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;

    protected:

      T s_value, t_value;

    public:

      NodeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) : 

	Parent(_G), 

	s_value(), 

	t_value() { }

      NodeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, T a) 

	: Parent(_G, a), 

	  s_value(a), 

	  t_value(a) { }

      T operator[](const Node& n) const { 

	switch (n.spec) {

	case 0: 

	  return Parent::operator[](n);

	case 1:

	  return s_value;

	case 2: 

	default:

	  return t_value;

	}

      }

      void set(const Node& n, T t) { 

	switch (n.spec) {

	case 0: 

	  GraphWrapper<Graph>::template NodeMap<T>::set(n, t);

	  break;

	case 1:

	  s_value=t;

	  break;

	case 2:

	default:

	  t_value=t;

	  break;

	}

      }

    };

    /// This class is to wrap a node-map of \c Graph and two variables 

    /// storing values for \c S_NODE and \c T_NODE to a node-map of 

    /// stGraphWrapper<Graph, sIterableMap, tIterableMap>.

    template<typename NM> class NodeMapWrapper { 

    public:

      typedef Node KeyType;

      typedef typename NM::ValueType ValueType;

    protected:

      NM* nm;

      ValueType* s_value, t_value;

    public:

      NodeMapWrapper(NM& _nm, ValueType& _s_value, ValueType& _t_value) : 

	nm(&_nm), s_value(&_s_value), t_value(&_t_value) { }

      ValueType operator[](const Node& n) const { 

	switch (n.getSpec()) {

	case 0: 

	  return (*nm)[n];

	case 1:

	  return *s_value;

	case 2: 

	default:

	  return *t_value;

	}

      }

      void set(const Node& n, ValueType t) { 

	switch (n.getSpec()) {

	case 0: 

	  nm->set(n, t);

	  break;

	case 1:

	  *s_value=t;

	  break;

	case 2:

	default:

	  *t_value=t;

	  break;

	}

      }

    };

    template<typename T> 

    class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { 

      typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;

    protected:

      typename GraphWrapper<Graph>::template NodeMap<T> node_value;

    public:

      EdgeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) 

	: Parent(_G), 

	  node_value(_G) { }

      EdgeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, T a) 

	: Parent(_G, a), 

	  node_value(_G, a) { }

      T operator[](const Edge& e) const { 

	switch (e.spec) {

	case 0: 

	  return Parent::operator[](e);

	case 1:

	  return node_value[e.n];

	case 2:

	default:

	  return node_value[e.n];

	}

      }

      void set(const Edge& e, T t) { 

	switch (e.spec) {

	case 0: 

	  Parent::set(e, t);

	  break;

	case 1:

	  node_value.set(e.n, t);

	  break;

	case 2:

	default:

	  node_value.set(e.n, t);

	  break;

	}

      }

    };

    /// This class is to wrap an edge-map and a node-map of \c Graph 

    /// to an edge-map of stGraphWrapper<Graph, sIterableMap, tIterableMap>.

    template<typename EM, typename NM> 

    class EdgeMapWrapper {

    public: 

      typedef Edge KeyType;

      typedef typename EM::ValueType ValueType;

    protected:

      EM* em;

      NM* nm;

    public:

      EdgeMapWrapper(EM& _em, NM& _nm) : em(&_em), nm(&_nm) { }

      ValueType operator[](const Edge& e) const { 

	switch (e.getSpec()) {

	case 0: 

	  return (*em)[e];

	case 1:

	  return (*nm)[e.getNode()];

	case 2:

	default:

	  return (*nm)[e.getNode()];

	}

      }

      void set(const Edge& e, ValueType t) { 

	switch (e.getSpec()) {

	case 0: 

	  em->set(e, t);

	  break;

	case 1:

	  nm->set(e.getNode(), t);

	  break;

	case 2:

	default:

	  nm->set(e.getNode(), t);

	  break;

	}

      }

    };

//  template<typename G> 

    friend std::ostream& 

    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i) { 

      os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; 

      return os; 

    }

//  template<typename G> 

    friend std::ostream& 

    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i) { 

      os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << 

	" node: " << i.n << ")"; 

      return os; 

    }

  };

  ///@}

} //namespace lemon

#endif //LEMON_BIPARTITE_GRAPH_WRAPPER_H