#if !defined  HAVE_MSET_PERM_LEX_H__
#define       HAVE_MSET_PERM_LEX_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 "aux0/swap.h"
#include "fxttypes.h"


class mset_perm_lex
// Multiset permutations in lexicographic order, iterative algorithm.
{
public:
    ulong k_;    // number of different sorts of objects
    ulong *r_;   // number of elements '0' in r[0], '1' in r[1], ..., 'k-1' in r[k-1]
    ulong n_;    // number of objects
    ulong *ms_;  // multiset data in ms[0], ..., ms[n-1], sentinel at [-1]

public:
    mset_perm_lex(const ulong *r, ulong k)
    {
        k_ = k;
        r_ = new ulong[k];
        for (ulong j=0; j<k_; ++j)  r_[j] = r[j];  // get buckets

        n_ = 0;
        for (ulong j=0; j<k_; ++j)  n_ += r_[j];
        ms_ = new ulong[n_+1];
        ms_[0] = 0;  // sentinel
        ++ms_;  // nota bene

        first();
    }

    void first()
    {
        for (ulong j=0, i=0;  j<k_;  ++j)
            for (ulong h=r_[j];  h!=0;  --h, ++i)  ms_[i] = j;
    }

    ~mset_perm_lex()
    {
        --ms_;
        delete [] ms_;
        delete [] r_;
    }

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

    bool next()
    {
        // find rightmost pair with ms[i] < ms[i+1]:
        const ulong n1 = n_ - 1;
        ulong i = n1;
        do  { --i; }  while ( ms_[i] >= ms_[i+1] );  // can touch sentinel
        if ( (long)i<0 )  return false;  // last sequence is falling seq.

        // find rightmost element p[j] less than p[i]:
        ulong j = n1;
        while ( ms_[i] >= ms_[j] )  { --j; }

        swap2(ms_[i], ms_[j]);

        // Here the elements ms[i+1], ..., ms[n-1] are a falling sequence.
        // Reverse order to the right:
        ulong r = n1;
        ulong s = i + 1;
        while ( r > s )  { swap2(ms_[r], ms_[s]);  --r;  ++s; }

        return true;
    }
};
// -------------------------


#endif  // !defined HAVE_MSET_PERM_LEX_H__