// This file is part of the FXT library.
// Copyright (C) 2010, 2011 Joerg Arndt
// License: GNU General Public License version 3 or later,
// see the file COPYING.txt in the main directory.

#include "perm/rotate.h"
#include "aux0/swap.h"
#include "fxttypes.h"

//#include "fxtalloca.h"
#include "jjassert.h"


void
perm2ffact(const ulong *x, ulong n, ulong *fc)
// Convert permutation in x[0,...,n-1] into
//   the (n-1) digit falling factorial representation in fc[0,...,n-2].
// We have: fc[0]<n, fc[1]<n-1, ..., fc[n-2]<2 (falling radices)
// Works as long as all elements in x[] are distinct.
// This is the so-called "Lehmer code" of a permutation.
// On return fc[k] contains the number of right inversions of position k,
//  the number of j > k where x[j] < x[k].
{
    for (ulong k=0; k<n-1; ++k)
    {
        ulong xk = x[k];
        ulong i = 0;
        for (ulong j=k+1; j<n; ++j)  if ( x[j]<xk )  ++i;
        fc[k] = i;
    }
}
// -------------------------

void
ffact2perm(const ulong *fc, ulong n, ulong *x)
// Inverse of perm2ffact():
// Convert the (n-1) digit falling factorial representation
//  in fc[0,...,n-2] into a permutation in x[0,...,n-1].
// Must have: fc[0]<n, fc[1]<n-1, ..., fc[n-2]<2 (falling radices)
{
#if 1
    for (ulong k=0; k<n; ++k)  x[k] = k;
    for (ulong k=0; k<n-1; ++k)
    {
        ulong i = fc[k];
        if ( i )  rotate_right1(x+k, i+1);
    }

#else
    ALLOCA(ulong, b, n);  // whether element used
    for (ulong k=0; k<n; ++k)  b[k] = 0;  // mark as unused
    for (ulong k=0; k<n-1; ++k)
    {
        ulong i = fc[k] + 1;
        for (ulong j=0;  ; ++j)
        {
            if ( b[j]==0 )
            {
                --i;
                if ( i==0 )  { x[k]=j; b[j]=1; break; }
            }
        }
    }
    ulong j=0;  while ( b[j] )  ++j;  // last unused element
    x[n-1] = j;
#endif
}
// -------------------------

void
ffact2invperm(const ulong *fc, ulong n, ulong *x)
// Convert the (n-1) digit falling factorial representation in fc[0,...,n-2]
// into permutation in x[0,...,n-1] such that
// the permutation is the inverse of the one computed via ffact2perm().
// Must have: fc[0]<n, fc[1]<n-1, ..., fc[n-2]<2 (falling radices)
{
#if 1
    for (ulong k=0; k<n; ++k)  x[k] = k;
    for (ulong k=n-2; (long)k>=0; --k)
    {
        ulong i = fc[k];
        if ( i )  rotate_left1(x+k, i+1);
    }

#else
    for (ulong k=0; k<n; ++k)  x[k] = n-1;  // "empty"
    for (ulong k=0; k<n-1; ++k)
    {
        ulong i = fc[k];
        for (ulong j=0;  ; ++j)
        {
            if ( x[j]==n-1 )  // if empty
            {
                if ( 0==i )  { x[j] = k;  break; }
                --i;
            }
        }
    }
#endif
}
// -------------------------


void
perm2rfact(const ulong *x, ulong n, ulong *fc)
// Convert permutation in x[0,...,n-1] into
//   the (n-1) digit rising factorial representation in fc[0,...,n-2].
// We have: fc[0]<2, fc[1]<3, ..., fc[n-2]<n (rising radices)
// Works as long as all elements in x[] are distinct.
// On return fc[k] contains the number of left inversions of position k,
//  the number of j < k where x[j] > x[k].
{
    for (ulong k=1; k<n; ++k)
    {
        ulong xk = x[k];
        ulong i = 0;
        for (ulong j=0; j<k; ++j)  if ( x[j]>xk )  ++i;
        fc[k-1] = i;
    }
}
// -------------------------

void
rfact2perm(const ulong *fc, ulong n, ulong *x)
// Inverse of perm2rfact():
// Convert the (n-1) digit rising factorial representation in fc[0,...,n-2].
//  into permutation in x[0,...,n-1]
// Must have: fc[0]<2, fc[1]<3, ..., fc[n-2]<n (rising radices)
{
    for (ulong k=0; k<n; ++k)  x[k] = k;
    ulong *y = x+n;
    for (ulong k=n-1;  k!=0;  --k, --y)
    {
        ulong i = fc[k-1];
        if ( i )  { ++i;  rotate_left1(y-i, i); }
    }
}
// -------------------------


void
rfact2invperm(const ulong *fc, ulong n, ulong *x)
// Convert the (n-1) digit rising factorial representation in fc[0,...,n-2].
//  into permutation in x[0,...,n-1] such that
// the permutation is the inverse of the one computed via rfact2perm().
// Must have: fc[0]<2, fc[1]<3, ..., fc[n-2]<n (rising radices)
{
#if 1
    for (ulong k=0; k<n; ++k)  x[k] = k;
    ulong *y = x + 2;
    for (ulong k=0;  k<n-1;  ++k, ++y)
    {
        ulong i = fc[k];
        if ( i )  { ++i;  rotate_right1(y-i, i); }
    }

#else
    for (ulong k=0; k<n; ++k)  x[k] = 0;  // "empty"
    for (ulong k=n-2; (long)k>=0; --k)
    {
        ulong i = fc[k];
        for (ulong j=0;  ; ++j)
        {
            if ( x[j]==0 )  // if empty
            {
                if ( 0==i )  { x[j] = k+1;  break; }
                --i;
            }
        }
    }
    // reverse x[]:
    for (ulong k=0, r=n-1;  k<r;  ++k, --r)  swap2(x[k], x[r]);
#endif
}
// -------------------------