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

#include "fxttypes.h"

// whether to use arrays instead of pointers:
//#define CATALAN_LEX_FIXARRAYS  // default is off

class catalan_lex
// Catalan restricted growth strings (RGS), lexicographic order.
{
public:
#ifndef CATALAN_LEX_FIXARRAYS
    ulong *a_;  // digits of the RGS: a_[k] <= a[k-1] + 1
#else
    ulong a_[64];
#endif
    ulong n_;   // Number of digits (paren pairs)

    char *str_; // paren string

public:
    catalan_lex(ulong n)
    {
        n_ = (n > 0 ? n : 1);  // shall work for n==0
#ifndef CATALAN_LEX_FIXARRAYS
        a_ = new ulong[n_];
#endif
        str_ = new char[2*n_+1];  str_[2*n_] = 0;
        first();
    }

    ~catalan_lex()
    {
#ifndef CATALAN_LEX_FIXARRAYS
        delete [] a_;
#endif
        delete [] str_;
    }

    void first()
    { for (ulong k=0; k<n_; ++k)  a_[k] = 0; }

    void last()
    { for (ulong k=0; k<n_; ++k)  a_[k] = k; }

    ulong next()
    // Return position of leftmost change, zero with last.
    {
        ulong j = n_ - 1;
        while ( j != 0 )
        {
            if ( a_[j] <= a_[j-1] )  break;
            a_[j] = 0;
            --j;
        }

        if ( j==0 )  return 0;  // current is last

        ++a_[j];
        return j;
    }

    ulong prev()
    // Return position of leftmost change, zero with first.
    {
        ulong j = n_ - 1;
        while ( j != 0 )
        {
            if ( a_[j] != 0 )  break;
            --j;
        }

        if ( j==0 )  return 0;  // current is first

        --a_[j];
        ulong i = j;
        while ( ++i < n_ )  a_[i] = a_[i-1] + 1;
        return j;
    }

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

    const char* str()  { make_str();  return (const char*)str_; }

protected:
    void make_str()
    {
        for (ulong k=0; k<2*n_; ++k)  str_[k] = ')';
        for (ulong k=0,j=0; k<n_; ++k,j+=2)  str_[ j - a_[k] ] = '(';
    }
};
// -------------------------


#endif  // !defined HAVE_CATALAN_LEX_H__