hxalgorithm.hpp

Go to the documentation of this file.

#pragma once
// SPDX-FileCopyrightText: © 2017-2026 Adrian Johnston.
// SPDX-License-Identifier: MIT
// This file is licensed under the MIT license found in the LICENSE.md file.

 
#include "libhatchet.h"
 
// HX_USE_MACROS_WITH_MODULE allows including macros alongside the module.
#if HX_USE_MACROS_WITH_MODULE
#error Header does not provide macros alone.
#endif
 
#include "hxkey.hpp"
 
HX_NS_BEGIN_

template<typename iterator_t_, typename callable_t_>
hxinline hxattr_flatten hxattr_nodiscard hxconstexpr
bool hxall_of(iterator_t_ begin_, iterator_t_ end_, callable_t_&& callable_) {
    for(; begin_ != end_; ++begin_) {
        if(!hxforward<callable_t_>(callable_)(*begin_)) {
            return false;
        }
    }
    return true;
}

template<typename iterator_t_, typename callable_t_>
hxinline hxattr_flatten hxattr_nodiscard hxconstexpr
bool hxany_of(iterator_t_ begin_, iterator_t_ end_, callable_t_&& callable_) {
    for(; begin_ != end_; ++begin_) {
        if(hxforward<callable_t_>(callable_)(*begin_)) {
            return true;
        }
    }
    return false;
}

template<typename iterator_t_, typename callable_t_>
hxinline hxattr_flatten hxattr_nodiscard hxconstexpr
hxsize_t hxcount_if(iterator_t_ begin_, iterator_t_ end_, callable_t_&& callable_) {
    hxsize_t count_ = hxsize_t{0};
    for(; begin_ != end_; ++begin_) {
        if(hxforward<callable_t_>(callable_)(*begin_)) {
            ++count_;
        }
    }
    return count_;
}

template<typename T_, typename U_>
hxattr_nodiscard hxinline hxattr_flatten hxconstexpr
T_ hxexchange(T_& obj_, U_&& new_value_) noexcept {
    T_ old_(hxmove(obj_));
    obj_ = hxforward<U_>(new_value_);
    return old_;
}

template<typename iterator_t_, typename callable_t_>
hxinline hxattr_flatten hxattr_nodiscard hxconstexpr
iterator_t_ hxfind_if(iterator_t_ begin_, iterator_t_ end_, callable_t_&& callable_) {
    for(; begin_ != end_; ++begin_) {
        if(hxforward<callable_t_>(callable_)(*begin_)) {
            return begin_;
        }
    }
    return end_;
}

template<typename iterator_t_, typename callable_t_>
hxinline hxattr_flatten hxconstexpr
callable_t_ hxfor_each(iterator_t_ begin_, iterator_t_ end_, callable_t_&& callable_) {
    for(; begin_ != end_; ++begin_) {
        hxforward<callable_t_>(callable_)(*begin_);
    }
    return hxforward<callable_t_>(callable_);
}

template<typename iterator_t_, typename output_iterator_t_, typename less_t_>
inline hxattr_flatten hxconstexpr
output_iterator_t_ hxmerge(iterator_t_ begin0_, iterator_t_ end0_, iterator_t_ begin1_, iterator_t_ end1_,
        output_iterator_t_&& output_, const less_t_& less_) noexcept {
    hxrestrict_t<iterator_t_> src0_(begin0_);
    hxrestrict_t<iterator_t_> src1_(begin1_);
    hxrestrict_t<output_iterator_t_> output_r_(output_);
    while(src0_ != end0_ && src1_ != end1_) {
        const bool take1_ = less_(*src1_, *src0_);
        const hxrestrict_t<iterator_t_> sel_ = take1_ ? src1_ : src0_;
        *output_r_ = hxmove(*sel_);
        ++output_r_;
        src1_ = src1_ + static_cast<ptrdiff_t>(take1_);
        src0_ = src0_ + static_cast<ptrdiff_t>(!take1_);
    }
    while(src0_ != end0_) {
        *output_r_ = hxmove(*src0_);
        ++output_r_; ++src0_;
    }
    while(src1_ != end1_) {
        *output_r_ = hxmove(*src1_);
        ++output_r_; ++src1_;
    }
    return output_r_;
}

