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 |