OXYGENHUB
◆ main openmsx / src / utils / ranges.hh
4.6 KiB · C++ · last changed chore(): initial commit 1 month ago source blame history raw
1 
#ifndef RANGES_HH
2 
#define RANGES_HH
3
4 
#include <algorithm>
5 
#include <bit>
6 
#include <cassert>
7 
#include <cstdint>
8 
#include <functional>
9 
#include <iterator>
10 
#include <memory>
11 
#include <ranges>
12 
#include <span>
13 
#include <version> // for _LIBCPP_VERSION
14
15 
// Range based versions of the standard algorithms, these will likely become
16 
// part of c++20. For example see this post:
17 
//   http://ericniebler.com/2018/12/05/standard-ranges/
18 
// In the future we can remove our implementation and instead use the standard
19 
// version (e.g. by a namespace alias like 'namespace ranges = std::ranges').
20 
//
21 
// All of the range algorithms below do nothing more than delegate to the
22 
// corresponding iterator-pair version of the algorithm.
23 
//
24 
// This list of algorithms is not complete. But it's easy to extend if/when we
25 
// need more.
26
27 
namespace ranges {
28
29 
// part of c++23, not yet available in clang-16
30 
template<std::forward_iterator ForwardIt, typename T>
31 
constexpr void iota(ForwardIt first, ForwardIt last, T value)
32 
{
33 
	while (first != last) {
34 
		*first++ = value;
35 
		++value;
36 
	}
37 
}
38
39 
template<std::ranges::forward_range Range, typename T>
40 
constexpr void iota(Range&& range, T&& value)
41 
{
42 
	::ranges::iota(std::ranges::begin(range), std::ranges::end(range), std::forward<T>(value));
43 
}
44
45 
// Test whether all elements in the given range are equal to each other (after
46 
// applying a projection).
47 
template<std::ranges::input_range Range, typename Proj = std::identity>
48 
bool all_equal(Range&& range, Proj proj = {})
49 
{
50 
	auto it = std::ranges::begin(range);
51 
	auto et = std::ranges::end(range);
52 
	if (it == et) return true;
53
54 
	auto val = std::invoke(proj, *it);
55 
	for (++it; it != et; ++it) {
56 
		if (std::invoke(proj, *it) != val) {
57 
			return false;
58 
		}
59 
	}
60 
	return true;
61 
}
62
63 
} // namespace ranges
64
65 
// Copy from a (sized-)range to another (non-overlapping) (sized-)range.
66 
// This differs from std::ranges::copy() in how the destination is passed:
67 
// * This version requires a (sized-)range.
68 
// * std::ranges::copy() requires an output-iterator.
69 
// The latter is more general, but the former can do an extra safety check:
70 
// * The destination size must be as least as large as the source size.
71 
template<std::ranges::sized_range Input, std::ranges::sized_range Output>
72 
constexpr auto copy_to_range(Input&& in, Output&& out)
73 
{
74 
	assert(std::ranges::size(in) <= std::ranges::size(out));
75 
	// Workaround: this doesn't work when copying a std::initializer_list into a std::array with libstdc++ debug-STL ???
76 
	//     return std::copy(std::begin(in), std::end(in), std::begin(out));
77 
	auto f = std::ranges::begin(in);
78 
	auto l = std::ranges::end(in);
79 
	auto o = std::ranges::begin(out);
80 
	while (f != l) {
81 
		*o++ = *f++;
82 
	}
83 
	return o;
84 
}
85
86 
// Perform a binary-search in a sorted range.
87 
// The given 'range' must be sorted according to 'comp'.
88 
// We search for 'value' after applying 'proj' to the elements in the range.
89 
// Returns a pointer to the element in 'range', or nullptr if not found.
90 
//
91 
// This helper function is typically used to simplify code like:
92 
//     auto it = std::ranges::lower_bound(myMap, name, {}, &Element::name);
93 
//     if ((it != myMap.end()) && (it->name == name)) {
94 
//         ... use *it
95 
//     }
96 
// Note that this code needs to check both for the end-iterator and that the
97 
// element was actually found. By using binary_find() this complexity is hidden:
98 
//     if (auto m = binary_find(myMap, name, {}, &Element::name)) {
99 
//         ... use *m
100 
//     }
101 
template<std::ranges::forward_range Range, typename T, typename Compare = std::less<>, typename Proj = std::identity>
102 
[[nodiscard]] auto* binary_find(Range&& range, const T& value, Compare comp = {}, Proj proj = {})
103 
{
104 
	auto it = std::ranges::lower_bound(range, value, comp, proj);
105 
	return ((it != std::ranges::end(range)) && (!std::invoke(comp, value, std::invoke(proj, *it))))
106 
	       ? std::to_address(it)
107 
	       : nullptr;
108 
}
109
110 
// Convenience function to convert part of an array (or vector, ...) into a
111 
// span. These are not part of the c++ ranges namespace, but often these results
112 
// are then further used in range algorithms, that's why I placed them in this
113 
// header.
114 
template<std::ranges::range Range>
115 
[[nodiscard]] constexpr auto subspan(Range&& range, size_t offset, size_t count = std::dynamic_extent)
116 
{
117 
	return std::span(std::forward<Range>(range)).subspan(offset, count);
118 
}
119
120 
template<size_t Count, std::ranges::range Range>
121 
[[nodiscard]] constexpr auto subspan(Range&& range, size_t offset = 0)
122 
{
123 
	return std::span(std::forward<Range>(range)).subspan(offset).template first<Count>();
124 
}
125
126 
template<typename T, size_t Size>
127 
[[nodiscard]] inline auto as_byte_span(std::span<T, Size> s)
128 
{
129 
	return std::span{std::bit_cast<const uint8_t*>(s.data()), s.size_bytes()};
130 
}
131
132 
#endif