template<typename iterator_t_, typename output_iterator_t_>
inline hxattr_flatten hxconstexpr
output_iterator_t_ hxmerge(iterator_t_ begin0_, iterator_t_ end0_, iterator_t_ begin1_,
        iterator_t_ end1_, output_iterator_t_&& output_) noexcept {
    return hxmerge<iterator_t_, output_iterator_t_>(begin0_, end0_, begin1_, end1_,
        hxforward<output_iterator_t_>(output_), hxkey_less_t<decltype(*begin0_)>{});
}

template<typename iterator_t_>
class hxminmax_result {
public:
    iterator_t_ min;
    iterator_t_ max;
};

template<typename iterator_t_, typename less_t_>
inline hxattr_flatten hxattr_nodiscard hxconstexpr
hxminmax_result<iterator_t_>
hxminmax(iterator_t_ begin_, iterator_t_ end_, const less_t_& less_) {
    hxminmax_result<iterator_t_> result_{begin_, begin_};
    if(begin_ == end_) { return result_; }
    for(++begin_; begin_ != end_; ++begin_) {
        if(less_(*begin_, *result_.min)) {
            result_.min = begin_;
        }
        else if(less_(*result_.max, *begin_)) {
            result_.max = begin_;
        }
    }
    return result_;
}

template<typename iterator_t_>
inline hxattr_flatten hxattr_nodiscard hxconstexpr
hxminmax_result<iterator_t_>
hxminmax(iterator_t_ begin_, iterator_t_ end_) {
    return hxminmax<iterator_t_>(begin_, end_, hxkey_less_t<decltype(*begin_)>{});
}

template<typename iterator_t_, typename output_iterator_t_, typename less_t_>
inline hxattr_flatten hxconstexpr
output_iterator_t_ hxset_difference(iterator_t_ begin0_, iterator_t_ end0_, iterator_t_ begin1_,
        iterator_t_ end1_, output_iterator_t_&& output_, const less_t_& less_) noexcept {
    hxrestrict_t<iterator_t_> src0_(begin0_);
    hxrestrict_t<iterator_t_> src1_(begin1_);
    hxrestrict_t<output_iterator_t_> output_r_(output_);
    while(src0_ != end0_ && src1_ != end1_) {
        const bool lt_ = less_(*src0_, *src1_);
        const bool gt_ = less_(*src1_, *src0_);
        if(lt_) {
            *output_r_ = hxmove(*src0_);
            ++output_r_;
        }
        src0_ = src0_ + static_cast<ptrdiff_t>(!gt_);
        src1_ = src1_ + static_cast<ptrdiff_t>(!lt_);
    }
    while(src0_ != end0_) {
        *output_r_ = hxmove(*src0_);
        ++output_r_; ++src0_;
    }
    return output_r_;
}

template<typename iterator_t_, typename output_iterator_t_>
inline hxattr_flatten hxconstexpr
output_iterator_t_ hxset_difference(iterator_t_ begin0_, iterator_t_ end0_, iterator_t_ begin1_,
        iterator_t_ end1_, output_iterator_t_&& output_) noexcept {
    return hxset_difference<iterator_t_, output_iterator_t_>(begin0_, end0_, begin1_, end1_,
        hxforward<output_iterator_t_>(output_), hxkey_less_t<decltype(*begin0_)>{});
}

