#if !defined HAVE_PARTITION_H__
#define      HAVE_PARTITION_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"

class partition
// Integer partitions
{
public:
    ulong *c_;  // partition:  c[1]* 1 + c[2]* 2 + ... + c[n]* n == n
    ulong *s_;  // cumulative sums:  s[j+1] = c[1]* 1 + c[2]* 2 + ... + c[j]* j
    ulong n_;   // partitions of n

public:
    partition(ulong n)
    {
        n_ = n;
        c_ = new ulong[n+1];
        s_ = new ulong[n+1];
        s_[0] = 0;  // unused
        c_[0] = 0;  // unused
        first();
    }

    ~partition()
    {
        delete [] c_;
        delete [] s_;
    }

    void first()
    {
        c_[1] = n_;
        for (ulong i=2; i<=n_; i++)  { c_[i] = 0; }
        if ( n_==0 )  c_[0] = 1;  // make things work for n==0
        s_[1] = 0;
        for (ulong i=2; i<=n_; i++)  { s_[i] = n_; }
    }

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

    const ulong * data()  const  { return c_; }  // one-based!

    bool next()
    {
        // This algorithm was given by Torsten Finke

        if ( c_[n_]!=0 )  return false;  // last == 1* n (c[n]==1)

        // Find first coefficient c[i], i>=2 that can be increased:
        ulong i = 2;
        while ( s_[i]<i )  ++i;

        ++c_[i];
        s_[i] -= i;
        ulong z = s_[i];
        // Now set c[1], c[2], ..., c[i-1] to the first partition
        // of z into i-1 parts, i.e. set to  z, 0, 0, ..., 0:
        while ( --i > 1 )
        {
            s_[i] = z;
            c_[i] = 0;
        }
        c_[1] = z;  // z* 1 == z
        // s_[1] unused

        return true;
    }


    bool prev()
    {
        if ( c_[1]==n_ )  return false;  // first == n* 1 (c[1]==n)

        // Find first nonzero coefficient c[i] where i>=2:
        ulong i = 2;
        while ( c_[i]==0 )  ++i;

        --c_[i];
        s_[i] += i;
        ulong z = s_[i];
        // Now set c[1], c[2], ..., c[i-1] to the last partition
        // of z into i-1 parts:
        while ( --i > 1  )
        {
//            ulong q = z/i;
            ulong q = (z>=i ? z/i : 0); // == z/i; (optimized)
            c_[i] = q;
            s_[i+1] = z;
            z -= q*i;
        }
        c_[1] = z;
        s_[2] = z;
        // s_[1] unused

        return true;
    }

    ulong num_parts()  const
    {
        ulong ct = 0;
        for (ulong k=1; k<=n_; ++k)  ct += c_[k];
        return ct;
    }

    ulong num_sorts()  const
    {
        ulong ct = 0;
        for (ulong k=1; k<=n_; ++k)  ct += ( c_[k] != 0 );
        return ct;
    }

    ulong num_of(ulong m)  const
    {
        return  c_[m];
    }

    bool OK()  const
    {
        ulong z = 0;
        for (ulong k=1; k<=n_; ++k)  z += k*c_[k];
        if ( z!=n_ )  return false;

        for (ulong k=0; k<n_; ++k)
            if ( s_[k+1] - s_[k] != k*c_[k] )  return false;

        return  true;
    }

    void print()  const;
    void print_long()  const;
};
// -------------------------

#endif  // !defined HAVE_PARTITION_H__