/*
zcode.c 組合せに対応する整数への変換とその逆変換の本体
programmed by Isaku WADA isaku@pb4.so-net.ne.jp
*/

#include "zcode.h"

enum { CT_IS_CODE=1, CT_IS_PERM };
volatile unsigned long MaxCodeTableSize;
code0_t DefaultCodeTable[1];

#ifdef __cplusplus
 #define GET_MEM(T,S) new T[S]
 #define FREE_MEM(P)  delete[]P
#else
 #define GET_MEM(T,S) malloc(sizeof(T)*(S))
 #define FREE_MEM(P)  free(P)
#endif

/*+------------+
　|メモリの確保|
　+------------+*/
static INDEX**CodeGetMem(code_t*t,unsigned long sz) {
    if (sz>MaxCodeTableSize) MaxCodeTableSize=sz;
#if INT_MAX == 32767
    if (sz>=65535UL) { t->ErrorCode=CEC_MEMORY; return 0; }
#endif
#ifdef __cplusplus
    delete[]t->table; t->table=0;
    if (sz) {
        try { t->table=new char[(size_t)sz]; }
        catch (...) { t->table=0; }
        if (t->table==0) { t->ErrorCode=CEC_MEMORY; return 0; }
    }
    return(INDEX**)t->table;
#else
    if ((void*)t==(void*)DefaultCodeTable) {
        free(DefaultCodeTable->table); DefaultCodeTable->table=0;
        if (sz) {
            DefaultCodeTable->table=malloc((size_t)sz);
            if (DefaultCodeTable->table==0)
            { DefaultCodeTable->ErrorCode=CEC_MEMORY; return 0; }
        }
        return(INDEX**)DefaultCodeTable->table;
    }else{
        if (sz>CODE_TABLE_SIZE)
        { t->ErrorCode=CEC_MEMORY; return 0; }
        return(INDEX**)t->table;
    }
#endif
}

/*+----------------------------------------+
　|Comb・Repe・Partのテーブルを作成の下請け|
　+----------------------------------------+*/
INDEX InitCode_r(code_t*t,int n,int r) {
    int i,j; INDEX**a,**b,*p;
#ifdef __cplusplus
    if (n==t->n&&r==t->r&&t->type==CT_IS_CODE) return t->size;
#else
    if ((void*)t==(void*)DefaultCodeTable&&
        n==t->n&&r==t->r&&!t->type==CT_IS_CODE)
        return t->size;
#endif
    t->ErrorCode=0; t->n=n; t->r=r; t->type=CT_IS_CODE; t->size=0;
    if (r<0||n<=0) { t->ErrorCode=CEC_PARAMETER; return 0; }
    a=CodeGetMem(t,2UL*sizeof(INDEX)*n*r+2UL*sizeof(INDEX*)*r);
    if ((r&&a==0)||t->ErrorCode==CEC_MEMORY) return 0;
    t->a=a; t->b=b=a+r; p=(INDEX*)(b+r);
    if (r==0) return t->size=1;
    for (i=0;i<r;i++) { a[i]=p; b[i]=p+=n; p+=n; }
    for (i=0;i<r;i++) a[i][n-1]=1;
    for (j=1;j<n;j++) a[r-1][j]=1;
    for (i=r-2;i>=0;i--) for (j=n-2;j>0;j--)
        a[i][j]=a[i][j+1]+a[i+1][j];
    for (i=0;i<r;i++) a[i][0]=0;
    for (i=0;i<r;i++) for (j=1;j<n;j++)
        b[i][j-1]=a[i][j]+=a[i][j-1];
    for (i=r-2;i>=0;i--) for (j=0;j<n-1;j++) b[i][j]+=b[i+1][j];
    if (n==1) for (i=0;i<r;i++) b[i][0]=1;
    else for (i=0;i<r;i++) b[i][n-1]=b[i][n-2]+1;
    t->ErrorCode=CEC_OVERFLOW;
    for (i=0;i<r;i++) for (j=1;j<n;j++) if (b[i][j]<=b[i][j-1]) return 0;
    if (n>1&&b[0][n-1]-b[0][n-2]!=1) return 0;
    t->ErrorCode=0; return t->size=b[0][n-1];
}

/*+------------------------------------------+
　|順列のテーブルを作成。組み合わせ総数を返す|
　+------------------------------------------+*/
INDEX InitPerm_r(code_t*t,int n,int r) {
    int i,j; INDEX**a,*b,u,v;
#ifdef __cplusplus
    if (n==t->n&&r==t->r&&t->type==CT_IS_PERM) return t->size;
#else
    if ((void*)t==(void*)DefaultCodeTable&&
        n==t->n&&r==t->r&&t->type==CT_IS_PERM)
        return t->size;
#endif
    t->ErrorCode=CEC_PARAMETER; t->size=0; t->n=n; t->r=r;
    t->type=CT_IS_PERM;
    if (r<=0||n<=0||r>n) return 0;
    a=CodeGetMem(t,1UL*sizeof(INDEX*)*r
                   +1UL*sizeof(INDEX)*(n+n-r+1)*r/2UL);
    if (t->ErrorCode==CEC_MEMORY) return 0;
    t->a=a; b=(INDEX*)(a+r);
    for (i=0;i<r;b+=n-i,i++) a[i]=b;
    t->b=(INDEX**)b; t->ErrorCode=CEC_OVERFLOW;
    for (i=r-1;i>=0;i--) {
        if (i==r-1) a[i][0]=1; else a[i][0]=a[i+1][n-i-2];
        for (j=1;j<n-i;j++) a[i][j]=a[i][0]+a[i][j-1];
    }
    for (i=0;i<r;i++) for (j=1;j<n-i;j++) if (a[i][j]<=a[i][j-1]) return 0;
    u=a[0][n-1]; v=u-1;
    if (u-v!=1) return 0;
    t->ErrorCode=0; return t->size=u;
}

