#if !defined  HAVE_PERM_GENUS_H__
#define       HAVE_PERM_GENUS_H__
// This file is part of the FXT library.
// Copyright (C) 2011, 2012 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 "perm/permq.h"  // count_cycles()

#include "fxttypes.h"

//#include "jjassert.h"


inline ulong perm_genus(const ulong *p, ulong n,  // permutation and length
                        const ulong *pi,  // inverse permutation
                        ulong *cpi,  // for rotated inverse permutation
                        bitarray *B=0)
// The genus g(P) of a permutation P of [1,2,...,n] is defined by
// g(P)=(1/2)*(n+1-Z(P)-Z(C P')), where P' is the inverse permutation of P,
// C = [2,3,4,...,n,1] = (1,2,...,n)  (cyclic shift),
// and Z(P) is the number of cycles of the permutation P.
// (taken from http://oeis.org/A177267)
{
    const ulong zp = count_cycles(p, n, B);

    // rotated inverse permutation:
    for (ulong j=1; j<n; ++j)  cpi[j-1] = pi[j];
    cpi[n-1] = pi[0];

    const ulong zcpi = count_cycles(cpi, n, B);

//    jjassert( 0==( (n + 1 - zp - zcpi) & 1 )  );
    const ulong gen = (n + 1 - zp - zcpi) / 2;
//    jjassert( gen <= (n+1)/2 );

    return gen;
}
// -------------------------


//inline bool perm_genus0_q(const ulong *f, ulong n, bitarray *tb/*=0*/)
//// Return whether permutation p[] has genus zero (INCORRECT:
////   condition is necessary but not sufficient).
//{
//    bitarray *b = tb;
//    if ( tb==0 )  b = new bitarray(n);
//    b->clear_all();
//
//    ulong ct = 0;
//    for (ulong k=0; k<n; ++k)
//    {
//        if ( b->test(k) )  continue; // already processed
//
//        ulong i = k;  // next in cycle
//        do
//        {
//            b->set(i);
//            ct += ( i > f[i] );
//        }
//        while ( (i=f[i]) != k );  // until we meet cycle leader again
//        ct -= ( k!=f[k] );  // ignore wrap around
//        if ( ct )  return false;
//    }
//
//    if ( tb==0 )  delete b;
//    return true;
//}
//// -------------------------


inline void genus0_perm_to_paren(const ulong *p, ulong n, bitarray &C)
// For a permutation p[] of genus zero, write the corresponding
// parenthesis string into C (which must hold 2*n bits).
// For example, the strings for all 4-permutations are
// (given only for permutations with genus zero):
//
//   #:      perm      genus  cycles            bits      parens
//   0:    [ . 1 2 3 ]  0   (0) (1) (2) (3)   1.1.1.1.   ()()()()
//   1:    [ . 1 3 2 ]  0   (0) (1) (2, 3)    1.1.11..   ()()(())
//   2:    [ . 2 1 3 ]  0   (0) (1, 2) (3)    1.11..1.   ()(())()
//   3:    [ . 2 3 1 ]  0   (0) (1, 2, 3)     1.11.1..   ()(()())
//   4:    [ . 3 1 2 ]  1   (0) (1, 3, 2)
//   5:    [ . 3 2 1 ]  0   (0) (1, 3) (2)    1.111...   ()((()))
//   6:    [ 1 . 2 3 ]  0   (0, 1) (2) (3)    11..1.1.   (())()()
//   7:    [ 1 . 3 2 ]  0   (0, 1) (2, 3)     11..11..   (())(())
//   8:    [ 1 2 . 3 ]  0   (0, 1, 2) (3)     11.1..1.   (()())()
//   9:    [ 1 2 3 . ]  0   (0, 1, 2, 3)      11.1.1..   (()()())
//  10:    [ 1 3 . 2 ]  1   (0, 1, 3, 2)
//  11:    [ 1 3 2 . ]  0   (0, 1, 3) (2)     11.11...   (()(()))
//  12:    [ 2 . 1 3 ]  1   (0, 2, 1) (3)
//  13:    [ 2 . 3 1 ]  1   (0, 2, 3, 1)
//  14:    [ 2 1 . 3 ]  0   (0, 2) (1) (3)    111...1.   ((()))()
//  15:    [ 2 1 3 . ]  0   (0, 2, 3) (1)     111..1..   ((())())
//  16:    [ 2 3 . 1 ]  1   (0, 2) (1, 3)
//  17:    [ 2 3 1 . ]  1   (0, 2, 1, 3)
//  18:    [ 3 . 1 2 ]  1   (0, 3, 2, 1)
//  19:    [ 3 . 2 1 ]  1   (0, 3, 1) (2)
//  20:    [ 3 1 . 2 ]  1   (0, 3, 2) (1)
//  21:    [ 3 1 2 . ]  0   (0, 3) (1) (2)    111.1...   ((()()))
//  22:    [ 3 2 . 1 ]  1   (0, 3, 1, 2)
//  23:    [ 3 2 1 . ]  0   (0, 3) (1, 2)     1111....   (((())))
//
{
    C.set_all();  // one for "open paren", zero for "close paren"
    ulong cpos = 0;
    for (ulong j=0; j<n; ++j)
    {
        // implicit "open paren" here.
        const ulong pj = p[j];

        if ( pj<=j )  C.clear(cpos+1);  // end of a cycle here
        else
            C.clear(cpos + 2*(pj-j));   // leave place for included cycle(s)

        cpos += 2;
    }
}
// -------------------------



#endif  // !defined HAVE_PERM_GENUS_H__