#if !defined HAVE_MIXEDRADIX_SUBSET_LEX_H__
#define      HAVE_MIXEDRADIX_SUBSET_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 "comb/mixedradix.h"
#include "comb/comb-print.h"
#include "fxttypes.h"


class mixedradix_subset_lex
// Mixed radix numbers in subset-lexicographic order.
// Successive numbers differ in at most three digits.
{
public:
    ulong n_;   // Number of digits (n kinds of elements in multiset)
    ulong tr_;  // aux: current track
    ulong *a_;  // digits of mixed radix number (multiplicity of kind k in subset).
    ulong *m1_; // nines (radix minus one) for each digit (multiplicity of kind k in set).

public:
    mixedradix_subset_lex(ulong n, ulong mm, const ulong *m=0)
    {
        n_ = n;
        a_ = new ulong[n_+2];  // two sentinels, one left, and one right
        a_[0] = 1;  a_[n_+1] = 1;
        ++a_;  // not bene
        m1_ = new ulong[n_];
        mixedradix_init(n_, mm, m, m1_);
        first();
    }

    ~mixedradix_subset_lex()
    {
        --a_;
        delete [] a_;
        delete [] m1_;
    }

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


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

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

    bool next()
    // Generate next.
    // Return false if current was last.
    {
        ulong j = tr_;
        if ( a_[j] < m1_[j] )  // easy case
        {
            ++a_[j];
            return true;
        }
        else
        {
            // here a_[j] == m1_[j]
            if ( j+1 < n_ )  // semi-easy case: move track to the right
            {
                ++j;
                a_[j] = 1;
                tr_ = j;
                return true;
            }

            a_[j] = 0;

            // find first nonzero digit to the left:
            --j;
            while ( a_[j] == 0 )  { --j; } // may read sentinel a_[-1]

            if ( (long)j < 0 )  return false;  // current is last

            --a_[j];  // decrement digit to the left
            ++j;
            a_[j] = 1;
            tr_ = j;
            return true;
        }
    }

    bool prev()
    // Generate previous.
    // Return false if current was first.
    // Loopless algorithm.
    {
        ulong j = tr_;
        if ( a_[j] > 1 )  // easy case
        {
            --a_[j];
            return true;
        }
        else
        {
            if ( tr_ == 0 )
            {
                if ( a_[0] == 0 )  return false;  // current is first
                a_[0] = 0;  // now word is first (all zero)
                return true;
            }

            a_[j] = 0;

            --j;  // now looking at next track to the left
            if ( a_[j] == m1_[j] )  // semi-easy case: move track to left
            {
                tr_ = j;  // move track one left
            }
            else
            {
                ++a_[j];  // increment digit to the left
                j = n_ - 1;
                a_[j] = m1_[j];  // set far right digit = nine
                tr_ = j;  // move track to far right
            }
            return true;
        }
    }

    void print(const char *bla, bool dfz=false)  const
    // If dfz is true then Dots are printed For Zeros.
    { ::print_mixedradix(bla, a_, n_, dfz); }

    void print_nines(const char *bla)  const
    { ::print_mixedradix(bla, m1_, n_, false); }
};
// -------------------------


#endif  // !defined HAVE_MIXEDRADIX_SUBSET_LEX_H__