util.hpp

Go to the documentation of this file.

#pragma once
#include <limits>
#include <string>
#include <sstream>
#include <vector>
#include <Eigen/Core>

namespace creativity { namespace data {

std::string double_str(double d, unsigned precision = std::numeric_limits<double>::max_digits10);

template<typename RAIter, typename = typename std::enable_if<
    std::is_same<
        std::random_access_iterator_tag,
        typename std::iterator_traits<RAIter>::iterator_category
    >::value and
    std::is_arithmetic<typename std::iterator_traits<RAIter>::value_type>::value
>::type>
double quantile(RAIter begin, RAIter end, double prob) {
    if (prob < 0 or prob > 1) throw std::logic_error("Requested quantile probability is invalid");
    if (begin == end) return std::numeric_limits<double>::quiet_NaN();
    double index = prob * (std::distance(begin, end) - 1);
    unsigned below = std::floor(index), above = std::ceil(index);
    if (below == above) return begin[above];
    return (above - index) * begin[below] + (index - below) * begin[above];
}

double quantile(const std::vector<double> &vals, double prob);

double quantile(const Eigen::Ref<const Eigen::VectorXd> &vals, double prob);

double variance(const std::vector<double> &vals, double mean = std::numeric_limits<double>::quiet_NaN());

enum class OverlapReducer {
    None, 
    Prefix, 
    Suffix, 
    Equalize, 
    Disequalize 
};

template <typename InputIt>
typename std::enable_if<
    // InputIt must be an input iterator:
    std::is_base_of<std::input_iterator_tag, typename std::iterator_traits<InputIt>::iterator_category>::value
    and
    // The value_type of InputIt must itself be bidirectional-iterable
    std::is_base_of<
        std::bidirectional_iterator_tag,
        typename std::iterator_traits<typename InputIt::value_type::iterator>::iterator_category
    >::value,
    std::pair<size_t, size_t>
>::type
common_ends(InputIt it, InputIt last,
        bool prefix = true, bool suffix = true,
        OverlapReducer reducer = OverlapReducer::Disequalize) {
    if (it == last) return {0,0};
    const auto &ref_0 = *it;
    std::pair<size_t, size_t> common(0, 0);
    // Use the first element as our reference element, using its length as the initial
    // prefix/suffix values.
    auto shortest = std::distance(it->begin(), it->end());
    if (prefix) common.first = shortest;
    if (suffix) common.second = shortest;

    // Now, starting from the second element, check how much of the prefix/suffix matches
    for (it++; it != last and (common.first > 0 or common.second > 0); it++) {
        if (common.first > 0) {
            // Iterate from the beginning, and keep iterating as long as each element is equal along
            // the way
            auto ref_it = ref_0.begin();
            auto new_it = it->begin();
            // NB: don't need to check ref_it != ref_0.end() here (because the i < common.first will
            // ensure we can't go past the end).
            for (size_t i = 0; i < common.first and new_it != it->end(); i++, ref_it++, new_it++) {
                if (not (*new_it == *ref_it)) {
                    // We found two unequal elements at [i], so reduce the common prefix length to i
                    common.first = i;
                    break;
                }
            }
        }
        if (common.second > 0) {
            // Iterate backwards from the end
            auto ref_it = ref_0.rbegin();
            auto new_it = it->rbegin();
            for (size_t i = 0; i < common.second and new_it != it->rend(); i++, ref_it++, new_it++) {
                // We found two unequal elements at i from the end, so reduce the common suffix
                // length to i
                if (not (*new_it == *ref_it)) {
                    common.second = i;
                    break;
                }
            }
        }

        if (common.first > 0 and common.second > 0) {
            shortest = std::min(shortest, std::distance(it->begin(), it->end()));
        }
    }

    if (common.first + common.second > (size_t) shortest) {
        switch (reducer) {
            case OverlapReducer::None:
                break;
            case OverlapReducer::Prefix:
                common.first = shortest - common.second;
                break;
            case OverlapReducer::Suffix:
                common.second = shortest - common.first;
                break;
            case OverlapReducer::Equalize:
                while (common.first + common.second > (size_t) shortest) {
                    if (common.second >= common.first) common.second--;
                    else common.first--;
                }
                break;
            case OverlapReducer::Disequalize:
                if (common.second <= common.first) common.second = shortest - common.first;
                else common.first = shortest - common.second;
                break;
        }
    }

    return common;
}

}}