include/tudocomp/util.hpp

Go to the documentation of this file.

#pragma once

#include <memory>
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <fstream>
#include <iostream>
#include <memory>
#include <sstream>
#include <string>
#include <type_traits>
#include <utility>
#include <iomanip>

#include <tudocomp/util/View.hpp>

namespace tdc {

template<class T>
struct char_as_uint_trait {
    static inline uint64_t conv(const T& t) { return t; }
};
template<>
struct char_as_uint_trait<char> {
    static inline uint64_t conv(const char& t) { return uint8_t(t); }
};

template<class T>
inline uint64_t char_as_uint(const T& t) {
    return char_as_uint_trait<T>::conv(t);
}

template<class T>
std::string vec_to_debug_string(const T& s, size_t indent = 0) {
    std::stringstream ss;
    ss << "[";
    if (s.size() > 0) {
        for (size_t i = 0; i < s.size() - 1; i++) {
            // crazy cast needed to bring negative char values
            // into their representation as a unsigned one
            ss << std::setw(indent) << uint((unsigned char) s[i]) << ", ";
        }
        ss << std::setw(indent) << uint((unsigned char) s[s.size() - 1]);
    }
    ss << "]";
    return ss.str();
}

template<class T>
std::string arr_to_debug_string(const T* s, size_t length) {
    if(length == 0) return "[]";
    std::stringstream ss;
    ss << "[";
    for (size_t i = 0; i < length - 1; ++i) {
        ss << s[i] << ", ";
    }
    ss << s[length - 1];
    ss << "]";
    return ss.str();
}

inline std::string byte_to_nice_ascii_char(uint64_t byte) {
    std::stringstream out;
    if (byte >= 32 && byte <= 127) {
        out << "'" << char(byte) << "'";
    } else {
        out << byte;
    }
    return out.str();
}

template<class T>
std::string vec_as_lossy_string(const T& s, size_t start = 0,
                                char replacement = '?') {
    std::stringstream ss;
    for (size_t i = start; i < s.size(); i++) {
        if (s[i] < 32 || s[i] > 127) {
            ss << replacement;
        } else {
            ss << char(s[i]);
        }
    }
    return ss.str();
}

template<typename T>
inline std::string to_str(const T& v) {
    std::stringstream ss;
    ss << v;
    return ss.str();
}

inline void debug_print_uint64_t(uint64_t v) {
    for(int i = 0; i < 64; i++) {
        if (i > 0 && i % 8 == 0) {
            std::cout << " ";
        }
        std::cout << int((v >> (63 - i)) & 1);
    }
    std::cout << "\n";
}

inline bool parse_number_until_other(std::istream& inp, char& last, size_t& out) {
    size_t n = 0;
    char c;
    bool more = true;
    while ((more = bool(inp.get(c)))) {
        if (c >= '0' && c <= '9') {
            n *= 10;
            n += (c - '0');
        } else {
            last = c;
            break;
        }
    }
    out = n;
    return more;
}

inline constexpr uint_fast8_t bits_hi(uint64_t x) {
    return x == 0 ? 0 : 64 - __builtin_clzll(x);
}

inline constexpr uint_fast8_t bits_for(size_t n) {
    return n == 0 ? 1U : bits_hi(n);
}

inline constexpr size_t idiv_ceil(size_t a, size_t b) {
    return (a / b) + ((a % b) > 0);
}

inline constexpr uint_fast8_t bytes_for(size_t n) {
    return idiv_ceil(bits_for(n), 8U);
}

template<typename int_t> struct msbf;

template<> struct msbf<uint8_t>  {
    static constexpr uint8_t pos = 7;
};
template<> struct msbf<uint16_t> {
    static constexpr uint8_t pos = 15;
};
template<> struct msbf<uint32_t> {
    static constexpr uint8_t pos = 31;
};
template<> struct msbf<uint64_t> {
    static constexpr uint8_t pos = 63;
};

template<class T>
std::vector<T> cross(std::vector<std::vector<T>>&& vs,
                     std::function<T(T, T&)> f) {
    auto remaining = vs;
    if (remaining.size() == 0) {
        return {};
    }

    std::vector<T> first = std::move(remaining[0]);
    remaining.erase(remaining.begin());

    auto next = cross(std::move(remaining), f);

    if (next.size() == 0) {
        return first;
    } else {
        std::vector<T> r;
        for (auto& x : first) {
            for (auto& y : next) {
                r.push_back(f(x, y));
            }
        }
        return r;
    }
}

inline std::vector<std::string> split_lines(const std::string& s) {
    std::stringstream ss(s);
    std::string to;
    std::vector<std::string> ret;

    while(std::getline(ss,to,'\n')) {
        ret.push_back(to);
    }

    return ret;
}

inline std::string indent_lines(const std::string& s, size_t indent) {
    std::stringstream ss(s);
    std::string to;
    std::stringstream ret;

    bool first = true;
    while(std::getline(ss,to,'\n')){
        if (!first) {
            ret << "\n";
        }
        ret << std::setw(indent) << "" << to;
        first = false;
    }

    return ret.str();
}

inline std::string make_table(const std::vector<std::string>& data,
                              size_t cols,
                              bool draw_grid = true) {
    std::vector<size_t> widths;
    std::vector<size_t> heights;
    std::vector<std::vector<std::string>> data_lines;

    // Gather inidividual cell dimensions
    for (auto& elem : data) {
        size_t w = 0;
        size_t h = 0;

        data_lines.push_back(split_lines(elem));
        auto& lines = data_lines[data_lines.size() - 1];

        for (auto& line : lines) {
            w = std::max(w, line.size());
        }

        h = lines.size();


        widths.push_back(w);
        heights.push_back(h);
    }

    std::vector<size_t> col_widths(cols, 0);
    std::vector<size_t> row_heights(data.size() / cols, 0);

    // Calculate max. common row/column dimensions
    for (size_t i = 0; i < data.size(); i++) {
        size_t x = i % cols;
        size_t y = i / cols;

        col_widths[x] = std::max(col_widths[x], widths[i]);
        row_heights[y] = std::max(row_heights[y], heights[i]);
    }

    // Adjust lines to match
    for (size_t i = 0; i < data.size(); i++) {
        size_t x = i % cols;
        size_t y = i / cols;

        while (data_lines[i].size() < row_heights[y]) {
            data_lines[i].push_back("");
        }

        for (auto& line : data_lines[i]) {
            size_t pad = col_widths[x] - line.size();
            line.append(pad, ' ');
        }
    }

    std::stringstream ret;

    // Create formatted table

    const char ROW = '-';
    const std::string COL = " | ";

    size_t total_width = 1;
    for (size_t i = 0; i < col_widths.size(); i++) {
        total_width += col_widths[i] + 3;
    }

    if (draw_grid) {
        ret << std::string(total_width, ROW) << "\n";
    }

    for (size_t y = 0; y < data.size() / cols; y++) {
        for (size_t line_i = 0; line_i < row_heights[y]; line_i++ ) {
            for (size_t x = 0; x < cols; x++) {
                if (draw_grid && x == 0) {
                    ret << COL.substr(1);
                }
                if (draw_grid && x != 0) {
                    ret << COL;
                }
                ret << data_lines[x + y * cols][line_i];
                if (draw_grid && x == cols - 1) {
                    ret << COL.substr(0, 2);
                }
            }
            ret << "\n";
        }
        if (draw_grid) {
            ret << std::string(total_width, ROW) << "\n";
        }
    }

    return ret.str();
}

#if defined(DEBUG) && defined(PARANOID) //functions that cost more than constant time to check
template<class T>
void assert_permutation(const T& p, size_t n) {
    for(size_t i = 0; i < n; ++i)
    for(size_t j = 0; j < n; ++j)
    {
        if(i == j) continue;
        DCHECK_NE(p[i],p[j]) << "at positions " << i << " and " << j;
        DCHECK_LT(p[i],n);
    }
}
template<class T>
void assert_permutation_offset(const T& p, size_t n,size_t offset) {
    for(size_t i = 0; i < n; ++i)
    for(size_t j = 0; j < n; ++j)
    {
        if(i == j) continue;
        DCHECK_NE(p[i],p[j]) << "at positions " << i << " and " << j;
        DCHECK_GE(p[i],offset);
        DCHECK_LT(p[i],offset+n);
    }
}
#else
template<class T> inline void assert_permutation(const T&, size_t) {}
template<class T> inline void assert_permutation_offset(const T&, size_t,size_t) {}
#endif


template<class T>
constexpr T round_up_div(T x, T y) {
    return (x + y -1)/y;
}

/*
 *  Square root by abacus algorithm, Martin Guy @ UKC, June 1985.
 *  From a book on programming abaci by Mr C. Woo.
 *  and from https://en.wikipedia.org/wiki/Methods_of_computing_square_roots
 */
template<class int_t>
int_t isqrt(int_t num) {
    int_t res = 0;
    int_t bit = 1ULL << (sizeof(int_t)-2); // The second-to-top bit is set: 1 << 30 for 32 bits

    // "bit" starts at the highest power of four <= the argument.
    while (bit > num)
        bit >>= 2;

    while (bit != 0) {
        if (num >= res + bit) {
            num -= res + bit;
            res = (res >> 1) + bit;
        }
        else
            res >>= 1;
        bit >>= 2;
    }
    return res;
}

static inline size_t lz78_expected_number_of_remaining_elements(const size_t z, const size_t n, const size_t remaining_characters) {
        if(remaining_characters*2 < n ) {
            return (z*remaining_characters) / (n - remaining_characters);
        }
    return remaining_characters*3/(bits_for(remaining_characters));
}

class MoveGuard {
    bool m_is_not_moved;
public:
    inline MoveGuard(): m_is_not_moved(true) {}
    inline MoveGuard(const MoveGuard& other) {
        DCHECK(other.m_is_not_moved) << "Trying to copy a already moved-from MoveGuard";
        m_is_not_moved = other.m_is_not_moved;
    }
    inline MoveGuard(MoveGuard&& other) {
        DCHECK(other.m_is_not_moved) << "Trying to move a already moved-from MoveGuard";
        m_is_not_moved = other.m_is_not_moved;
        other.m_is_not_moved = false;
    }

