wilf/single/treewalk.cpp

#include <iostream>
#include <iomanip>
#include <chrono>
#include <cmath>
#include <cpuid.h>
#include <fstream>
#include "treewalk.hpp"

using namespace std;
using namespace std::chrono;


fstream file;


void treat(const monoid& m){
  //  output(m,file);
  //return;
  //  int w=m.e*m.left-m.conductor;
  int q=ceil(float(m.conductor)/float(m.min));
  unsigned int rho=q*m.min-m.conductor;
  if(m.wilf<=rho){
    if((m.wilf<0) or (m.wilf<=rho and m.e>2 and m.left_primitive>1 and q>=4)){
      output(m,file);
    }
  }
}

//static const int mcut=ceil(float(3*(MAX_GENUS+2))/5);

bool cut(const monoid& m){
  if(3*m.left_primitive>=m.min) return true;
  return false;
}


#define STACK_SIZE (MAX_GENUS*(MAX_GENUS+1))/2
void walk(int m,int k)
{
  monoid data[STACK_SIZE], *stack[STACK_SIZE], *current,temp,temp2;
  size_t stack_size=0;
  for (ind_t i=0; i<STACK_SIZE; i++) stack[i] = &(data[i]); 
  init_ordinary(data[0],m);
  for(int i=0;i<k;++i){
    auto it = generator_iter<CHILDREN>(data[i]);
    it.move_next();
    ind_t pos=0;
    if(i==0){
      it.move_next();
      pos=1;
    }
    remove_generator(data[i+1],data[i],it.get_gen(),pos);
  }
  //Root @ data[k]
  temp=data[k];
  cout<<"Root : ";
  print_monoid_gen(temp);
  
  auto it = generator_iter<CHILDREN>(temp);
  it.move_next();
  ind_t pos=0;
  if(k==0){
    it.move_next();
    ++pos;
  }
  while (it.move_next()){
    remove_generator(*stack[stack_size], temp, it.get_gen(),pos++);
    cout<<"Pop "<<it.get_gen()<<" : ";
    print_monoid_gen(*stack[stack_size]);
    treat(*stack[stack_size]);
    ++stack_size;
  }
  while (stack_size != 0)
    {
      current = stack[--stack_size];
      /*if(current->conductor>=35){
	cout<<"Pop ";
	print_monoid_gen(*current);
	}*/
      
      if(not cut(*current))
	{
	  if (current->genus < MAX_GENUS - 1)
	    {
	      auto it = generator_iter<CHILDREN>(*current);
	      ind_t pos=0;
	      while (it.move_next())
		{
		  swap(stack[stack_size],stack[stack_size+1]);
		  //Current is tored @ stack_size+1
		  remove_generator(*stack[stack_size], *current, it.get_gen(),pos++);
		  treat(*stack[stack_size]);
		  ++stack_size;
		}
	      
	    }
	  else
	    {
	      auto it = generator_iter<CHILDREN>(*current);
	      ind_t pos=0;
	      while (it.move_next())
		{
		  remove_generator(temp2, *current, it.get_gen(),pos++);
		  temp2.conductor=0;
		  treat(temp2);
		}
	    }
	}
    }
}



int main(int argc, char **argv)
{
  if(argc!=4){
    cerr<<"Usage : "<<argv[0]<<" [m] [k] filename with k in [0,MAX_GENUS-m]"<<endl;
    exit(-1);
  }
  int m=atoi(argv[1]);
  int k=atoi(argv[2]);
  char* filename_base=argv[3];
  if(k<0 or k>=MAX_GENUS-m){
    cerr<<"k must be in [0,MAX_GENUS-m]"<<endl;
    exit(-2);
  }
  unsigned int ax, bx, cx, dx;
  if (!__get_cpuid(0x00000001, &ax, &bx, &cx, &dx))
    {
      cerr << "Unable to determine the processor type !" << endl;
      return EXIT_FAILURE;
    }
  if (!(cx & bit_SSSE3))
    {
      cerr << "This programm require sse3 instructions set !" << endl;
      return EXIT_FAILURE;
    }
  if (!(cx & bit_POPCNT))
    {
      cerr << "This programm require popcount instruction !" << endl;
      return EXIT_FAILURE;
    }

 
  cout << "Testing Wilf's conjecture for numerical semigroups of genus <= "
       << MAX_GENUS << " for m="<<m<<" and k="<<k<<"."<<endl;
  /*cerr << "Testing Wilf's conjecture for numerical semigroups of genus <= "
    << MAX_GENUS << " for m="<<m<<" and k="<<k<<"."<<endl;*/
  auto begin = high_resolution_clock::now();
  string filename=string(filename_base)+"_wilf_"+to_string(m)+"_"+to_string(k);
  file.open(filename.c_str(),ios::out|ios::trunc);
  walk(m,k);
  auto end = high_resolution_clock::now();
  duration<double> ticks = end-begin;
  cout << " Computation time = " << std::setprecision(4) << ticks.count() << " s."  << endl;
  file.close();
  return EXIT_SUCCESS;
}