#include "graph/digraph.h"
#include "graph/digraph-paths.h"
// demo-include "graph/search-digraph.cc"
#include "graph/mk-special-digraphs.h"
// demo-include "graph/mk-perm-gray-digraph.cc"

#include "aux0/factorial.h"
#include "comb/num2perm.h"
#include "comb/fact2perm.h"
#include "comb/comb-print.h"
#include "perm/perminvert.h"
#include "bits/printbin.h"

#include "fxttypes.h"
#include "fxtiomanip.h"
#include "jjassert.h"
#include "demo/nextarg.h"


//% Gray codes through permutations with only adjacent interchanges and
//% successive transpositions overlapping (doubly-adjacent Gray codes).


bool jcyc;
//ulong pn;

ulong n;
ulong nf;  // n!
ulong xx[64];  // aux (permutation)
ulong xxo[64]; // aux (last permutation)
ulong yy[64];  // aux (inverse permutation)
ulong yyo[64]; // aux (last inverse permutation)
ulong ff[64];  // aux (factorial number)

inline void print_one(ulong k, ulong x)
{
        cout << setw(4) << k << ": " << setw(6) << x;

        // show permutations:
        num2perm_ffact(x, xx, n);
        print_perm(" == ", xx, n, true);
//        perm2ffact(xx, n, ff);
//        print_perm("   ", ff, n-1, true);

        ulong df = 0;
        if ( k>0 )
        {
            for (ulong j=0; j<n; ++j)
                if ( xxo[j]!=xx[j] )  { df |= (1UL<<j); }
        }
        for (ulong j=0; j<n; ++j)  xxo[j]=xx[j];
        print_bin_vec("    ", df, n);

        make_inverse(xx, yy, n);
        print_perm("       ", yy, n, true);
        perm2ffact(yy, n, ff);
        print_perm("   ", ff, n-1, true);

        df = 0;
        if ( k>0 )
        {
            for (ulong j=0; j<n; ++j)
                if ( yyo[j]!=yy[j] )  { df |= (1UL<<j); }
        }
        for (ulong j=0; j<n; ++j)  yyo[j]=yy[j];
        print_bin_vec("    ", df, n);


        cout << endl;
}
// -------------------------


ulong
pfunc_permgray(const digraph_paths &dp)
// Function to be called with each path.
{
    // ----- conditions:
    if ( jcyc && (!dp.cq_) )  return 0; // only cycles


    // ----- actions:
//    dp.pfdone_ = true;

    const ulong *rv = dp.rv_;
    ulong ng = dp.ng_;


    cout << "Path #" << dp.pfct_ << ":" << endl;

#if 1
    for (ulong k=0; k<ng; ++k)
    {
        const ulong x = rv[k];
        print_one(k, x);
    }

#else // short output only:
    print_one(0, rv[0]);
    print_one(1, rv[1]);
    print_one(ng-1, rv[ng-1]);
#endif

    cout << endl;

    return 1;
}
// -------------------------

ulong *perms;
void cond_init()
{
    nf = factorial(n);
    perms = new ulong[nf * n];
    for (ulong k=0; k<nf; ++k)
    {
        num2perm_ffact(k, perms+k*n, n);
    }
}
// -------------------------


bool cfunc_adj(digraph_paths &dp, ulong ns)
// Condition: successive transpositions must overlap
{
    if ( ns<2 )  return  true;

    if ( ns==nf-1 )
    {
        if ( jcyc )  // cycle also wrt. double adjacent condition
        {
            ulong ct = 0;
            ulong p0 = n * dp.rv_[ns], p2 = n * dp.rv_[1];
            for (ulong j=0; j<n; ++j)  ct += ( perms[p0+j] != perms[p2+j] );
            if (ct!=3)  return false;
        }
    }

    ulong ct = 0;
    ulong p0 = n * dp.rv_[ns], p2 = n * dp.rv_[ns-2];
    for (ulong j=0; j<n; ++j)  ct += ( perms[p0+j] != perms[p2+j] );
    return (ct==3);
}
// -------------------------


int
main(int argc, char **argv)
{
    n = 4;
    NXARG(n, "Number of elements in permutations");

    jcyc = true;
    NXARG(jcyc, "Whether only cycles are output");

    ulong maxnp = 1;
    NXARG(maxnp, "stop after maxnp paths (0: never stop)");

    uint  rnds = 0;
    NXARG(rnds, "if set, edge order is randomized and rnds is used as random seed");

    cond_init();

//    digraph dg( make_perm_gray_digraph(n) );

    digraph * dgp = make_perm_gray_digraph(n);
    digraph & dg = *dgp;

    dg.sort_edges(0);
    if ( rnds )
    {
        srand(rnds);
        dg.randomize_edge_order();
    }

//    dg.print();

    cout << "Graph has "
         << dg.num_nodes() << " nodes, "
         << dg.num_edges() << " edges."
         << endl;

    digraph_paths dp(dg);
    ulong npt = dp.all_cond_paths(pfunc_permgray, cfunc_adj, 0, 0, maxnp );
    cout << " % n=" << n << "  npt=" << npt << endl;

    delete [] perms;

    delete dgp;

    return 0;
}
// -------------------------


/// Emacs:
/// Local Variables:
/// MyRelDir: "demo/graph"
/// makefile-dir: "../../"
/// make-target: "1demo DSRC=demo/graph/graph-perm-gray-demo.cc"
/// make-target2: "1demo DSRC=demo/graph/graph-perm-gray-demo.cc DEMOFLAGS=-DTIMING"
/// End: