scalgorithm.hpp

#ifndef SIMPLE_CPLUSPLUS_ALGORITHM
#define SIMPLE_CPLUSPLUS_ALGORITHM
 
// cpp stl 
#include <type_traits>
#include <vector>
#include <functional>
#include <iterator>
#include <memory>
#include <algorithm>
 
namespace sca { // simple cpp algorithm
namespace detail {
 
// ----------------------------------------------------------------------------- 
// is_lvalue_ref_t
 
template <typename C>
using is_lvalue_ref_t = typename std::is_lvalue_reference<C>::type;
 
//------------------------------------------------------------------------------
// to_vector_t
 
// a `std::vector<T>` where `T` is the `::value_type` of a container `C`
template <typename C>
using to_vector_t = std::vector<typename std::decay_t<C>::value_type>;
 
// ----------------------------------------------------------------------------- 
// container_reference_value_t  
 
// acquire the ::value_type of a container<T> (normally T) as a reference (T&)
template <typename C>
using container_reference_value_t = typename std::decay_t<C>::value_type&;
 
// ----------------------------------------------------------------------------- 
// callable_return_t 
 
// handle pre and post c++17 
#if __cplusplus >= 201703L
template <typename F, typename... Ts>
using callable_return_t = typename std::invoke_result<std::decay_t<F>,Ts...>::type;
#else 
template <typename F, typename... Ts>
using callable_return_t = typename std::result_of<std::decay_t<F>(Ts...)>::type;
#endif 
 
// -----------------------------------------------------------------------------
// size  
 
template <typename T>
struct has_size_struct {
    typedef typename std::decay_t<T> BT; // remove any references from T
    template<typename U, typename U::size_type (U::*)() const> struct SFINAE {};
    template<typename U> static char test(SFINAE<U, &U::size>*);
    template<typename U> static int test(...);
    static const bool has = sizeof(test<BT>(0)) == sizeof(char);
};
 
template <typename T>
using has_size = std::integral_constant<bool, detail::has_size_struct<T>::has>;
 
// Get the size of an object with its `size()` method
template <typename C>
size_t size(C& c, std::true_type) { 
    return c.size(); 
}
 
// Get the size of an object the *slow* way by iterating through it
template <typename C>
size_t size(C& c, std::false_type) {
    return std::distance(c.begin(), c.end());
}
 
// ----------------------------------------------------------------------------- 
// transfer  
 
// Copy or move only one value
template <typename DEST, typename SRC>
void transfer(std::true_type, DEST& dst, SRC& src) {
    dst = src;
}
 
template <typename DEST, typename SRC>
void transfer(std::false_type, DEST& dst, SRC& src) {
    dst = std::move(src);
}
 
// ----------------------------------------------------------------------------- 
// range_transfer 
 
// Copy or move a range of data to another range of data. Don't use std::copy or 
// std::move algorithms to preserve the side effects of incrementing 
template <typename DIT, typename IT>
void range_transfer(std::true_type, DIT&& dst_cur, IT&& src_cur, IT&& src_end) {
    for(; src_cur != src_end; ++src_cur, ++dst_cur) {
        *dst_cur = *src_cur;
    }
}
 
template <typename DIT, typename IT>
void range_transfer(std::false_type, DIT&& dst_cur, IT&& src_cur, IT&& src_end) {
    for(; src_cur != src_end; ++src_cur, ++dst_cur) {
        *dst_cur = std::move(*src_cur);
    }
}
 
// ----------------------------------------------------------------------------- 
// values 
 
// copy pointed values
template <typename OUT_IT, typename INP_IT>
void 
values(std::true_type, OUT_IT&& out_it, INP_IT&& cur_it, INP_IT&& end_it) {
    while(cur_it != end_it) {
        *out_it = **cur_it; // dereference pointer
        ++cur_it;
        ++out_it;
    }
}
 
// copy values
template <typename OUT_IT, typename INP_IT>
void 
values(std::false_type, OUT_IT&& out_it, INP_IT&& cur_it, INP_IT&& end_it) {
    while(cur_it != end_it) {
        *out_it = *cur_it;
        ++cur_it;
        ++out_it;
    }
}
 
// ----------------------------------------------------------------------------- 
// sum 
 
template <typename V>
size_t sum(V cur_sum, V v) {
    return cur_sum + v;
}
 
template <typename V, typename... Values>
size_t sum(V cur_sum, V v, V v2, Values... vs) {
    return sum(cur_sum + v, v2, vs...);
}
 
// ----------------------------------------------------------------------------- 
// group 
 
template <typename IT>
void group(IT&& cur) {
}
 
template <typename IT, typename C, typename... Cs>
void group(IT&& cur, C&& c, Cs&&... cs) {
    detail::range_transfer(detail::is_lvalue_ref_t<C>(), cur, c.begin(), c.end());
    group(cur, std::forward<Cs>(cs)...);
}
 
// ----------------------------------------------------------------------------- 
// advance group 
 
/*
 * The purpose of this algorithm is to increment any number of iterators by reference
 */
template <typename IT>
void advance_group(IT& it) { 
    ++it;
}
 
template <typename IT, typename IT2, typename... ITs>
void advance_group(IT& it, IT2& it2, ITs&... its) {
    ++it;
    advance_group(it2, its...);
}
 
// ----------------------------------------------------------------------------- 
// map
template <typename F, typename RIT, typename IT, typename... ITs>
void map(F&& f, RIT&& rit, IT&& it, IT&& it_end, ITs&&... its) {
    while(it != it_end) {
        *rit = f(*it, *its...);
        advance_group(rit, it, its...);
    }
}
 
// ----------------------------------------------------------------------------
// fold
template <typename F, 
          typename R,
          typename IT,
          typename... ITs>
std::decay_t<R>
fold(F& f, R&& init, IT&& it, IT&& it_end, ITs&&... its) {
    std::decay_t<R> mutable_state(std::forward<R>(init));
 
    while(it != it_end) {
        mutable_state = f(std::move(mutable_state), *it, *its...);
        advance_group(it, its...);
    }
 
    return mutable_state;
}
 
// ----------------------------------------------------------------------------- 
// each
template <typename F, typename IT, typename... ITs>
void each(F&& f, IT&& it, IT&& it_end, ITs&&... its) {
    while(it != it_end) {
        f(*it, *its...);
        advance_group(it, its...);
    }
}
 
// ----------------------------------------------------------------------------
// all
template <typename F, typename IT, typename... ITs>
bool
all(F&& f, IT&& it, IT&& it_end, ITs&&... its) {
    bool ret = true;
 
    while(it != it_end) {
        if(!f(*it, *its...)) {
            ret = false;
            break;
        }
 
        advance_group(it, its...);
    }
 
    return ret;
}
 
// ----------------------------------------------------------------------------
// some
template <typename F, typename IT, typename... ITs>
bool
some(F&& f, IT&& it, IT&& it_end, ITs&&... its) {
    bool ret = false;
 
    while(it != it_end) {
        if(f(*it, *its...)) {
            ret = true;
            break;
        }
 
        advance_group(it, its...);
    }
 
    return ret;
}
 
}
 
//------------------------------------------------------------------------------
// size
 
template <typename C>
size_t // size_t is convertable from all std:: container `size_type`s
size(C&& c) { 
    return detail::size(c, detail::has_size<C>()); 
}
 
//------------------------------------------------------------------------------
// pointers
 
template <typename C>
auto
pointers(C& c) {
    typedef typename std::decay_t<C>::value_type CV;
    std::vector<CV*> ret(sca::size(c));
    std::transform(c.begin(), c.end(), ret.begin(), [](CV& e){ return &e; });
    return ret;
}
 
template <typename C>
auto
pointers(const C& c) {
    typedef typename std::decay_t<C>::value_type CV;
    std::vector<const CV*> ret(sca::size(c));
    std::transform(c.begin(), c.end(), ret.begin(), [](const CV& e){ return &e; });
    return ret;
}
 
//------------------------------------------------------------------------------
// values
 
template <typename C>
auto 
values(C&& c) {
    typedef typename std::decay_t<C>::value_type CV;
    typedef typename std::decay_t<std::remove_pointer_t<CV>> BCV; // base container value type
    std::vector<BCV> ret(sca::size(c));
    detail::values(typename std::is_pointer<CV>::type(), ret.begin(), c.begin(), c.end());
    return ret;
}
 
//------------------------------------------------------------------------------
// slice 
 
template<typename C>
class slice_of {
    typedef std::decay_t<C> DC;
 
public:
    typedef typename DC::iterator iterator;
    typedef typename DC::value_type value_type;
    typedef typename DC::size_type size_type;
 
    slice_of() = delete; // no default initialization
    slice_of(const C& c, size_t idx, size_t len) = delete; // must use const_slice_of
 
    // mutable lvalue constructor
    slice_of(C& c, size_t idx, size_t len) :
        m_size(len),
        m_begin(std::next(c.begin(), idx)),
        m_end(std::next(m_begin, len))
    { }
 
    // rvalue constructor
    slice_of(C&& c, size_t idx, size_t len) :
        m_mem(std::make_shared<DC>(std::move(c))), // keep container in memory
        m_size(len),
        m_begin(std::next(m_mem->begin(), idx)),
        m_end(std::next(m_begin, len))
    { }
 
    // iterator constructor
    template <typename IT>
    slice_of(IT begin, IT end) : 
        m_size(std::distance(begin, end)),
        m_begin(std::move(begin)),
        m_end(std::move(end))
    { }
 
    inline size_t size() const {
        return m_size;
    }
 
    inline auto begin() {
        return m_begin;
    }
 
    inline auto end() { 
        return m_end;
    }
 
private:
    std::shared_ptr<DC> m_mem; // place to hold container memory if constructed with an rvalue 
    const size_t m_size;
    iterator m_begin;
    iterator m_end;
};
 
template <typename C>
class const_slice_of {
    typedef std::decay_t<C> DC;
 
public:
    typedef typename DC::const_iterator const_iterator;
    typedef typename DC::value_type value_type;
    typedef typename DC::size_type size_type;
 
    const_slice_of() = delete; // no default initialization
 
    // const lvalue constructor
    const_slice_of(const C& c, size_t idx, size_t len) :
        m_size(len),
        m_cbegin(std::next(c.cbegin(), idx)),
        m_cend(std::next(m_cbegin, len))
    { }
 
    // iterator constructor
    template <typename IT>
    const_slice_of(IT begin, IT end) : 
        m_size(std::distance(begin, end)),
        m_cbegin(std::move(begin)),
        m_cend(std::move(end))
    { }
 
    inline size_t size() const {
        return m_size;
    }
 
    inline auto begin() const {
        return m_cbegin;
    }
 
    inline auto end() const {
        return m_cend;
    }
 
private:
    const size_t m_size;
    const_iterator m_cbegin;
    const_iterator m_cend;
};
 
template <typename C>
auto
slice(C&& c, size_t idx, size_t len) {
    return slice_of<C>(std::forward<C>(c), idx, len);
}
 
template <typename C>
auto
slice(const C& c, size_t idx, size_t len) {
    return const_slice_of<C>(c, idx, len);
}
 
template <typename C>
auto
slice(C& c, size_t idx, size_t len) {
    return const_slice_of<C>(c, idx, len);
}
 
template <typename C>
auto
mslice(C&& c, size_t idx, size_t len) {
    return slice_of<C>(std::forward<C>(c), idx, len);
}
 
// explicitly catch mutable lvalue reference so compiler doesn't convert to `const C&`
template <typename C>
auto
mslice(C& c, size_t idx, size_t len) {
    return slice_of<C>(c, idx, len);
}
 
//------------------------------------------------------------------------------
// group
 
template <typename C, typename C2, typename... Cs>
auto
group(C&& c, C2&& c2, Cs&&... cs) {
    detail::to_vector_t<C> ret(detail::sum(sca::size(c), sca::size(c2), sca::size(cs)...));
    detail::group(ret.begin(), std::forward<C>(c), std::forward<C2>(c2), std::forward<Cs>(cs)...);
    return ret;
}
 
//------------------------------------------------------------------------------
// reverse
 
template <typename C>
auto
reverse(C&& c) {
    detail::to_vector_t<C> ret(sca::size(c));
    detail::range_transfer(detail::is_lvalue_ref_t<C>(), ret.begin(), c.begin(), c.end());
    std::reverse(ret.begin(), ret.end());
    return ret; 
}
 
//------------------------------------------------------------------------------
// sort 
 
template <typename C, typename F>
auto
sort(C&& c, F&& cmp) {
    detail::to_vector_t<C> ret(sca::size(c));
    detail::range_transfer(detail::is_lvalue_ref_t<C>(), ret.begin(), c.begin(), c.end());
    std::sort(ret.begin(), ret.end(), cmp);
    return ret;
}
 
//------------------------------------------------------------------------------
// filter
 
template <typename F, typename C>
auto
filter(F&& f, C&& c) {
    detail::to_vector_t<C> ret(sca::size(c));
    size_t cur = 0;
 
    for(auto& e : c) {
        if(f(e)) {
            detail::transfer(detail::is_lvalue_ref_t<C>(), ret[cur], e);
            ++cur;
        }
    }
 
    ret.resize(cur);
    return ret;
}
 
//------------------------------------------------------------------------------
// map 
 
template <typename F, typename C, typename... Cs>
auto
map(F&& f, C&& c, Cs&&... cs) {
    typedef detail::callable_return_t<
        F,
        detail::container_reference_value_t<C>,
        detail::container_reference_value_t<Cs>...
    > FR;
 
    std::vector<FR> ret(sca::size(c));
    detail::map(std::forward<F>(f), ret.begin(), c.begin(), c.end(), cs.begin()...);
    return ret;
}
 
//------------------------------------------------------------------------------
// fold 
 
template <typename F, typename Result, typename C, typename... Cs>
auto
fold(F&& f, Result&& init, C&& c, Cs&&... cs) {
    return detail::fold(f, std::forward<Result>(init), c.begin(), c.end(), cs.begin()...);
}
 
//------------------------------------------------------------------------------
// for_each
 
template <typename F, typename C, typename... Cs>
void
each(F&& f, C&& c, Cs&&... cs) {
    detail::each(f, c.begin(), c.end(), cs.begin()...);
}
 
//------------------------------------------------------------------------------
// all
 
template <typename F, typename C, typename... Cs>
bool 
all(F&& f, C&& c, Cs&&... cs) {
    return detail::all(f, c.begin(), c.end(), cs.begin()...);
}
 
//------------------------------------------------------------------------------
// some
 
template <typename F, typename C, typename... Cs>
bool 
some(F&& f, C&& c, Cs&&... cs) {
    return detail::some(f, c.begin(), c.end(), cs.begin()...);
}
 
}
 
#endif