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 |