| 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 222 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 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])) << "Test failed for seed " |
| 240 << seed; | 240 << 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.erase(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; |
| 251 else if (!removedElements.size()) | 251 else if (!removedElements.size()) |
| 252 add = false; | 252 add = false; |
| 253 else | 253 else |
| 254 add = (nextRandom(2) == 1); | 254 add = (nextRandom(2) == 1); |
| 255 if (add) { | 255 if (add) { |
| 256 int index = nextRandom(removedElements.size()); | 256 int index = nextRandom(removedElements.size()); |
| 257 #ifdef DEBUG_INSERTION_AND_DELETION_TEST | 257 #ifdef DEBUG_INSERTION_AND_DELETION_TEST |
| 258 DLOG(ERROR) << "*** Adding element " | 258 DLOG(ERROR) << "*** Adding element " |
| 259 << ValueToString<PODInterval<int>>::string( | 259 << ValueToString<PODInterval<int>>::string( |
| 260 removedElements[index]); | 260 removedElements[index]); |
| 261 #endif | 261 #endif |
| 262 tree.add(removedElements[index]); | 262 tree.add(removedElements[index]); |
| 263 addedElements.push_back(removedElements[index]); | 263 addedElements.push_back(removedElements[index]); |
| 264 removedElements.remove(index); | 264 removedElements.erase(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])) << "Test failed for seed " |
| 275 << seed; | 275 << seed; |
| 276 removedElements.push_back(addedElements[index]); | 276 removedElements.push_back(addedElements[index]); |
| 277 addedElements.remove(index); | 277 addedElements.erase(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) { |
| 286 InsertionAndDeletionTest(13972, 100); | 286 InsertionAndDeletionTest(13972, 100); |
| 287 } | 287 } |
| (...skipping 52 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 |