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 351
