/* -*- C++ -*-

 *

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

 *

 * Copyright (C) 2003-2008

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

{

public:

  Graph &_g;

  DynEdgeLookUp<Graph> _el;

  DEL(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(DEL(g),1);

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

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

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

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

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

	    << t2.userTime() << ' '

	    << t3.userTime() << ' '

	    << t4.userTime() << ' '

	    << t5.userTime() << ' '

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

//  	    << t6.userTime()

	    << std::endl;

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

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

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

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

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

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

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

	    << std::endl;

}