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 38namespace blink { 39 40using TreeTestHelpers::initRandom; 41using TreeTestHelpers::nextRandom; 42 43#ifndef NDEBUG 44template<> 45struct ValueToString<float> { 46 static String string(const float& value) { return String::number(value); } 47}; 48 49template<> 50struct ValueToString<void*> { 51 static String string(void* const& value) 52 { 53 return String::format("0x%p", value); 54 } 55}; 56#endif 57 58TEST(PODIntervalTreeTest, TestInsertion) 59{ 60 PODIntervalTree<float> tree; 61 tree.add(PODInterval<float>(2, 4)); 62 ASSERT_TRUE(tree.checkInvariants()); 63} 64 65TEST(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 76TEST(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 90template<> 91struct ValueToString<int*> { 92 static String string(int* const& value) 93 { 94 return String::format("0x%p", value); 95 } 96}; 97#endif 98 99TEST(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 119namespace { 120 121struct UserData1 { 122public: 123 UserData1() 124 : a(0), b(1) { } 125 126 float a; 127 int b; 128}; 129 130} // anonymous namespace 131 132#ifndef NDEBUG 133template<> 134struct 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 142TEST(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 152TEST(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 166namespace { 167 168class EndpointType1 { 169public: 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 178private: 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 190template<> 191struct ValueToString<EndpointType1> { 192 static String string(const EndpointType1& value) 193 { 194 return String("[EndpointType1 value=") + String::number(value.value()) + "]"; 195 } 196}; 197#endif 198 199TEST(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 211template<> 212struct ValueToString<int> { 213 static String string(const int& value) { return String::number(value); } 214}; 215#endif 216 217namespace { 218 219void 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 283TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest1) 284{ 285 InsertionAndDeletionTest(13972, 100); 286} 287 288TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest2) 289{ 290 InsertionAndDeletionTest(1283382113, 10); 291} 292 293TEST(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 332TEST(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