#if !defined  HAVE_PAREN_H__
#define       HAVE_PAREN_H__
// 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"

class paren
// Parentheses strings by a modified comb_colex procedure
{
public:
    ulong k_;  // Number of paren pairs
    ulong n_;  // ==2*k
    ulong *x_; // Positions where an opening paren occurs
    char *str_;  // String representation,  e.g. "((())())()"

public:
    paren(ulong k)
    {
        k_ = (k>1 ? k : 2);  // not zero (empty) or one (trivial: "()")
        n_ = 2 * k_;
        x_ = new ulong[k_ + 1];
        x_[k_] = 999;  // sentinel (value repeated in method OK())
        str_ = new char[n_ + 1];
        str_[n_] = 0;
        first();
    }

    ~paren()
    {
        delete [] x_;
        delete [] str_;
    }

    void first()  { for (ulong i=0; i<k_; ++i)  x_[i] = i; }

    void last()  { for (ulong i=0; i<k_; ++i)  x_[i] = 2*i; }

    ulong next()  // return zero if current paren is the last
    {
        // if ( k_==1 )  return 0;  // uncomment to make algorithm work for k_==1

        ulong j = 0;
        if ( x_[1] == 2 )
        {
            // scan for low end == 010101:
            j = 2;
//            while ( (j<=k_) && (x_[j]==2*j) )  ++j;
            while ( x_[j]==2*j )  ++j;  // can touch sentinel
            if ( j==k_ )  {  first();  return 0; }
        }

        // scan block:
        while ( 1 == (x_[j+1] - x_[j]) )  { ++j; }

        ++x_[j];  // move edge element up
        for (ulong i=0; i<j; ++i)  x_[i] = i; // attach block at low end

        return 1;
    }

    ulong prev()  // return zero if current paren is the first
    {
        // if ( k_==1 )  return 0;  // uncomment to make algorithm work for k_==1

        ulong j = 0;
        // scan for first gap:
        while ( x_[j]==j )  ++j;
        if ( j==k_ )  {  last();  return 0; }

        if ( x_[j]-x_[j-1] == 2 )  --x_[j];  // gap of length one
        else
        {
            ulong i = --x_[j];
            --j;
            --i;
            // j items to go, distribute as 1.1.1.11111
            for (  ;  2*i>j;  --i,--j)  x_[j] = i;
            for (  ; i; --i)  x_[i] = 2*i;
            x_[0] = 0;
        }

        return 1;
    }

    const ulong * data()  const  { return x_; }

    bool OK()  const
    {
        if ( x_[k_] != 999 ) return false;  // sentinel
        for (ulong j=1; j<k_; ++j)  if ( x_[j]<=x_[j-1] )  return false;
        int s=0;
        ulong j=0, i=0;
        while ( j < k_ )
        {
            for (  ; i<x_[j]; ++i)  --s;
            if ( s<0 )  return false;
            ++s;  ++i;  ++j;
        }
        for ( ; i<2*k_; ++i)  --s;
        return (s==0);
    }

    const char * string()  // generate on demand
    {
        for (ulong j=0; j<n_; ++j)  str_[j] = ')';
        for (ulong j=0; j<k_; ++j)  str_[x_[j]] = '(';
        return str_;
    }
};
// -------------------------



#endif  // !defined HAVE_PAREN_H__