algorithm.hpp

#ifndef SIPLASPLAS_CONSTEXPR_ALGORITHM_HPP
#define SIPLASPLAS_CONSTEXPR_ALGORITHM_HPP

#include <cstdint>
#include <type_traits>

namespace cpp
{

namespace constexp
{

struct Equal
{
    constexpr Equal() = default;

    template<typename T, typename U>
    constexpr bool operator()(const T& lhs, const U& rhs) const
    {
        return lhs == rhs;
    }
};

struct NotEqual
{
    constexpr NotEqual() = default;

    template<typename T, typename U>
    constexpr bool operator()(const T& lhs, const U& rhs) const
    {
        return lhs != rhs;
    }
};

template<typename Sequence>
constexpr auto begin(const Sequence& sequence)
{
    return sequence.begin();
}

template<typename T, std::size_t N>
constexpr auto begin(const T (&array)[N])
{
    return &array[0];
}

template<typename Sequence>
constexpr auto end(const Sequence& sequence)
{
    return sequence.end();
}

template<typename T, std::size_t N>
constexpr auto end(const T (&array)[N])
{
    return &array[N];
}

template<typename Begin, typename End>
constexpr auto distance(Begin begin, End end)
{
    return end - begin;
}

template<
    typename Begin1, typename End1,
    typename Begin2, typename End2,
    typename Compare
>
constexpr bool equal(
    Begin1 begin1, End1 end1,
    Begin2 begin2, End2 end2,
    Compare compare
)
{
    return (begin1 == end1 || begin2 == end2) ?
        ((::cpp::constexp::distance(begin1, end1) !=
          ::cpp::constexp::distance(begin2, end2)) ?
            false
        :
            true
        )
    :
        compare(*begin1++, *begin2++) &&
        ::cpp::constexp::equal(begin1, end1, begin2, end2, compare);
}

template<
    typename Begin1, typename End1,
    typename Begin2, typename End2
>
constexpr bool equal(
    Begin1 begin1, End1 end1,
    Begin2 begin2, End2 end2
)
{
    return equal(
        begin1, end1,
        begin2, end2,
        ::cpp::constexp::Equal()
    );
}

template<typename Lhs, typename Rhs>
constexpr bool equal(const Lhs& lhs, const Rhs& rhs)
{
    return ::cpp::constexp::equal(
        ::cpp::constexp::begin(lhs), ::cpp::constexp::end(lhs),
        ::cpp::constexp::begin(rhs), ::cpp::constexp::end(rhs)
    );
}

template<typename T>
constexpr const T& max(const T& lhs, const T& rhs)
{
    return lhs >= rhs ?
        lhs
    :
        rhs;
}

template<typename T, typename U>
constexpr std::common_type_t<T, U> max(const T& lhs, const U& rhs)
{
    return static_cast<std::common_type_t<T, U>>(lhs) >=
           static_cast<std::common_type_t<T, U>>(rhs) ?
        lhs
    :
        rhs;
}

template<typename First, typename Second, typename Third, typename... Tail>
constexpr decltype(auto) max(const First& first, const Second& second, const Third& third,
                   const Tail&... tail)
{
    return ::cpp::constexp::max(
        first,
        ::cpp::constexp::max(
            second,
            third,
            tail...
        )
    );
}



template<typename T>
constexpr const T& min(const T& lhs, const T& rhs)
{
    return lhs <= rhs ?
        lhs
    :
        rhs;
}

template<typename T, typename U>
constexpr std::common_type_t<T, U> min(const T& lhs, const U& rhs)
{
    // The cast is needed to prevemt signed vs unsigned comparison
    // warnings
    return static_cast<std::common_type_t<T, U>>(lhs) <=
           static_cast<std::common_type_t<T, U>>(rhs) ?
        lhs
    :
        rhs;
}

template<typename First, typename Second, typename Third, typename... Tail>
constexpr decltype(auto) min(const First& first, const Second& second, const Third& third,
                   const Tail&... tail)
{
    return ::cpp::constexp::min(
        first,
        ::cpp::constexp::min(
            second,
            third,
            tail...
        )
    );
}


template<
    typename Begin1, typename End1,
    typename Begin2, typename End2
>
constexpr std::size_t levenshteinDistance(
    Begin1 begin1, End1 end1,
    Begin2 begin2, End2 end2
)
{
    return (begin1 >= end1) ?
        ::cpp::constexp::distance(begin2, end2)
    :(
           (begin2 >= end2) ?
        ::cpp::constexp::distance(begin1, end1)
    :(
        ::cpp::constexp::min(
            ::cpp::constexp::levenshteinDistance(begin1 + 1, end1, begin2, end2) + 1,
            ::cpp::constexp::levenshteinDistance(begin1, end1, begin2 + 1, end2) + 1,
            ::cpp::constexp::levenshteinDistance(begin1 + 1, end1, begin2 + 1, end2) +
            ((*begin1 == *begin2) ? 0 : 1)
        )
    ));
}

template<typename Lhs, typename Rhs>
constexpr std::size_t levenshteinDistance(const Lhs& lhs, const Rhs& rhs)
{
    return ::cpp::constexp::levenshteinDistance(
        ::cpp::constexp::begin(lhs),
        ::cpp::constexp::end(lhs),
        ::cpp::constexp::begin(rhs),
        ::cpp::constexp::end(rhs)
    );
}

template<typename Iterator, typename T>
constexpr Iterator find(Iterator begin, Iterator end, const T& value)
{
    return (begin == end) ? end :
        (*begin == value) ? begin :
        find(begin + 1, end, value);
}

#ifndef SIPLASPLAS_CONSTEXPR_ALGORITHM_MAX_STRLEN_LENGTH

    constexpr std::size_t MAX_STRLEN_LENGTH = 1024 * 1024;
#else

    constexpr std::size_t MAX_STRLEN_LENGTH = SIPLASPLAS_CONSTEXPR_ALGORITHM_MAX_STRLEN_LENGTH;
#endif // SIPLASPLAS_CONSTEXPR_ALGORITHM_MAX_STRLEN_LENGTH

constexpr std::size_t strlen(const char* str)
{
    return ::cpp::constexp::distance(
        str,
        ::cpp::constexp::find(str, str + ::cpp::constexp::MAX_STRLEN_LENGTH, '\0')
    );
}

}

}

#endif // SIPLASPLAS_CONSTEXPR_ALGORITHM_HPP