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

media/blink/interval_map_unittest.cc

+// 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 range 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 rangemap, so making this too big will the test down a lot.
+const int kTestSize = 16;
+
+class SimpleIntervalMap {
+ public:
+  SimpleIntervalMap() : data_(kTestSize) {}
+
+  void IncrementRange(int32_t from, int32_t to, int32_t how_much) {
+    for (int32_t i = from; i < to; i++) {
+      data_[i] += how_much;
+    }
+  }
+
+  void SetRange(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 IncrementRange(int32_t from, int32_t to, int32_t how_much) {
+    truth_.IncrementRange(from, to, how_much);
+    testee_.IncrementRange(from, to, how_much);
+    std::string message =
+        base::StringPrintf("After [%d - %d) += %d", from, to, how_much);
+    Compare(message);
+  }
+
+  void SetRange(int32_t from, int32_t to, int32_t how_much) {
+    truth_.SetRange(from, to, how_much);
+    testee_.SetRange(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_range = 0;
+    int32_t num_ranges = 0;
+    for (const auto& r : testee_) {
+      num_ranges++;
+      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_range, 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_range = 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) << "Range:  " << r.first.begin << " - " << r.first.end
+                   << " = " << r.second;
+      }
+    }
+  }
+
+  void Clear() {
+    for (int j = 0; j < kTestSize; j++) {
+      IncrementRange(j, j + 1, -truth_[j]);
+    }
+  }
+
+ protected:
+  media::TestRandom rnd_;
+  SimpleIntervalMap truth_;
+  media::IntervalMap<int32_t, int32_t> testee_;
+};
+}
+
+TEST_F(IntervalMapTest, SimpleTest) {
+  IncrementRange(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]);
+  IncrementRange(3, 7, -4);
+  EXPECT_TRUE(testee_.empty());
+}
+
+TEST_F(IntervalMapTest, SimpleIncrementTest) {
+  IncrementRange(3, 7, 1);
+  IncrementRange(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]);
+  SetRange(3, 12, 0);
+  EXPECT_TRUE(testee_.empty());
+}
+
+TEST_F(IntervalMapTest, IncrementJoinRangesTest) {
+  IncrementRange(3, 5, 1);
+  IncrementRange(7, 8, 1);
+  IncrementRange(9, 11, 1);
+  IncrementRange(5, 7, 1);
+  IncrementRange(8, 9, 1);
+  auto i = testee_.find(5);
+  EXPECT_EQ(3, i.range_begin());
+  EXPECT_EQ(11, i.range_end());
+  EXPECT_EQ(1, i.value());
+}
+
+TEST_F(IntervalMapTest, SetJoinRangesTest) {
+  SetRange(3, 5, 1);
+  SetRange(7, 8, 1);
+  SetRange(9, 11, 1);
+  SetRange(5, 9, 1);  // overwrites one range
+  auto i = testee_.find(5);
+  EXPECT_EQ(3, i.range_begin());
+  EXPECT_EQ(11, i.range_end());
+  EXPECT_EQ(1, i.value());
+}
+
+TEST_F(IntervalMapTest, FindTest) {
+  IncrementRange(5, 6, 1);
+  IncrementRange(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.range_begin());
+  EXPECT_EQ(1, i.range_end());
+  EXPECT_EQ(0, i.value());
+  i = testee_.find(4);
+  EXPECT_EQ(1, i.range_begin());
+  EXPECT_EQ(5, i.range_end());
+  EXPECT_EQ(2, i.value());
+  i = testee_.find(5);
+  EXPECT_EQ(5, i.range_begin());
+  EXPECT_EQ(6, i.range_end());
+  EXPECT_EQ(3, i.value());
+  i = testee_.find(6);
+  EXPECT_EQ(6, i.range_begin());
+  EXPECT_EQ(10, i.range_end());
+  EXPECT_EQ(2, i.value());
+  i = testee_.find(9);
+  EXPECT_EQ(6, i.range_begin());
+  EXPECT_EQ(10, i.range_end());
+  EXPECT_EQ(2, i.value());
+  i = testee_.find(10);
+  EXPECT_EQ(10, i.range_begin());
+  EXPECT_EQ(max_value, i.range_end());
+  EXPECT_EQ(0, i.value());
+}
+

[xhwang, 2015/11/12 18:24:58]

Can you add a test to cover MIN_INT, MAX_INT etc?

[hubbe, 2015/11/12 19:03:13]

Done.

+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);
+      IncrementRange(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);
+      SetRange(begin, end, rnd_.Rand() & 3);
+      if (HasFailure()) {
+        return;
+      }
+    }
+  }
+}