Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(142)

Side by Side Diff: Source/platform/PODIntervalTreeTest.cpp

Issue 858663002: Fix template angle bracket syntax in platform (Closed) Base URL: https://chromium.googlesource.com/chromium/blink.git@master
Patch Set: Rebase Created 5 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « Source/platform/PODIntervalTree.h ('k') | Source/platform/PODRedBlackTree.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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
OLDNEW
« no previous file with comments | « Source/platform/PODIntervalTree.h ('k') | Source/platform/PODRedBlackTree.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698