#include <algorithm>

   ///\sa EdgeLookUp

   ///\se AllEdgeLookup

   ///\sa EdgeLookUp

   ///\se AllEdgeLookup

   ///Fast edge look up between given endpoints.

   ///\ingroup gutils

   ///Using this class, you can find an edge in a graph from a given

   ///source to a given target in time <em>O(log d)</em>,

   ///where <em>d</em> is the out-degree of the source node.

   ///

   ///It is not possible to find \e all parallel edges between two nodes.

   ///Use \ref AllEdgeLookUp for this purpose.

   ///

   ///\warning This class is static, so you should refresh() (or at least

   ///refresh(Node)) this data structure

   ///whenever the graph changes. This is a time consuming (superlinearly

   ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).

   ///

   ///\param G The type of the underlying graph.

   ///

   ///\sa AllEdgeLookUp  

   template<class G>

   class EdgeLookUp 

   {

   public:

     GRAPH_TYPEDEFS(typename G)

     typedef G Graph;

   protected:

     const Graph &_g;

     typename Graph::template NodeMap<Edge> _head;

     typename Graph::template EdgeMap<Edge> _left;

     typename Graph::template EdgeMap<Edge> _right;

     class EdgeLess {

       const Graph &g;

     public:

       EdgeLess(const Graph &_g) : g(_g) {}

       bool operator()(Edge a,Edge b) const 

       {

 	return g.target(a)<g.target(b);

       }

     };

   public:

     ///Constructor

     ///Constructor.

     ///

     ///It builds up the search database, which remains valid until the graph

     ///changes.

     EdgeLookUp(const Graph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}

   private:

     Edge refresh_rec(std::vector<Edge> &v,int a,int b) 

     {

       int m=(a+b)/2;

       Edge me=v[m];

       _left[me] = a<m?refresh_rec(v,a,m-1):INVALID;

       _right[me] = m<b?refresh_rec(v,m+1,b):INVALID;

       return me;

     }

   public:

     ///Refresh the data structure at a node.

     ///Build up the search database of node \c n.

     ///

     ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is

     ///the number of the outgoing edges of \c n.

     void refresh(Node n) 

     {

       std::vector<Edge> v;

       for(OutEdgeIt e(_g,n);e!=INVALID;++e) v.push_back(e);

       if(v.size()) {

 	std::sort(v.begin(),v.end(),EdgeLess(_g));

 	_head[n]=refresh_rec(v,0,v.size()-1);

       }

       else _head[n]=INVALID;

     }

     ///Refresh the full data structure.

     ///Build up the full search database. In fact, it simply calls

     ///\ref refresh(Node) "refresh(n)" for each node \c n.

     ///

     ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is

     ///the number of the edges of \c n and <em>D</em> is the maximum

     ///out-degree of the graph.

     void refresh() 

     {

       for(NodeIt n(_g);n!=INVALID;++n) refresh(n);

     }

     ///Find an edge between two nodes.

     ///Find an edge between two nodes in time <em>O(</em>log<em>d)</em>, where

     /// <em>d</em> is the number of outgoing edges of \c s.

     ///\param s The source node

     ///\param t The target node

     ///\return An edge from \c s to \c t if there exists,

     ///\ref INVALID otherwise.

     ///

     ///\warning If you change the graph, refresh() must be called before using

     ///this operator. If you change the outgoing edges of

     ///a single node \c n, then

     ///\ref refresh(Node) "refresh(n)" is enough.

     ///

     Edge operator()(Node s, Node t) const

     {

       Edge e;

       for(e=_head[s];

 	  e!=INVALID&&_g.target(e)!=t;

 	  e = t < _g.target(e)?_left[e]:_right[e]) ;

       return e;

     }

   };

   ///Fast look up of all edges between given endpoints.

   ///\ingroup gutils

   ///This class is the same as \ref EdgeLookUp, with the addition

   ///that it makes it possible to find all edges between given endpoints.

   ///

   ///\warning This class is static, so you should refresh() (or at least

   ///refresh(Node)) this data structure

   ///whenever the graph changes. This is a time consuming (superlinearly

   ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).

   ///

   ///\param G The type of the underlying graph.

   ///

   ///\sa EdgeLookUp  

   template<class G>

   class AllEdgeLookUp : public EdgeLookUp<G>

   {

     using EdgeLookUp<G>::_g;

     using EdgeLookUp<G>::_right;

     using EdgeLookUp<G>::_left;

     using EdgeLookUp<G>::_head;

     GRAPH_TYPEDEFS(typename G)

     typedef G Graph;

     typename Graph::template EdgeMap<Edge> _next;

     Edge refreshNext(Edge head,Edge next=INVALID)

     {

       if(head==INVALID) return next;

       else {

 	next=refreshNext(_right[head],next);

 // 	_next[head]=next;

 	_next[head]=( next!=INVALID && _g.target(next)==_g.target(head))

 	  ? next : INVALID;

 	return refreshNext(_left[head],head);

       }

     }

     void refreshNext()

     {

       for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);

     }

   public:

     ///Constructor

     ///Constructor.

     ///

     ///It builds up the search database, which remains valid until the graph

     ///changes.

     AllEdgeLookUp(const Graph &g) : EdgeLookUp<G>(g), _next(g) {refreshNext();}

     ///Refresh the data structure at a node.

     ///Build up the search database of node \c n.

     ///

     ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is

     ///the number of the outgoing edges of \c n.

     void refresh(Node n) 

     {

       EdgeLookUp<G>::refresh(n);

       refreshNext(_head[n]);

     }

     ///Refresh the full data structure.

     ///Build up the full search database. In fact, it simply calls

     ///\ref refresh(Node) "refresh(n)" for each node \c n.

     ///

     ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is

     ///the number of the edges of \c n and <em>D</em> is the maximum

     ///out-degree of the graph.

     void refresh() 

     {

       for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);

     }

     ///Find an edge between two nodes.

     ///Find an edge between two nodes.

     ///\param s The source node

     ///\param t The target node

     ///\param prev The previous edge between \c s and \c t. It it is INVALID or

     ///not given, the operator finds the first appropriate edge.

     ///\return An edge from \c s to \c t after \prev or

     ///\ref INVALID if there is no more.

     ///

     ///For example, you can count the number of edges from \c u to \c v in the

     ///following way.

     ///\code

     ///AllEdgeLookUp<ListGraph> ae(g);

     ///...

     ///int n=0;

     ///for(Edge e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;

     ///\endcode

     ///

     ///Finding the first edge take <em>O(</em>log<em>d)</em> time, where

     /// <em>d</em> is the number of outgoing edges of \c s. Then, the

     ///consecutive edges are found in constant time.

     ///

     ///\warning If you change the graph, refresh() must be called before using

     ///this operator. If you change the outgoing edges of

     ///a single node \c n, then

     ///\ref refresh(Node) "refresh(n)" is enough.

     ///

 #ifdef DOXYGEN

     Edge operator()(Node s, Node t, Edge prev=INVALID) const {}

 #else

     using EdgeLookUp<G>::operator() ;

     Edge operator()(Node s, Node t, Edge prev) const

     {

       return prev==INVALID?(*this)(s,t):_next[prev];

     }

 #endif

   };