| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (C) 2010 Google Inc. All rights reserved. | 2 * Copyright (C) 2010 Google Inc. All rights reserved. |
| 3 * | 3 * |
| 4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
| 5 * modification, are permitted provided that the following conditions | 5 * modification, are permitted provided that the following conditions |
| 6 * are met: | 6 * are met: |
| 7 * | 7 * |
| 8 * 1. Redistributions of source code must retain the above copyright | 8 * 1. Redistributions of source code must retain the above copyright |
| 9 * notice, this list of conditions and the following disclaimer. | 9 * notice, this list of conditions and the following disclaimer. |
| 10 * 2. Redistributions in binary form must reproduce the above copyright | 10 * 2. Redistributions in binary form must reproduce the above copyright |
| (...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 60 PODIntervalTree<float> tree; | 60 PODIntervalTree<float> tree; |
| 61 tree.add(PODInterval<float>(2, 4)); | 61 tree.add(PODInterval<float>(2, 4)); |
| 62 ASSERT_TRUE(tree.checkInvariants()); | 62 ASSERT_TRUE(tree.checkInvariants()); |
| 63 } | 63 } |
| 64 | 64 |
| 65 TEST(PODIntervalTreeTest, TestInsertionAndQuery) | 65 TEST(PODIntervalTreeTest, TestInsertionAndQuery) |
| 66 { | 66 { |
| 67 PODIntervalTree<float> tree; | 67 PODIntervalTree<float> tree; |
| 68 tree.add(PODInterval<float>(2, 4)); | 68 tree.add(PODInterval<float>(2, 4)); |
| 69 ASSERT_TRUE(tree.checkInvariants()); | 69 ASSERT_TRUE(tree.checkInvariants()); |
| 70 Vector<PODInterval<float> > result = tree.allOverlaps(PODInterval<float>(1,
3)); | 70 Vector<PODInterval<float>> result = tree.allOverlaps(PODInterval<float>(1, 3
)); |
| 71 EXPECT_EQ(1U, result.size()); | 71 EXPECT_EQ(1U, result.size()); |
| 72 EXPECT_EQ(2, result[0].low()); | 72 EXPECT_EQ(2, result[0].low()); |
| 73 EXPECT_EQ(4, result[0].high()); | 73 EXPECT_EQ(4, result[0].high()); |
| 74 } | 74 } |
| 75 | 75 |
| 76 TEST(PODIntervalTreeTest, TestQueryAgainstZeroSizeInterval) | 76 TEST(PODIntervalTreeTest, TestQueryAgainstZeroSizeInterval) |
| 77 { | 77 { |
| 78 PODIntervalTree<float> tree; | 78 PODIntervalTree<float> tree; |
| 79 tree.add(PODInterval<float>(1, 2.5)); | 79 tree.add(PODInterval<float>(1, 2.5)); |
| 80 tree.add(PODInterval<float>(3.5, 5)); | 80 tree.add(PODInterval<float>(3.5, 5)); |
| 81 tree.add(PODInterval<float>(2, 4)); | 81 tree.add(PODInterval<float>(2, 4)); |
| 82 ASSERT_TRUE(tree.checkInvariants()); | 82 ASSERT_TRUE(tree.checkInvariants()); |
| 83 Vector<PODInterval<float> > result = tree.allOverlaps(PODInterval<float>(3,
3)); | 83 Vector<PODInterval<float>> result = tree.allOverlaps(PODInterval<float>(3, 3
)); |
| 84 EXPECT_EQ(1U, result.size()); | 84 EXPECT_EQ(1U, result.size()); |
| 85 EXPECT_EQ(2, result[0].low()); | 85 EXPECT_EQ(2, result[0].low()); |
| 86 EXPECT_EQ(4, result[0].high()); | 86 EXPECT_EQ(4, result[0].high()); |
| 87 } | 87 } |
| 88 | 88 |
| 89 #ifndef NDEBUG | 89 #ifndef NDEBUG |
| 90 template<> | 90 template<> |
| 91 struct ValueToString<int*> { | 91 struct ValueToString<int*> { |
| 92 static String string(int* const& value) | 92 static String string(int* const& value) |
| 93 { | 93 { |
| (...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 150 } | 150 } |
| 151 | 151 |
| 152 TEST(PODIntervalTreeTest, TestQueryingOfComplexUserData) | 152 TEST(PODIntervalTreeTest, TestQueryingOfComplexUserData) |
| 153 { | 153 { |
| 154 PODIntervalTree<float, UserData1> tree; | 154 PODIntervalTree<float, UserData1> tree; |
| 155 UserData1 data1; | 155 UserData1 data1; |
| 156 data1.a = 5; | 156 data1.a = 5; |
| 157 data1.b = 6; | 157 data1.b = 6; |
| 158 tree.add(tree.createInterval(2, 4, data1)); | 158 tree.add(tree.createInterval(2, 4, data1)); |
| 159 ASSERT_TRUE(tree.checkInvariants()); | 159 ASSERT_TRUE(tree.checkInvariants()); |
| 160 Vector<PODInterval<float, UserData1> > overlaps = tree.allOverlaps(tree.crea
teInterval(3, 5, data1)); | 160 Vector<PODInterval<float, UserData1>> overlaps = tree.allOverlaps(tree.creat
eInterval(3, 5, data1)); |
| 161 EXPECT_EQ(1U, overlaps.size()); | 161 EXPECT_EQ(1U, overlaps.size()); |
| 162 EXPECT_EQ(5, overlaps[0].data().a); | 162 EXPECT_EQ(5, overlaps[0].data().a); |
| 163 EXPECT_EQ(6, overlaps[0].data().b); | 163 EXPECT_EQ(6, overlaps[0].data().b); |
| 164 } | 164 } |
| 165 | 165 |
| 166 namespace { | 166 namespace { |
| 167 | 167 |
| 168 class EndpointType1 { | 168 class EndpointType1 { |
| 169 public: | 169 public: |
| 170 explicit EndpointType1(int value) | 170 explicit EndpointType1(int value) |
| (...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 215 #endif | 215 #endif |
| 216 | 216 |
| 217 namespace { | 217 namespace { |
| 218 | 218 |
| 219 void InsertionAndDeletionTest(int32_t seed, int treeSize) | 219 void InsertionAndDeletionTest(int32_t seed, int treeSize) |
| 220 { | 220 { |
| 221 initRandom(seed); | 221 initRandom(seed); |
| 222 int maximumValue = treeSize; | 222 int maximumValue = treeSize; |
| 223 // Build the tree | 223 // Build the tree |
| 224 PODIntervalTree<int> tree; | 224 PODIntervalTree<int> tree; |
| 225 Vector<PODInterval<int> > addedElements; | 225 Vector<PODInterval<int>> addedElements; |
| 226 Vector<PODInterval<int> > removedElements; | 226 Vector<PODInterval<int>> removedElements; |
| 227 for (int i = 0; i < treeSize; i++) { | 227 for (int i = 0; i < treeSize; i++) { |
| 228 int left = nextRandom(maximumValue); | 228 int left = nextRandom(maximumValue); |
| 229 int length = nextRandom(maximumValue); | 229 int length = nextRandom(maximumValue); |
| 230 PODInterval<int> interval(left, left + length); | 230 PODInterval<int> interval(left, left + length); |
| 231 tree.add(interval); | 231 tree.add(interval); |
| 232 #ifdef DEBUG_INSERTION_AND_DELETION_TEST | 232 #ifdef DEBUG_INSERTION_AND_DELETION_TEST |
| 233 WTF_LOG_ERROR("*** Adding element %s", ValueToString<PODInterval<int> >:
:string(interval).ascii().data()); | 233 WTF_LOG_ERROR("*** Adding element %s", ValueToString<PODInterval<int>>::
string(interval).ascii().data()); |
| 234 #endif | 234 #endif |
| 235 addedElements.append(interval); | 235 addedElements.append(interval); |
| 236 } | 236 } |
| 237 // Churn the tree's contents. | 237 // Churn the tree's contents. |
| 238 // First remove half of the elements in random order. | 238 // First remove half of the elements in random order. |
| 239 for (int i = 0; i < treeSize / 2; i++) { | 239 for (int i = 0; i < treeSize / 2; i++) { |
| 240 int index = nextRandom(addedElements.size()); | 240 int index = nextRandom(addedElements.size()); |
| 241 #ifdef DEBUG_INSERTION_AND_DELETION_TEST | 241 #ifdef DEBUG_INSERTION_AND_DELETION_TEST |
| 242 WTF_LOG_ERROR("*** Removing element %s", ValueToString<PODInterval<int>
>::string(addedElements[index]).ascii().data()); | 242 WTF_LOG_ERROR("*** Removing element %s", ValueToString<PODInterval<int>>
::string(addedElements[index]).ascii().data()); |
| 243 #endif | 243 #endif |
| 244 ASSERT_TRUE(tree.contains(addedElements[index])) << "Test failed for see
d " << seed; | 244 ASSERT_TRUE(tree.contains(addedElements[index])) << "Test failed for see
d " << seed; |
| 245 tree.remove(addedElements[index]); | 245 tree.remove(addedElements[index]); |
| 246 removedElements.append(addedElements[index]); | 246 removedElements.append(addedElements[index]); |
| 247 addedElements.remove(index); | 247 addedElements.remove(index); |
| 248 ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; | 248 ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; |
| 249 } | 249 } |
| 250 // Now randomly add or remove elements. | 250 // Now randomly add or remove elements. |
| 251 for (int i = 0; i < 2 * treeSize; i++) { | 251 for (int i = 0; i < 2 * treeSize; i++) { |
| 252 bool add = false; | 252 bool add = false; |
| 253 if (!addedElements.size()) | 253 if (!addedElements.size()) |
| 254 add = true; | 254 add = true; |
| 255 else if (!removedElements.size()) | 255 else if (!removedElements.size()) |
| 256 add = false; | 256 add = false; |
| 257 else | 257 else |
| 258 add = (nextRandom(2) == 1); | 258 add = (nextRandom(2) == 1); |
| 259 if (add) { | 259 if (add) { |
| 260 int index = nextRandom(removedElements.size()); | 260 int index = nextRandom(removedElements.size()); |
| 261 #ifdef DEBUG_INSERTION_AND_DELETION_TEST | 261 #ifdef DEBUG_INSERTION_AND_DELETION_TEST |
| 262 WTF_LOG_ERROR("*** Adding element %s", ValueToString<PODInterval<int
> >::string(removedElements[index]).ascii().data()); | 262 WTF_LOG_ERROR("*** Adding element %s", ValueToString<PODInterval<int
>>::string(removedElements[index]).ascii().data()); |
| 263 #endif | 263 #endif |
| 264 tree.add(removedElements[index]); | 264 tree.add(removedElements[index]); |
| 265 addedElements.append(removedElements[index]); | 265 addedElements.append(removedElements[index]); |
| 266 removedElements.remove(index); | 266 removedElements.remove(index); |
| 267 } else { | 267 } else { |
| 268 int index = nextRandom(addedElements.size()); | 268 int index = nextRandom(addedElements.size()); |
| 269 #ifdef DEBUG_INSERTION_AND_DELETION_TEST | 269 #ifdef DEBUG_INSERTION_AND_DELETION_TEST |
| 270 WTF_LOG_ERROR("*** Removing element %s", ValueToString<PODInterval<i
nt> >::string(addedElements[index]).ascii().data()); | 270 WTF_LOG_ERROR("*** Removing element %s", ValueToString<PODInterval<i
nt>>::string(addedElements[index]).ascii().data()); |
| 271 #endif | 271 #endif |
| 272 ASSERT_TRUE(tree.contains(addedElements[index])) << "Test failed for
seed " << seed; | 272 ASSERT_TRUE(tree.contains(addedElements[index])) << "Test failed for
seed " << seed; |
| 273 ASSERT_TRUE(tree.remove(addedElements[index])) << "Test failed for s
eed " << seed; | 273 ASSERT_TRUE(tree.remove(addedElements[index])) << "Test failed for s
eed " << seed; |
| 274 removedElements.append(addedElements[index]); | 274 removedElements.append(addedElements[index]); |
| 275 addedElements.remove(index); | 275 addedElements.remove(index); |
| 276 } | 276 } |
| 277 ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; | 277 ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; |
| 278 } | 278 } |
| 279 } | 279 } |
| 280 | 280 |
| (...skipping 60 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 341 ASSERT_TRUE(tree.checkInvariants()); | 341 ASSERT_TRUE(tree.checkInvariants()); |
| 342 tree.add(tree.createInterval(3, 5)); | 342 tree.add(tree.createInterval(3, 5)); |
| 343 ASSERT_TRUE(tree.checkInvariants()); | 343 ASSERT_TRUE(tree.checkInvariants()); |
| 344 tree.add(tree.createInterval(4, 12)); | 344 tree.add(tree.createInterval(4, 12)); |
| 345 ASSERT_TRUE(tree.checkInvariants()); | 345 ASSERT_TRUE(tree.checkInvariants()); |
| 346 tree.remove(tree.createInterval(4, 12)); | 346 tree.remove(tree.createInterval(4, 12)); |
| 347 ASSERT_TRUE(tree.checkInvariants()); | 347 ASSERT_TRUE(tree.checkInvariants()); |
| 348 } | 348 } |
| 349 | 349 |
| 350 } // namespace blink | 350 } // namespace blink |
| OLD | NEW |