third_party/WebKit/Source/platform/PODIntervalTreeTest.cpp

   1 /*
   2  * Copyright (C) 2010 Google Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * 1.  Redistributions of source code must retain the above copyright
   9  *     notice, this list of conditions and the following disclaimer.
  10  * 2.  Redistributions in binary form must reproduce the above copyright
  11  *     notice, this list of conditions and the following disclaimer in the
  12  *     documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
  15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  16  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  17  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
  18  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  19  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  20  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  21  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  23  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 // Tests for the interval tree class.
  27
  28 #include "config.h"
  29 #include "platform/PODIntervalTree.h"
  30
  31 #include "platform/Logging.h"
  32 #include "platform/testing/TreeTestHelpers.h"
  33 #include "wtf/Vector.h"
  34 #include "wtf/text/WTFString.h"
  35
  36 #include <gtest/gtest.h>
  37
  38 namespace blink {
  39
  40 using TreeTestHelpers::initRandom;
  41 using TreeTestHelpers::nextRandom;
  42
  43 #ifndef NDEBUG
  44 template<>
  45 struct ValueToString<float> {
  46     static String string(const float& value) { return String::number(value); }
  47 };
  48
  49 template<>
  50 struct ValueToString<void*> {
  51     static String string(void* const& value)
  52     {
  53         return String::format("0x%p", value);
  54     }
  55 };
  56 #endif
  57
  58 TEST(PODIntervalTreeTest, TestInsertion)
  59 {
  60     PODIntervalTree<float> tree;
  61     tree.add(PODInterval<float>(2, 4));
  62     ASSERT_TRUE(tree.checkInvariants());
  63 }
  64
  65 TEST(PODIntervalTreeTest, TestInsertionAndQuery)
  66 {
  67     PODIntervalTree<float> tree;
  68     tree.add(PODInterval<float>(2, 4));
  69     ASSERT_TRUE(tree.checkInvariants());
  70     Vector<PODInterval<float>> result = tree.allOverlaps(PODInterval<float>(1, 3));
  71     EXPECT_EQ(1U, result.size());
  72     EXPECT_EQ(2, result[0].low());
  73     EXPECT_EQ(4, result[0].high());
  74 }
  75
  76 TEST(PODIntervalTreeTest, TestQueryAgainstZeroSizeInterval)
  77 {
  78     PODIntervalTree<float> tree;
  79     tree.add(PODInterval<float>(1, 2.5));
  80     tree.add(PODInterval<float>(3.5, 5));
  81     tree.add(PODInterval<float>(2, 4));
  82     ASSERT_TRUE(tree.checkInvariants());
  83     Vector<PODInterval<float>> result = tree.allOverlaps(PODInterval<float>(3, 3));
  84     EXPECT_EQ(1U, result.size());
  85     EXPECT_EQ(2, result[0].low());
  86     EXPECT_EQ(4, result[0].high());
  87 }
  88
  89 #ifndef NDEBUG
  90 template<>
  91 struct ValueToString<int*> {
  92     static String string(int* const& value)
  93     {
  94         return String::format("0x%p", value);
  95     }
  96 };
  97 #endif
  98
  99 TEST(PODIntervalTreeTest, TestDuplicateElementInsertion)
 100 {
 101     PODIntervalTree<float, int*> tree;
 102     int tmp1 = 1;
 103     int tmp2 = 2;
 104     typedef PODIntervalTree<float, int*>::IntervalType IntervalType;
 105     IntervalType interval1(1, 3, &tmp1);
 106     IntervalType interval2(1, 3, &tmp2);
 107     tree.add(interval1);
 108     tree.add(interval2);
 109     ASSERT_TRUE(tree.checkInvariants());
 110     EXPECT_TRUE(tree.contains(interval1));
 111     EXPECT_TRUE(tree.contains(interval2));
 112     EXPECT_TRUE(tree.remove(interval1));
 113     EXPECT_TRUE(tree.contains(interval2));
 114     EXPECT_FALSE(tree.contains(interval1));
 115     EXPECT_TRUE(tree.remove(interval2));
 116     EXPECT_EQ(0, tree.size());
 117 }
 118
 119 namespace {
 120
 121 struct UserData1 {
 122 public:
 123     UserData1()
 124         : a(0), b(1) { }
 125
 126     float a;
 127     int b;
 128 };
 129
 130 } // anonymous namespace
 131
 132 #ifndef NDEBUG
 133 template<>
 134 struct ValueToString<UserData1> {
 135     static String string(const UserData1& value)
 136     {
 137         return String("[UserData1 a=") + String::number(value.a) + " b=" + String::number(value.b) + "]";
 138     }
 139 };
 140 #endif
 141
 142 TEST(PODIntervalTreeTest, TestInsertionOfComplexUserData)
 143 {
 144     PODIntervalTree<float, UserData1> tree;
 145     UserData1 data1;
 146     data1.a = 5;
 147     data1.b = 6;
 148     tree.add(tree.createInterval(2, 4, data1));
 149     ASSERT_TRUE(tree.checkInvariants());
 150 }
 151
 152 TEST(PODIntervalTreeTest, TestQueryingOfComplexUserData)
 153 {
 154     PODIntervalTree<float, UserData1> tree;
 155     UserData1 data1;
 156     data1.a = 5;
 157     data1.b = 6;
 158     tree.add(tree.createInterval(2, 4, data1));
 159     ASSERT_TRUE(tree.checkInvariants());
 160     Vector<PODInterval<float, UserData1>> overlaps = tree.allOverlaps(tree.createInterval(3, 5, data1));
 161     EXPECT_EQ(1U, overlaps.size());
 162     EXPECT_EQ(5, overlaps[0].data().a);
 163     EXPECT_EQ(6, overlaps[0].data().b);
 164 }
 165
 166 namespace {
 167
 168 class EndpointType1 {
 169 public:
 170     explicit EndpointType1(int value)
 171         : m_value(value) { }
 172
 173     int value() const { return m_value; }
 174
 175     bool operator<(const EndpointType1& other) const { return m_value < other.m_value; }
 176     bool operator==(const EndpointType1& other) const { return m_value == other.m_value; }
 177
 178 private:
 179     int m_value;
 180     // These operators should not be called by the interval tree.
 181     bool operator>(const EndpointType1& other);
 182     bool operator<=(const EndpointType1& other);
 183     bool operator>=(const EndpointType1& other);
 184     bool operator!=(const EndpointType1& other);
 185 };
 186
 187 } // anonymous namespace
 188
 189 #ifndef NDEBUG
 190 template<>
 191 struct ValueToString<EndpointType1> {
 192     static String string(const EndpointType1& value)
 193     {
 194         return String("[EndpointType1 value=") + String::number(value.value()) + "]";
 195     }
 196 };
 197 #endif
 198
 199 TEST(PODIntervalTreeTest, TestTreeDoesNotRequireMostOperators)
 200 {
 201     PODIntervalTree<EndpointType1> tree;
 202     tree.add(tree.createInterval(EndpointType1(1), EndpointType1(2)));
 203     ASSERT_TRUE(tree.checkInvariants());
 204 }
 205
 206 // Uncomment to debug a failure of the insertion and deletion test. Won't work
 207 // in release builds.
 208 // #define DEBUG_INSERTION_AND_DELETION_TEST
 209
 210 #ifndef NDEBUG
 211 template<>
 212 struct ValueToString<int> {
 213     static String string(const int& value) { return String::number(value); }
 214 };
 215 #endif
 216
 217 namespace {
 218
 219 void InsertionAndDeletionTest(int32_t seed, int treeSize)
 220 {
 221     initRandom(seed);
 222     int maximumValue = treeSize;
 223     // Build the tree
 224     PODIntervalTree<int> tree;
 225     Vector<PODInterval<int>> addedElements;
 226     Vector<PODInterval<int>> removedElements;
 227     for (int i = 0; i < treeSize; i++) {
 228         int left = nextRandom(maximumValue);
 229         int length = nextRandom(maximumValue);
 230         PODInterval<int> interval(left, left + length);
 231         tree.add(interval);
 232 #ifdef DEBUG_INSERTION_AND_DELETION_TEST
 233         WTF_LOG_ERROR("*** Adding element %s", ValueToString<PODInterval<int>>::string(interval).ascii().data());
 234 #endif
 235         addedElements.append(interval);
 236     }
 237     // Churn the tree's contents.
 238     // First remove half of the elements in random order.
 239     for (int i = 0; i < treeSize / 2; i++) {
 240         int index = nextRandom(addedElements.size());
 241 #ifdef DEBUG_INSERTION_AND_DELETION_TEST
 242         WTF_LOG_ERROR("*** Removing element %s", ValueToString<PODInterval<int>>::string(addedElements[index]).ascii().data());
 243 #endif
 244         ASSERT_TRUE(tree.contains(addedElements[index])) << "Test failed for seed " << seed;
 245         tree.remove(addedElements[index]);
 246         removedElements.append(addedElements[index]);
 247         addedElements.remove(index);
 248         ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed;
 249     }
 250     // Now randomly add or remove elements.
 251     for (int i = 0; i < 2 * treeSize; i++) {
 252         bool add = false;
 253         if (!addedElements.size())
 254             add = true;
 255         else if (!removedElements.size())
 256             add = false;
 257         else
 258             add = (nextRandom(2) == 1);
 259         if (add) {
 260             int index = nextRandom(removedElements.size());
 261 #ifdef DEBUG_INSERTION_AND_DELETION_TEST
 262             WTF_LOG_ERROR("*** Adding element %s", ValueToString<PODInterval<int>>::string(removedElements[index]).ascii().data());
 263 #endif
 264             tree.add(removedElements[index]);
 265             addedElements.append(removedElements[index]);
 266             removedElements.remove(index);
 267         } else {
 268             int index = nextRandom(addedElements.size());
 269 #ifdef DEBUG_INSERTION_AND_DELETION_TEST
 270             WTF_LOG_ERROR("*** Removing element %s", ValueToString<PODInterval<int>>::string(addedElements[index]).ascii().data());
 271 #endif
 272             ASSERT_TRUE(tree.contains(addedElements[index])) << "Test failed for seed " << seed;
 273             ASSERT_TRUE(tree.remove(addedElements[index])) << "Test failed for seed " << seed;
 274             removedElements.append(addedElements[index]);
 275             addedElements.remove(index);
 276         }
 277         ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed;
 278     }
 279 }
 280
 281 } // anonymous namespace
 282
 283 TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest1)
 284 {
 285     InsertionAndDeletionTest(13972, 100);
 286 }
 287
 288 TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest2)
 289 {
 290     InsertionAndDeletionTest(1283382113, 10);
 291 }
 292
 293 TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest3)
 294 {
 295     // This is the sequence of insertions and deletions that triggered
 296     // the failure in RandomDeletionAndInsertionRegressionTest2.
 297     PODIntervalTree<int> tree;
 298     tree.add(tree.createInterval(0, 5));
 299     ASSERT_TRUE(tree.checkInvariants());
 300     tree.add(tree.createInterval(4, 5));
 301     ASSERT_TRUE(tree.checkInvariants());
 302     tree.add(tree.createInterval(8, 9));
 303     ASSERT_TRUE(tree.checkInvariants());
 304     tree.add(tree.createInterval(1, 4));
 305     ASSERT_TRUE(tree.checkInvariants());
 306     tree.add(tree.createInterval(3, 5));
 307     ASSERT_TRUE(tree.checkInvariants());
 308     tree.add(tree.createInterval(4, 12));
 309     ASSERT_TRUE(tree.checkInvariants());
 310     tree.add(tree.createInterval(0, 2));
 311     ASSERT_TRUE(tree.checkInvariants());
 312     tree.add(tree.createInterval(0, 2));
 313     ASSERT_TRUE(tree.checkInvariants());
 314     tree.add(tree.createInterval(9, 13));
 315     ASSERT_TRUE(tree.checkInvariants());
 316     tree.add(tree.createInterval(0, 1));
 317     ASSERT_TRUE(tree.checkInvariants());
 318     tree.remove(tree.createInterval(0, 2));
 319     ASSERT_TRUE(tree.checkInvariants());
 320     tree.remove(tree.createInterval(9, 13));
 321     ASSERT_TRUE(tree.checkInvariants());
 322     tree.remove(tree.createInterval(0, 2));
 323     ASSERT_TRUE(tree.checkInvariants());
 324     tree.remove(tree.createInterval(0, 1));
 325     ASSERT_TRUE(tree.checkInvariants());
 326     tree.remove(tree.createInterval(4, 5));
 327     ASSERT_TRUE(tree.checkInvariants());
 328     tree.remove(tree.createInterval(4, 12));
 329     ASSERT_TRUE(tree.checkInvariants());
 330 }
 331
 332 TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest4)
 333 {
 334     // Even further reduced test case for RandomDeletionAndInsertionRegressionTest3.
 335     PODIntervalTree<int> tree;
 336     tree.add(tree.createInterval(0, 5));
 337     ASSERT_TRUE(tree.checkInvariants());
 338     tree.add(tree.createInterval(8, 9));
 339     ASSERT_TRUE(tree.checkInvariants());
 340     tree.add(tree.createInterval(1, 4));
 341     ASSERT_TRUE(tree.checkInvariants());
 342     tree.add(tree.createInterval(3, 5));
 343     ASSERT_TRUE(tree.checkInvariants());
 344     tree.add(tree.createInterval(4, 12));
 345     ASSERT_TRUE(tree.checkInvariants());
 346     tree.remove(tree.createInterval(4, 12));
 347     ASSERT_TRUE(tree.checkInvariants());
 348 }
 349
 350 } // namespace blink