    inline bool is_not_moved() const {
        return m_is_not_moved;
    }
    inline bool is_moved() const {
        return !m_is_not_moved;
    }
    inline operator bool() const {
        return is_not_moved();
    }
    inline bool operator!() const {
        return is_moved();
    }
};

namespace portable_arithmetic_shift {
    // Source: https://gist.github.com/palotasb/de46414a93ba90fff22bdbd2327ae393

    template <typename T>
    constexpr auto builtin_shr(T value, int amount) noexcept
        -> decltype(value >> amount)
    {
        return value >> amount;
    }

    template <typename T>
    struct uses_arithmetic_shift : std::integral_constant<bool, builtin_shr(T(-1), 1) == -1> {};

    template <typename T = int>
    constexpr T shift_by_portable(T value, int amount) noexcept
    {
        return value < 0 ?
        amount < 0 ? ~(~value >> -amount) : -(-value << amount) :
        amount < 0 ? value >> -amount : value << amount;
    }

    template <typename T = int>
    constexpr T shift_by_arithmetic(T value, int amount) noexcept
    {
        // Only use with negative T values when the compiler translates right shift to arithmetic shift instructions.
        return amount < 0 ? value >> -amount : value << amount;
    }
}

template <typename T = int>
constexpr T shift_by(T value, int amount) noexcept
{
    using namespace portable_arithmetic_shift;

    return uses_arithmetic_shift<T>::value ? shift_by_arithmetic(value, amount) : shift_by_portable(value, amount);
}

inline uint64_t zero_or_next_power_of_two(uint64_t x) {
    --x;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;

    return x + 1;
}

}//ns