| 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 107 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 118 float a; | 118 float a; |
| 119 int b; | 119 int b; |
| 120 }; | 120 }; |
| 121 | 121 |
| 122 } // anonymous namespace | 122 } // anonymous namespace |
| 123 | 123 |
| 124 #ifndef NDEBUG | 124 #ifndef NDEBUG |
| 125 template <> | 125 template <> |
| 126 struct ValueToString<UserData1> { | 126 struct ValueToString<UserData1> { |
| 127 static String toString(const UserData1& value) { | 127 static String toString(const UserData1& value) { |
| 128 return String("[UserData1 a=") + String::number(value.a) + " b=" + | 128 return String("[UserData1 a=") + String::number(value.a) + |
| 129 String::number(value.b) + "]"; | 129 " b=" + String::number(value.b) + "]"; |
| 130 } | 130 } |
| 131 }; | 131 }; |
| 132 #endif | 132 #endif |
| 133 | 133 |
| 134 TEST(PODIntervalTreeTest, TestInsertionOfComplexUserData) { | 134 TEST(PODIntervalTreeTest, TestInsertionOfComplexUserData) { |
| 135 PODIntervalTree<float, UserData1> tree; | 135 PODIntervalTree<float, UserData1> tree; |
| 136 UserData1 data1; | 136 UserData1 data1; |
| 137 data1.a = 5; | 137 data1.a = 5; |
| 138 data1.b = 6; | 138 data1.b = 6; |
| 139 tree.add(tree.createInterval(2, 4, data1)); | 139 tree.add(tree.createInterval(2, 4, data1)); |
| (...skipping 89 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 229 } | 229 } |
| 230 // Churn the tree's contents. | 230 // Churn the tree's contents. |
| 231 // First remove half of the elements in random order. | 231 // First remove half of the elements in random order. |
| 232 for (int i = 0; i < treeSize / 2; i++) { | 232 for (int i = 0; i < treeSize / 2; i++) { |
| 233 int index = nextRandom(addedElements.size()); | 233 int index = nextRandom(addedElements.size()); |
| 234 #ifdef DEBUG_INSERTION_AND_DELETION_TEST | 234 #ifdef DEBUG_INSERTION_AND_DELETION_TEST |
| 235 DLOG(ERROR) << "*** Removing element " | 235 DLOG(ERROR) << "*** Removing element " |
| 236 << ValueToString<PODInterval<int>>::string( | 236 << ValueToString<PODInterval<int>>::string( |
| 237 addedElements[index]); | 237 addedElements[index]); |
| 238 #endif | 238 #endif |
| 239 ASSERT_TRUE(tree.contains(addedElements[index])) << "Test failed for seed " | 239 ASSERT_TRUE(tree.contains(addedElements[index])) |
| 240 << seed; | 240 << "Test failed for seed " << seed; |
| 241 tree.remove(addedElements[index]); | 241 tree.remove(addedElements[index]); |
| 242 removedElements.push_back(addedElements[index]); | 242 removedElements.push_back(addedElements[index]); |
| 243 addedElements.remove(index); | 243 addedElements.remove(index); |
| 244 ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; | 244 ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; |
| 245 } | 245 } |
| 246 // Now randomly add or remove elements. | 246 // Now randomly add or remove elements. |
| 247 for (int i = 0; i < 2 * treeSize; i++) { | 247 for (int i = 0; i < 2 * treeSize; i++) { |
| 248 bool add = false; | 248 bool add = false; |
| 249 if (!addedElements.size()) | 249 if (!addedElements.size()) |
| 250 add = true; | 250 add = true; |
| (...skipping 13 matching lines...) Expand all Loading... |
| 264 removedElements.remove(index); | 264 removedElements.remove(index); |
| 265 } else { | 265 } else { |
| 266 int index = nextRandom(addedElements.size()); | 266 int index = nextRandom(addedElements.size()); |
| 267 #ifdef DEBUG_INSERTION_AND_DELETION_TEST | 267 #ifdef DEBUG_INSERTION_AND_DELETION_TEST |
| 268 DLOG(ERROR) << "*** Removing element " | 268 DLOG(ERROR) << "*** Removing element " |
| 269 << ValueToString<PODInterval<int>>::string( | 269 << ValueToString<PODInterval<int>>::string( |
| 270 addedElements[index]); | 270 addedElements[index]); |
| 271 #endif | 271 #endif |
| 272 ASSERT_TRUE(tree.contains(addedElements[index])) | 272 ASSERT_TRUE(tree.contains(addedElements[index])) |
| 273 << "Test failed for seed " << seed; | 273 << "Test failed for seed " << seed; |
| 274 ASSERT_TRUE(tree.remove(addedElements[index])) << "Test failed for seed " | 274 ASSERT_TRUE(tree.remove(addedElements[index])) |
| 275 << seed; | 275 << "Test failed for seed " << seed; |
| 276 removedElements.push_back(addedElements[index]); | 276 removedElements.push_back(addedElements[index]); |
| 277 addedElements.remove(index); | 277 addedElements.remove(index); |
| 278 } | 278 } |
| 279 ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; | 279 ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed; |
| 280 } | 280 } |
| 281 } | 281 } |
| 282 | 282 |
| 283 } // anonymous namespace | 283 } // anonymous namespace |
| 284 | 284 |
| 285 TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest1) { | 285 TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest1) { |
| (...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 340 ASSERT_TRUE(tree.checkInvariants()); | 340 ASSERT_TRUE(tree.checkInvariants()); |
| 341 tree.add(tree.createInterval(3, 5)); | 341 tree.add(tree.createInterval(3, 5)); |
| 342 ASSERT_TRUE(tree.checkInvariants()); | 342 ASSERT_TRUE(tree.checkInvariants()); |
| 343 tree.add(tree.createInterval(4, 12)); | 343 tree.add(tree.createInterval(4, 12)); |
| 344 ASSERT_TRUE(tree.checkInvariants()); | 344 ASSERT_TRUE(tree.checkInvariants()); |
| 345 tree.remove(tree.createInterval(4, 12)); | 345 tree.remove(tree.createInterval(4, 12)); |
| 346 ASSERT_TRUE(tree.checkInvariants()); | 346 ASSERT_TRUE(tree.checkInvariants()); |
| 347 } | 347 } |
| 348 | 348 |
| 349 } // namespace blink | 349 } // namespace blink |
| OLD | NEW |