// -*- 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 source(const Edge& e) { 
//       if (!(*(this->s_false_t_true_map))[this->graph->source(e)]) 
// 	return Node(this->graph->source(e));
//       else
// 	return Node(this->graph->target(e));	
//     }
//     Node target(const Edge& e) { 
//       if (!(*(this->s_false_t_true_map))[this->graph->source(e)]) 
// 	return Node(this->graph->target(e));
//       else
// 	return Node(this->graph->source(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 source have to be in \c S_Class and \c target in \c T_Class.
    Edge addEdge(const Node& source, const Node& target) {
      return Parent::graph->addEdge(source, target);
    }

    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 source(const Edge& e) const { 
      switch (e.spec) {
      case 0: 
	return Node(this->graph->source(e));
	break;
      case 1:
	return S_NODE;
	break;
      case 2:
      default:
	return Node(e.n);
	break;
      }
    }
    Node target(const Edge& e) const { 
      switch (e.spec) {
      case 0: 
	return Node(this->graph->target(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 source(e); }
    Node aNode(const InEdgeIt& e) const { return target(e); }
    Node bNode(const OutEdgeIt& e) const { return target(e); }
    Node bNode(const InEdgeIt& e) const { return source(e); }

    void addNode() const { }
    void addEdge() const { }
    
//    Node addNode() const { return Node(this->graph->addNode()); }
//    Edge addEdge(const Node& source, const Node& target) const { 
//      return Edge(this->graph->addEdge(source, target)); }

//    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 Key;
      typedef typename NM::Value Value;
    protected:
      NM* nm;
      Value* s_value, t_value;
    public:
      NodeMapWrapper(NM& _nm, Value& _s_value, Value& _t_value) : 
	nm(&_nm), s_value(&_s_value), t_value(&_t_value) { }
      Value 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, Value 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 Key;
      typedef typename EM::Value Value;
    protected:
      EM* em;
      NM* nm;
    public:
      EdgeMapWrapper(EM& _em, NM& _nm) : em(&_em), nm(&_nm) { }
      Value 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, Value 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