/*+--------------------------+
　|重複組み合わせを整数に変換|
　+--------------------------+*/
INDEX RepeToNum_r(code_t*t,int*vec) {
    int i,r=t->r; INDEX num=0,**a=t->a;
#ifdef NO_CODE_SORT
    for (i=0;i<r;i++) num+=a[i][vec[i]];
#else
    int j,k,z[CODE_SORT_R_MAX],*tmp=z;
    if (r>CODE_SORT_R_MAX) tmp=GET_MEM(int,r);
    if (tmp==0) return 0;
    for (j=0;j<r;j++) {
        k=vec[j];
        for (i=j;i>0&&tmp[i-1]>k;i--) tmp[i]=tmp[i-1];
        tmp[i]=k;
    }
    for (i=0;i<r;i++) num+=a[i][tmp[i]];
    if (r>CODE_SORT_R_MAX) FREE_MEM(tmp);
#endif
    return num;
}

/*+------------------------------+
　|いわゆる組み合わせを整数に変換|
　+------------------------------+*/
INDEX CombToNum_r(code_t*t,int*vec) {
    int i,r=t->r; INDEX num=0,**a=t->a;
#ifdef NO_CODE_SORT
    for (i=0;i<r;i++) num+=a[i][vec[i]-i];
#else
    int j,k,z[CODE_SORT_R_MAX],*tmp=z;
    if (r>CODE_SORT_R_MAX) tmp=GET_MEM(int,r);
    if (tmp==0) return 0;
    for (j=0;j<r;j++) {
        k=vec[j];
        for (i=j;i>0&&tmp[i-1]>k;i--) tmp[i]=tmp[i-1];
        tmp[i]=k;
    }
    for (i=0;i<r;i++) num+=a[i][tmp[i]-i];
    if (r>CODE_SORT_R_MAX) FREE_MEM(tmp);
#endif
    return num;
}

/*+--------------------------+
　|分割組み合わせを整数に変換|
　+--------------------------+*/
INDEX PartToNum_r(code_t*t,int*vec) {
    int i,z=0,r=t->r; INDEX num=0,**a=t->a;
    for (i=0;i<r;i++) num+=a[i][z+=vec[i]];
    return num;
}

/*+----------------+
　|順列を整数に変換|
　+----------------+*/
INDEX PermToNum_r(code_t*t,int*vec) {
    int i,j,k,r=t->r; INDEX u=0,**a=t->a;
    for (i=0;i<r;i++) {
        for (k=vec[i],j=0;j<i;j++) if (vec[j]<vec[i]) k--;
        if (k) u+=a[i][k-1];
    }
    return u;
}

/*+------------------------------+
　|整数を重複組み合わせへ展開する|
　+------------------------------+*/
void NumToRepe_r(code_t*t,int*vec,INDEX num) {
    int i,j=0,r=t->r; INDEX**a=t->a,**b=t->b;
    for (i=0;i<r;i++) {
        while (b[i][j]<=num) j++;
        num-=a[i][j]; vec[i]=j;
    }
}

/*+----------------------------------+
　|整数をいわゆる組み合わせへ展開する|
　+----------------------------------+*/
void NumToComb_r(code_t*t,int*vec,INDEX num) {
    int i,j=0,r=t->r; INDEX**a=t->a,**b=t->b;
    for (i=0;i<r;i++) {
        while (b[i][j]<=num) j++;
        num-=a[i][j]; vec[i]=j+i;
    }
}

/*+------------------------------+
　|整数を分割組み合わせへ展開する|
　+------------------------------+*/
void NumToPart_r(code_t*t,int*vec,INDEX num) {
    int i,j=0,sum=t->n-1,prev=0,r=t->r; INDEX**a=t->a,**b=t->b;
    for (i=0;i<r;i++) {
        while (b[i][j]<=num) j++;
        num-=a[i][j]; sum-=vec[i]=j-prev; prev=j;
    }
    vec[i]=sum;
}

/*+--------------------+
　|整数を順列へ展開する|
　+--------------------+*/
void NumToPerm_r(code_t*t,int*vec,INDEX num) {
    int i,j,k,r=t->r,n=t->n; INDEX**a=t->a; char z[PERM_N_MAX],*f=z;
    if (n>PERM_N_MAX) f=GET_MEM(char,n);
    if (f==0) return;
    for (j=(n>PERM_N_MAX?n:PERM_N_MAX);j--;) f[j]=0;
    for (i=0;i<r;i++) {
        for (k=0;a[i][k]<=num;k++) ;
        if (k) num-=a[i][k-1];
        for (j=0;k>=0;k--,j++) while (f[j]) j++;
        f[--j]=1; vec[i]=j;
    }
    if (n>PERM_N_MAX) FREE_MEM(f);
}