/* -*- C++ -*-

  *

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

  *

  * Copyright (C) 2003-2007

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

  *

  */

 #include<lemon/smart_graph.h>

 #include<vector>

 #include<lemon/time_measure.h>

 #include<lemon/random.h>

 #include<lemon/graph_utils.h>

 #include<algorithm>

 using 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) 

 // 	{

 // // #ifdef X86

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

 // // #elif X86_64

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

 // // #else

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

 // // #endif

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

 //   {

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

 //     EdgeLookUp5(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) 

 // 	{

 // // #ifdef X86

 //  	  Edge *m=(Edge*)((((unsigned int)a>>1)+((unsigned int)b)>>1)

 // 			  & 0xfffffffc);

 // // #elif X86_64

 // // 	  Edge *m=(Edge*)(((unsigned long)a>>1+(undigned long)b)>>1)&0xfffffffc);

 // // #else

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

 // // #endif

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

 //     }

 //   };

 GRAPH_TYPEDEFS(SmartGraph)

 typedef SmartGraph Graph;

 class FE 

 {

 public:

   Graph &_g;

   FE(Graph &g) :_g(g) {}

   void operator()() 

   {

     Edge e;

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

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

 	e=findEdge(_g,u,v);

   }

 };

 class EL 

 {

 public:

   Graph &_g;

   EdgeLookUp<Graph> _el;

   EL(Graph &g) :_g(g), _el(g) {}

   void operator()() 

   {

     Edge e;

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

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

 	e=_el(u,v);

   }

 };

 class EL2

 {

 public:

   Graph &_g;

   EdgeLookUp2<Graph> _el;

   EL2(Graph &g) :_g(g), _el(g) {}

   void operator()() 

   {

     Edge e;

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

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

 	e=_el(u,v);

   }

 };

 class EL3

 {

 public:

   Graph &_g;

   EdgeLookUp3<Graph> _el;

   EL3(Graph &g) :_g(g), _el(g) {}

   void operator()() 

   {

     Edge e;

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

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

 	e=_el(u,v);

   }

 };

 // class EL4

 // {

 // public:

 //   Graph &_g;

 //   EdgeLookUp4<Graph> _el;

 //   EL4(Graph &g) :_g(g), _el(g) {}

 //   void operator()() 

 //   {

 //     Edge e;

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

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

 // 	e=_el(u,v);

 //   }

 // };

 // class EL5

 // {

 // public:

 //   Graph &_g;

 //   EdgeLookUp5<Graph> _el;

 //   EL5(Graph &g) :_g(g), _el(g) {}

 //   void operator()() 

 //   {

 //     Edge e;

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

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

 // 	e=_el(u,v);

 //   }

 // };

 int main(int, char**argv)

 {

   int N=atoi(argv[1]);

   int M=int(N*atof(argv[2]));

   Graph g;

   std::vector<Node> v;

   for(int i=0;i<N;i++) v.push_back(g.addNode());

   for(int i=0;i<M;i++) g.addEdge(v[rnd[N]],v[rnd[N]]);

 //   {

 //     Edge e;

 //     TimeReport t("findEdge: ");

 //     for(NodeIt u(g);u!=INVALID;++u)

 //       for(NodeIt v(g);v!=INVALID;++v)

 // 	e=findEdge(g,u,v);

 //   }

 //   {

 //     Edge e;

 //     EdgeLookUp<Graph> el(g);

 //     TimeReport t("EdgeLookUp: ");

 //     for(NodeIt u(g);u!=INVALID;++u)

 //       for(NodeIt v(g);v!=INVALID;++v)

 // 	e=el(u,v);

 //   }

   TimeStamp t1 = runningTimeTest(FE(g),1);

   TimeStamp t2 = runningTimeTest(EL(g),1);

   TimeStamp t3 = runningTimeTest(EL2(g),1);

   TimeStamp t4 = runningTimeTest(EL3(g),1);

 //   TimeStamp t5 = runningTimeTest(EL4(g),1);

 //   TimeStamp t6 = runningTimeTest(EL5(g),1);

   std::cout << t1.userTime()/N/N << ' ' 

 	    << t2.userTime()/N/N << ' '

 	    << t3.userTime()/N/N << ' '

 	    << t4.userTime()/N/N << ' '

 // 	    << t5.userTime()/N/N << ' '

 //  	    << t6.userTime()/N/N

 	    << std::endl;

 }