//
/////////////////////////////////
// mikbitsetA1.c++
//
// A132581 terms.
// (this program is Different from the one 
// that calculates terms of the A132582 series)
// Read the comments at the end.
// MIT Licensed source code.
//
// J.M. Aranda. Madrid. 2021.
/////////////////////////////
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <bitset> 
#include <array>
#include <unordered_map>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
/////////////////////////////////////////////
#pragma pack(16)
#define WIDE 256
using typeposet=bitset<WIDE>;
using typesize=boost::multiprecision::uint128_t;
static std::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(poset.count()==1)return +2;   // (1,+2)
// 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.
MAP.clear();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++) 
  {
  typeposet poset=REPUNIT;
  typesize An=POSETSIZE(poset);
  cout<<setw(4)<<n;
  cout<<right<<setw(18)<< An<<endl;
// next must be here
  REPUNIT<<=1;REPUNIT|=1;
  }
//
cout<<"mapsz: "<<MAP.size()<<endl;
MAP.clear();
return +1;
}
//
// This is my version of the Algorithm Splitting Result
// of P.Koehler and J.Berman,
// from "Cardinalities of finite distributive lattices".
// With whose program I compare it.
// The copyrighted BigInt class is limited to 256 terms,
// does not support hash functions,
// is based on 16-bit arithmetic,
// and cannot be used as a "const" parameter.
// It is replaced by
// - a  std::bitset to encode the poset.
// - an std::cpp_int for its size.
// the bitset class improves the readability of the code,
// and is implemented by _builtin functions.
// It allows to use a hashmap, a std::unordered_map,
// pre-scalable, smaller and more efficient.
// Only 32GB in term 160.
// The cpp_int class also takes up less memory than BigInt.
///////////////////////////////////////////////////////////
//
//