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;
  if(w<=0){
    if(m.e!=3 and (m.e!=m.min or m.left_primitive!=1)){
      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_children(monoid m)
{
  monoid data[MAX_GENUS-1], *stack[MAX_GENUS], *current,temp;
  monoid **stack_pointer = stack + 1;

  for (ind_t i=1; i<MAX_GENUS; i++) stack[i] = &(data[i-1]); // Nathann's trick to avoid copy
  stack[0] = &m;
  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(temp, *current, it.get_gen(),pos++);
		  treat(temp);
		}
	    }
	}
    }
}



int main(int argc, char **argv)
{
  monoid O,S;
  string nproc = "0";

  if(argc!=3){
    cerr<<"Usage : "<<argv[0]<<" [m] [k] with k in [1,m-1]"<<endl;
    exit(-1);
  }
  int m=atoi(argv[1]);
  int k=atoi(argv[2]);
  if(k<=0 or k>=m){
    cerr<<"k must be in [1,m-1]"<<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 << " which are sons of O_{"<<m<<"}\\{"<<m+k<<"}."<<endl;
  auto begin = high_resolution_clock::now();
  init_ordinary(O,m);
  remove_generator(S,O,m+k,k);
  string filename="wilf_"+to_string(m)+"_"+to_string(k);
  file.open(filename.c_str(),ios::out|ios::trunc);
  walk_children(S);
  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;
}