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 |