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

#include "sort/minmaxmed23.h"  // max2()

#include "fxttypes.h"


class setpart_rgs_lex
// Set partitions of the n-set as restricted growth strings (RGS).
// Lexicographic order.
{
public:
    ulong n_;    // Number of elements of set (set = {1,2,3,...,n})
    ulong *m_;   // m[k+1] = max(s[0], s[1],..., s[k]) + 1
    ulong *s_;   // RGS

public:
    setpart_rgs_lex(ulong n)
    {
        n_ = n;
        m_ = new ulong[n_+1];
        m_[0] = ~0UL;    // sentinel m[0] = infinity
        s_ = new ulong[n_];
        first();
    }

    ~setpart_rgs_lex()
    {
        delete [] m_;
        delete [] s_;
    }

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

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



    bool next()
    {
        if ( m_[n_] == n_ )  return false;

        ulong k = n_;
        do  { --k; }  while ( (s_[k] + 1) > m_[k] );

//        if ( k == 0 )  return false;

        s_[k] += 1UL;
#if 0
        const ulong mm = m_[k+1] = max2(m_[k], s_[k]+1);
#else  // faster:
        ulong mm = m_[k];
        mm += (s_[k]>=mm);
        m_[k+1] = mm;  // == max2(m_[k], s_[k]+1)
#endif

        while ( ++k<n_ )
        {
            s_[k] = 0;
            m_[k+1] = mm;
        }

        return true;
    }

    bool prev()
    {
        if ( m_[n_] == 1 )  return false;

        ulong k = n_;
        do  { --k; }  while ( s_[k]==0 );

//        if ( k == 0 )  return false;

        s_[k] -= 1;
        ulong mm = m_[k+1] = max2(m_[k], s_[k]+1);

        while ( ++k<n_ )
        {
            s_[k] = mm;  // == m[k]
            ++mm;
            m_[k+1] = mm;
        }

        return true;
    }

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

    void print()  const;
    void print_set(ulong off=1)  const;
};
// -------------------------


#endif  // !defined HAVE_SETPART_RGS_LEX_H__