[Scummvm-git-logs] scummvm master -> 4248f351f36658f2e0b35245b2b3283320a4666a

[grisenti]

This automated email contains information about 1 new commit which have been
pushed to the 'scummvm' repo located at https://github.com/scummvm/scummvm .

Summary:
4248f351f3 COMMON: add upperBound and lowerBound to algorithm


Commit: 4248f351f36658f2e0b35245b2b3283320a4666a
    https://github.com/scummvm/scummvm/commit/4248f351f36658f2e0b35245b2b3283320a4666a
Author: grisenti (emanuele at grisenti.net)
Date: 2023-06-01T18:28:01+02:00

Commit Message:
COMMON: add upperBound and lowerBound to algorithm

Changed paths:
    common/algorithm.h


diff --git a/common/algorithm.h b/common/algorithm.h
index 7b4fc188f14..943d4e6fc76 100644
--- a/common/algorithm.h
+++ b/common/algorithm.h
@@ -414,6 +414,40 @@ It remove(It first, It last, const T& val) {
 	return first;
 }
 
+/**
+ * Finds the first item in the range [first, last) for which comp(item, val)
+ * (item < val by default) is false.
+ * This function is the equivalent of std::lower_bound for random access iterators.
+ */
+template<typename RandomIt, typename V, typename Comp = Less<V> >
+RandomIt lowerBound(RandomIt first, RandomIt last, const V &val, Comp comp = {}) {
+	while (first < last) {
+		const RandomIt mid = first + distance(first, last) / 2;
+		if (comp(*mid, val))
+			first = mid + 1;
+		else
+			last = mid;
+	}
+	return first;
+}
+
+/**
+ * Finds the first item in the range [first, last) for which comp(val, item)
+ * (val < item by default) is true.
+ * This function is the equivalent of std::upper_bound for random access iterators.
+ */
+template<typename RandomIt, typename V, typename Comp = Less<V> >
+RandomIt upperBound(RandomIt first, RandomIt last, const V &val, Comp comp = {}) {
+	while (first < last) {
+		const RandomIt mid = first + distance(first, last) / 2;
+		if (!comp(val, *mid))
+			first = mid + 1;
+		else
+			last = mid;
+	}
+	return first;
+}
+
 /** @} */
 
 } // End of namespace Common