RangeMap: A int->int mapping with fast range operations

media/blink/interval_map_unittest.cc

Index: media/blink/interval_map_unittest.cc
diff --git a/media/blink/interval_map_unittest.cc b/media/blink/interval_map_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..bfcf9a088f05117a1a8c5700f4603d43c47b6362
--- /dev/null
+++ b/media/blink/interval_map_unittest.cc
@@ -0,0 +1,272 @@
+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <stdint.h>
+
+#include <string>
+
+#include "base/strings/stringprintf.h"
+#include "media/blink/interval_map.h"
+#include "media/blink/test_random.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace {
+
+// Our tests only modifiy the interval map entries in [0..kTestSize).
+// We need this to be big enough to hit tricky corner cases, but small
+// enough that we get lots of entry duplication to clean up.
+// Also, SimpleIntervalMap uses a vector of size kTestSize to emulate
+// a intervalmap, so making this too big will the test down a lot.
+const int kTestSize = 16;
+
+class SimpleIntervalMap {
+ public:
+  SimpleIntervalMap() : data_(kTestSize) {}
+
+  void IncrementInterval(int32_t from, int32_t to, int32_t how_much) {
+    for (int32_t i = from; i < to; i++) {
+      data_[i] += how_much;
+    }
+  }
+
+  void SetInterval(int32_t from, int32_t to, int32_t how_much) {
+    for (int32_t i = from; i < to; i++) {
+      data_[i] = how_much;
+    }
+  }
+
+  int32_t operator[](int32_t index) const { return data_[index]; }
+
+ private:
+  std::vector<int32_t> data_;
+};
+
+class IntervalMapTest : public testing::Test {
+ public:
+  IntervalMapTest() : rnd_(42) {}
+  void IncrementInterval(int32_t from, int32_t to, int32_t how_much) {
+    truth_.IncrementInterval(from, to, how_much);
+    testee_.IncrementInterval(from, to, how_much);
+    std::string message =
+        base::StringPrintf("After [%d - %d) += %d", from, to, how_much);
+    Compare(message);
+  }
+
+  void SetInterval(int32_t from, int32_t to, int32_t how_much) {
+    truth_.SetInterval(from, to, how_much);
+    testee_.SetInterval(from, to, how_much);
+    std::string message =
+        base::StringPrintf("After [%d - %d) += %d", from, to, how_much);
+    Compare(message);
+  }
+
+  // Will exercise operator[] and IntervalMap::const_iterator.
+  void Compare(const std::string& message) {
+    bool had_fail = HasFailure();
+    for (int i = 0; i < kTestSize; i++) {
+      EXPECT_EQ(truth_[i], testee_[i]) << " i = " << i << " " << message;
+    }
+    EXPECT_EQ(testee_[-1], 0) << message;
+    EXPECT_EQ(testee_[kTestSize], 0) << message;
+    int32_t prev_ = 0;
+    int32_t end_of_last_interval = 0;
+    int32_t num_intervals = 0;
+    for (const auto& r : testee_) {
+      num_intervals++;
+      EXPECT_LT(r.first.begin, r.first.end);
+      if (r.first.begin == std::numeric_limits<int32_t>::min()) {
+        EXPECT_EQ(0, r.second);
+      } else {
+        EXPECT_EQ(end_of_last_interval, r.first.begin);
+        EXPECT_GE(r.first.begin, 0) << message;
+        EXPECT_LE(r.first.begin, kTestSize) << message;
+        EXPECT_NE(r.second, prev_) << message;
+      }
+      end_of_last_interval = r.first.end;
+      prev_ = r.second;
+    }
+    EXPECT_EQ(prev_, 0) << message;
+
+    if (HasFailure() && !had_fail) {
+      for (int i = 0; i < kTestSize; i++) {
+        LOG(ERROR) << i << ": Truth =" << truth_[i]
+                   << " Testee = " << testee_[i];
+      }
+      for (const auto& r : testee_) {
+        LOG(ERROR) << "Interval:  " << r.first.begin << " - " << r.first.end
+                   << " = " << r.second;
+      }
+    }
+  }
+
+  void Clear() {
+    for (int j = 0; j < kTestSize; j++) {
+      IncrementInterval(j, j + 1, -truth_[j]);
+    }
+  }
+
+ protected:
+  media::TestRandom rnd_;
+  SimpleIntervalMap truth_;
+  media::IntervalMap<int32_t, int32_t> testee_;
+};
+}
+
+TEST_F(IntervalMapTest, SimpleTest) {
+  IncrementInterval(3, 7, 4);
+  EXPECT_EQ(0, testee_[0]);
+  EXPECT_EQ(0, testee_[2]);
+  EXPECT_EQ(4, testee_[3]);
+  EXPECT_EQ(4, testee_[5]);
+  EXPECT_EQ(4, testee_[6]);
+  EXPECT_EQ(0, testee_[7]);
+  IncrementInterval(3, 7, -4);
+  EXPECT_TRUE(testee_.empty());
+}
+
+TEST_F(IntervalMapTest, SimpleIncrementTest) {
+  IncrementInterval(3, 7, 1);
+  IncrementInterval(6, 10, 2);
+  EXPECT_EQ(0, testee_[2]);
+  EXPECT_EQ(1, testee_[3]);
+  EXPECT_EQ(1, testee_[5]);
+  EXPECT_EQ(3, testee_[6]);
+  EXPECT_EQ(2, testee_[7]);
+  EXPECT_EQ(2, testee_[9]);
+  EXPECT_EQ(0, testee_[10]);
+  SetInterval(3, 12, 0);
+  EXPECT_TRUE(testee_.empty());
+}
+
+TEST_F(IntervalMapTest, IncrementJoinIntervalsTest) {
+  IncrementInterval(3, 5, 1);
+  IncrementInterval(7, 8, 1);
+  IncrementInterval(9, 11, 1);
+  IncrementInterval(5, 7, 1);
+  IncrementInterval(8, 9, 1);
+  auto i = testee_.find(5);
+  EXPECT_EQ(3, i.interval_begin());
+  EXPECT_EQ(11, i.interval_end());
+  EXPECT_EQ(1, i.value());
+}
+
+TEST_F(IntervalMapTest, SetJoinIntervalsTest) {
+  SetInterval(3, 5, 1);
+  SetInterval(7, 8, 1);
+  SetInterval(9, 11, 1);
+  SetInterval(5, 9, 1);  // overwrites one interval
+  auto i = testee_.find(5);
+  EXPECT_EQ(3, i.interval_begin());
+  EXPECT_EQ(11, i.interval_end());
+  EXPECT_EQ(1, i.value());
+}
+
+TEST_F(IntervalMapTest, FindTest) {
+  IncrementInterval(5, 6, 1);
+  IncrementInterval(1, 10, 2);
+  int32_t min_value = std::numeric_limits<int32_t>::min();
+  int32_t max_value = std::numeric_limits<int32_t>::max();
+  auto i = testee_.find(0);
+  EXPECT_EQ(min_value, i.interval_begin());
+  EXPECT_EQ(1, i.interval_end());
+  EXPECT_EQ(0, i.value());
+  i = testee_.find(4);
+  EXPECT_EQ(1, i.interval_begin());
+  EXPECT_EQ(5, i.interval_end());
+  EXPECT_EQ(2, i.value());
+  i = testee_.find(5);
+  EXPECT_EQ(5, i.interval_begin());
+  EXPECT_EQ(6, i.interval_end());
+  EXPECT_EQ(3, i.value());
+  i = testee_.find(6);
+  EXPECT_EQ(6, i.interval_begin());
+  EXPECT_EQ(10, i.interval_end());
+  EXPECT_EQ(2, i.value());
+  i = testee_.find(9);
+  EXPECT_EQ(6, i.interval_begin());
+  EXPECT_EQ(10, i.interval_end());
+  EXPECT_EQ(2, i.value());
+  i = testee_.find(10);
+  EXPECT_EQ(10, i.interval_begin());
+  EXPECT_EQ(max_value, i.interval_end());
+  EXPECT_EQ(0, i.value());
+}
+
+TEST_F(IntervalMapTest, MinMaxInt) {
+  int32_t min_value = std::numeric_limits<int32_t>::min();
+  int32_t max_value = std::numeric_limits<int32_t>::max();
+
+  // Change a single value at minint
+  testee_.IncrementInterval(min_value, min_value + 1, 7);
+  EXPECT_EQ(7, testee_[min_value]);
+  EXPECT_EQ(0, testee_[min_value + 1]);
+  auto i = testee_.find(0);
+  EXPECT_EQ(min_value + 1, i.interval_begin());
+  EXPECT_EQ(max_value, i.interval_end());
+  EXPECT_EQ(0, i.value());
+  --i;
+  EXPECT_TRUE(i == testee_.find(min_value));
+  EXPECT_EQ(min_value, i.interval_begin());
+  EXPECT_EQ(min_value + 1, i.interval_end());
+  EXPECT_EQ(7, i.value());
+  testee_.clear();
+
+  // Change a single value at maxint
+  // Note that we don't actually have a way to represent a range
+  // that includes maxint as the end of the interval is non-inclusive.
+  testee_.IncrementInterval(max_value - 1, max_value, 7);
+  EXPECT_EQ(7, testee_[max_value - 1]);
+  EXPECT_EQ(0, testee_[max_value - 2]);
+  i = testee_.find(0);
+  EXPECT_EQ(min_value, i.interval_begin());
+  EXPECT_EQ(max_value - 1, i.interval_end());
+  EXPECT_EQ(0, i.value());
+  ++i;
+  EXPECT_TRUE(i == testee_.find(max_value - 1));
+  EXPECT_EQ(max_value - 1, i.interval_begin());
+  EXPECT_EQ(max_value, i.interval_end());
+  EXPECT_EQ(7, i.value());
+
+  testee_.clear();
+
+  // Change entire range (almost)
+  testee_.IncrementInterval(min_value, max_value, 17);
+  EXPECT_EQ(17, testee_[min_value]);
+  EXPECT_EQ(17, testee_[0]);
+  EXPECT_EQ(17, testee_[max_value - 1]);
+  i = testee_.find(0);
+  EXPECT_EQ(min_value, i.interval_begin());
+  EXPECT_EQ(max_value, i.interval_end());
+  EXPECT_EQ(17, i.value());
+  EXPECT_TRUE(i == testee_.find(max_value - 1));
+  EXPECT_TRUE(i == testee_.find(min_value));
+}
+
+TEST_F(IntervalMapTest, RandomIncrementTest) {
+  for (int j = 0; j < 200; j++) {
+    Clear();
+    for (int i = 0; i < 200; i++) {
+      int32_t begin = rnd_.Rand() % (kTestSize - 1);
+      int32_t end = begin + 1 + rnd_.Rand() % (kTestSize - begin - 1);
+      IncrementInterval(begin, end, (rnd_.Rand() & 32) ? 1 : -1);
+      if (HasFailure()) {
+        return;
+      }
+    }
+  }
+}
+
+TEST_F(IntervalMapTest, RandomSetTest) {
+  for (int j = 0; j < 200; j++) {
+    Clear();
+    for (int i = 0; i < 200; i++) {
+      int32_t begin = rnd_.Rand() % (kTestSize - 1);
+      int32_t end = begin + 1 + rnd_.Rand() % (kTestSize - begin - 1);
+      SetInterval(begin, end, rnd_.Rand() & 3);
+      if (HasFailure()) {
+        return;
+      }
+    }
+  }
+}