[util] AdjacentFind + AdjacentFindBy

ref:76575abc5c39caf128339b56115c217c15766b51

2 files changed, 58 insertions, 0 deletions

diff --git a/util/generic/algorithm.h b/util/generic/algorithm.h
index bce242679f..d3b198fb23 100644
--- a/util/generic/algorithm.h
+++ b/util/generic/algorithm.h
@@ -714,6 +714,34 @@ constexpr std::pair<It, It> EqualRange(It begin, It end, const Val& val, Comp co
     return std::equal_range(begin, end, val, comp);
 }
 
+template <class TContainer>
+constexpr auto AdjacentFind(const TContainer& c) {
+    using std::begin;
+    using std::end;
+    return std::adjacent_find(begin(c), end(c));
+}
+
+template <class TContainer, class Compare>
+constexpr auto AdjacentFind(const TContainer& c, Compare comp) {
+    using std::begin;
+    using std::end;
+    return std::adjacent_find(begin(c), end(c), comp);
+}
+
+namespace NPrivate {
+    template <class TForwardIterator, class TGetKey>
+    constexpr TForwardIterator AdjacentFindBy(TForwardIterator begin, TForwardIterator end, const TGetKey& getKey) {
+        return std::adjacent_find(begin, end, [&](auto&& left, auto&& right) { return getKey(left) == getKey(right); });
+    }
+}
+
+template <class TContainer, class TGetKey>
+constexpr auto AdjacentFindBy(const TContainer& c, const TGetKey& getKey) {
+    using std::begin;
+    using std::end;
+    return ::NPrivate::AdjacentFindBy(begin(c), end(c), getKey);
+}
+
 template <class ForwardIt>
 constexpr bool IsSorted(ForwardIt begin, ForwardIt end) {
     return std::is_sorted(begin, end);
diff --git a/util/generic/algorithm_ut.cpp b/util/generic/algorithm_ut.cpp
index 72b326ebbe..4cdeef0a80 100644
--- a/util/generic/algorithm_ut.cpp
+++ b/util/generic/algorithm_ut.cpp
@@ -416,6 +416,36 @@ Y_UNIT_TEST_SUITE(TAlgorithm) {
         }
     }
 
+    Y_UNIT_TEST(AdjacentFindTest) {
+        TVector<int> v0;
+        UNIT_ASSERT_EQUAL(AdjacentFind(v0), v0.end());
+
+        TVector<int> v1 = {1};
+        UNIT_ASSERT_EQUAL(AdjacentFind(v1), v1.end());
+
+        const int v2[] = {8, 7, 6, 6, 5, 5, 5, 4, 3, 2, 1};
+        UNIT_ASSERT_EQUAL(AdjacentFind(v2), std::begin(v2) + 2);
+
+        TVector<TStringBuf> v3 = {"six", "five", "four", "three", "two", "one"};
+        UNIT_ASSERT_EQUAL(AdjacentFind(v3), v3.end());
+    }
+
+    Y_UNIT_TEST(AdjacentFindByTest) {
+        TVector<int> v0;
+        UNIT_ASSERT_EQUAL(AdjacentFindBy(v0, std::negate<int>()), v0.end());
+
+        TVector<int> v1 = {1};
+        UNIT_ASSERT_EQUAL(AdjacentFindBy(v1, std::negate<int>()), v1.end());
+
+        const int v2[] = {8, 7, 6, 6, 5, 5, 5, 4, 3, 2, 1};
+        UNIT_ASSERT_EQUAL(AdjacentFindBy(v2, std::negate<int>()), std::begin(v2) + 2);
+        UNIT_ASSERT_EQUAL(AdjacentFindBy(v2, [](const auto& e) { return e / 8; }), std::begin(v2) + 1);
+
+        TVector<TStringBuf> v3 = {"six", "five", "four", "three", "two", "one"};
+        UNIT_ASSERT_EQUAL(AdjacentFind(v3), v3.end());
+        UNIT_ASSERT_EQUAL(AdjacentFindBy(v3, std::mem_fn(&TStringBuf::size)), v3.begin() + 1);
+    }
+
     Y_UNIT_TEST(IsSortedTest) {
         TVector<int> v0;
         UNIT_ASSERT_VALUES_EQUAL(IsSorted(v0.begin(), v0.end()), true);