#include<math.h>
#include<hugo/list_graph.h>
#include<hugo/time_measure.h>
#include<iostream>
#include<sage_graph.h>
#include<vector>

using namespace hugo;

///An experimental typedef factory
#define GRAPH_TYPEDEF_FACTORY(Graph) \
   typedef typename Graph::   Node      Node;\
   typedef typename Graph::   NodeIt    NodeIn;\
   typedef typename Graph::   Edge      Edge;\
   typedef typename Graph::   EdgeIt    EdgeIt;\
   typedef typename Graph:: InEdgeIt  InEdgeIt;\
   typedef typename Graph::OutEdgeIt OutEdgeIt;
 

///A primitive primtest
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.
int nextPrim(int n)
{
  for(n+=!(n%2);!isPrim(n);n+=2) ;
  return n;
}

///Makes a full graph by adding and deleting a lot of edges;

///\param n Number of nodes.
///\param rat The funcion will make \f$rat\timesn^2\f$ edge addition and
///\f$(rat-1)\timesn^2\f$ deletion.
///\param p Tuning parameters.
///\warning \c rat, \c p, and \c n must be pairwise relative primes. 
template <class Graph>
void makeFullGraph(int n, int rat, int p)
{
  GRAPH_TYPEDEF_FACTORY(Graph);

  Graph G;
  
  //  Node nodes[n];
  std::vector<Node> nodes(n);
  for(int i=0;i<n;i++) nodes[i]=G.addNode();
  
  //Edge equ[rat];
  std::vector<Edge> equ(rat);
  
  unsigned long long int count;
  
  for(count=0;count<rat;count++) {
    equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]);
  }
  for(;(count%rat)||((count*p)%n)||((count*p/n)%n);count++) {
    //    if(!(count%1000000)) fprintf(stderr,"%d\r",count);
    if(count%rat) G.erase(equ[count%rat]);
    equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]);
  }
  std::cout << "Added " << count
	    << " ( " << n << "^2 * " << rat << " ) edges\n";
  //  for(int i=0;1;i++) ;
}

int main()
{
  std::cout << "START: n="  << nextPrim(1000) << " rat="
	    << nextPrim(300) << " p=" << nextPrim(100) << '\n';
  hugo::Timer T;
  makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100));
  std::cout << T  << '\n';
  std::cout << "START: n="  << nextPrim(1000) << " rat="
	    << nextPrim(300) << " p=" << nextPrim(100) << '\n';
  T.reset();
  makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150));
  std::cout << T  << '\n';
}