/* -*- C++ -*-

  *

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

  *

  * Copyright (C) 2003-2006

  * 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_EDGE_LOOKUP_H

 #define LEMON_EDGE_LOOKUP_H

 #include<lemon/graph_utils.h>

 #include<algorithm>

 #include<vector>

 namespace lemon {

   template<class G>

   class EdgeLookUp2

   {

   public:

     GRAPH_TYPEDEFS(typename G)

     typedef G Graph;

   private:

     const Graph &_g;

     typename Graph::template NodeMap<int> _start;

     typename Graph::template NodeMap<int> _end;

     std::vector<Edge> _edges;

     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

     EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}

   public:

     ///Refresh the data structure at a node.

     void refresh(Node n) 

     {

       const int bi = _start[n] = _edges.size();

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

       const typename std::vector<Edge>::iterator ei=_edges.end();

       _end[n]=_edges.size();

       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));

     }

     ///Refresh the full data structure.

     void refresh() 

     {

       _edges.clear();

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

     }

     ///Find an edge between two nodes.

     ///Find an edge between two nodes.

     ///\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.

     Edge operator()(Node s, Node t) 

     {

       int a=_start[s];

       int b=_end[s];

       while(a<b) 

 	{

 	  int n=(a+b)/2;

 	  Node tt = _g.target(_edges[n]);

 	  if(tt==t) return _edges[n];

 	  else if(tt<t) a=n+1;

 	  else b=n;

 	}

       return INVALID;

     }

     ///Find the next edge

       ///\warning This function is unimplemented.

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

     {

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

     }

   };

   template<class G>

   class EdgeLookUp3

   {

   public:

     GRAPH_TYPEDEFS(typename G)

     typedef G Graph;

   private:

     const Graph &_g;

     typename Graph::template NodeMap<Edge*> _start;

     typename Graph::template NodeMap<Edge*> _end;

     std::vector<Edge> _edges;

     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

     EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}

   public:

     ///Refresh the data structure at a node.

     void refresh(Node n) 

     {

       const int bi = _start[n] = _edges.size();

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

       const typename std::vector<Edge>::iterator ei=_edges.end();

       _end[n]=_edges.size();

       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));

     }

     ///Refresh the full data structure.

     void refresh() 

     {

       _edges.resize(countEdges(_g));

       int l=0;

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

 	{

 	  int ls = l;

 	  _start[n]=&(_edges[l]);	

 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;

 	  _end[n]=&(_edges[l]);

 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));

 	}

     }

     ///Find an edge between two nodes.

     ///Find an edge between two nodes.

     ///\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.

     Edge operator()(Node s, Node t) 

     {

       Edge *a=_start[s];

       Edge *b=_end[s];

       while(a!=b) 

 	{

  	  Edge *m=a+((b-a)/2);

 	  Node tt = _g.target(*m);

 	  if(tt==t) return *m;

 	  else if(tt<t) a=m+1;

 	  else b=m;

 	}

       return INVALID;

     }

     ///Find the next edge

       ///\warning This function is unimplemented.

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

     {

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

     }

   };

 //   template<class G>

 //   class EdgeLookUp4

 //   {

 //   public:

 //     GRAPH_TYPEDEFS(typename G)

 //     typedef G Graph;

 //   private:

 //     const Graph &_g;

 //     typename Graph::template NodeMap<Edge*> _start;

 //     typename Graph::template NodeMap<Edge*> _end;

 //     std::vector<Edge> _edges;

 //     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

 //     EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}

 //   public:

 //     ///Refresh the data structure at a node.

 //     void refresh(Node n) 

 //     {

 //       const int bi = _start[n] = _edges.size();

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

 //       const typename std::vector<Edge>::iterator ei=_edges.end();

 //       _end[n]=_edges.size();

 //       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));

 //     }

 //     ///Refresh the full data structure.

 //     void refresh() 

 //     {

 //       _edges.resize(countEdges(_g));

 //       int l=0;

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

 // 	{

 // 	  int ls = l;

 // 	  _start[n]=&(_edges[l]);	

 // 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;

 // 	  _end[n]=&(_edges[l]);

 // 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));

 // 	}

 //     }

 //     ///Find an edge between two nodes.

 //     ///Find an edge between two nodes.

 //     ///\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.

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

 //     {

 //       Edge *a=_start[s];

 //       Edge *b=_end[s];

 //       while(a!=b) 

 // 	{

 // 	  Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);

 // 	  Node tt = _g.target(*m);

 // 	  if(tt==t) return *m;

 // 	  else if(tt<t) a=m+1;

 // 	  else b=m;

 // 	}

 //       return INVALID;

 //     }

 //     ///Find the next edge

 //       ///\warning This function is unimplemented.

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

 //     {

 //       return prev==INVALID?(*this)(s,t):INVALID;

 //     }

 //   };

 }

 #endif