added visit_ranges generic utility function

4 files changed, 148 insertions, 0 deletions

diff --git a/vespalib/CMakeLists.txt b/vespalib/CMakeLists.txt
index a76b8848b47..9339cdacea0 100644
--- a/vespalib/CMakeLists.txt
+++ b/vespalib/CMakeLists.txt
@@ -131,6 +131,7 @@ vespa_define_module(
     src/tests/util/md5
     src/tests/util/rcuvector
     src/tests/valgrind
+    src/tests/visit_ranges
     src/tests/websocket
     src/tests/zcurve
 
diff --git a/vespalib/src/tests/visit_ranges/CMakeLists.txt b/vespalib/src/tests/visit_ranges/CMakeLists.txt
new file mode 100644
index 00000000000..de94b2ebb1e
--- /dev/null
+++ b/vespalib/src/tests/visit_ranges/CMakeLists.txt
@@ -0,0 +1,9 @@
+# Copyright 2020 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+vespa_add_executable(vespalib_visit_ranges_test_app TEST
+    SOURCES
+    visit_ranges_test.cpp
+    DEPENDS
+    vespalib
+    gtest
+)
+vespa_add_test(NAME vespalib_visit_ranges_test_app COMMAND vespalib_visit_ranges_test_app)
diff --git a/vespalib/src/tests/visit_ranges/visit_ranges_test.cpp b/vespalib/src/tests/visit_ranges/visit_ranges_test.cpp
new file mode 100644
index 00000000000..d6e83b4d495
--- /dev/null
+++ b/vespalib/src/tests/visit_ranges/visit_ranges_test.cpp
@@ -0,0 +1,99 @@
+// Copyright 2020 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include <vespa/vespalib/util/overload.h>
+#include <vespa/vespalib/util/visit_ranges.h>
+#include <vespa/vespalib/gtest/gtest.h>
+#include <variant>
+#include <string>
+
+using namespace vespalib;
+
+TEST(VisitRangesTest, empty_ranges_can_be_visited) {
+    std::vector<int> a;
+    std::vector<int> b;
+    std::vector<int> c;
+    auto visitor = overload
+                   {
+                       [&c](visit_ranges_either, int) {
+                           c.push_back(42);
+                       },
+                       [&c](visit_ranges_both, int, int) {
+                           c.push_back(42);
+                       }
+                   };
+    vespalib::visit_ranges(visitor, a.begin(), a.end(), b.begin(), b.end());
+    EXPECT_EQ(c, std::vector<int>({}));
+}
+
+TEST(VisitRangesTest, simple_merge_can_be_implemented) {
+    std::vector<int> a({1,3,7});
+    std::vector<int> b({2,3,8});
+    std::vector<int> c;
+    auto visitor = overload
+                   {
+                       [&c](visit_ranges_either, int x) {
+                           c.push_back(x);
+                       },
+                       [&c](visit_ranges_both, int x, int y) {
+                           c.push_back(x);
+                           c.push_back(y);
+                       }
+                   };
+    vespalib::visit_ranges(visitor, a.begin(), a.end(), b.begin(), b.end());
+    EXPECT_EQ(c, std::vector<int>({1,2,3,3,7,8}));
+}
+
+TEST(VisitRangesTest, simple_union_can_be_implemented) {
+    std::vector<int> a({1,3,7});
+    std::vector<int> b({2,3,8});
+    std::vector<int> c;
+    auto visitor = overload
+                   {
+                       [&c](visit_ranges_either, int x) {
+                           c.push_back(x);
+                       },
+                       [&c](visit_ranges_both, int x, int) {
+                           c.push_back(x);
+                       }
+                   };
+    vespalib::visit_ranges(visitor, a.begin(), a.end(), b.begin(), b.end());
+    EXPECT_EQ(c, std::vector<int>({1,2,3,7,8}));
+}
+
+TEST(VisitRangesTest, asymmetric_merge_can_be_implemented) {
+    std::vector<int> a({1,3,7});
+    std::vector<int> b({2,3,8});
+    std::vector<int> c;
+    auto visitor = overload
+                   {
+                       [&c](visit_ranges_first, int x) {
+                           c.push_back(x);
+                       },
+                       [&c](visit_ranges_second, int) {},
+                       [&c](visit_ranges_both, int x, int y) {
+                           c.push_back(x * y);
+                       }
+                   };
+    vespalib::visit_ranges(visitor, a.begin(), a.end(), b.begin(), b.end());
+    EXPECT_EQ(c, std::vector<int>({1,9,7}));
+}
+
+TEST(VisitRangesTest, comparator_can_be_specified) {
+    std::vector<int> a({7,3,1});
+    std::vector<int> b({8,3,2});
+    std::vector<int> c;
+    auto visitor = overload
+                   {
+                       [&c](visit_ranges_either, int x) {
+                           c.push_back(x);
+                       },
+                       [&c](visit_ranges_both, int x, int y) {
+                           c.push_back(x);
+                           c.push_back(y);
+                       }
+                   };
+    vespalib::visit_ranges(visitor, a.begin(), a.end(), b.begin(), b.end(), std::greater<>());
+    EXPECT_EQ(c, std::vector<int>({8,7,3,3,2,1}));
+}
+
+GTEST_MAIN_RUN_ALL_TESTS()
diff --git a/vespalib/src/vespa/vespalib/util/visit_ranges.h b/vespalib/src/vespa/vespalib/util/visit_ranges.h
new file mode 100644
index 00000000000..70e2d9c2da6
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/visit_ranges.h
@@ -0,0 +1,39 @@
+// Copyright 2020 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include <functional>
+
+namespace vespalib {
+
+struct visit_ranges_either {};
+struct visit_ranges_first : visit_ranges_either {};
+struct visit_ranges_second : visit_ranges_either {};
+struct visit_ranges_both {};
+
+template <typename V, typename ItA, typename ItB, typename Cmp = std::less<> >
+void visit_ranges(V &&visitor, ItA pos_a, ItA end_a, ItB pos_b, ItB end_b, Cmp cmp = Cmp()) {
+    while ((pos_a != end_a) && (pos_b != end_b)) {
+        if (cmp(*pos_a, *pos_b)) {
+            visitor(visit_ranges_first(), *pos_a);
+            ++pos_a;
+        } else if (cmp(*pos_b, *pos_a)) {
+            visitor(visit_ranges_second(), *pos_b);
+            ++pos_b;
+        } else {
+            visitor(visit_ranges_both(), *pos_a, *pos_b);
+            ++pos_a;
+            ++pos_b;
+        }
+    }
+    while (pos_a != end_a) {
+        visitor(visit_ranges_first(), *pos_a);
+        ++pos_a;
+    }
+    while (pos_b != end_b) {
+        visitor(visit_ranges_second(), *pos_b);
+        ++pos_b;
+    }
+}
+
+}