Support.hpp

// Copyright 2021 Arnaud Becheler    <abechele@umich.edu>
 
/*********************************************************************** * This program is free software; you can
 *redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free
 *Software Foundation; either version 2 of the License, or    * (at your option) any later version. *
 *                                                                      *
 ***************************************************************************/
 
#ifndef __OCCUPANCY_SPECTRUM_SUPPORT_H_INCLUDED__
#define __OCCUPANCY_SPECTRUM_SUPPORT_H_INCLUDED__
 
#include "OccupancySpectrum.hpp"
 
#include <utility>
#include <vector>
 
namespace quetzal
{
namespace coalescence
{
namespace occupancy_spectrum
{
class Support
{
  public:
    Support(int n, int m) : initial_n(n), initial_m(m)
    {
        std::cout << n << " " << m << std::endl;
    }
    using occupancy_spectrum_type = OccupancySpectrum;
    template <class UnaryOperation> void generate(UnaryOperation op) const
    {
        std::vector<int> M_j(this->initial_n + 1);
        f(this->initial_n, this->initial_m, this->initial_n, M_j, op);
    }
 
  private:
    int initial_n;
    int initial_m;
    template <class Callback> void f(int n, int m, int j_max, std::vector<int> &v, Callback callback) const
    {
        if (m == 0 && n == 0)
        {
            // problem solved
            callback(OccupancySpectrum(std::move(v), this->initial_n, this->initial_m));
            return;
        }
        if (m != 0)
        {
            if (n == 0)
            {
                auto copy = v;
                copy[0] = m; // here n = 0 et m = 0, so problem is solved
                callback(OccupancySpectrum(std::move(copy), this->initial_n, this->initial_m));
                return;
            }
            else
            {
                if (j_max > 0)
                {
                    // vertical descent
                    for (int i = n / j_max; i >= 1; --i)
                    {
                        auto copy = v;
                        copy[j_max] = i;
                        if (m >= i)
                        {
                            int balls_left = n - i * j_max;
                            if (balls_left < j_max)
                            {
                                f(balls_left, m - i, balls_left, copy, callback);
                            }
                            else
                            {
                                f(balls_left, m - i, j_max - 1, copy, callback);
                            }
                        }
                    }
                }
            }
        }
        // horizontal descent
        if (j_max == 0 && n > 0)
        {
            // not solvable
            return;
        }
        auto copy = v;
        copy[j_max] = 0;
        f(n, m, j_max - 1, copy, callback);
    }
}; // end class Support
} // namespace occupancy_spectrum
} // namespace coalescence
} // namespace quetzal
 
#endif