// 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 "ds/bitarray.h"
#include "fxtio.h"
#include "fxttypes.h"


void
perm2ccf(const ulong *p, ulong n, ulong *c, bitarray *tb/*=0*/)
// Convert permutation in p[] (array form) into
// canonical cycle form (CCF), written to c[].
{
    bitarray * b = tb;
    if ( 0==tb )  b = new bitarray(n);
    b->clear_all();

    ulong m = 0;  // minimum of unprocessed elements (==cycle end)
    ulong j = 0;  // position in c[]
    while ( m!=n )
    {
        ulong lc = m;  // last in cycle
        do
        {
            ulong nc = p[lc];  // next in cycle
            c[j] = nc;
            ++j;
            lc = nc;
            b->set(lc);  // mark as processed
        }
        while ( lc!=m );
        m = b->next_clear(m+1);  // ==n if no clear bit present
    }

    if ( 0==tb )  delete b;
}
// -------------------------

void
ccf2perm(const ulong *c, ulong n, ulong *p, bitarray *tb/*=0*/)
// Convert permutation in canonical cycle form (CCF) in c[] into
// array form, written to p[].
{
    bitarray * b = tb;
    if ( 0==tb )  b = new bitarray(n);
    b->clear_all();

    ulong m = 0;  // minimum of unprocessed elements (==cycle end)
    ulong j = 0;  // position in c[]
    while ( j!=n )
    {
        ulong lc = m;  // last in cycle
        do
        {
            ulong nc = c[j];  // next in cycle
            ++j;
            p[lc] = nc;
            lc = nc;
            b->set(lc);  // mark as processed
        }
        while ( lc!=m );  // until cycle end
        m = b->next_clear(m+1);  // ==n if no clear bit present
    }

    if ( 0==tb )  delete b;
}
// -------------------------


void
print_ccf(const char *bla, const ulong *c, ulong n, bitarray *tb/*=0*/)
// Print cycles of c[], interpreted as canonical cycle form (CCF).
{
    if ( bla )  cout << bla;

    bitarray * b = tb;
    if ( 0==tb )  b = new bitarray(n);
    b->clear_all();

    ulong np = 3*n;  // for padding

    ulong m = 0;  // minimum of unprocessed elements (==cycle end)
    ulong j = 0;  // position in c[]
    while ( j!=n )
    {
        ulong lc = m;  // last in cycle
        cout << "(";  np-=1;
        do
        {
            ulong nc = c[j];  // next in cycle
            cout << nc;
            if ( nc!=m )  { cout << ", ";  np-=2; }
            ++j;
            lc = nc;
            b->set(lc);  // mark as processed
        }
        while ( lc!=m );  // until cycle end
        cout << ") ";  np-=2;
        m = b->next_clear(m+1);
    }

    for (  ; np; --np)  cout << " ";

    if ( 0==tb )  delete b;
}
// -------------------------