1 files changed, 56 insertions, 0 deletions
diff --git a/extractor/veb_test.cc b/extractor/veb_test.cc
new file mode 100644
index 00000000..c40c9f28
--- /dev/null
+++ b/extractor/veb_test.cc
@@ -0,0 +1,56 @@
+#include <gtest/gtest.h>
+
+#include <algorithm>
+#include <vector>
+
+#include "veb.h"
+
+using namespace std;
+
+namespace {
+
+class VEBTest : public ::testing::Test {
+ protected:
+  void VEBSortTester(vector<int> values, int max_value) {
+    shared_ptr<VEB> veb = VEB::Create(max_value);
+    for (int value: values) {
+      veb->Insert(value);
+    }
+
+    sort(values.begin(), values.end());
+    EXPECT_EQ(values.front(), veb->GetMinimum());
+    EXPECT_EQ(values.back(), veb->GetMaximum());
+    for (size_t i = 0; i + 1 < values.size(); ++i) {
+      EXPECT_EQ(values[i + 1], veb->GetSuccessor(values[i]));
+    }
+    EXPECT_EQ(-1, veb->GetSuccessor(values.back()));
+  }
+};
+
+TEST_F(VEBTest, SmallRange) {
+  vector<int> values{8, 13, 5, 1, 4, 15, 2, 10, 6, 7};
+  VEBSortTester(values, 16);
+}
+
+TEST_F(VEBTest, MediumRange) {
+  vector<int> values{167, 243, 88, 12, 137, 199, 212, 45, 150, 189};
+  VEBSortTester(values, 255);
+}
+
+TEST_F(VEBTest, LargeRangeSparse) {
+  vector<int> values;
+  for (size_t i = 0; i < 100; ++i) {
+    values.push_back(i * 1000000);
+  }
+  VEBSortTester(values, 100000000);
+}
+
+TEST_F(VEBTest, LargeRangeDense) {
+  vector<int> values;
+  for (size_t i = 0; i < 1000000; ++i) {
+    values.push_back(i);
+  }
+  VEBSortTester(values, 1000000);
+}
+
+}  // namespace