hxset_algorithms.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 "hxrange.hpp"
 
// 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
 
HX_NS_BEGIN_

template<hxrandom_range_concept_ range0_t_, hxrandom_range_concept_ range1_t_,
        typename output_iterator_t_, typename less_t_>
inline hxconstexpr hxattr_flatten
output_iterator_t_ hxmerge(range0_t_&& range0_, range1_t_&& range1_,
        output_iterator_t_&& output_, const less_t_& less_) noexcept {
    hxrestrict_t<decltype(range0_.begin())> src0_(range0_.begin());
    const auto end0_ = range0_.end();
    hxrestrict_t<decltype(range1_.begin())> src1_(range1_.begin());
    const auto end1_ = range1_.end();
    hxrestrict_t<output_iterator_t_> output_r_(hxforward<output_iterator_t_>(output_));
    while(src0_ != end0_ && src1_ != end1_) {
        const bool take1_ = less_(*src1_, *src0_);
        if(take1_) { *output_r_ = hxforward_like<range1_t_>(*src1_); }
        else { *output_r_ = hxforward_like<range0_t_>(*src0_); }
        ++output_r_;
        src1_ = src1_ + static_cast<ptrdiff_t>(take1_);
        src0_ = src0_ + static_cast<ptrdiff_t>(!take1_);
    }
    while(src0_ != end0_) {
        *output_r_ = hxforward_like<range0_t_>(*src0_);
        ++output_r_; ++src0_;
    }
    while(src1_ != end1_) {
        *output_r_ = hxforward_like<range1_t_>(*src1_);
        ++output_r_; ++src1_;
    }
    return output_r_;
}

template<hxsorted_range_concept_ range0_t_, hxsorted_range_concept_ range1_t_,
        typename output_iterator_t_>
