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){
  //  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;
}

void walk(int m,int k)
{
  monoid data[MAX_GENUS-1], *stack[MAX_GENUS], *current,temp,temp2;
  monoid **stack_pointer = stack+1;
  for (ind_t i=1; i<MAX_GENUS; i++) stack[i] = &(data[i-1]); 
  init_ordinary(data[0],m);
  for(int i=0;i<k;++i){
    auto it = generator_iter<CHILDREN>(data[i]);
    it.move_next();
    // printq_monoid_gen(data[i]);
    ind_t pos=0;
    if(i==0){
      it.move_next();
      pos=1;
    }
    remove_generator(data[i+1],data[i],it.get_gen(),pos);
  }
  temp=data[k];
  stack[0]=&temp;
  cout<<"Root : ";
  print_monoid_gen(temp);
  
  auto it = generator_iter<CHILDREN>(temp);
  it.move_next();
  ind_t pos=1;
  if(k==0){
    it.move_next();
    ++pos;
  }
  while (it.move_next()){
    stack_pointer[0] = stack_pointer[1];
    remove_generator(**stack_pointer, temp, it.get_gen(),pos++);
    cout<<"Pop "<<it.get_gen()<<" : ";
    print_monoid_gen(**stack_pointer);
    treat(**stack_pointer);
    stack_pointer++;
  }
  while (stack_pointer != stack)
    {
      --stack_pointer;
      current = *stack_pointer;
      if(not cut(*current))
	{
	  if (current->genus < MAX_GENUS - 1)
	    {
	      auto it = generator_iter<CHILDREN>(*current);
	      ind_t pos=0;
	      while (it.move_next())
		{
		  // exchange top with top+1
		  stack_pointer[0] = stack_pointer[1];
		  remove_generator(**stack_pointer, *current, it.get_gen(),pos++);
		  treat(**stack_pointer);
		  stack_pointer++;
		}
	      *stack_pointer = current;
	    }
	  else
	    {
	      auto it = generator_iter<CHILDREN>(*current);
	      ind_t pos=0;
	      while (it.move_next())
		{
		  remove_generator(temp2, *current, it.get_gen(),pos++);
		  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;
}