code.vuplus.com Git - vuplus_webkit/blob - Source/WebKit/chromium/tests/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
  30 #include "PODIntervalTree.h"
  31
  32 #include "Logging.h"
  33 #include "TreeTestHelpers.h"
  34 #include <gtest/gtest.h>
  35 #include <wtf/Vector.h>
  36 #include <wtf/text/WTFString.h>
  37
  38 namespace WebCore {
  39
  40 using TreeTestHelpers::generateSeed;
  41 using TreeTestHelpers::initRandom;
  42 using TreeTestHelpers::nextRandom;
  43
  44 #ifndef NDEBUG
  45 template<>
  46 struct ValueToString<float> {
  47     static String string(const float& value) { return String::number(value); }
  48 };
  49
  50 template<>
  51 struct ValueToString<void*> {
  52     static String string(void* const& value)
  53     {
  54         return String::format("0x%p", value);
  55     }
  56 };
  57 #endif
  58
  59 TEST(PODIntervalTreeTest, TestInsertion)
  60 {
  61     PODIntervalTree<float> tree;
  62     tree.add(PODInterval<float>(2, 4));
  63     ASSERT_TRUE(tree.checkInvariants());
  64 }
  65
  66 TEST(PODIntervalTreeTest, TestInsertionAndQuery)
  67 {
  68     PODIntervalTree<float> tree;
  69     tree.add(PODInterval<float>(2, 4));
  70     ASSERT_TRUE(tree.checkInvariants());
  71     Vector<PODInterval<float> > result = tree.allOverlaps(PODInterval<float>(1, 3));
  72     EXPECT_EQ(1U, result.size());
  73     EXPECT_EQ(2, result[0].low());
  74     EXPECT_EQ(4, result[0].high());
  75 }
  76
  77 TEST(PODIntervalTreeTest, TestQueryAgainstZeroSizeInterval)
  78 {
  79     PODIntervalTree<float> tree;
  80     tree.add(PODInterval<float>(1, 2.5));
  81     tree.add(PODInterval<float>(3.5, 5));
  82     tree.add(PODInterval<float>(2, 4));
  83     ASSERT_TRUE(tree.checkInvariants());
  84     Vector<PODInterval<float> > result = tree.allOverlaps(PODInterval<float>(3, 3));
  85     EXPECT_EQ(1U, result.size());
  86     EXPECT_EQ(2, result[0].low());
  87     EXPECT_EQ(4, result[0].high());
  88 }
  89
  90 #ifndef NDEBUG
  91 template<>
  92 struct ValueToString<int*> {
  93     static String string(int* const& value)
  94     {
  95         return String::format("0x%p", value);
  96     }
  97 };
  98 #endif
  99
 100 TEST(PODIntervalTreeTest, TestDuplicateElementInsertion)
 101 {
 102     PODIntervalTree<float, int*> tree;
 103     int tmp1 = 1;
 104     int tmp2 = 2;
 105     typedef PODIntervalTree<float, int*>::IntervalType IntervalType;
 106     IntervalType interval1(1, 3, &tmp1);
 107     IntervalType interval2(1, 3, &tmp2);
 108     tree.add(interval1);
 109     tree.add(interval2);
 110     ASSERT_TRUE(tree.checkInvariants());
 111     EXPECT_TRUE(tree.contains(interval1));
 112     EXPECT_TRUE(tree.contains(interval2));
 113     EXPECT_TRUE(tree.remove(interval1));
 114     EXPECT_TRUE(tree.contains(interval2));
 115     EXPECT_FALSE(tree.contains(interval1));
 116     EXPECT_TRUE(tree.remove(interval2));
 117     EXPECT_EQ(0, tree.size());
 118 }
 119
 120 namespace {
 121
 122 struct UserData1 {
 123 public:
 124     UserData1()
 125         : a(0), b(1) { }
 126
 127     float a;
 128     int b;
 129 };
 130
 131 } // anonymous namespace
 132
 133 #ifndef NDEBUG
 134 template<>
 135 struct ValueToString<UserData1> {
 136     static String string(const UserData1& value)
 137     {
 138         return String("[UserData1 a=") + String::number(value.a) + " b=" + String::number(value.b) + "]";
 139     }
 140 };
 141 #endif
 142
 143 TEST(PODIntervalTreeTest, TestInsertionOfComplexUserData)
 144 {
 145     PODIntervalTree<float, UserData1> tree;
 146     UserData1 data1;
 147     data1.a = 5;
 148     data1.b = 6;
 149     tree.add(tree.createInterval(2, 4, data1));
 150     ASSERT_TRUE(tree.checkInvariants());
 151 }
 152
 153 TEST(PODIntervalTreeTest, TestQueryingOfComplexUserData)
 154 {
 155     PODIntervalTree<float, UserData1> tree;
 156     UserData1 data1;
 157     data1.a = 5;
 158     data1.b = 6;
 159     tree.add(tree.createInterval(2, 4, data1));
 160     ASSERT_TRUE(tree.checkInvariants());
 161     Vector<PODInterval<float, UserData1> > overlaps = tree.allOverlaps(tree.createInterval(3, 5, data1));
 162     EXPECT_EQ(1U, overlaps.size());
 163     EXPECT_EQ(5, overlaps[0].data().a);
 164     EXPECT_EQ(6, overlaps[0].data().b);
 165 }
 166
 167 namespace {
 168
 169 class EndpointType1 {
 170 public:
 171     explicit EndpointType1(int value)
 172         : m_value(value) { }
 173
 174     int value() const { return m_value; }
 175
 176     bool operator<(const EndpointType1& other) const { return m_value < other.m_value; }
 177     bool operator==(const EndpointType1& other) const { return m_value == other.m_value; }
 178
 179 private:
 180     int m_value;
 181     // These operators should not be called by the interval tree.
 182     bool operator>(const EndpointType1& other);
 183     bool operator<=(const EndpointType1& other);
 184     bool operator>=(const EndpointType1& other);
 185     bool operator!=(const EndpointType1& other);
 186 };
 187
 188 } // anonymous namespace
 189
 190 #ifndef NDEBUG
 191 template<>
 192 struct ValueToString<EndpointType1> {
 193     static String string(const EndpointType1& value)
 194     {
 195         return String("[EndpointType1 value=") + String::number(value.value()) + "]";
 196     }
 197 };
 198 #endif
 199
 200 TEST(PODIntervalTreeTest, TestTreeDoesNotRequireMostOperators)
 201 {
 202     PODIntervalTree<EndpointType1> tree;
 203     tree.add(tree.createInterval(EndpointType1(1), EndpointType1(2)));
 204     ASSERT_TRUE(tree.checkInvariants());
 205 }
 206
 207 // Uncomment to debug a failure of the insertion and deletion test. Won't work
 208 // in release builds.
 209 // #define DEBUG_INSERTION_AND_DELETION_TEST
 210
 211 #ifndef NDEBUG
 212 template<>
 213 struct ValueToString<int> {
 214     static String string(const int& value) { return String::number(value); }
 215 };
 216 #endif
 217
 218 namespace {
 219
 220 void InsertionAndDeletionTest(int32_t seed, int treeSize)
 221 {
 222     initRandom(seed);
 223     int maximumValue = treeSize;
 224     // Build the tree
 225     PODIntervalTree<int> tree;
 226     Vector<PODInterval<int> > addedElements;
 227     Vector<PODInterval<int> > removedElements;
 228     for (int i = 0; i < treeSize; i++) {
 229         int left = nextRandom(maximumValue);
 230         int length = nextRandom(maximumValue);
 231         PODInterval<int> interval(left, left + length);
 232         tree.add(interval);
 233 #ifdef DEBUG_INSERTION_AND_DELETION_TEST
 234         LOG_ERROR("*** Adding element %s", ValueToString<PODInterval<int> >::string(interval).ascii().data());
 235 #endif
 236         addedElements.append(interval);
 237     }
 238     // Churn the tree's contents.
 239     // First remove half of the elements in random order.
 240     for (int i = 0; i < treeSize / 2; i++) {
 241         int index = nextRandom(addedElements.size());
 242 #ifdef DEBUG_INSERTION_AND_DELETION_TEST
 243         LOG_ERROR("*** Removing element %s", ValueToString<PODInterval<int> >::string(addedElements[index]).ascii().data());
 244 #endif
 245         ASSERT_TRUE(tree.contains(addedElements[index])) << "Test failed for seed " << seed;
 246         tree.remove(addedElements[index]);
 247         removedElements.append(addedElements[index]);
 248         addedElements.remove(index);
 249         ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed;
 250     }
 251     // Now randomly add or remove elements.
 252     for (int i = 0; i < 2 * treeSize; i++) {
 253         bool add = false;
 254         if (!addedElements.size())
 255             add = true;
 256         else if (!removedElements.size())
 257             add = false;
 258         else
 259             add = (nextRandom(2) == 1);
 260         if (add) {
 261             int index = nextRandom(removedElements.size());
 262 #ifdef DEBUG_INSERTION_AND_DELETION_TEST
 263             LOG_ERROR("*** Adding element %s", ValueToString<PODInterval<int> >::string(removedElements[index]).ascii().data());
 264 #endif
 265             tree.add(removedElements[index]);
 266             addedElements.append(removedElements[index]);
 267             removedElements.remove(index);
 268         } else {
 269             int index = nextRandom(addedElements.size());
 270 #ifdef DEBUG_INSERTION_AND_DELETION_TEST
 271             LOG_ERROR("*** Removing element %s", ValueToString<PODInterval<int> >::string(addedElements[index]).ascii().data());
 272 #endif
 273             ASSERT_TRUE(tree.contains(addedElements[index])) << "Test failed for seed " << seed;
 274             ASSERT_TRUE(tree.remove(addedElements[index])) << "Test failed for seed " << seed;
 275             removedElements.append(addedElements[index]);
 276             addedElements.remove(index);
 277         }
 278         ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed;
 279     }
 280 }
 281
 282 } // anonymous namespace
 283
 284 TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest1)
 285 {
 286     InsertionAndDeletionTest(13972, 100);
 287 }
 288
 289 TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest2)
 290 {
 291     InsertionAndDeletionTest(1283382113, 10);
 292 }
 293
 294 TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest3)
 295 {
 296     // This is the sequence of insertions and deletions that triggered
 297     // the failure in RandomDeletionAndInsertionRegressionTest2.
 298     PODIntervalTree<int> tree;
 299     tree.add(tree.createInterval(0, 5));
 300     ASSERT_TRUE(tree.checkInvariants());
 301     tree.add(tree.createInterval(4, 5));
 302     ASSERT_TRUE(tree.checkInvariants());
 303     tree.add(tree.createInterval(8, 9));
 304     ASSERT_TRUE(tree.checkInvariants());
 305     tree.add(tree.createInterval(1, 4));
 306     ASSERT_TRUE(tree.checkInvariants());
 307     tree.add(tree.createInterval(3, 5));
 308     ASSERT_TRUE(tree.checkInvariants());
 309     tree.add(tree.createInterval(4, 12));
 310     ASSERT_TRUE(tree.checkInvariants());
 311     tree.add(tree.createInterval(0, 2));
 312     ASSERT_TRUE(tree.checkInvariants());
 313     tree.add(tree.createInterval(0, 2));
 314     ASSERT_TRUE(tree.checkInvariants());
 315     tree.add(tree.createInterval(9, 13));
 316     ASSERT_TRUE(tree.checkInvariants());
 317     tree.add(tree.createInterval(0, 1));
 318     ASSERT_TRUE(tree.checkInvariants());
 319     tree.remove(tree.createInterval(0, 2));
 320     ASSERT_TRUE(tree.checkInvariants());
 321     tree.remove(tree.createInterval(9, 13));
 322     ASSERT_TRUE(tree.checkInvariants());
 323     tree.remove(tree.createInterval(0, 2));
 324     ASSERT_TRUE(tree.checkInvariants());
 325     tree.remove(tree.createInterval(0, 1));
 326     ASSERT_TRUE(tree.checkInvariants());
 327     tree.remove(tree.createInterval(4, 5));
 328     ASSERT_TRUE(tree.checkInvariants());
 329     tree.remove(tree.createInterval(4, 12));
 330     ASSERT_TRUE(tree.checkInvariants());
 331 }
 332
 333 TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest4)
 334 {
 335     // Even further reduced test case for RandomDeletionAndInsertionRegressionTest3.
 336     PODIntervalTree<int> tree;
 337     tree.add(tree.createInterval(0, 5));
 338     ASSERT_TRUE(tree.checkInvariants());
 339     tree.add(tree.createInterval(8, 9));
 340     ASSERT_TRUE(tree.checkInvariants());
 341     tree.add(tree.createInterval(1, 4));
 342     ASSERT_TRUE(tree.checkInvariants());
 343     tree.add(tree.createInterval(3, 5));
 344     ASSERT_TRUE(tree.checkInvariants());
 345     tree.add(tree.createInterval(4, 12));
 346     ASSERT_TRUE(tree.checkInvariants());
 347     tree.remove(tree.createInterval(4, 12));
 348     ASSERT_TRUE(tree.checkInvariants());
 349 }
 350
 351 TEST(PODIntervalTreeTest, TestRandomDeletionAndInsertion)
 352 {
 353     InsertionAndDeletionTest(generateSeed(), 1000);
 354 }
 355
 356 } // namespace WebCore