#if !defined HAVE_SUBSET_LEX_H__
#define      HAVE_SUBSET_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 "fxttypes.h"

// If defined, an array is used instead of a pointer:
//#define SUBSET_LEX_MAX_ARRAY_LEN 64  // default is off

class subset_lex
// Nonempty subsets of the set {0,1,2,...,n-1} in lexicographic order.
// Loopless generation.
{
public:
    ulong n_;   // number of elements in set, must have n>=1
    ulong k_;   // index of last element in subset
    // Number of elements in subset == k+1
#ifndef SUBSET_LEX_MAX_ARRAY_LEN
    ulong *x_;  // x[0...k-1]:  subset of {0,1,2,...,n-1}
#else
    ulong x_[SUBSET_LEX_MAX_ARRAY_LEN];
#endif

public:
    subset_lex(ulong n)
    {
        n_ = n;
#ifndef SUBSET_LEX_MAX_ARRAY_LEN
        x_ = new ulong[n_];
#endif
        first();
    }

    ~subset_lex()
    {
#ifndef SUBSET_LEX_MAX_ARRAY_LEN
        delete [] x_;
#endif
    }


    ulong first()
    {
        k_ = 0;
        x_[0] = 0;
        return  k_ + 1;
    }

    ulong last()
    {
        k_ = 0;
        x_[0] = n_ - 1;
        return  k_ + 1;
    }

    ulong next()
    // Generate next subset.
    // Return number of elements in subset
    // Return zero if current == last
    {
        if ( x_[k_] == n_-1 )  // last element is max ?
        {
            if ( k_==0 )  { first();  return 0; }

            --k_;      // remove last element
            x_[k_]++;  // increase last element
        }
        else  // add next element from set:
        {
            ++k_;
            x_[k_] = x_[k_-1] + 1;
        }

        return  k_ + 1;
    }

    ulong prev()
    // Generate previous subset.
    // Return number of elements in subset
    // Return zero if current == first
    {
        if ( k_ == 0 )  // only one element ?
        {
            if ( x_[0]==0 )  { last();  return 0; }

            x_[0]--;  // decr first element
            x_[++k_] = n_ - 1;     // add element
        }
        else
        {
            if ( x_[k_] == x_[k_-1]+1 )  --k_;  // remove last element
            else
            {
                x_[k_]--;  // decr last element
                x_[++k_] = n_ - 1;     // add element
            }
        }

        return  k_ + 1;
    }

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


//#undef SUBSET_LEX_MAX_ARRAY_LEN // better leave in


#endif  // !defined HAVE_SUBSET_LEX_H__