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 357
