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

  *

  */

 #ifndef LEMON_BENCH_TEST_H

 #define LEMON_BENCH_TEST_H

 #include<vector>

 #include<iostream>

 #include<lemon/graph_utils.h>

 #include<lemon/time_measure.h>

 ///A primitive primtest

 ///\bug 2 is not a prime according to this function!

 ///

 ///\bug This function should go out of header file. I'm making it

 /// inline for now.

 inline bool isPrim(int n)

 {

   if(n%2) {

     for(int k=3;n/k>=k;k+=2)

       if(!(n%k)) return false;

     return true;

   }

   return false;

 }

 ///Finds the smallest prime not less then \c n.

 ///\bug This function should go out of header file. I'm making it

 /// inline for now.

 inline int nextPrim(int n)

 {

   for(n+=!(n%2);!isPrim(n);n+=2) ;

   return n;

 }

 /// Class to generate consecutive primes

 class Primes 

 {

   std::vector<int> primes;

   int n;

   bool isPrime(int m) 

   {

     for(int i=0;m<primes[i]*primes[i];i++) if(!(m%primes[i])) return false;

     return true;

   }

 public:

   Primes() : n(1) {}

   int operator() ()

     {

       if(primes.size()==0) {

 	primes.push_back(2);

 	return 2;

       }

       else {

 	do n+=2; while(!isPrime(n));

 	primes.push_back(n);

 	return n;

       }

     }

 };

 inline void PrintTime(const char *ID, lemon::Timer &T) 

 {

   lemon::TimeStamp S(T);

   std::cout << ID << ' ' << S.userTime() << ' '

 	    << S.systemTime() << ' ' << S.realTime() << std::endl;

 }

 ///

 template<class Graph>

 void addHyperCube(Graph &G,int dim,std::vector<typename Graph::Node> &nodes)

 {

   GRAPH_TYPEDEFS(typename Graph);

   std::vector<int> bits(dim+1);

   bits[0]=1;

   for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];

   for(int i=0;i<bits[dim];i++) {

     nodes.push_back(G.addNode());

     for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);

   }

 }

 ///

 template<class Graph>

 void addBiDirHyperCube(Graph &G,int dim,std::vector<typename Graph::Node>&nodes)

 {

   GRAPH_TYPEDEFS(typename Graph);

   std::vector<int> bits(dim+1);

   bits[0]=1;

   for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];

   for(int i=0;i<bits[dim];i++) {

     nodes.push_back(G.addNode());

     for(int j=0;j<dim;j++) if(i&bits[j]) {

       G.addEdge(nodes[i-bits[j]],nodes[i]);

       G.addEdge(nodes[i],nodes[i-bits[j]]);

     }

   }

 }  

 #endif