#pragma once

#include <cstddef>

namespace sd
{
namespace setcover
{

template <typename U>
struct setcover_trait;

struct DefaultSetMinus
{
    template <typename To_Cover, typename Set>
    constexpr void operator()(To_Cover& to_cover, const Set& set) const noexcept
    {
        setcover_trait<To_Cover>::set_minus(to_cover, set);
    }
};

struct DefaultWeightFunction
{
    template <typename Set, typename To_Cover>
    constexpr size_t operator()(size_t, const Set& set, const To_Cover& to_cover) const noexcept
    {
        const auto c = setcover_trait<To_Cover>::size_of_intersection(set, to_cover);
        return (c != setcover_trait<To_Cover>::count(set) ? decltype(c)(0) : c);
    }
};

struct WeakWeightFunction
{
    template <typename Set, typename To_Cover>
    constexpr size_t operator()(size_t, const Set& set, const To_Cover& to_cover) const noexcept
    {
        return setcover_trait<To_Cover>::size_of_intersection(set, to_cover);
    }
};

// struct SetcoverSettings
// {
//     size_t budget_limit = 1'000'000;
//     double min_gain     = -1.0;
// };

// template <typename Sets, typename Set>
// bool has_converged(const SetcoverSettings& settings,
//                    const size_t            num_used_sets,
//                    const double            ,
//                    const Sets&             sets,
//                    const Set&              tocover)
// {

//     if (num_used_sets >= sets.size()) return true;
//     // if (num_used_sets >= settings.budget_limit) return true;
//     // if (value < settings.min_gain /* * (sets.size() - num_used_sets)*/) return true;
//     if (tocover.empty()) return true;
//     return false;
// }

template <typename T>
struct GreedySetcoverResult
{
    size_t index;
    T      value;
};

template <typename Set, typename Sets, typename Weight_Function>
auto select_next_set(const Sets& sets, const Set& y, const Weight_Function& weight_function)
{
    using value_type = std::decay_t<decltype(weight_function(0, sets[0], y))>;

    GreedySetcoverResult<value_type> r = {sets.size() + 1, 0};
    for (size_t i = 0, n = sets.size(); i < n; i++) {
        auto cur = weight_function(i, sets[i], y);
        if (cur > 0 && r.value <= cur) {
            r = {i, cur};
            if (r.value == std::numeric_limits<value_type>::max()) {
                return r;
            }
        }
    }
    return r;
}

template <typename Sets,
          typename Set,
          typename Visitor_Type,
          typename Weight_Function   = DefaultWeightFunction,
          typename Setminus_Function = DefaultSetMinus>
void greedy_set_cover(const Sets&            sets,
                      Set&                   tocover,
                      Visitor_Type&&         visit,
                      const Weight_Function& weight_function = {},
                      Setminus_Function      set_minus       = {})
{
    if (sets.empty()) return;

    for (size_t count = 0;;) {
        auto selected = select_next_set(sets, tocover, weight_function);
        if (selected.index >= sets.size()) break;

        visit(selected.index);

        set_minus(tocover, sets[selected.index]);

        count++;

        if(count >= sets.size() || tocover.empty()) break;
    }
}

template <typename Sets,
          typename Set,
          typename Visitor_Type,
          typename Weight_Function   = DefaultWeightFunction,
          typename Setminus_Function = DefaultSetMinus>
void greedy_set_cover_by_value(const Sets&            sets,
                               Set                    tocover,
                               Visitor_Type&&         visit,
                               const Weight_Function& weight_function = {},
                               Setminus_Function      set_minus       = {})
{
    greedy_set_cover(sets,
                     tocover,
                     std::forward<Visitor_Type>(visit),
                     weight_function,
                     std::move(set_minus));
}

template <typename Set, typename Sets, typename Weight_Function, typename Bit_set>
auto select_next_set(const Sets&            sets,
                     const Set&             y,
                     const Weight_Function& weight_function,
                     Bit_set&               ignore)
{
    using value_type = std::decay_t<decltype(weight_function(0, sets[0], y))>;

    GreedySetcoverResult<value_type> r = {sets.size() + 1, 0};
    for (size_t i = 0, n = sets.size(); i < n; i++) {
        if (ignore.contains(i)) continue;

        auto cur = weight_function(i, sets[i], y);
        if (cur > 0 && r.value <= cur) {
            r = {i, cur};
            if (r.value == std::numeric_limits<value_type>::max()) {
                return r;
            }
        }
    }
    return r;
}

struct NoSetminus
{
    template <typename Set, typename To_Cover>
    constexpr void operator()(const To_Cover&, const Set&) const noexcept
    {
    }
};

template <typename Bit_set,
          typename Sets,
          typename Set,
          typename Visitor_Type,
          typename Weight_Function   = DefaultWeightFunction,
          typename Setminus_Function = DefaultSetMinus>
void greedy_set_cover(Bit_set&               ignore,
                      const Sets&            sets,
                      Set&                   tocover,
                      Visitor_Type&&         visit,
                      const Weight_Function& weight_function = {},
                      Setminus_Function      set_minus       = {})
{
    // assert(ignore.length() >= sets.size());

    ignore.assign(sets.size(), false);

    if (sets.empty()) return;

    for (size_t count = 0;;) {
        auto selected = select_next_set(sets, tocover, weight_function, ignore);
        if (selected.index >= sets.size()) break;

        ignore.insert(selected.index);

        visit(selected.index);

        set_minus(tocover, sets[selected.index]);

        ++count;

        if(count >= sets.size() || tocover.empty()) break;
    }
}

} // namespace setcover
} // namespace sd
