combine_to_factor.hpp

Go to the documentation of this file.

#ifndef FACTORIZE_COMBINE_TO_FACTOR_HPP
#define FACTORIZE_COMBINE_TO_FACTOR_HPP
 
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <cstddef>
 
#include "sanisizer/sanisizer.hpp"
 
#include "create_factor.hpp"
#include "utils.hpp"
 
namespace factorize {
 
template<typename Input_, typename Code_>
std::vector<std::vector<Input_> > combine_to_factor(const std::size_t n, const std::vector<const Input_*>& inputs, Code_* const codes) {
    const auto ninputs = inputs.size();
    auto output = sanisizer::create<std::vector<std::vector<Input_> > >(ninputs);
 
    // Handling the special cases.
    if (ninputs == 0) {
        std::fill_n(codes, n, 0);
        return output;
    }
    if (ninputs == 1) {
        output[0] = create_factor(n, inputs.front(), codes);
        return output;
    }
 
    // Creating a hashmap on the combinations of each factor.
    struct Combination {
        Combination(const std::size_t i) : index(i) {}
        std::size_t index;
    };
 
    auto unique = [&]{ // scoping this in an IIFE to release map memory sooner.
        // Using a map with a custom comparator that uses the index
        // of first occurrence of each factor as the key. Currently using a map
        // to (i) avoid issues with collisions of combined hashes and (ii)
        // avoid having to write more code for sorting a vector of arrays.
        auto cmp = [&](const Combination& left, const Combination& right) -> bool {
            for (auto curf : inputs) {
                if (curf[left.index] < curf[right.index]) {
                    return true;
                } else if (curf[left.index] > curf[right.index]) {
                    return false;
                }
            }
            return false;
        };
        std::map<Combination, Code_, I<decltype(cmp)> > mapping(std::move(cmp));
 
        const auto eq = [&](const Combination& left, const Combination& right) -> bool {
            for (auto curf : inputs) {
                if (curf[left.index] != curf[right.index]) {
                    return false;
                }
            }
            return true;
        };
 
        for (I<decltype(n)> i = 0; i < n; ++i) {
            Combination current(i);
            const auto mIt = mapping.find(current);
            if (mIt == mapping.end() || !eq(mIt->first, current)) {
                Code_ alt = mapping.size();
                mapping.insert(mIt, std::make_pair(current, alt));
                codes[i] = alt;
            } else {
                codes[i] = mIt->second;
            }
        }
 
        return std::vector<std::pair<Combination, Code_> >(mapping.begin(), mapping.end());
    }();
 
    // Remapping to a sorted set.
    const auto nuniq = unique.size();
    for (auto& ofac : output) {
        ofac.reserve(nuniq);
    }
    auto remapping = sanisizer::create<std::vector<Code_> >(nuniq);
    for (I<decltype(nuniq)> u = 0; u < nuniq; ++u) {
        const auto ix = unique[u].first.index;
        for (I<decltype(ninputs)> f = 0; f < ninputs; ++f) {
            output[f].push_back(inputs[f][ix]);
        }
        remapping[unique[u].second] = u;
    }
 
    // Mapping each cell to its sorted combination.
    for (I<decltype(n)> i = 0; i < n; ++i) {
        codes[i] = remapping[codes[i]];
    }
 
    return output;
}
 
template<typename Input_, typename Number_, typename Code_>
std::vector<std::vector<Input_> > combine_to_factor_unused(const std::size_t n, const std::vector<std::pair<const Input_*, Number_> >& inputs, Code_* const codes) {
    const auto ninputs = inputs.size();
    auto output = sanisizer::create<std::vector<std::vector<Input_> > >(ninputs);
 
    // Handling the special cases.
    if (ninputs == 0) {
        std::fill_n(codes, n, 0);
        return output;
    }
    if (ninputs == 1) {
        sanisizer::resize(output[0], inputs[0].second);
        std::iota(output[0].begin(), output[0].end(), static_cast<Code_>(0));
        std::copy_n(inputs[0].first, n, codes);
        return output;
    }
 
    // We iterate from back to front, where the first factor is the slowest changing.
    std::copy_n(inputs[ninputs - 1].first, n, codes); 
    Code_ ncombos = inputs[ninputs - 1].second;
    for (I<decltype(ninputs)> f = ninputs - 1; f > 0; --f) {
        const auto& finfo = inputs[f - 1];
        const auto next_ncombos = sanisizer::product<Code_>(ncombos, finfo.second);
        const auto ff = finfo.first;
        for (I<decltype(n)> i = 0; i < n; ++i) {
            // Product is safe as it is obviously less than 'next_combos' for 'ff[i] < finfo.second'.
            // Addition is also safe as it will be less than 'next_combos', though this is less obvious.
            codes[i] += sanisizer::product_unsafe<Code_>(ncombos, ff[i]);
        }
        ncombos = next_ncombos;
    }
 
    sanisizer::cast<I<decltype(output[0].size())> >(ncombos); // check that we can actually make the output vectors.
    Code_ outer_repeats = ncombos;
    Code_ inner_repeats = 1;
    for (I<decltype(ninputs)> f = ninputs; f > 0; --f) {
        auto& out = output[f - 1];
        out.reserve(ncombos);
 
        const auto& finfo = inputs[f - 1];
        const Code_ initial_size = inner_repeats * finfo.second;
        out.resize(initial_size);
 
        if (inner_repeats == 1) {
            std::iota(out.begin(), out.end(), static_cast<Code_>(0));
        } else {
            auto oIt = out.begin();
            for (Number_ l = 0; l < finfo.second; ++l) {
                std::fill_n(oIt, inner_repeats, l);
                oIt += inner_repeats;
            }
        }
        inner_repeats = initial_size;
 
        outer_repeats /= finfo.second;
        for (Code_ r = 1; r < outer_repeats; ++r) {
            // Referencing to 'begin()' while inserting is safe, as we reserved the full length at the start.
            // Thus, there shouldn't be any allocations.
            out.insert(out.end(), out.begin(), out.begin() + initial_size);
        }
    }
 
    return output;
}
 
}
 
#endif