Added interval tree data structure and unit tests. This is built on

the red/black tree and is a key data structure in one of the
forthcoming algorithms in this code.

Review URL: http://codereview.chromium.org/594048

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@39284 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 498 insertions, 0 deletions

diff --git a/o3d/core/core.gyp b/o3d/core/core.gyp
index b864f31..92db6f7 100644
--- a/o3d/core/core.gyp
+++ b/o3d/core/core.gyp
@@ -270,6 +270,7 @@
         'cross/visitor_base.h',
         'cross/weak_ptr.h',
         'cross/gpu2d/arena.h',
+        'cross/gpu2d/interval_tree.h',
         'cross/gpu2d/red_black_tree.h',
       ],
       'direct_dependent_settings': {
@@ -512,6 +513,7 @@
           'cross/visitor_base_test.cc',
           'cross/weak_ptr_test.cc',
           'cross/gpu2d/arena_test.cc',
+          'cross/gpu2d/interval_tree_test.cc',
           'cross/gpu2d/red_black_tree_test.cc',
           'cross/gpu2d/tree_test_helpers.cc',
           'cross/gpu2d/tree_test_helpers.h',
diff --git a/o3d/core/cross/gpu2d/interval_tree.h b/o3d/core/cross/gpu2d/interval_tree.h
new file mode 100644
index 0000000..71a7ca1
--- /dev/null
+++ b/o3d/core/cross/gpu2d/interval_tree.h
@@ -0,0 +1,281 @@
+/*
+ * Copyright 2010, Google Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ *     * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *     * Neither the name of Google Inc. nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+
+#ifndef O3D_CORE_CROSS_GPU2D_INTERVAL_TREE_H_
+#define O3D_CORE_CROSS_GPU2D_INTERVAL_TREE_H_
+
+#include <vector>
+
+#include "base/logging.h"
+#include "core/cross/gpu2d/arena.h"
+#include "core/cross/gpu2d/red_black_tree.h"
+
+namespace o3d {
+namespace gpu2d {
+
+// Interval class which can hold an arbitrary type as its endpoints
+// and a piece of user data. An important characteristic for the
+// algorithms we use is that if two intervals have identical endpoints
+// but different user data, they are not considered to be equal. This
+// situation can arise when representing the vertical extents of
+// bounding boxes of overlapping triangles, where the pointer to the
+// triangle is the user data of the interval.
+//
+// The following constructors and operators must be implemented on
+// type T:
+//
+//   - Copy constructor (if user data is desired)
+//   - operator<
+//   - operator==
+//   - operator=
+//
+// If the UserData type is specified, it must support a copy
+// constructor and assignment operator.
+//
+// *Note* that the destructors of type T and UserData will *not* be
+// called by this class. They must not allocate any memory in their
+// constructors.
+//
+// Note that this class requires a copy constructor and assignment
+// operator in order to be stored in the red-black tree.
+template<class T, class UserData = void*>
+class Interval {
+ public:
+  // Constructor from endpoints. This constructor only works when the
+  // UserData type is a pointer or other type which can be initialized
+  // with NULL.
+  Interval(const T& low, const T& high)
+      : low_(low),
+        high_(high),
+        data_(NULL),
+        max_high_(high) {
+  }
+
+  // Constructor from two endpoints plus explicit user data.
+  Interval(const T& low, const T& high, const UserData data)
+      : low_(low),
+        high_(high),
+        data_(data),
+        max_high_(high) {
+  }
+
+  const T& low() const {
+    return low_;
+  }
+
+  const T& high() const {
+    return high_;
+  }
+
+  const UserData& data() const {
+    return data_;
+  }
+
+  // Returns true if this interval overlaps that specified by the
+  // given low and high endpoints.
+  bool Overlaps(const T& low, const T& high) const {
+    if (this->high() < low)
+      return false;
+    if (high < this->low())
+      return false;
+    if (this->high() == low || this->low() == high)
+      return false;
+    return true;
+  }
+
+  // Returns true if this interval overlaps the other.
+  bool Overlaps(const Interval& other) const {
+    return Overlaps(other.low(), other.high());
+  }
+
+  // Returns true if this interval is "less" than the other. The
+  // comparison is performed on the low endpoints of the intervals.
+  bool operator<(const Interval& other) const {
+    return low() < other.low();
+  }
+
+  // Returns true if this interval is strictly equal to the other,
+  // including comparison of the user data.
+  bool operator==(const Interval& other) const {
+    return (low() == other.low() &&
+            high() == other.high() &&
+            data() == other.data());
+  }
+
+  // Summary information needed for efficient queries.
+  const T& max_high() const {
+    return max_high_;
+  }
+
+  // Updates the cache of the summary information for this interval.
+  // It is not really const, but it does not affect the user-level
+  // state, and must be declared const to obey the contract in the
+  // RedBlackTree that Node::data() returns a const reference.
+  void set_max_high(const T& max_high) const {
+    max_high_ = max_high;
+  }
+
+ private:
+  T low_;
+  T high_;
+  UserData data_;
+  // See the documentation for set_max_high() for an explanation of
+  // why this must be mutable.
+  mutable T max_high_;
+};
+
+// Suppport for logging Intervals.
+template<class T, class UserData>
+std::ostream& operator<<(std::ostream& ostr,  // NOLINT
+                         const Interval<T, UserData>& arg) {
+  ostr << "[Interval (" << arg.low()
+       << ", " << arg.high()
+       << "), data " << arg.data() << "]";
+  return ostr;
+}
+
+// An interval tree, which is a form of augmented red-black tree. It
+// supports efficient (O(lg n)) insertion, removal and querying of
+// intervals in the tree.
+template<class T, class UserData = void*>
+class IntervalTree : public RedBlackTree<Interval<T, UserData> > {
+ public:
+  // Typedef to reduce typing when declaring intervals to be stored in
+  // this tree.
+  typedef Interval<T, UserData> IntervalType;
+
+  IntervalTree()
+      : RedBlackTree<IntervalType>() {
+    Init();
+  }
+
+  explicit IntervalTree(Arena* arena)
+      : RedBlackTree<IntervalType>(arena) {
+    Init();
+  }
+
+  // Returns all intervals in the tree which overlap the given query
+  // interval. The returned intervals are sorted by increasing low
+  // endpoint.
+  std::vector<IntervalType> AllOverlaps(const IntervalType& interval) {
+    std::vector<IntervalType> result;
+    AllOverlaps(interval, result);
+    return result;
+  }
+
+  // Returns all intervals in the tree which overlap the given query
+  // interval. The returned intervals are sorted by increasing low
+  // endpoint.
+  void AllOverlaps(const IntervalType& interval,
+                   std::vector<IntervalType>& result) {
+    // gcc requires explicit dereference of "this" here
+    SearchForOverlapsFrom(this->root(), interval, result);
+  }
+
+  // Helper to create interval objects.
+  static IntervalType MakeInterval(const T& low,
+                                   const T& high,
+                                   const UserData data = NULL) {
+    return IntervalType(low, high, data);
+  }
+
+ private:
+  typedef typename RedBlackTree<IntervalType>::Node IntervalNode;
+
+  // Initializes the tree.
+  void Init() {
+    // gcc requires explicit dereference of "this" here
+    this->set_needs_full_ordering_comparisons(true);
+  }
+
+  // Starting from the given node, adds all overlaps with the given
+  // interval to the result vector. The intervals are sorted by
+  // increasing low endpoint.
+  void SearchForOverlapsFrom(IntervalNode* node,
+                             const IntervalType& interval,
+                             std::vector<IntervalType>& res) {
+    if (node == NULL)
+      return;
+
+    // Because the intervals are sorted by left endpoint, inorder
+    // traversal produces results sorted as desired.
+
+    // See whether we need to traverse the left subtree.
+    IntervalNode* left = node->left();
+    if (left != NULL &&
+        interval.low() < left->data().max_high()) {
+      SearchForOverlapsFrom(left, interval, res);
+    }
+
+    // Check for overlap with current node.
+    if (node->data().Overlaps(interval)) {
+      res.push_back(node->data());
+    }
+
+    // See whether we need to traverse the right subtree.
+    if (node->data().low() < interval.high()) {
+      SearchForOverlapsFrom(node->right(), interval, res);
+    }
+  }
+
+  virtual bool UpdateNode(IntervalNode* node) {
+    // Would use const T&, but need to reassign this reference in this
+    // function.
+    const T* cur_max = &node->data().high();
+    IntervalNode* left = node->left();
+    if (left != NULL) {
+      if (*cur_max < left->data().max_high()) {
+        cur_max = &left->data().max_high();
+      }
+    }
+    IntervalNode* right = node->right();
+    if (right != NULL) {
+      if (*cur_max < right->data().max_high()) {
+        cur_max = &right->data().max_high();
+      }
+    }
+    // This is phrased like this to avoid needing operator!= on type T.
+    if (!(*cur_max == node->data().max_high())) {
+      node->data().set_max_high(*cur_max);
+      return true;
+    }
+    return false;
+  }
+
+  DISALLOW_COPY_AND_ASSIGN(IntervalTree);
+};
+
+}  // namespace gpu2d
+}  // namespace o3d
+
+#endif  // O3D_CORE_CROSS_GPU2D_INTERVAL_TREE_H_
+
diff --git a/o3d/core/cross/gpu2d/interval_tree_test.cc b/o3d/core/cross/gpu2d/interval_tree_test.cc
new file mode 100644
index 0000000..29118b2
--- /dev/null
+++ b/o3d/core/cross/gpu2d/interval_tree_test.cc
@@ -0,0 +1,215 @@
+/*
+ * Copyright 2010, Google Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ *     * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *     * Neither the name of Google Inc. nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+// Tests for the interval tree class.
+
+#include "core/cross/gpu2d/interval_tree.h"
+#include "core/cross/gpu2d/tree_test_helpers.h"
+#include "gtest/gtest.h"
+
+namespace o3d {
+namespace gpu2d {
+
+TEST(IntervalTreeTest, TestInsertion) {
+  IntervalTree<float> tree;
+  tree.Insert(Interval<float>(2, 4));
+  ASSERT_TRUE(tree.Verify());
+}
+
+TEST(IntervalTreeTest, TestInsertionAndQuery) {
+  IntervalTree<float> tree;
+  tree.Insert(Interval<float>(2, 4));
+  ASSERT_TRUE(tree.Verify());
+  std::vector<Interval<float> > res =
+      tree.AllOverlaps(Interval<float>(1, 3));
+  EXPECT_EQ(1U, res.size());
+  EXPECT_EQ(2, res[0].low());
+  EXPECT_EQ(4, res[0].high());
+}
+
+TEST(IntervalTreeTest, TestQueryAgainstZeroSizeInterval) {
+  IntervalTree<float> tree;
+  tree.Insert(Interval<float>(1, 2.5));
+  tree.Insert(Interval<float>(3.5, 5));
+  tree.Insert(Interval<float>(2, 4));
+  ASSERT_TRUE(tree.Verify());
+  std::vector<Interval<float> > res =
+      tree.AllOverlaps(Interval<float>(3, 3));
+  EXPECT_EQ(1U, res.size());
+  EXPECT_EQ(2, res[0].low());
+  EXPECT_EQ(4, res[0].high());
+}
+
+TEST(IntervalTreeTest, TestDuplicateElementInsertion) {
+  IntervalTree<float, int*> tree;
+  int tmp1 = 1;
+  int tmp2 = 2;
+  typedef IntervalTree<float, int*>::IntervalType IntervalType;
+  IntervalType interval1(1, 3, &tmp1);
+  IntervalType interval2(1, 3, &tmp2);
+  tree.Insert(interval1);
+  tree.Insert(interval2);
+  ASSERT_TRUE(tree.Verify());
+  EXPECT_TRUE(tree.Contains(interval1));
+  EXPECT_TRUE(tree.Contains(interval2));
+  EXPECT_TRUE(tree.Delete(interval1));
+  EXPECT_TRUE(tree.Contains(interval2));
+  EXPECT_FALSE(tree.Contains(interval1));
+  EXPECT_TRUE(tree.Delete(interval2));
+  EXPECT_EQ(0, tree.NumElements());
+}
+
+namespace {
+struct UserData1 {
+ public:
+  UserData1() : a(0), b(1) {
+  }
+
+  float a;
+  int b;
+};
+}  // anonymous namespace
+
+TEST(IntervalTreeTest, TestInsertionOfComplexUserData) {
+  IntervalTree<float, UserData1> tree;
+  UserData1 data1;
+  data1.a = 5;
+  data1.b = 6;
+  tree.Insert(tree.MakeInterval(2, 4, data1));
+  ASSERT_TRUE(tree.Verify());
+}
+
+TEST(IntervalTreeTest, TestQueryingOfComplexUserData) {
+  IntervalTree<float, UserData1> tree;
+  UserData1 data1;
+  data1.a = 5;
+  data1.b = 6;
+  tree.Insert(tree.MakeInterval(2, 4, data1));
+  ASSERT_TRUE(tree.Verify());
+  std::vector<Interval<float, UserData1> > overlaps =
+      tree.AllOverlaps(tree.MakeInterval(3, 5, data1));
+  EXPECT_EQ(1U, overlaps.size());
+  EXPECT_EQ(5, overlaps[0].data().a);
+  EXPECT_EQ(6, overlaps[0].data().b);
+}
+
+namespace {
+class EndpointType1 {
+ public:
+  explicit EndpointType1(int val) : val_(val) {
+  }
+
+  bool operator<(const EndpointType1& other) const {
+    return val_ < other.val_;
+  }
+
+  bool operator==(const EndpointType1& other) const {
+    return val_ == other.val_;
+  }
+
+ private:
+  int val_;
+  // These operators should not be required by the interval tree.
+  bool operator>(const EndpointType1& other);
+  bool operator<=(const EndpointType1& other);
+  bool operator>=(const EndpointType1& other);
+  bool operator!=(const EndpointType1& other);
+};
+}  // anonymous namespace
+
+TEST(IntervalTreeTest, TestTreeDoesNotRequireMostOperators) {
+  IntervalTree<EndpointType1> tree;
+  tree.Insert(tree.MakeInterval(EndpointType1(1), EndpointType1(2)));
+  ASSERT_TRUE(tree.Verify());
+}
+
+static void
+InsertionAndDeletionTest(unsigned seed, int tree_size) {
+  InitRandom(seed);
+  int max_val = tree_size;
+  // Build the tree
+  IntervalTree<int> tree;
+  std::vector<Interval<int> > added_elements;
+  std::vector<Interval<int> > removed_elements;
+  for (int i = 0; i < tree_size; i++) {
+    int left = NextRandom(max_val);
+    int len = NextRandom(max_val);
+    Interval<int> interval(left, left + len);
+    tree.Insert(interval);
+    added_elements.push_back(interval);
+  }
+  // Churn the tree's contents.
+  // First remove half of the elements in random order.
+  for (int i = 0; i < tree_size / 2; i++) {
+    int idx = NextRandom(added_elements.size());
+    tree.Insert(added_elements[idx]);
+    EXPECT_TRUE(tree.Verify()) << "Test failed for seed " << seed;
+    added_elements.erase(added_elements.begin() + idx);
+  }
+  // Now randomly add or remove elements.
+  for (int i = 0; i < 2 * tree_size; i++) {
+    bool add = false;
+    if (added_elements.size() == 0) {
+      add = true;
+    } else if (removed_elements.size() == 0) {
+      add = false;
+    } else {
+      add = (NextRandom(2) == 1);
+    }
+    if (add) {
+      int idx = NextRandom(removed_elements.size());
+      tree.Insert(removed_elements[idx]);
+      added_elements.push_back(removed_elements[idx]);
+      removed_elements.erase(removed_elements.begin() + idx);
+    } else {
+      int idx = NextRandom(added_elements.size());
+      EXPECT_TRUE(tree.Contains(added_elements[idx]))
+          << "Test failed for seed " << seed;
+      EXPECT_TRUE(tree.Delete(added_elements[idx]))
+          << "Test failed for seed " << seed;
+      removed_elements.push_back(added_elements[idx]);
+      added_elements.erase(added_elements.begin() + idx);
+    }
+    EXPECT_TRUE(tree.Verify()) << "Test failed for seed " << seed;
+  }
+}
+
+TEST(IntervalTreeTest, RandomDeletionAndInsertionRegressionTest1) {
+  InsertionAndDeletionTest((unsigned) 13972, 100);
+}
+
+TEST(IntervalTreeTest, TestRandomDeletionAndInsertion) {
+  InsertionAndDeletionTest((unsigned) GenerateSeed(), 1000);
+}
+
+}  // namespace gpu2d
+}  // namespace o3d
+