/* *****************************************************************************
* kblib is a general utility library for C++14 and C++17, intended to provide
* performant high-level abstractions and more expressive ways to do simple
* things.
*
* Copyright (c) 2021 killerbee
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
* ****************************************************************************/
/**
* @file
* @brief This file provides some iterators, ranges, iterator/range adapters,
* and operations that can be performed on iterators or smart pointers.
*
* @author killerbee
* @date 2019-2021
* @copyright GNU General Public Licence v3.0
*/
#ifndef KBLIB_ITERATORS_H
#define KBLIB_ITERATORS_H
#include "enumerate-contrib-cry.h"
#include "enumerate-contrib-tw.h"
#include "fakestd.h"
#include
#include
#include
#if KBLIB_USE_CXX17
#include
#endif
namespace kblib {
template
struct to_pointer_impl {
constexpr auto operator()(ptr&& p) const noexcept -> auto {
return to_pointer_impl())>{}(p.operator->());
}
constexpr auto operator()(const ptr& p) const noexcept -> auto {
return to_pointer_impl())>{}(p.operator->());
}
};
template
struct to_pointer_impl {
constexpr auto operator()(T* p) const noexcept -> T* { return p; }
};
/**
* @brief Gets a raw pointer out of any smart pointer or iterator you might pass
* in, without dereferencing it or relying on a get() method.
*
* @param p A smart pointer to extract from.
*/
template
constexpr auto to_pointer(P&& p) noexcept -> auto* {
return to_pointer_impl>{}(p);
}
template >>
auto max_element(Container& c, Comp comp) -> value_type_linear_t* {
auto it = max_element(std::begin(c), std::end(c), comp);
if (it != std::end(c)) {
return to_pointer(it);
} else {
return nullptr;
}
}
/**
* @brief Determine if T is a valid output iterator to which values of type E
* may be written.
*/
template
struct is_output_iterator : std::false_type {};
template
struct is_output_iterator<
T, E, void_t() = std::declval())>>
: std::true_type {};
template
/**
* @brief Like a std::back_insert_iterator, but it keeps track of how many
* insertions it has made, allowing an end iterator to be created.
*
* @attention This iterator must be incremented and dereferenced exactly once
* for each assignment, in order to maintain the accuracy of the counter.
*
*/
class counting_back_insert_iterator {
public:
using value_type = void;
using difference_type = std::ptrdiff_t;
using pointer = void;
using reference = void;
using iterator_category = std::output_iterator_tag;
counting_back_insert_iterator() noexcept = default;
explicit counting_back_insert_iterator(Container& c, std::size_t n = 0)
: container(std::addressof(c)), count(n) {}
explicit counting_back_insert_iterator(std::size_t n) : count(n) {}
struct proxy_iterator {
using value_type = typename Container::value_type;
auto operator=(const value_type& value) & -> proxy_iterator& {
assert(container);
// Multiple assignments for a single dereference are not allowed
assert(*dirty);
*dirty = false;
container->push_back(value);
return *this;
}
auto operator=(value_type&& value) & -> proxy_iterator& {
assert(container);
// Multiple assignments for a single dereference are not allowed
assert(*dirty);
*dirty = false;
container->push_back(std::move(value));
return *this;
}
Container* container;
bool* dirty;
};
auto operator*() noexcept -> proxy_iterator {
assert(dirty);
return {container, &dirty};
}
auto operator++() & noexcept -> counting_back_insert_iterator& {
assert(not dirty);
++count;
dirty = true;
return *this;
}
auto operator++(int) noexcept -> counting_back_insert_iterator = delete;
friend auto operator==(const counting_back_insert_iterator& a,
const counting_back_insert_iterator& b) noexcept
-> bool {
return a.count == b.count;
}
friend auto operator!=(const counting_back_insert_iterator& a,
const counting_back_insert_iterator& b) noexcept
-> bool {
return a.count != b.count;
}
friend auto operator<(const counting_back_insert_iterator& a,
const counting_back_insert_iterator& b) noexcept
-> bool {
return a.count < b.count;
}
friend auto operator<=(const counting_back_insert_iterator& a,
const counting_back_insert_iterator& b) noexcept
-> bool {
return a.count <= b.count;
}
friend auto operator>(const counting_back_insert_iterator& a,
const counting_back_insert_iterator& b) noexcept
-> bool {
return a.count > b.count;
}
friend auto operator>=(const counting_back_insert_iterator& a,
const counting_back_insert_iterator& b) noexcept
-> bool {
return a.count >= b.count;
}
friend auto operator-(const counting_back_insert_iterator& a,
const counting_back_insert_iterator& b) noexcept
-> std::ptrdiff_t {
return std::ptrdiff_t(a.count) - ptrdiff_t(b.count);
}
protected:
Container* container = nullptr;
std::size_t count = 0;
bool dirty = true;
};
template
KBLIB_NODISCARD counting_back_insert_iterator
counting_back_inserter(C& c, std::size_t count = 0) {
return counting_back_insert_iterator{c, count};
}
/**
* @brief A range generator, similar to Python 3's range().
*
* Generates a half-open range, [min, max).
* @tparam Value The type of elements in the range. Must support comparison
* (equality and relational) and subtraction, but does not strictly need to be
* numeric. Must be copyable. Must be value-initializable. Notably,
* RandomAccessIterators are valid Value types.
* @tparam Delta A type used to mutate Value values.
* std::declval() + std::declval() must be a valid expression
* and must return type Value. Delta must be implicitly constructible and
* assignable from, as well as comparable to, int.
*/
template
class range_t {
private:
Value min, max;
Delta step;
constexpr static bool nothrow_copyable =
std::is_nothrow_copy_constructible::value;
constexpr static bool nothrow_steppable = noexcept(min + step);
public:
/**
* @brief 2- and 3-argument constructor. Explicitly specify start, end, and
* optionally the step amount.
*
* @param min_ The first value in the range.
* @param max_ The end of the range.
* @param step_ The difference between values in the range.
*/
constexpr range_t(Value min_, Value max_, Delta step_ = 1)
: min(min_), max(max_), step(step_) {
normalize();
}
/**
* @brief 1-argument constructor. Start is implicitly zero and step is 1 or
* -1, depending on the sign of max.
*
* @param max The end of the range.
*/
constexpr range_t(Value max)
: range_t(Value{}, max, (max >= Value{}) ? 1 : -1) {}
/**
* @brief A helper struct which acts as an iterator for the range elements,
* as they are generated on the fly.
*/
struct iterator {
Value val;
Delta step;
using difference_type = std::ptrdiff_t;
using value_type = Value;
using pointer = const Value*;
using reference = Value;
using iterator_category = std::input_iterator_tag;
/**
* @brief Return the "pointed-to" value.
*
* @return Value The value in the range this iterator corresponds to.
*/
constexpr auto operator*() const noexcept(nothrow_copyable) -> Value {
return val;
}
/**
* @brief Return a pointer to the value.
*
* @return pointer A pointer to a value equivalent to *(*this). Valid
* until the iterator is modified in any way or destroyed.
*/
constexpr auto operator->() const noexcept -> pointer { return &val; }
/**
* @brief Prefix increment. Advance to the next value in the range.
*
* @return iterator& *this.
*/
constexpr auto operator++() & noexcept(nothrow_steppable) -> iterator& {
val = val + step;
return *this;
}
/**
* @brief Postfix increment. Advance to the next value in the range, but
* return the current value.
*
* @return iterator A copy of the pre-incrementing value of *this.
*/
constexpr auto operator++(int) noexcept(nothrow_steppable) -> iterator {
auto ret = *this;
val = val + step;
return ret;
}
/**
* @brief Compare two range iterators for equality.
*
* Range iterators compare equal if they point to the same value and have
* the same step.
*/
constexpr friend auto operator==(iterator l, iterator r) noexcept
-> bool {
return l.val == r.val and l.step == r.step;
}
/**
* @brief Compare two range iterators for inequality.
*
* Range iterators compare equal if they point to the same value and have
* the same step.
*/
constexpr friend auto operator!=(iterator l, iterator r) noexcept
-> bool {
return l.val != r.val or l.step != r.step;
}
/**
* @brief Compare two range iterators.
*
* For range iterators, (A < B) is true when A can be advanced until (*A -
* *B) changes sign.
*/
constexpr friend auto operator<(iterator l, iterator r) noexcept -> bool {
if (l.step > 0)
return l.val < r.val;
else
return l.val > r.val;
}
/**
* @brief Compare two range iterators.
*
* For range iterators, (A < B) is true when A can be advanced until (*A -
* *B) changes sign.
*/
constexpr friend auto operator<=(iterator l, iterator r) noexcept
-> bool {
return not(r < l);
}
/**
* @brief Compare two range iterators.
*
* For range iterators, (A < B) is true when A can be advanced until (*A -
* *B) changes sign.
*/
constexpr friend auto operator>(iterator l, iterator r) noexcept -> bool {
return r < l;
}
/**
* @brief Compare two range iterators.
*
* For range iterators, (A < B) is true when A can be advanced until (*A -
* *B) changes sign.
*/
constexpr friend auto operator>=(iterator l, iterator r) noexcept
-> bool {
return not(l < r);
}
constexpr auto operator[](std::ptrdiff_t x) const noexcept -> Value {
return val + x * step;
}
template
constexpr auto operator[](Integral x) const noexcept -> Value {
return val + std::ptrdiff_t(x) * step;
}
};
/**
* @brief Returns an iterator to the beginning of the range.
*/
constexpr auto begin() const noexcept -> iterator { return {min, step}; }
/**
* @brief Return an iterator to the end of the range.
*/
constexpr auto end() const noexcept -> iterator { return {max, step}; }
/**
* @brief Returns the distance between start() and stop().
*/
constexpr auto size() const noexcept -> std::size_t {
return (max - min) / step;
}
/**
* @brief Returns an iterator to the beginning of the range.
*/
friend constexpr auto begin(const range_t& r) noexcept -> iterator {
return {r.min, r.step};
}
/**
* @brief Return an iterator to the end of the range.
*/
friend constexpr auto end(const range_t& r) noexcept -> iterator {
return {r.max, r.step};
}
/**
* @brief Returns the distance between start() and stop().
*/
friend constexpr auto size(const range_t& r) noexcept -> std::size_t {
return (r.max - r.min) / r.step;
}
/**
* @brief Query whether the range will generate any elements.
*/
constexpr auto empty() const noexcept -> bool { return size() == 0; }
template
constexpr auto operator[](Integral x) const noexcept
-> decltype(begin()[x]) {
return begin()[x];
}
constexpr auto lesser() const noexcept(nothrow_copyable) -> Value {
return (step > 0) ? max : min;
}
constexpr auto greater() const noexcept(nothrow_copyable) -> Value {
return (step > 0) ? min : max;
}
/**
\brief Returns a linear container whose elements are this range
*/
template and
std::is_constructible::value>* = nullptr>
explicit operator Container() const
noexcept(noexcept(Container(std::declval(),
std::declval()))) {
return Container(begin(), end());
}
/**
\brief Returns a setlike container whose elements are this range
*/
template and
std::is_constructible::value>* = nullptr>
explicit operator Container() const
noexcept(noexcept(Container(std::declval(),
std::declval()))) {
return Container(begin(), end());
}
/**
* @brief Compare l and r for equality.
*
* Ranges are equal when they generate identical ranges.
*/
constexpr friend auto operator==(range_t l, range_t r) noexcept -> bool {
return (l.empty() and r.empty()) or
((l.begin() == r.begin()) and (l.end() == r.end()) and
(l.step == r.step));
}
/**
* @brief Compare l and r for inequality.
*
* Ranges are equal when they generate identical ranges.
*/
constexpr friend auto operator!=(range_t l, range_t r) noexcept -> bool {
return not(l == r);
}
private:
template
static constexpr enable_if_t::value, std::true_type>
positive(const T&) {
return {};
}
template
static constexpr enable_if_t::value, bool> positive(T v) {
return v >= 0;
}
template ::value and
std::is_integral::value>* = nullptr>
static constexpr auto signed_cast(T v) {
return kblib::signed_cast(v);
}
template ::value and
std::is_integral::value)>* = nullptr>
static constexpr auto signed_cast(T v) {
return v;
}
constexpr auto normalize() noexcept(nothrow_steppable) -> void {
if (min == max) {
} else if (step == 0) {
if (min != std::numeric_limits::max()) {
max = min + 1;
} else {
max = min - 1;
}
} else {
auto difference = max - min;
std::ptrdiff_t sign = (step > 0) ? 1 : -1;
if ((sign * to_signed(difference)) <= (sign * step)) {
step = sign;
max = min + step;
} else {
auto remainder = difference % step;
if (remainder != 0) {
max = max - remainder;
assert(
not(positive(max) and
(signed_cast(std::numeric_limits::max() -
max) < step)));
max = max + step;
}
}
}
}
};
namespace detail_iterators {
template
struct is_addable : std::false_type {};
template
struct is_addable() + std::declval())>>
: std::true_type {};
} // namespace detail_iterators
struct adjuster {
std::ptrdiff_t adj;
constexpr adjuster(std::ptrdiff_t adj) noexcept : adj(adj) {}
constexpr operator std::ptrdiff_t() const noexcept { return adj; }
};
template
constexpr auto operator+(T val, adjuster a) noexcept
-> enable_if_t::value,
decltype(std::advance(val, a.adj))> {
return std::advance(val, a.adj);
}
/**
* @brief A struct which increments anything it is added to. Suitable for use as
* a Delta type for range_t.
*/
struct incrementer {
constexpr incrementer() noexcept = default;
constexpr incrementer(int) noexcept {}
constexpr operator int() const noexcept { return 1; }
friend constexpr auto operator*(std::ptrdiff_t x, incrementer) {
return adjuster{x};
}
};
/**
* @brief Increments val.
*/
template
constexpr auto operator+(T val, incrementer) -> T {
return ++val;
}
/**
* @brief A struct which decrements anything it is added to. Suitable for use as
* a Delta type for range_t.
*/
struct decrementer {
constexpr decrementer() noexcept = default;
constexpr decrementer(int) noexcept {}
constexpr operator int() const noexcept { return -1; }
friend constexpr auto operator*(std::ptrdiff_t x, decrementer) {
return adjuster{-x};
}
};
/**
* @brief Decrements val.
*/
template
constexpr auto operator+(T val, decrementer) -> T {
return --val;
}
/**
* @brief Constructs a range from beginning, end, and step amount. The range is
* half-open, that is min is in the range but max is not. If unspecified, the
* step is automatically either 1 or -1, depending on whether max > min.
*
* @param min The first value in the produced range.
* @param max The first value not in the produced range.
* @param step The difference between values in the produced range.
* @return range_t An iterable range [min, max).
*/
template
constexpr auto range(Value min, Value max, Delta step = 0)
-> range_t {
if (step == 0) {
if (min <= max) {
return {min, max, 1};
} else {
return {min, max, -1};
}
} else {
return {min, max, step};
}
}
/**
* @brief Constructs a half-open range [0, max). The step is automatically
* determined based on the sign of max.
*
* @param max The first value not in the produced range.
* @return range_t An iterable range [0, max).
*/
template
constexpr auto range(Value max) -> range_t {
return {max};
}
#if KBLIB_USE_CXX17
template
class irange_t {};
template
constexpr auto irange(Value min, Value max, Delta step = 0) {}
template
class enumerator_iterator;
/**
* @internal
*/
namespace detail_enumerate {
template
auto get_or(T1&& t1, T2&& t2) -> decltype(auto) {
return t1 ? *t1 : *t2;
}
struct force_copy_tag {};
// Get a pointer which is guaranteed to be invalid to use (but not UB to
// merely store)
template
auto get_magic_ptr() -> T* {
static const char enumeration_magic_pointer = '\0';
return reinterpret_cast(
const_cast(&enumeration_magic_pointer));
}
} // namespace detail_enumerate
template
class enumeration {
public:
enumeration() = default;
enumeration(const enumeration& other)
: idx(other.idx), local([&] {
assert(other.source or other.local);
assert(other.source != detail_enumerate::get_magic_ptr());
return other.copied();
}()),
source(nullptr) {}
enumeration(volatile enumeration& other)
: enumeration(const_cast(other)) {}
enumeration(enumeration&&) = delete;
auto operator=(const enumeration&) = delete;
auto operator=(enumeration&&) = delete;
~enumeration() = default;
private:
enumeration(detail_enumerate::force_copy_tag, std::size_t i) : idx(i) {}
public:
auto index() const noexcept -> std::size_t { return idx; }
auto copied() & noexcept -> std::remove_const_t& {
assert(source != detail_enumerate::get_magic_ptr());
assert(local);
return *local;
}
auto copied() const& noexcept -> const T& {
assert(source != detail_enumerate::get_magic_ptr());
return detail_enumerate::get_or(local, source);
}
auto reffed() & noexcept -> T& {
assert(source != detail_enumerate::get_magic_ptr());
return detail_enumerate::get_or(local, source);
}
auto reffed() const& noexcept -> const T& {
assert(source != detail_enumerate::get_magic_ptr());
return detail_enumerate::get_or(local, source);
}
private:
auto set(T* t) & -> void { source = t; }
auto advance() & noexcept -> void {
++idx;
source = detail_enumerate::get_magic_ptr();
local = std::nullopt;
}
std::size_t idx = 0;
mutable std::optional> local = std::nullopt;
T* source = detail_enumerate::get_magic_ptr();
template
friend class enumerator_iterator;
};
} // namespace kblib
namespace std {
#if defined(__clang__)
// Fix from: https://github.com/nlohmann/json/issues/1401
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wmismatched-tags"
#endif
template
class tuple_size<::kblib::enumeration>
: public std::integral_constant {};
template
class tuple_element<0, ::kblib::enumeration> {
public:
using type = std::size_t;
};
/**
* @brief references keep the same qualifications as the original
*/
template
class tuple_element<1, volatile ::kblib::enumeration> {
public:
using type = T;
};
/**
* @brief but you can also add const to a reference
*/
template
class tuple_element<1, const volatile ::kblib::enumeration> {
public:
using type = const T;
};
/**
* @brief copies decay away the const
*/
template
class tuple_element<1, ::kblib::enumeration> {
public:
using type = std::remove_const_t;
};
/**
* @brief unless const is explicitly added
*/
template
class tuple_element<1, const ::kblib::enumeration> {
public:
using type = const T;
};
#if defined(__clang__)
#pragma clang diagnostic pop
#endif
} // namespace std
namespace kblib {
// When a structured binding is created by value, this function is called as if
// by get(std::move(e)), so it does not call the lvalue reference function.
// I have no idea why it's implicitly moved, but it works for my purposes.
template
auto get(enumeration&& e) -> decltype(auto) {
static_assert(I <= 1, "enumeration only has two elements");
if constexpr (I == 0) {
return e.index();
} else {
return e.copied();
}
}
template
auto get(const enumeration&& e) -> decltype(auto) {
static_assert(I <= 1, "enumeration only has two elements");
if constexpr (I == 0) {
return e.index();
} else {
return e.copied();
}
}
// When captured by reference, the volatile qualifier is added, which allows
// std::tuple_element to detect the copying-nonconst-from-const case.
template
auto get(volatile enumeration& e) -> decltype(auto) {
static_assert(I <= 1, "enumeration only has two elements");
if constexpr (I == 0) {
return const_cast&>(e).index();
} else {
return const_cast&>(e).reffed();
}
}
template
auto get(const volatile enumeration& e) -> decltype(auto) {
static_assert(I <= 1, "enumeration only has two elements");
if constexpr (I == 0) {
return const_cast&>(e).index();
} else {
return const_cast&>(e).reffed();
}
}
template
class enumerator_iterator {
public:
using nested_value =
copy_const_t()),
typename std::iterator_traits::value_type>;
using value_type = enumeration;
using difference_type = std::ptrdiff_t;
using pointer = const value_type*;
using reference = const value_type&;
using iterator_category = std::input_iterator_tag;
enumerator_iterator() = default;
enumerator_iterator(const enumerator_iterator& other)
: enumerator_iterator(detail_enumerate::force_copy_tag{},
other.curr_.idx, other.it_) {}
enumerator_iterator(It it) : it_(it) {}
enumerator_iterator(enumerator_iterator&&) = default;
auto operator=(const enumerator_iterator&) -> enumerator_iterator& = default;
auto operator=(enumerator_iterator &&) -> enumerator_iterator& = default;
~enumerator_iterator() = default;
auto operator*() & -> volatile value_type& {
if (not captured) {
curr_.set(to_pointer(it_));
captured = true;
}
return curr_;
}
auto operator++() & -> enumerator_iterator& {
curr_.advance();
captured = false;
++it_;
return *this;
}
friend auto operator==(const enumerator_iterator& lhs,
const enumerator_iterator& rhs) noexcept -> bool {
return lhs.it_ == rhs.it_;
}
friend auto operator!=(const enumerator_iterator& lhs,
const enumerator_iterator& rhs) noexcept -> bool {
return lhs.it_ != rhs.it_;
}
private:
enumerator_iterator(detail_enumerate::force_copy_tag t, std::size_t idx,
It it)
: it_(it), curr_(t, idx) {}
It it_;
bool captured = false;
value_type curr_;
};
template
class enumerator_t;
template
class enumerator_t {
public:
detail::no_dangle_t r;
using range_t = typename std::remove_reference_t;
using nested_iterator = decltype(r.begin());
using nested_end_iterator = decltype(r.end());
using iterator = enumerator_iterator;
using end_iterator = enumerator_iterator;
using nested_const_iterator = typename range_t::const_iterator;
using const_iterator = enumerator_iterator;
auto begin() const& noexcept(noexcept(r.cbegin())) -> const_iterator {
return r.cbegin();
}
auto begin() & noexcept(noexcept(r.begin())) -> iterator {
return r.begin();
}
auto end() const& noexcept(noexcept(r.cend())) -> const_iterator {
return r.cend();
}
auto end() & noexcept(noexcept(r.end())) -> end_iterator { return r.end(); }
};
template
class enumerator_t {
public:
using nested_iterator = It;
using iterator = enumerator_iterator;
using end_iterator = enumerator_iterator;
auto begin() const& noexcept -> iterator { return {r_begin}; }
auto end() const& noexcept -> end_iterator { return {r_end}; }
It r_begin;
EndIt r_end;
};
/**
* @brief Allow access to indexes while using range-based for loops.
*
* The "magic" part is that
* \code
* for (auto&& [idx, val] : kblib::magic_enumerate(range)) {
* \endcode
* captures 'val' by reference, while
* \code
* for (auto [idx, val] : kblib::magic_enumerate(range)) {
* \endcode
* captures 'val' by value, so that the effect is similar to if you had written
* \code
* for (auto val : range) {
* \endcode
* and kept track of the index manually.
*
* @param begin,end The input range.
*/
template
auto magic_enumerate(It begin, EIt end) -> enumerator_t {
return {begin, end};
}
/**
* @brief Allow access to indexes while using range-based for loops. Safe to use
* with rvalues.
*
* The "magic" part is that
* \code
* for (auto&& [idx, val] : kblib::magic_enumerate(range)) {
* \endcode
* captures 'val' by reference, while
* \code
* for (auto [idx, val] : kblib::magic_enumerate(range)) {
* \endcode
* captures 'val' by value, so that the effect is similar to if you had written
* \code
* for (auto val : range) {
* \endcode
* and kept track of the index manually.
*
* @param r A range to iterate over.
*/
template
auto magic_enumerate(Range&& r) -> auto {
if constexpr (std::is_lvalue_reference_v) {
using std::begin;
using std::end;
return magic_enumerate(begin(r), end(r));
} else {
return enumerator_t{std::forward(r)};
}
}
#endif
/**
* @brief Allow range-for iteration of an iterator pair.
*/
template
struct indirect_range {
Iter1 begin_;
Iter2 end_;
constexpr auto begin() const noexcept -> Iter1 { return begin_; }
constexpr auto end() const noexcept -> Iter2 { return end_; }
constexpr auto rbegin() const noexcept -> auto {
return std::make_reverse_iterator(begin_);
}
constexpr auto rend() const noexcept -> auto {
return std::make_reverse_iterator(end_);
}
constexpr friend auto begin(const indirect_range& r) noexcept -> Iter1 {
return r.begin_;
}
constexpr friend auto end(const indirect_range& r) noexcept -> Iter2 {
return r.end_;
}
};
/**
* @brief Create a range from an iterator pair. Primarily useful for range-for
* loops.
*
* @param begin,end The range to wrap.
*/
template
constexpr auto
indirect(Iter1 begin,
Iter2 end) noexcept(noexcept(indirect_range{begin, end}))
-> indirect_range {
return {begin, end};
}
#if KBLIB_USE_CXX17
template
indirect_range(Iter1, Iter2) -> indirect_range;
template
auto cry_enumerate(Iter1 begin, Iter2 end) -> auto {
return cry_enumerate(indirect_range{begin, end});
}
#endif
// Fixed number of ranges
template
class multi_range {
public:
private:
struct range {
Iter1 begin;
EndIter end;
};
std::array ranges;
};
// Dynamic number of ranges
template
class multi_range {
public:
private:
struct range {
Iter1 begin;
EndIter end;
};
std::vector ranges;
};
/**
* @brief A smart pointer to an object contained inside the smart pointer
* object.
*
*/
template
struct containing_ptr {
/**
* @brief Returns the contained object.
*/
constexpr auto operator*() noexcept -> T& { return val; }
/**
* @brief Returns the contained object.
*/
constexpr auto operator*() const noexcept -> const T& { return val; }
/**
* @brief Return the address of the contained object.
*/
constexpr auto operator->() noexcept -> T* { return &val; }
/**
* @brief Return the address of the contained object.
*/
constexpr auto operator->() const noexcept -> const T* { return &val; }
/**
* @brief Returns the address of the contained object.
*/
constexpr auto get() noexcept -> T* { return &val; }
/**
* @brief Returns the address of the contained object.
*/
constexpr auto get() const noexcept -> const T* { return &val; }
T val;
};
#if KBLIB_USE_CXX17
/**
* @brief An InputIterator that applies a transformation to the elements of the
* range.
*
* @attention This class template depends on features introduced in C++17.
*/
template
class transform_iterator {
private:
base_iterator it;
std::optional op;
public:
using difference_type = std::ptrdiff_t;
using result_type = decltype(kblib::invoke(*op, *it));
using const_result_type =
decltype(kblib::invoke(*std::as_const(op), *std::as_const(it)));
using value_type = result_type;
using pointer = void;
using reference = value_type;
using iterator_category = std::input_iterator_tag;
/**
* @brief Constructs a transform_iterator which applies _op to the values
* obtained from *_it.
*
* @param _it An InputIterator to a range to be transformed.
* @param _op The operation to apply to each element.
*/
explicit transform_iterator(base_iterator _it, operation _op) noexcept(
noexcept(base_iterator{_it}) and noexcept(op.emplace(std::move(_op))))
: it(_it), op(std::move(_op)) {}
/**
* @brief constructs a non-dereferenceable sentinel iterator
*
* @param end_it An iterator that marks the end of the input range.
*/
explicit transform_iterator(base_iterator end_it) noexcept(
noexcept(base_iterator{end_it}))
: it(end_it), op(std::nullopt) {}
/**
* @brief Transforms the value obtained by dereferencing it.
*
* @return decltype(auto) The result of invoking op on *it.
*/
auto operator*() noexcept(noexcept(kblib::invoke(*op, *it)))
-> decltype(auto) {
return kblib::invoke(*op, *it);
}
/**
* @brief Transforms the value obtained by dereferencing it.
*
* @return decltype(auto) The result of invoking op on *it.
*/
decltype(auto) operator*() const
noexcept(noexcept(kblib::invoke(*op, *it))) {
return kblib::invoke(*op, *it);
}
/**
* @brief Returns a containing_ptr with the transformed value, because
* operator-> expects a pointer-like return type.
*/
auto operator->() noexcept(noexcept(kblib::invoke(*op, *it))) -> auto {
return containing_ptr{{kblib::invoke(*op, *it)}};
}
/**
* @brief Returns a containing_ptr with the transformed value, because
* operator-> expects a pointer-like return type.
*/
auto operator->() const noexcept(noexcept(kblib::invoke(*op, *it))) -> auto {
return containing_ptr{{kblib::invoke(*op, *it)}};
}
/**
* @brief Increments the underlying iterator and returns *this.
*/
auto operator++() noexcept(noexcept(++it)) -> transform_iterator& {
++it;
return *this;
}
/**
* @brief Increments the underlying iterator and returns a copy of the
* current value.
*/
[[deprecated("Needlessly copies op. Use preincrement instead.")]] auto
operator++(int) noexcept(noexcept(transform_iterator{it++, op}))
-> transform_iterator {
return {it++, op};
}
auto base() const noexcept -> base_iterator { return it; }
/**
* @brief Compares the base iterators of lhs and rhs.
*/
friend auto operator==(const transform_iterator& lhs,
const transform_iterator& rhs) noexcept -> bool {
return lhs.it == rhs.it;
}
/**
* @brief Compares the base iterators of lhs and rhs.
*/
friend auto operator!=(const transform_iterator& lhs,
const transform_iterator& rhs) noexcept -> bool {
return lhs.it != rhs.it;
}
template
friend auto operator==(const transform_iterator& lhs,
const OIt& rhs) noexcept -> bool {
return lhs.base() == rhs;
}
template
friend auto operator==(const OIt& lhs,
const transform_iterator& rhs) noexcept -> bool {
return lhs == rhs.base();
}
template
friend auto operator!=(const transform_iterator& lhs,
const OIt& rhs) noexcept -> bool {
return lhs.base() != rhs;
}
template
friend auto operator!=(const OIt& lhs,
const transform_iterator& rhs) noexcept -> bool {
return lhs != rhs.base();
}
};
template
transform_iterator(It, operation) -> transform_iterator;
/**
* @brief Factory function to make transform_iterators.
*
* @param it An InputIterator to a range to transform.
* @param op The transformation to apply.
* @return transform_iterator
*
* @deprecated Use transformer instead
*/
template
[[deprecated("use transformer instead")]] auto
make_transform_iterator(base_iterator it, operation op) noexcept(
noexcept(transform_iterator{it, std::move(op)}))
-> transform_iterator {
return {it, std::move(op)};
}
/**
* @brief Factory function to make transform_iterators.
*
* @param it An InputIterator to a range to transform.
* @param op The transformation to apply.
* @return transform_iterator
*/
template
auto transformer(base_iterator it, operation op) noexcept(
noexcept(transform_iterator{it, std::move(op)}))
-> transform_iterator {
return {it, std::move(op)};
}
template
auto transform_range(It begin, EndIt end, operation op) noexcept(
noexcept(indirect(transform_iterator{begin, op}, end))) -> auto {
return indirect(transform_iterator{begin, op}, end);
}
#endif
template
struct zip_iterator {
InputIt1 pos1{};
EndIt end1{};
InputIt2 pos2{};
constexpr static bool is_nothrow_copyable =
std::is_nothrow_copy_constructible::value and
std::is_nothrow_copy_constructible::value and
std::is_nothrow_copy_constructible::value;
auto operator++() noexcept(noexcept(++pos1) and noexcept(++pos2))
-> zip_iterator& {
++pos1;
++pos2;
return *this;
}
auto operator++(int) noexcept(is_nothrow_copyable and noexcept(
++pos1) and noexcept(++pos2)) -> const zip_iterator {
auto tmp = *this;
++pos1;
++pos2;
return tmp;
}
KBLIB_NODISCARD auto operator*() const noexcept -> auto {
return std::forward_as_tuple(*pos1, *pos2);
}
KBLIB_NODISCARD auto begin() const noexcept(is_nothrow_copyable)
-> zip_iterator {
return *this;
}
KBLIB_NODISCARD auto end() const
noexcept(std::is_nothrow_copy_constructible::value and
std::is_nothrow_copy_constructible::value)
-> zip_iterator {
return {end1, end1};
}
KBLIB_NODISCARD friend auto
operator==(const zip_iterator& z1,
const zip_iterator& z2) noexcept(noexcept(z1.pos1 == z2.pos1))
-> bool {
return z1.pos1 == z2.pos1;
}
KBLIB_NODISCARD friend auto
operator!=(const zip_iterator& z1,
const zip_iterator& z2) noexcept(noexcept(z1.pos1 != z2.pos1))
-> bool {
return z1.pos1 != z2.pos1;
}
KBLIB_NODISCARD friend auto operator==(
const zip_iterator& z1,
zip_iterator end) noexcept(noexcept(z1.pos1 ==
end.val))
-> bool {
return z1.end1 == end.val;
}
KBLIB_NODISCARD friend auto operator!=(
const zip_iterator& z1,
zip_iterator end) noexcept(noexcept(z1.pos1 ==
end.val))
-> bool {
return z1.end1 != end.val;
}
};
template
struct zip_iterator {
It1 pos1{};
It1 end1{};
It2 pos2{};
constexpr static bool is_nothrow_copyable =
std::is_nothrow_copy_constructible::value and
std::is_nothrow_copy_constructible::value;
auto operator++() noexcept(noexcept(++pos1)) -> zip_iterator& {
++pos1;
++pos2;
return *this;
}
auto operator++(int) noexcept(is_nothrow_copyable and noexcept(++pos1))
-> const zip_iterator {
auto tmp = *this;
++pos1;
++pos2;
return tmp;
}
KBLIB_NODISCARD auto operator*() -> auto {
return std::forward_as_tuple(*pos1, *pos2);
}
KBLIB_NODISCARD auto begin() const noexcept(is_nothrow_copyable)
-> zip_iterator {
return *this;
}
KBLIB_NODISCARD auto end() const
noexcept(std::is_nothrow_copy_constructible::value)
-> zip_iterator {
return {end1, end1, pos2};
}
KBLIB_NODISCARD friend auto
operator==(const zip_iterator& z1,
const zip_iterator& z2) noexcept(noexcept(z1.pos1 == z2.pos1))
-> bool {
return z1.pos1 == z2.pos1;
}
KBLIB_NODISCARD friend auto
operator!=(const zip_iterator& z1,
const zip_iterator& z2) noexcept(noexcept(z1.pos1 == z2.pos1))
-> bool {
return z1.pos1 != z2.pos1;
}
};
/**
* @brief Iterate over two ranges in lockstep, like Python's zip.
*
* InputIt1 and EndIt may be different types, however that breaks range-for
* in C++14.
*
* @param begin1,end1 The first range.
* @param begin2 The beginning of the second range.
* @return zip_iterator A range (and also an
* iterator) which represents the two ranges taken in pairs.
*/
template
KBLIB_NODISCARD auto zip(InputIt1 begin1, EndIt end1, InputIt2 begin2) noexcept(
zip_iterator::is_nothrow_copyable)
-> zip_iterator {
return {begin1, end1, begin2};
}
/**
* @brief Iterate over two ranges in lockstep, like Python's zip.
*
* @param r1 The first range.
* @param r2 The second range.
* @return zip_iterator A range (and also an iterator) which represents the two
* ranges taken in pairs.
*/
template
KBLIB_NODISCARD auto zip(Range1&& r1, Range2&& r2) noexcept(
zip_iterator::is_nothrow_copyable)
-> zip_iterator {
return {begin(r1), end(r1), begin(r2)};
}
template
class adjacent_iterator {
public:
using difference_type = std::ptrdiff_t;
using base_reference = typename std::iterator_traits::reference;
using value_type = std::pair;
using pointer = void;
using reference = value_type;
using iterator_category = std::input_iterator_tag;
private:
ForwardIt it;
};
/**
* @brief An OutputIterator that transforms the values assigned to it before
* inserting them into the back of a container.
*
* @author From marttyfication#4235 on the C++ Help discord.
*/
template
class back_insert_iterator_F {
public:
/**
* @brief
*
* @param c The container to be inserted into.
* @param f The tranformation to apply to each argument.
*/
explicit back_insert_iterator_F(Container& c, F f)
: container(c), fun(std::move(f)) {}
using value_type = void;
using difference_type = void;
using pointer = void;
using reference = void;
using iterator_category = std::output_iterator_tag;
template
/**
* @brief Calls container.push_back(kblib::invoke(fun,
* std::forward(value)));
*
* @param value The value to transform and insert.
* @return back_insert_iterator& *this.
*/
auto operator=(V&& value) -> back_insert_iterator_F& {
container.push_back(invoke(fun, std::forward(value)));
return *this;
}
/**
* @brief A no-op.
*/
auto operator*() -> back_insert_iterator_F& { return *this; }
/**
* @brief A no-op.
*/
auto operator++() -> back_insert_iterator_F& { return *this; }
private:
Container& container;
F fun;
};
/**
* @brief An OutputIterator that simply calls a provided functor for each value
* assigned to it.
*/
template
class consume_iterator {
private:
F fun;
public:
using value_type = void;
using difference_type = void;
using pointer = void;
using reference = void;
using iterator_category = std::output_iterator_tag;
/**
* @brief Constructs a consume_iterator with the given function object.
*
* @param f The functor to pass values to.
*/
explicit consume_iterator(F f) : fun(std::move(f)) {}
/**
* @brief Pass value to F.
*
* @param value The argument for the functor.
* @return consume_iterator& *this.
*/
template
auto operator=(V&& value) noexcept(noexcept(
kblib::invoke(fun, std::forward(value)))) -> consume_iterator& {
kblib::invoke(fun, std::forward(value));
return *this;
}
/**
* @brief A no-op.
*/
auto operator*() -> consume_iterator& { return *this; }
/**
* @brief A no-op.
*/
auto operator++() -> consume_iterator& { return *this; }
};
/**
* @brief Creates a consume_iterator of deduced type F.
*
* This could be a deduction guide, if kblib didn't also support C++14. Thus,
* the old style is used for compatibility.
*
* @param f A functor to call on assignment.
* @return consume_iterator
*/
template
auto consumer(F f) -> consume_iterator {
return consume_iterator{std::move(f)};
}
} // namespace kblib
#endif // KBLIB_ITERATORS_H