//
/////////////////////////////////
// mikbitset.c++
//
// Direct computing of A132582 terms.
// Approximately 100 lines of C++.
// Read the comments at the end.
// MIT Licensed source code.
//
// J.M. Aranda. Madrid. 2021.
/////////////////////////////
//
#define WIDE 160
//////////////////
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <cstdint>
#include <cstdbool>
#include <cassert>
#include <bitset> 
#include <array>
#include <unordered_map>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using typeposet=bitset<WIDE>;
using typesize=boost::multiprecision::uint128_t;
static unordered_map<typeposet,typesize> MAP;
static array<typeposet,WIDE> powers;
////////////////////////////////////
//
// poset: poset expressed as bitset.
// result: size of the poset.
static typesize POSETSIZE(const typeposet poset)
{
if(poset.none())return +1;       // (0,+1)
// If value known take from map.
auto ite=MAP.find(poset);
if(ite!=MAP.end())return ite->second;
/////////////////////////////////////
// Determine log2(poset)
int posethb=-1;typeposet tmp=poset;   
while(tmp.any()){posethb++;tmp>>=1;}
//
// Split on left and right posets.
typeposet left=poset;   // left Poset P-{x}
left&=~powers[posethb];
typesize Fleft=POSETSIZE(left);
//
typeposet right=poset;  // right Poset P-cone(x)
for(int i=0;i<=posethb;i++) {
  if((i&posethb)==i)right&=~powers[i];
  }
typesize Fright=POSETSIZE(right);
typesize SUM=Fleft+Fright;
MAP.emplace(poset,SUM); 
return SUM; 
}
//
int main (void)
{
// Init MAP.
#define MAPDIM 352011011
MAP.clear();MAP.reserve(MAPDIM);
MAP.emplace(0,1);MAP.emplace(1,2);
//
// fill powers array ************************
for(int i=0;i<WIDE;i++) {
  typeposet tmp;tmp.reset();tmp.set(0);tmp<<=i;
  powers[i]=tmp;
  }
// main loop
typeposet REPUNIT;REPUNIT.reset();
for(int n=0;n<WIDE;n++) 
  {
  REPUNIT<<=1;REPUNIT|=1;
  typeposet poset=REPUNIT;
////////////////////////////
  //// right poset P-cone(x)
  int highbit=-1;
  for(int bit=0;bit<WIDE;bit++)
    if(poset[bit]==1)highbit=bit;
  for(int i=0;i<=highbit;i++) {
    if((i&highbit)==i)poset&=~powers[i];
    }
/////////////////////////////////////////
  typesize An=POSETSIZE(poset);
  cout<<left<<setw(4)<<n;
  cout<<left<<setw(18)<<An<<endl;
  }
//
cout<<"mapsz: "<<MAP.size()<<endl;
MAP.clear();
return +1;
}
//
/***********************************
This is my version of the "Splitting result", 
from "Cardinalities of finite distributive lattices",
by P.Koehler and J.Berman.

Their program is on page A132581, and with which I compare it.
The copyrighted BigInt class does not support hash functions,
it is based on 16-bit arithmetic,
and it cannot be used as a "const" parameter.

It is replaced by
- a std::bitset to encode the poset.
- a boost::cpp_int for its size.
bitset class improves the readability of C++ code,
and it is implemented by _builtin functions.
Allows a hashmap, a std::unordered_map,
of fixed size, smaller and more efficient.
(Only 32GB at term 160).
The cpp_int class also occupies less memory than BigInt.
*******************************************************/