inline hxconstexpr hxattr_flatten
output_iterator_t_ hxmerge(range0_t_&& range0_, range1_t_&& range1_,
        output_iterator_t_&& output_) noexcept {
    const auto begin0_ = range0_.begin();
    return hxmerge<range0_t_, range1_t_, output_iterator_t_>(hxforward<range0_t_>(range0_),
        hxforward<range1_t_>(range1_), 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<hxrange_concept_ range_t_, typename less_t_>
hxattr_nodiscard inline hxconstexpr hxattr_flatten
auto hxminmax(range_t_&& range_, const less_t_& less_) -> hxminmax_result<decltype(range_.begin())> {
    hxrestrict_t<decltype(range_.begin())> it_(range_.begin());
    const auto end_ = range_.end();
    hxminmax_result<decltype(range_.begin())> result_{it_, it_};
    if(it_ == end_) { return result_; }
    for(++it_; it_ != end_; ++it_) {
        if(less_(*it_, *result_.min)) {
            result_.min = it_;
        }
        else if(less_(*result_.max, *it_)) {
            result_.max = it_;
        }
    }
    return result_;
}

template<hxrange_concept_ range_t_>
hxattr_nodiscard inline hxconstexpr hxattr_flatten
auto hxminmax(range_t_&& range_) -> hxminmax_result<decltype(range_.begin())> {
    const auto begin_ = range_.begin();
    return hxminmax<range_t_>(hxforward<range_t_>(range_), hxkey_less_t<decltype(*begin_)>{});
}

template<hxrandom_range_concept_ range0_t_, hxrandom_range_concept_ range1_t_,
        typename output_iterator_t_, typename less_t_>
inline hxconstexpr hxattr_flatten
output_iterator_t_ hxset_difference(range0_t_&& range0_, range1_t_&& range1_,
        output_iterator_t_&& output_, const less_t_& less_) noexcept {
    hxrestrict_t<decltype(range0_.begin())> src0_(range0_.begin());
    const auto end0_ = range0_.end();
    hxrestrict_t<decltype(range1_.begin())> src1_(range1_.begin());
    const auto end1_ = range1_.end();
    hxrestrict_t<output_iterator_t_> output_r_(hxforward<output_iterator_t_>(output_));
    while(src0_ != end0_ && src1_ != end1_) {
        const bool lt_ = less_(*src0_, *src1_);
        const bool gt_ = less_(*src1_, *src0_);
        if(lt_) {
            *output_r_ = hxforward_like<range0_t_>(*src0_);
            ++output_r_;
        }
        src0_ = src0_ + static_cast<ptrdiff_t>(!gt_);
        src1_ = src1_ + static_cast<ptrdiff_t>(!lt_);
    }
    while(src0_ != end0_) {
        *output_r_ = hxforward_like<range0_t_>(*src0_);
        ++output_r_; ++src0_;
    }
    return output_r_;
}

template<hxsorted_range_concept_ range0_t_, hxsorted_range_concept_ range1_t_,
        typename output_iterator_t_>
inline hxconstexpr hxattr_flatten
output_iterator_t_ hxset_difference(range0_t_&& range0_, range1_t_&& range1_,
        output_iterator_t_&& output_) noexcept {
    const auto begin0_ = range0_.begin();
    return hxset_difference<range0_t_, range1_t_, output_iterator_t_>(hxforward<range0_t_>(range0_),
        hxforward<range1_t_>(range1_), hxforward<output_iterator_t_>(output_),
        hxkey_less_t<decltype(*begin0_)>{});
}

template<hxrandom_range_concept_ range0_t_, hxrandom_range_concept_ range1_t_,
        typename output_iterator_t_, typename less_t_>
inline hxconstexpr hxattr_flatten
output_iterator_t_ hxset_intersection(range0_t_&& range0_, range1_t_&& range1_,
        output_iterator_t_&& output_, const less_t_& less_) noexcept {
    hxrestrict_t<decltype(range0_.begin())> src0_(range0_.begin());
    const auto end0_ = range0_.end();
    hxrestrict_t<decltype(range1_.begin())> src1_(range1_.begin());
    const auto end1_ = range1_.end();
    hxrestrict_t<output_iterator_t_> output_r_(hxforward<output_iterator_t_>(output_));
    while(src0_ != end0_ && src1_ != end1_) {
        const bool lt_ = less_(*src0_, *src1_);
        const bool gt_ = less_(*src1_, *src0_);
        if(!lt_ && !gt_) {
            *output_r_ = hxforward_like<range0_t_>(*src0_);
            ++output_r_;
        }
        src0_ = src0_ + static_cast<ptrdiff_t>(!gt_);
        src1_ = src1_ + static_cast<ptrdiff_t>(!lt_);
    }
    return output_r_;
}

template<hxsorted_range_concept_ range0_t_, hxsorted_range_concept_ range1_t_,
        typename output_iterator_t_>
inline hxconstexpr hxattr_flatten
output_iterator_t_ hxset_intersection(range0_t_&& range0_, range1_t_&& range1_,
        output_iterator_t_&& output_) noexcept {
    const auto begin0_ = range0_.begin();
    return hxset_intersection<range0_t_, range1_t_, output_iterator_t_>(hxforward<range0_t_>(range0_),
        hxforward<range1_t_>(range1_), hxforward<output_iterator_t_>(output_),
        hxkey_less_t<decltype(*begin0_)>{});
}

template<hxrandom_range_concept_ range0_t_, hxrandom_range_concept_ range1_t_,
        typename output_iterator_t_, typename less_t_>
inline hxconstexpr hxattr_flatten
output_iterator_t_ hxset_union(range0_t_&& range0_, range1_t_&& range1_,
        output_iterator_t_&& output_, const less_t_& less_) noexcept {
    hxrestrict_t<decltype(range0_.begin())> src0_(range0_.begin());
    const auto end0_ = range0_.end();
    hxrestrict_t<decltype(range1_.begin())> src1_(range1_.begin());
    const auto end1_ = range1_.end();
    hxrestrict_t<output_iterator_t_> output_r_(hxforward<output_iterator_t_>(output_));
    while(src0_ != end0_ && src1_ != end1_) {
        const bool take1_ = less_(*src1_, *src0_);
        const bool less0_ = less_(*src0_, *src1_);
        if(take1_) { *output_r_ = hxforward_like<range1_t_>(*src1_); }
        else { *output_r_ = hxforward_like<range0_t_>(*src0_); }
        ++output_r_;
        src0_ = src0_ + static_cast<ptrdiff_t>(!take1_);
        src1_ = src1_ + static_cast<ptrdiff_t>(!less0_);
    }
    while(src0_ != end0_) {
        *output_r_ = hxforward_like<range0_t_>(*src0_);
        ++output_r_; ++src0_;
    }
    while(src1_ != end1_) {
        *output_r_ = hxforward_like<range1_t_>(*src1_);
        ++output_r_; ++src1_;
    }
    return output_r_;
}

template<hxsorted_range_concept_ range0_t_, hxsorted_range_concept_ range1_t_,
        typename output_iterator_t_>
inline hxconstexpr hxattr_flatten
output_iterator_t_ hxset_union(range0_t_&& range0_, range1_t_&& range1_,
        output_iterator_t_&& output_) noexcept {
    const auto begin0_ = range0_.begin();
    return hxset_union<range0_t_, range1_t_, output_iterator_t_>(hxforward<range0_t_>(range0_),
        hxforward<range1_t_>(range1_), hxforward<output_iterator_t_>(output_),
        hxkey_less_t<decltype(*begin0_)>{});
}

template<hxrandom_iterator_concept_ iterator_t_, typename equal_t_>
hxattr_nodiscard inline hxconstexpr hxattr_flatten
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_; }
    hxrestrict_t<iterator_t_> dst_r_(dst_);
    hxrestrict_t<iterator_t_> src_r_(begin_);
    for(++src_r_; src_r_ != end_; ++src_r_) {
        if(!equal_(*dst_r_, *src_r_)) {
            ++dst_r_;
            *dst_r_ = hxmove(*src_r_);
        }
    }
    return ++dst_r_;
}

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