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

#include "fxttypes.h"
#include "restrict.h"

#include "ds/bitarray.h"
#include "bits/bit2pow.h"


void
make_inverse(const ulong *f, ulong * restrict g, ulong n)
// Set (as permutation) g to the inverse of f
{
    for (ulong k=0; k<n; ++k)  g[f[k]] = k;
}
// -------------------------


void
make_inverse(ulong *f, ulong n, bitarray *bp/*=0*/)
// Set (as permutation) f to its own inverse.
// In-place version.
{
    bitarray *tp = bp;
    if ( 0==bp )  tp = new bitarray(n);  // tags
    tp->clear_all();

    for (ulong k=0; k<n; ++k)
    {
        if ( tp->test_clear(k) )  continue;  // already processed
        tp->set(k);

        // invert a cycle:
        ulong i = k;
        ulong g = f[i];  // next index
        while ( 0==(tp->test_set(g)) )
        {
            ulong t = f[g];
            f[g] = i;
            i = g;
            g = t;
        }
        f[g] = i;
    }

    if ( 0==bp )  delete tp;
}
// -------------------------


void
boothroyd_invert(ulong *f, ulong n, bitarray *bp/*=0*/)
// Set f to its own inverse. Boothroyd's algorithm.
// Complexity is n*log(n), so make_inverse() is faster.
// Knuth says the algorithm is ingenious, so its here.
// In-place version.
{
    bp = 0;
    bitarray *tp = bp;
    if ( 0==bp )  tp = new bitarray(n);  // tags
    tp->clear_all();

    for (ulong m=0; m<n; ++m)
    {
        ulong j = m;
        ulong i = f[j];
        while ( tp->test(j) )  // already processed
        {
            j = i;
            i = f[j];  // next index
        }

        f[j] = f[i];
        f[i] = m;

        tp->set(i);
        //  j stays untagged !
    }

    if ( 0==bp )  delete tp;
}
// -------------------------