template<typename iterator_t_, typename output_iterator_t_, typename less_t_>
inline hxattr_flatten hxconstexpr
output_iterator_t_ hxset_intersection(iterator_t_ begin0_, iterator_t_ end0_, iterator_t_ begin1_,
        iterator_t_ end1_, output_iterator_t_&& output_, const less_t_& less_) noexcept {
    hxrestrict_t<iterator_t_> src0_(begin0_);
    hxrestrict_t<iterator_t_> src1_(begin1_);
    hxrestrict_t<output_iterator_t_> output_r_(output_);
    while(src0_ != end0_ && src1_ != end1_) {
        const bool lt_ = less_(*src0_, *src1_);
        const bool gt_ = less_(*src1_, *src0_);
        if(!lt_ && !gt_) {
            *output_r_ = hxmove(*src0_);
            ++output_r_;
        }
        src0_ = src0_ + static_cast<ptrdiff_t>(!gt_);
        src1_ = src1_ + static_cast<ptrdiff_t>(!lt_);
    }
    return output_r_;
}

template<typename iterator_t_, typename output_iterator_t_>
inline hxattr_flatten hxconstexpr
output_iterator_t_ hxset_intersection(iterator_t_ begin0_, iterator_t_ end0_, iterator_t_ begin1_,
        iterator_t_ end1_, output_iterator_t_&& output_) noexcept {
    return hxset_intersection<iterator_t_, output_iterator_t_>(begin0_, end0_, begin1_, end1_,
        hxforward<output_iterator_t_>(output_), hxkey_less_t<decltype(*begin0_)>{});
}

template<typename iterator_t_, typename output_iterator_t_, typename less_t_>
inline hxattr_flatten hxconstexpr
output_iterator_t_ hxset_union(iterator_t_ begin0_, iterator_t_ end0_, iterator_t_ begin1_,
        iterator_t_ end1_, output_iterator_t_&& output_, const less_t_& less_) noexcept {
    hxrestrict_t<iterator_t_> src0_(begin0_);
    hxrestrict_t<iterator_t_> src1_(begin1_);
    hxrestrict_t<output_iterator_t_> output_r_(output_);
    while(src0_ != end0_ && src1_ != end1_) {
        const bool take1_ = less_(*src1_, *src0_);
        const bool less0_ = less_(*src0_, *src1_);
        const hxrestrict_t<iterator_t_> sel_ = take1_ ? src1_ : src0_;
        *output_r_ = hxmove(*sel_);
        ++output_r_;
        src0_ = src0_ + static_cast<ptrdiff_t>(!take1_);
        src1_ = src1_ + static_cast<ptrdiff_t>(!less0_);
    }
    while(src0_ != end0_) {
        *output_r_ = hxmove(*src0_);
        ++output_r_; ++src0_;
    }
    while(src1_ != end1_) {
        *output_r_ = hxmove(*src1_);
        ++output_r_; ++src1_;
    }
    return output_r_;
}

template<typename iterator_t_, typename output_iterator_t_>
inline hxattr_flatten hxconstexpr
output_iterator_t_ hxset_union(iterator_t_ begin0_, iterator_t_ end0_, iterator_t_ begin1_,
        iterator_t_ end1_, output_iterator_t_&& output_) noexcept {
    return hxset_union<iterator_t_, output_iterator_t_>(begin0_, end0_, begin1_, end1_,
        hxforward<output_iterator_t_>(output_), hxkey_less_t<decltype(*begin0_)>{});
}

template<typename iterator_t_, typename equal_t_>
inline hxattr_flatten hxattr_nodiscard hxconstexpr
iterator_t_ hxunique(iterator_t_ begin_, iterator_t_ end_, const equal_t_& equal_) noexcept {
    if(begin_ == end_) { return end_; }
    iterator_t_ dst_ = begin_;
    for(++begin_; begin_ != end_; ++begin_, ++dst_) {
        if(equal_(*dst_, *begin_)) { break; }
    }
    if(begin_ == end_) { return end_; }
    for(++begin_; begin_ != end_; ++begin_) {
        if(!equal_(*dst_, *begin_)) {
            ++dst_;
            *dst_ = hxmove(*begin_);
        }
    }
    return ++dst_;
}

template<typename iterator_t_>
inline hxattr_flatten hxattr_nodiscard hxconstexpr
iterator_t_ hxunique(iterator_t_ begin_, iterator_t_ end_) noexcept {
    return hxunique<iterator_t_>(begin_, end_, hxkey_equal_t<decltype(*begin_)>{});
}
 
HX_NS_END_