1 // Copyright (c) 2019 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "quiche/quic/core/quic_interval_set.h"
6
7 #include <stdarg.h>
8
9 #include <algorithm>
10 #include <iostream>
11 #include <iterator>
12 #include <limits>
13 #include <string>
14 #include <vector>
15
16 #include "quiche/quic/platform/api/quic_test.h"
17
18 namespace quic {
19 namespace test {
20 namespace {
21
22 using ::testing::ElementsAreArray;
23
24 class QuicIntervalSetTest : public QuicTest {
25 protected:
SetUp()26 virtual void SetUp() {
27 // Initialize two QuicIntervalSets for union, intersection, and difference
28 // tests
29 is.Add(100, 200);
30 is.Add(300, 400);
31 is.Add(500, 600);
32 is.Add(700, 800);
33 is.Add(900, 1000);
34 is.Add(1100, 1200);
35 is.Add(1300, 1400);
36 is.Add(1500, 1600);
37 is.Add(1700, 1800);
38 is.Add(1900, 2000);
39 is.Add(2100, 2200);
40
41 // Lots of different cases:
42 other.Add(50, 70); // disjoint, at the beginning
43 other.Add(2250, 2270); // disjoint, at the end
44 other.Add(650, 670); // disjoint, in the middle
45 other.Add(350, 360); // included
46 other.Add(370, 380); // also included (two at once)
47 other.Add(470, 530); // overlaps low end
48 other.Add(770, 830); // overlaps high end
49 other.Add(870, 900); // meets at low end
50 other.Add(1200, 1230); // meets at high end
51 other.Add(1270, 1830); // overlaps multiple ranges
52 }
53
TearDown()54 virtual void TearDown() {
55 is.Clear();
56 EXPECT_TRUE(is.Empty());
57 other.Clear();
58 EXPECT_TRUE(other.Empty());
59 }
60 QuicIntervalSet<int> is;
61 QuicIntervalSet<int> other;
62 };
63
TEST_F(QuicIntervalSetTest,IsDisjoint)64 TEST_F(QuicIntervalSetTest, IsDisjoint) {
65 EXPECT_TRUE(is.IsDisjoint(QuicInterval<int>(0, 99)));
66 EXPECT_TRUE(is.IsDisjoint(QuicInterval<int>(0, 100)));
67 EXPECT_TRUE(is.IsDisjoint(QuicInterval<int>(200, 200)));
68 EXPECT_TRUE(is.IsDisjoint(QuicInterval<int>(200, 299)));
69 EXPECT_TRUE(is.IsDisjoint(QuicInterval<int>(400, 407)));
70 EXPECT_TRUE(is.IsDisjoint(QuicInterval<int>(405, 499)));
71 EXPECT_TRUE(is.IsDisjoint(QuicInterval<int>(2300, 2300)));
72 EXPECT_TRUE(
73 is.IsDisjoint(QuicInterval<int>(2300, std::numeric_limits<int>::max())));
74 EXPECT_FALSE(is.IsDisjoint(QuicInterval<int>(100, 105)));
75 EXPECT_FALSE(is.IsDisjoint(QuicInterval<int>(199, 300)));
76 EXPECT_FALSE(is.IsDisjoint(QuicInterval<int>(250, 450)));
77 EXPECT_FALSE(is.IsDisjoint(QuicInterval<int>(299, 400)));
78 EXPECT_FALSE(is.IsDisjoint(QuicInterval<int>(250, 2000)));
79 EXPECT_FALSE(
80 is.IsDisjoint(QuicInterval<int>(2199, std::numeric_limits<int>::max())));
81 // Empty intervals.
82 EXPECT_TRUE(is.IsDisjoint(QuicInterval<int>(90, 90)));
83 EXPECT_TRUE(is.IsDisjoint(QuicInterval<int>(100, 100)));
84 EXPECT_TRUE(is.IsDisjoint(QuicInterval<int>(100, 90)));
85 EXPECT_TRUE(is.IsDisjoint(QuicInterval<int>(150, 150)));
86 EXPECT_TRUE(is.IsDisjoint(QuicInterval<int>(200, 200)));
87 EXPECT_TRUE(is.IsDisjoint(QuicInterval<int>(400, 300)));
88 }
89
90 // Base helper method for verifying the contents of an interval set.
91 // Returns true iff <is> contains <count> intervals whose successive
92 // endpoints match the sequence of args in <ap>:
VA_Check(const QuicIntervalSet<int> & is,int count,va_list ap)93 static bool VA_Check(const QuicIntervalSet<int>& is, int count, va_list ap) {
94 std::vector<QuicInterval<int>> intervals(is.begin(), is.end());
95 if (count != static_cast<int>(intervals.size())) {
96 QUIC_LOG(ERROR) << "Expected " << count << " intervals, got "
97 << intervals.size() << ": " << is;
98 return false;
99 }
100 if (count != static_cast<int>(is.Size())) {
101 QUIC_LOG(ERROR) << "Expected " << count << " intervals, got Size "
102 << is.Size() << ": " << is;
103 return false;
104 }
105 bool result = true;
106 for (int i = 0; i < count; i++) {
107 int min = va_arg(ap, int);
108 int max = va_arg(ap, int);
109 if (min != intervals[i].min() || max != intervals[i].max()) {
110 QUIC_LOG(ERROR) << "Expected: [" << min << ", " << max << ") got "
111 << intervals[i] << " in " << is;
112 result = false;
113 }
114 }
115 return result;
116 }
117
Check(const QuicIntervalSet<int> & is,int count,...)118 static bool Check(const QuicIntervalSet<int>& is, int count, ...) {
119 va_list ap;
120 va_start(ap, count);
121 const bool result = VA_Check(is, count, ap);
122 va_end(ap);
123 return result;
124 }
125
126 // Some helper functions for testing Contains and Find, which are logically the
127 // same.
TestContainsAndFind(const QuicIntervalSet<int> & is,int value)128 static void TestContainsAndFind(const QuicIntervalSet<int>& is, int value) {
129 EXPECT_TRUE(is.Contains(value)) << "Set does not contain " << value;
130 auto it = is.Find(value);
131 EXPECT_NE(it, is.end()) << "No iterator to interval containing " << value;
132 EXPECT_TRUE(it->Contains(value)) << "Iterator does not contain " << value;
133 }
134
TestContainsAndFind(const QuicIntervalSet<int> & is,int min,int max)135 static void TestContainsAndFind(const QuicIntervalSet<int>& is, int min,
136 int max) {
137 EXPECT_TRUE(is.Contains(min, max))
138 << "Set does not contain interval with min " << min << "and max " << max;
139 auto it = is.Find(min, max);
140 EXPECT_NE(it, is.end()) << "No iterator to interval with min " << min
141 << "and max " << max;
142 EXPECT_TRUE(it->Contains(QuicInterval<int>(min, max)))
143 << "Iterator does not contain interval with min " << min << "and max "
144 << max;
145 }
146
TestNotContainsAndFind(const QuicIntervalSet<int> & is,int value)147 static void TestNotContainsAndFind(const QuicIntervalSet<int>& is, int value) {
148 EXPECT_FALSE(is.Contains(value)) << "Set contains " << value;
149 auto it = is.Find(value);
150 EXPECT_EQ(it, is.end()) << "There is iterator to interval containing "
151 << value;
152 }
153
TestNotContainsAndFind(const QuicIntervalSet<int> & is,int min,int max)154 static void TestNotContainsAndFind(const QuicIntervalSet<int>& is, int min,
155 int max) {
156 EXPECT_FALSE(is.Contains(min, max))
157 << "Set contains interval with min " << min << "and max " << max;
158 auto it = is.Find(min, max);
159 EXPECT_EQ(it, is.end()) << "There is iterator to interval with min " << min
160 << "and max " << max;
161 }
162
TEST_F(QuicIntervalSetTest,AddInterval)163 TEST_F(QuicIntervalSetTest, AddInterval) {
164 QuicIntervalSet<int> s;
165 s.Add(QuicInterval<int>(0, 10));
166 EXPECT_TRUE(Check(s, 1, 0, 10));
167 }
168
TEST_F(QuicIntervalSetTest,DecrementIterator)169 TEST_F(QuicIntervalSetTest, DecrementIterator) {
170 auto it = is.end();
171 EXPECT_NE(it, is.begin());
172 --it;
173 EXPECT_EQ(*it, QuicInterval<int>(2100, 2200));
174 ++it;
175 EXPECT_EQ(it, is.end());
176 }
177
TEST_F(QuicIntervalSetTest,AddOptimizedForAppend)178 TEST_F(QuicIntervalSetTest, AddOptimizedForAppend) {
179 QuicIntervalSet<int> empty_one, empty_two;
180 empty_one.AddOptimizedForAppend(QuicInterval<int>(0, 99));
181 EXPECT_TRUE(Check(empty_one, 1, 0, 99));
182
183 empty_two.AddOptimizedForAppend(1, 50);
184 EXPECT_TRUE(Check(empty_two, 1, 1, 50));
185
186 QuicIntervalSet<int> iset;
187 iset.AddOptimizedForAppend(100, 150);
188 iset.AddOptimizedForAppend(200, 250);
189 EXPECT_TRUE(Check(iset, 2, 100, 150, 200, 250));
190
191 iset.AddOptimizedForAppend(199, 200);
192 EXPECT_TRUE(Check(iset, 2, 100, 150, 199, 250));
193
194 iset.AddOptimizedForAppend(251, 260);
195 EXPECT_TRUE(Check(iset, 3, 100, 150, 199, 250, 251, 260));
196
197 iset.AddOptimizedForAppend(252, 260);
198 EXPECT_TRUE(Check(iset, 3, 100, 150, 199, 250, 251, 260));
199
200 iset.AddOptimizedForAppend(252, 300);
201 EXPECT_TRUE(Check(iset, 3, 100, 150, 199, 250, 251, 300));
202
203 iset.AddOptimizedForAppend(300, 350);
204 EXPECT_TRUE(Check(iset, 3, 100, 150, 199, 250, 251, 350));
205 }
206
TEST_F(QuicIntervalSetTest,PopFront)207 TEST_F(QuicIntervalSetTest, PopFront) {
208 QuicIntervalSet<int> iset{{100, 200}, {400, 500}, {700, 800}};
209 EXPECT_TRUE(Check(iset, 3, 100, 200, 400, 500, 700, 800));
210
211 iset.PopFront();
212 EXPECT_TRUE(Check(iset, 2, 400, 500, 700, 800));
213
214 iset.PopFront();
215 EXPECT_TRUE(Check(iset, 1, 700, 800));
216
217 iset.PopFront();
218 EXPECT_TRUE(iset.Empty());
219 }
220
TEST_F(QuicIntervalSetTest,TrimLessThan)221 TEST_F(QuicIntervalSetTest, TrimLessThan) {
222 QuicIntervalSet<int> iset{{100, 200}, {400, 500}, {700, 800}};
223 EXPECT_TRUE(Check(iset, 3, 100, 200, 400, 500, 700, 800));
224
225 EXPECT_FALSE(iset.TrimLessThan(99));
226 EXPECT_FALSE(iset.TrimLessThan(100));
227 EXPECT_TRUE(Check(iset, 3, 100, 200, 400, 500, 700, 800));
228
229 EXPECT_TRUE(iset.TrimLessThan(101));
230 EXPECT_TRUE(Check(iset, 3, 101, 200, 400, 500, 700, 800));
231
232 EXPECT_TRUE(iset.TrimLessThan(199));
233 EXPECT_TRUE(Check(iset, 3, 199, 200, 400, 500, 700, 800));
234
235 EXPECT_TRUE(iset.TrimLessThan(450));
236 EXPECT_TRUE(Check(iset, 2, 450, 500, 700, 800));
237
238 EXPECT_TRUE(iset.TrimLessThan(500));
239 EXPECT_TRUE(Check(iset, 1, 700, 800));
240
241 EXPECT_TRUE(iset.TrimLessThan(801));
242 EXPECT_TRUE(iset.Empty());
243
244 EXPECT_FALSE(iset.TrimLessThan(900));
245 EXPECT_TRUE(iset.Empty());
246 }
247
TEST_F(QuicIntervalSetTest,QuicIntervalSetBasic)248 TEST_F(QuicIntervalSetTest, QuicIntervalSetBasic) {
249 // Test Add, Get, Contains and Find
250 QuicIntervalSet<int> iset;
251 EXPECT_TRUE(iset.Empty());
252 EXPECT_EQ(0u, iset.Size());
253 iset.Add(100, 200);
254 EXPECT_FALSE(iset.Empty());
255 EXPECT_EQ(1u, iset.Size());
256 iset.Add(100, 150);
257 iset.Add(150, 200);
258 iset.Add(130, 170);
259 iset.Add(90, 150);
260 iset.Add(170, 220);
261 iset.Add(300, 400);
262 iset.Add(250, 450);
263 EXPECT_FALSE(iset.Empty());
264 EXPECT_EQ(2u, iset.Size());
265 EXPECT_TRUE(Check(iset, 2, 90, 220, 250, 450));
266
267 // Test two intervals with a.max == b.min, that will just join up.
268 iset.Clear();
269 iset.Add(100, 200);
270 iset.Add(200, 300);
271 EXPECT_FALSE(iset.Empty());
272 EXPECT_EQ(1u, iset.Size());
273 EXPECT_TRUE(Check(iset, 1, 100, 300));
274
275 // Test adding two sets together.
276 iset.Clear();
277 QuicIntervalSet<int> iset_add;
278 iset.Add(100, 200);
279 iset.Add(100, 150);
280 iset.Add(150, 200);
281 iset.Add(130, 170);
282 iset_add.Add(90, 150);
283 iset_add.Add(170, 220);
284 iset_add.Add(300, 400);
285 iset_add.Add(250, 450);
286
287 iset.Union(iset_add);
288 EXPECT_FALSE(iset.Empty());
289 EXPECT_EQ(2u, iset.Size());
290 EXPECT_TRUE(Check(iset, 2, 90, 220, 250, 450));
291
292 // Test begin()/end(), and rbegin()/rend()
293 // to iterate over intervals.
294 {
295 std::vector<QuicInterval<int>> expected(iset.begin(), iset.end());
296
297 std::vector<QuicInterval<int>> actual1;
298 std::copy(iset.begin(), iset.end(), back_inserter(actual1));
299 ASSERT_EQ(expected.size(), actual1.size());
300
301 std::vector<QuicInterval<int>> actual2;
302 std::copy(iset.begin(), iset.end(), back_inserter(actual2));
303 ASSERT_EQ(expected.size(), actual2.size());
304
305 for (size_t i = 0; i < expected.size(); i++) {
306 EXPECT_EQ(expected[i].min(), actual1[i].min());
307 EXPECT_EQ(expected[i].max(), actual1[i].max());
308
309 EXPECT_EQ(expected[i].min(), actual2[i].min());
310 EXPECT_EQ(expected[i].max(), actual2[i].max());
311 }
312
313 // Ensure that the rbegin()/rend() iterators correctly yield the intervals
314 // in reverse order.
315 EXPECT_THAT(std::vector<QuicInterval<int>>(iset.rbegin(), iset.rend()),
316 ElementsAreArray(expected.rbegin(), expected.rend()));
317 }
318
319 TestNotContainsAndFind(iset, 89);
320 TestContainsAndFind(iset, 90);
321 TestContainsAndFind(iset, 120);
322 TestContainsAndFind(iset, 219);
323 TestNotContainsAndFind(iset, 220);
324 TestNotContainsAndFind(iset, 235);
325 TestNotContainsAndFind(iset, 249);
326 TestContainsAndFind(iset, 250);
327 TestContainsAndFind(iset, 300);
328 TestContainsAndFind(iset, 449);
329 TestNotContainsAndFind(iset, 450);
330 TestNotContainsAndFind(iset, 451);
331
332 TestNotContainsAndFind(iset, 50, 60);
333 TestNotContainsAndFind(iset, 50, 90);
334 TestNotContainsAndFind(iset, 50, 200);
335 TestNotContainsAndFind(iset, 90, 90);
336 TestContainsAndFind(iset, 90, 200);
337 TestContainsAndFind(iset, 100, 200);
338 TestContainsAndFind(iset, 100, 220);
339 TestNotContainsAndFind(iset, 100, 221);
340 TestNotContainsAndFind(iset, 220, 220);
341 TestNotContainsAndFind(iset, 240, 300);
342 TestContainsAndFind(iset, 250, 300);
343 TestContainsAndFind(iset, 260, 300);
344 TestContainsAndFind(iset, 300, 450);
345 TestNotContainsAndFind(iset, 300, 451);
346
347 QuicIntervalSet<int> iset_contains;
348 iset_contains.Add(50, 90);
349 EXPECT_FALSE(iset.Contains(iset_contains));
350 iset_contains.Clear();
351
352 iset_contains.Add(90, 200);
353 EXPECT_TRUE(iset.Contains(iset_contains));
354 iset_contains.Add(100, 200);
355 EXPECT_TRUE(iset.Contains(iset_contains));
356 iset_contains.Add(100, 220);
357 EXPECT_TRUE(iset.Contains(iset_contains));
358 iset_contains.Add(250, 300);
359 EXPECT_TRUE(iset.Contains(iset_contains));
360 iset_contains.Add(300, 450);
361 EXPECT_TRUE(iset.Contains(iset_contains));
362 iset_contains.Add(300, 451);
363 EXPECT_FALSE(iset.Contains(iset_contains));
364 EXPECT_FALSE(iset.Contains(QuicInterval<int>()));
365 EXPECT_FALSE(iset.Contains(QuicIntervalSet<int>()));
366
367 // Check the case where the query set isn't contained, but the spanning
368 // intervals do overlap.
369 QuicIntervalSet<int> i2({{220, 230}});
370 EXPECT_FALSE(iset.Contains(i2));
371 }
372
TEST_F(QuicIntervalSetTest,QuicIntervalSetContainsEmpty)373 TEST_F(QuicIntervalSetTest, QuicIntervalSetContainsEmpty) {
374 const QuicIntervalSet<int> empty;
375 const QuicIntervalSet<int> other_empty;
376 const QuicIntervalSet<int> non_empty({{10, 20}, {40, 50}});
377 EXPECT_FALSE(empty.Contains(empty));
378 EXPECT_FALSE(empty.Contains(other_empty));
379 EXPECT_FALSE(empty.Contains(non_empty));
380 EXPECT_FALSE(non_empty.Contains(empty));
381 }
382
TEST_F(QuicIntervalSetTest,Equality)383 TEST_F(QuicIntervalSetTest, Equality) {
384 QuicIntervalSet<int> is_copy = is;
385 EXPECT_EQ(is, is);
386 EXPECT_EQ(is, is_copy);
387 EXPECT_NE(is, other);
388 EXPECT_NE(is, QuicIntervalSet<int>());
389 EXPECT_EQ(QuicIntervalSet<int>(), QuicIntervalSet<int>());
390 }
391
TEST_F(QuicIntervalSetTest,LowerAndUpperBound)392 TEST_F(QuicIntervalSetTest, LowerAndUpperBound) {
393 QuicIntervalSet<int> intervals;
394 intervals.Add(10, 20);
395 intervals.Add(30, 40);
396
397 // [10, 20) [30, 40) end
398 // ^ LowerBound(5)
399 // ^ LowerBound(10)
400 // ^ LowerBound(15)
401 // ^ LowerBound(20)
402 // ^ LowerBound(25)
403 // ^ LowerBound(30)
404 // ^ LowerBound(35)
405 // ^ LowerBound(40)
406 // ^ LowerBound(50)
407 EXPECT_EQ(intervals.LowerBound(5)->min(), 10);
408 EXPECT_EQ(intervals.LowerBound(10)->min(), 10);
409 EXPECT_EQ(intervals.LowerBound(15)->min(), 10);
410 EXPECT_EQ(intervals.LowerBound(20)->min(), 30);
411 EXPECT_EQ(intervals.LowerBound(25)->min(), 30);
412 EXPECT_EQ(intervals.LowerBound(30)->min(), 30);
413 EXPECT_EQ(intervals.LowerBound(35)->min(), 30);
414 EXPECT_EQ(intervals.LowerBound(40), intervals.end());
415 EXPECT_EQ(intervals.LowerBound(50), intervals.end());
416
417 // [10, 20) [30, 40) end
418 // ^ UpperBound(5)
419 // ^ UpperBound(10)
420 // ^ UpperBound(15)
421 // ^ UpperBound(20)
422 // ^ UpperBound(25)
423 // ^ UpperBound(30)
424 // ^ UpperBound(35)
425 // ^ UpperBound(40)
426 // ^ UpperBound(50)
427 EXPECT_EQ(intervals.UpperBound(5)->min(), 10);
428 EXPECT_EQ(intervals.UpperBound(10)->min(), 30);
429 EXPECT_EQ(intervals.UpperBound(15)->min(), 30);
430 EXPECT_EQ(intervals.UpperBound(20)->min(), 30);
431 EXPECT_EQ(intervals.UpperBound(25)->min(), 30);
432 EXPECT_EQ(intervals.UpperBound(30), intervals.end());
433 EXPECT_EQ(intervals.UpperBound(35), intervals.end());
434 EXPECT_EQ(intervals.UpperBound(40), intervals.end());
435 EXPECT_EQ(intervals.UpperBound(50), intervals.end());
436 }
437
TEST_F(QuicIntervalSetTest,SpanningInterval)438 TEST_F(QuicIntervalSetTest, SpanningInterval) {
439 // Spanning interval of an empty set is empty:
440 {
441 QuicIntervalSet<int> iset;
442 const QuicInterval<int>& ival = iset.SpanningInterval();
443 EXPECT_TRUE(ival.Empty());
444 }
445
446 // Spanning interval of a set with one interval is that interval:
447 {
448 QuicIntervalSet<int> iset;
449 iset.Add(100, 200);
450 const QuicInterval<int>& ival = iset.SpanningInterval();
451 EXPECT_EQ(100, ival.min());
452 EXPECT_EQ(200, ival.max());
453 }
454
455 // Spanning interval of a set with multiple elements is determined
456 // by the endpoints of the first and last element:
457 {
458 const QuicInterval<int>& ival = is.SpanningInterval();
459 EXPECT_EQ(100, ival.min());
460 EXPECT_EQ(2200, ival.max());
461 }
462 {
463 const QuicInterval<int>& ival = other.SpanningInterval();
464 EXPECT_EQ(50, ival.min());
465 EXPECT_EQ(2270, ival.max());
466 }
467 }
468
TEST_F(QuicIntervalSetTest,QuicIntervalSetUnion)469 TEST_F(QuicIntervalSetTest, QuicIntervalSetUnion) {
470 is.Union(other);
471 EXPECT_TRUE(Check(is, 12, 50, 70, 100, 200, 300, 400, 470, 600, 650, 670, 700,
472 830, 870, 1000, 1100, 1230, 1270, 1830, 1900, 2000, 2100,
473 2200, 2250, 2270));
474 }
475
TEST_F(QuicIntervalSetTest,QuicIntervalSetIntersection)476 TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersection) {
477 EXPECT_TRUE(is.Intersects(other));
478 EXPECT_TRUE(other.Intersects(is));
479 is.Intersection(other);
480 EXPECT_TRUE(Check(is, 7, 350, 360, 370, 380, 500, 530, 770, 800, 1300, 1400,
481 1500, 1600, 1700, 1800));
482 EXPECT_TRUE(is.Intersects(other));
483 EXPECT_TRUE(other.Intersects(is));
484 }
485
TEST_F(QuicIntervalSetTest,QuicIntervalSetIntersectionBothEmpty)486 TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionBothEmpty) {
487 QuicIntervalSet<std::string> mine, theirs;
488 EXPECT_FALSE(mine.Intersects(theirs));
489 EXPECT_FALSE(theirs.Intersects(mine));
490 mine.Intersection(theirs);
491 EXPECT_TRUE(mine.Empty());
492 EXPECT_FALSE(mine.Intersects(theirs));
493 EXPECT_FALSE(theirs.Intersects(mine));
494 }
495
TEST_F(QuicIntervalSetTest,QuicIntervalSetIntersectionEmptyMine)496 TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionEmptyMine) {
497 QuicIntervalSet<std::string> mine;
498 QuicIntervalSet<std::string> theirs("a", "b");
499 EXPECT_FALSE(mine.Intersects(theirs));
500 EXPECT_FALSE(theirs.Intersects(mine));
501 mine.Intersection(theirs);
502 EXPECT_TRUE(mine.Empty());
503 EXPECT_FALSE(mine.Intersects(theirs));
504 EXPECT_FALSE(theirs.Intersects(mine));
505 }
506
TEST_F(QuicIntervalSetTest,QuicIntervalSetIntersectionEmptyTheirs)507 TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionEmptyTheirs) {
508 QuicIntervalSet<std::string> mine("a", "b");
509 QuicIntervalSet<std::string> theirs;
510 EXPECT_FALSE(mine.Intersects(theirs));
511 EXPECT_FALSE(theirs.Intersects(mine));
512 mine.Intersection(theirs);
513 EXPECT_TRUE(mine.Empty());
514 EXPECT_FALSE(mine.Intersects(theirs));
515 EXPECT_FALSE(theirs.Intersects(mine));
516 }
517
TEST_F(QuicIntervalSetTest,QuicIntervalSetIntersectionTheirsBeforeMine)518 TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionTheirsBeforeMine) {
519 QuicIntervalSet<std::string> mine("y", "z");
520 QuicIntervalSet<std::string> theirs;
521 theirs.Add("a", "b");
522 theirs.Add("c", "d");
523 EXPECT_FALSE(mine.Intersects(theirs));
524 EXPECT_FALSE(theirs.Intersects(mine));
525 mine.Intersection(theirs);
526 EXPECT_TRUE(mine.Empty());
527 EXPECT_FALSE(mine.Intersects(theirs));
528 EXPECT_FALSE(theirs.Intersects(mine));
529 }
530
TEST_F(QuicIntervalSetTest,QuicIntervalSetIntersectionMineBeforeTheirs)531 TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionMineBeforeTheirs) {
532 QuicIntervalSet<std::string> mine;
533 mine.Add("a", "b");
534 mine.Add("c", "d");
535 QuicIntervalSet<std::string> theirs("y", "z");
536 EXPECT_FALSE(mine.Intersects(theirs));
537 EXPECT_FALSE(theirs.Intersects(mine));
538 mine.Intersection(theirs);
539 EXPECT_TRUE(mine.Empty());
540 EXPECT_FALSE(mine.Intersects(theirs));
541 EXPECT_FALSE(theirs.Intersects(mine));
542 }
543
TEST_F(QuicIntervalSetTest,QuicIntervalSetIntersectionTheirsBeforeMineInt64Singletons)544 TEST_F(QuicIntervalSetTest,
545 QuicIntervalSetIntersectionTheirsBeforeMineInt64Singletons) {
546 QuicIntervalSet<int64_t> mine({{10, 15}});
547 QuicIntervalSet<int64_t> theirs({{-20, -5}});
548 EXPECT_FALSE(mine.Intersects(theirs));
549 EXPECT_FALSE(theirs.Intersects(mine));
550 mine.Intersection(theirs);
551 EXPECT_TRUE(mine.Empty());
552 EXPECT_FALSE(mine.Intersects(theirs));
553 EXPECT_FALSE(theirs.Intersects(mine));
554 }
555
TEST_F(QuicIntervalSetTest,QuicIntervalSetIntersectionMineBeforeTheirsIntSingletons)556 TEST_F(QuicIntervalSetTest,
557 QuicIntervalSetIntersectionMineBeforeTheirsIntSingletons) {
558 QuicIntervalSet<int> mine({{10, 15}});
559 QuicIntervalSet<int> theirs({{90, 95}});
560 EXPECT_FALSE(mine.Intersects(theirs));
561 EXPECT_FALSE(theirs.Intersects(mine));
562 mine.Intersection(theirs);
563 EXPECT_TRUE(mine.Empty());
564 EXPECT_FALSE(mine.Intersects(theirs));
565 EXPECT_FALSE(theirs.Intersects(mine));
566 }
567
TEST_F(QuicIntervalSetTest,QuicIntervalSetIntersectionTheirsBetweenMine)568 TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionTheirsBetweenMine) {
569 QuicIntervalSet<int64_t> mine({{0, 5}, {40, 50}});
570 QuicIntervalSet<int64_t> theirs({{10, 15}});
571 EXPECT_FALSE(mine.Intersects(theirs));
572 EXPECT_FALSE(theirs.Intersects(mine));
573 mine.Intersection(theirs);
574 EXPECT_TRUE(mine.Empty());
575 EXPECT_FALSE(mine.Intersects(theirs));
576 EXPECT_FALSE(theirs.Intersects(mine));
577 }
578
TEST_F(QuicIntervalSetTest,QuicIntervalSetIntersectionMineBetweenTheirs)579 TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionMineBetweenTheirs) {
580 QuicIntervalSet<int> mine({{20, 25}});
581 QuicIntervalSet<int> theirs({{10, 15}, {30, 32}});
582 EXPECT_FALSE(mine.Intersects(theirs));
583 EXPECT_FALSE(theirs.Intersects(mine));
584 mine.Intersection(theirs);
585 EXPECT_TRUE(mine.Empty());
586 EXPECT_FALSE(mine.Intersects(theirs));
587 EXPECT_FALSE(theirs.Intersects(mine));
588 }
589
TEST_F(QuicIntervalSetTest,QuicIntervalSetIntersectionAlternatingIntervals)590 TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionAlternatingIntervals) {
591 QuicIntervalSet<int> mine, theirs;
592 mine.Add(10, 20);
593 mine.Add(40, 50);
594 mine.Add(60, 70);
595 theirs.Add(25, 39);
596 theirs.Add(55, 59);
597 theirs.Add(75, 79);
598 EXPECT_FALSE(mine.Intersects(theirs));
599 EXPECT_FALSE(theirs.Intersects(mine));
600 mine.Intersection(theirs);
601 EXPECT_TRUE(mine.Empty());
602 EXPECT_FALSE(mine.Intersects(theirs));
603 EXPECT_FALSE(theirs.Intersects(mine));
604 }
605
TEST_F(QuicIntervalSetTest,QuicIntervalSetIntersectionAdjacentAlternatingNonIntersectingIntervals)606 TEST_F(QuicIntervalSetTest,
607 QuicIntervalSetIntersectionAdjacentAlternatingNonIntersectingIntervals) {
608 // Make sure that intersection with adjacent interval set is empty.
609 const QuicIntervalSet<int> x1({{0, 10}});
610 const QuicIntervalSet<int> y1({{-50, 0}, {10, 95}});
611
612 QuicIntervalSet<int> result1 = x1;
613 result1.Intersection(y1);
614 EXPECT_TRUE(result1.Empty()) << result1;
615
616 const QuicIntervalSet<int16_t> x2({{0, 10}, {20, 30}, {40, 90}});
617 const QuicIntervalSet<int16_t> y2(
618 {{-50, -40}, {-2, 0}, {10, 20}, {32, 40}, {90, 95}});
619
620 QuicIntervalSet<int16_t> result2 = x2;
621 result2.Intersection(y2);
622 EXPECT_TRUE(result2.Empty()) << result2;
623
624 const QuicIntervalSet<int64_t> x3({{-1, 5}, {5, 10}});
625 const QuicIntervalSet<int64_t> y3({{-10, -1}, {10, 95}});
626
627 QuicIntervalSet<int64_t> result3 = x3;
628 result3.Intersection(y3);
629 EXPECT_TRUE(result3.Empty()) << result3;
630 }
631
TEST_F(QuicIntervalSetTest,QuicIntervalSetIntersectionAlternatingIntersectingIntervals)632 TEST_F(QuicIntervalSetTest,
633 QuicIntervalSetIntersectionAlternatingIntersectingIntervals) {
634 const QuicIntervalSet<int> x1({{0, 10}});
635 const QuicIntervalSet<int> y1({{-50, 1}, {9, 95}});
636 const QuicIntervalSet<int> expected_result1({{0, 1}, {9, 10}});
637
638 QuicIntervalSet<int> result1 = x1;
639 result1.Intersection(y1);
640 EXPECT_EQ(result1, expected_result1);
641
642 const QuicIntervalSet<int16_t> x2({{0, 10}, {20, 30}, {40, 90}});
643 const QuicIntervalSet<int16_t> y2(
644 {{-50, -40}, {-2, 2}, {9, 21}, {32, 41}, {85, 95}});
645 const QuicIntervalSet<int16_t> expected_result2(
646 {{0, 2}, {9, 10}, {20, 21}, {40, 41}, {85, 90}});
647
648 QuicIntervalSet<int16_t> result2 = x2;
649 result2.Intersection(y2);
650 EXPECT_EQ(result2, expected_result2);
651
652 const QuicIntervalSet<int64_t> x3({{-1, 5}, {5, 10}});
653 const QuicIntervalSet<int64_t> y3({{-10, 3}, {4, 95}});
654 const QuicIntervalSet<int64_t> expected_result3({{-1, 3}, {4, 10}});
655
656 QuicIntervalSet<int64_t> result3 = x3;
657 result3.Intersection(y3);
658 EXPECT_EQ(result3, expected_result3);
659 }
660
TEST_F(QuicIntervalSetTest,QuicIntervalSetIntersectionIdentical)661 TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionIdentical) {
662 QuicIntervalSet<int> copy(is);
663 EXPECT_TRUE(copy.Intersects(is));
664 EXPECT_TRUE(is.Intersects(copy));
665 is.Intersection(copy);
666 EXPECT_EQ(copy, is);
667 }
668
TEST_F(QuicIntervalSetTest,QuicIntervalSetIntersectionSuperset)669 TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionSuperset) {
670 QuicIntervalSet<int> mine(-1, 10000);
671 EXPECT_TRUE(mine.Intersects(is));
672 EXPECT_TRUE(is.Intersects(mine));
673 mine.Intersection(is);
674 EXPECT_EQ(is, mine);
675 }
676
TEST_F(QuicIntervalSetTest,QuicIntervalSetIntersectionSubset)677 TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionSubset) {
678 QuicIntervalSet<int> copy(is);
679 QuicIntervalSet<int> theirs(-1, 10000);
680 EXPECT_TRUE(copy.Intersects(theirs));
681 EXPECT_TRUE(theirs.Intersects(copy));
682 is.Intersection(theirs);
683 EXPECT_EQ(copy, is);
684 }
685
TEST_F(QuicIntervalSetTest,QuicIntervalSetIntersectionLargeSet)686 TEST_F(QuicIntervalSetTest, QuicIntervalSetIntersectionLargeSet) {
687 QuicIntervalSet<int> mine, theirs;
688 // mine: [0, 9), [10, 19), ..., [990, 999)
689 for (int i = 0; i < 1000; i += 10) {
690 mine.Add(i, i + 9);
691 }
692
693 theirs.Add(500, 520);
694 theirs.Add(535, 545);
695 theirs.Add(801, 809);
696 EXPECT_TRUE(mine.Intersects(theirs));
697 EXPECT_TRUE(theirs.Intersects(mine));
698 mine.Intersection(theirs);
699 EXPECT_TRUE(Check(mine, 5, 500, 509, 510, 519, 535, 539, 540, 545, 801, 809));
700 EXPECT_TRUE(mine.Intersects(theirs));
701 EXPECT_TRUE(theirs.Intersects(mine));
702 }
703
TEST_F(QuicIntervalSetTest,QuicIntervalSetDifference)704 TEST_F(QuicIntervalSetTest, QuicIntervalSetDifference) {
705 is.Difference(other);
706 EXPECT_TRUE(Check(is, 10, 100, 200, 300, 350, 360, 370, 380, 400, 530, 600,
707 700, 770, 900, 1000, 1100, 1200, 1900, 2000, 2100, 2200));
708 QuicIntervalSet<int> copy = is;
709 is.Difference(copy);
710 EXPECT_TRUE(is.Empty());
711 }
712
TEST_F(QuicIntervalSetTest,QuicIntervalSetDifferenceSingleBounds)713 TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceSingleBounds) {
714 std::vector<QuicInterval<int>> ivals(other.begin(), other.end());
715 for (const QuicInterval<int>& ival : ivals) {
716 is.Difference(ival.min(), ival.max());
717 }
718 EXPECT_TRUE(Check(is, 10, 100, 200, 300, 350, 360, 370, 380, 400, 530, 600,
719 700, 770, 900, 1000, 1100, 1200, 1900, 2000, 2100, 2200));
720 }
721
TEST_F(QuicIntervalSetTest,QuicIntervalSetDifferenceSingleInterval)722 TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceSingleInterval) {
723 std::vector<QuicInterval<int>> ivals(other.begin(), other.end());
724 for (const QuicInterval<int>& ival : ivals) {
725 is.Difference(ival);
726 }
727 EXPECT_TRUE(Check(is, 10, 100, 200, 300, 350, 360, 370, 380, 400, 530, 600,
728 700, 770, 900, 1000, 1100, 1200, 1900, 2000, 2100, 2200));
729 }
730
TEST_F(QuicIntervalSetTest,QuicIntervalSetDifferenceAlternatingIntervals)731 TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceAlternatingIntervals) {
732 QuicIntervalSet<int> mine, theirs;
733 mine.Add(10, 20);
734 mine.Add(40, 50);
735 mine.Add(60, 70);
736 theirs.Add(25, 39);
737 theirs.Add(55, 59);
738 theirs.Add(75, 79);
739
740 mine.Difference(theirs);
741 EXPECT_TRUE(Check(mine, 3, 10, 20, 40, 50, 60, 70));
742 }
743
TEST_F(QuicIntervalSetTest,QuicIntervalSetDifferenceEmptyMine)744 TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceEmptyMine) {
745 QuicIntervalSet<std::string> mine, theirs;
746 theirs.Add("a", "b");
747
748 mine.Difference(theirs);
749 EXPECT_TRUE(mine.Empty());
750 }
751
TEST_F(QuicIntervalSetTest,QuicIntervalSetDifferenceEmptyTheirs)752 TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceEmptyTheirs) {
753 QuicIntervalSet<std::string> mine, theirs;
754 mine.Add("a", "b");
755
756 mine.Difference(theirs);
757 EXPECT_EQ(1u, mine.Size());
758 EXPECT_EQ("a", mine.begin()->min());
759 EXPECT_EQ("b", mine.begin()->max());
760 }
761
TEST_F(QuicIntervalSetTest,QuicIntervalSetDifferenceTheirsBeforeMine)762 TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceTheirsBeforeMine) {
763 QuicIntervalSet<std::string> mine, theirs;
764 mine.Add("y", "z");
765 theirs.Add("a", "b");
766
767 mine.Difference(theirs);
768 EXPECT_EQ(1u, mine.Size());
769 EXPECT_EQ("y", mine.begin()->min());
770 EXPECT_EQ("z", mine.begin()->max());
771 }
772
TEST_F(QuicIntervalSetTest,QuicIntervalSetDifferenceMineBeforeTheirs)773 TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceMineBeforeTheirs) {
774 QuicIntervalSet<std::string> mine, theirs;
775 mine.Add("a", "b");
776 theirs.Add("y", "z");
777
778 mine.Difference(theirs);
779 EXPECT_EQ(1u, mine.Size());
780 EXPECT_EQ("a", mine.begin()->min());
781 EXPECT_EQ("b", mine.begin()->max());
782 }
783
TEST_F(QuicIntervalSetTest,QuicIntervalSetDifferenceIdentical)784 TEST_F(QuicIntervalSetTest, QuicIntervalSetDifferenceIdentical) {
785 QuicIntervalSet<std::string> mine;
786 mine.Add("a", "b");
787 mine.Add("c", "d");
788 QuicIntervalSet<std::string> theirs(mine);
789
790 mine.Difference(theirs);
791 EXPECT_TRUE(mine.Empty());
792 }
793
TEST_F(QuicIntervalSetTest,EmptyComplement)794 TEST_F(QuicIntervalSetTest, EmptyComplement) {
795 // The complement of an empty set is the input interval:
796 QuicIntervalSet<int> iset;
797 iset.Complement(100, 200);
798 EXPECT_TRUE(Check(iset, 1, 100, 200));
799 }
800
TEST(QuicIntervalSetMultipleCompactionTest,OuterCovering)801 TEST(QuicIntervalSetMultipleCompactionTest, OuterCovering) {
802 QuicIntervalSet<int> iset;
803 // First add a bunch of disjoint ranges
804 iset.Add(100, 150);
805 iset.Add(200, 250);
806 iset.Add(300, 350);
807 iset.Add(400, 450);
808 EXPECT_TRUE(Check(iset, 4, 100, 150, 200, 250, 300, 350, 400, 450));
809 // Now add a big range that covers all of these ranges
810 iset.Add(0, 500);
811 EXPECT_TRUE(Check(iset, 1, 0, 500));
812 }
813
TEST(QuicIntervalSetMultipleCompactionTest,InnerCovering)814 TEST(QuicIntervalSetMultipleCompactionTest, InnerCovering) {
815 QuicIntervalSet<int> iset;
816 // First add a bunch of disjoint ranges
817 iset.Add(100, 150);
818 iset.Add(200, 250);
819 iset.Add(300, 350);
820 iset.Add(400, 450);
821 EXPECT_TRUE(Check(iset, 4, 100, 150, 200, 250, 300, 350, 400, 450));
822 // Now add a big range that partially covers the left and right most ranges.
823 iset.Add(125, 425);
824 EXPECT_TRUE(Check(iset, 1, 100, 450));
825 }
826
TEST(QuicIntervalSetMultipleCompactionTest,LeftCovering)827 TEST(QuicIntervalSetMultipleCompactionTest, LeftCovering) {
828 QuicIntervalSet<int> iset;
829 // First add a bunch of disjoint ranges
830 iset.Add(100, 150);
831 iset.Add(200, 250);
832 iset.Add(300, 350);
833 iset.Add(400, 450);
834 EXPECT_TRUE(Check(iset, 4, 100, 150, 200, 250, 300, 350, 400, 450));
835 // Now add a big range that partially covers the left most range.
836 iset.Add(125, 500);
837 EXPECT_TRUE(Check(iset, 1, 100, 500));
838 }
839
TEST(QuicIntervalSetMultipleCompactionTest,RightCovering)840 TEST(QuicIntervalSetMultipleCompactionTest, RightCovering) {
841 QuicIntervalSet<int> iset;
842 // First add a bunch of disjoint ranges
843 iset.Add(100, 150);
844 iset.Add(200, 250);
845 iset.Add(300, 350);
846 iset.Add(400, 450);
847 EXPECT_TRUE(Check(iset, 4, 100, 150, 200, 250, 300, 350, 400, 450));
848 // Now add a big range that partially covers the right most range.
849 iset.Add(0, 425);
850 EXPECT_TRUE(Check(iset, 1, 0, 450));
851 }
852
853 // Helper method for testing and verifying the results of a one-interval
854 // completement case.
CheckOneComplement(int add_min,int add_max,int comp_min,int comp_max,int count,...)855 static bool CheckOneComplement(int add_min, int add_max, int comp_min,
856 int comp_max, int count, ...) {
857 QuicIntervalSet<int> iset;
858 iset.Add(add_min, add_max);
859 iset.Complement(comp_min, comp_max);
860 bool result = true;
861 va_list ap;
862 va_start(ap, count);
863 if (!VA_Check(iset, count, ap)) {
864 result = false;
865 }
866 va_end(ap);
867 return result;
868 }
869
TEST_F(QuicIntervalSetTest,SingleIntervalComplement)870 TEST_F(QuicIntervalSetTest, SingleIntervalComplement) {
871 // Verify the complement of a set with one interval (i):
872 // |----- i -----|
873 // |----- args -----|
874 EXPECT_TRUE(CheckOneComplement(0, 10, 50, 150, 1, 50, 150));
875
876 // |----- i -----|
877 // |----- args -----|
878 EXPECT_TRUE(CheckOneComplement(50, 150, 0, 100, 1, 0, 50));
879
880 // |----- i -----|
881 // |----- args -----|
882 EXPECT_TRUE(CheckOneComplement(50, 150, 50, 150, 0));
883
884 // |---------- i ----------|
885 // |----- args -----|
886 EXPECT_TRUE(CheckOneComplement(50, 500, 100, 300, 0));
887
888 // |----- i -----|
889 // |---------- args ----------|
890 EXPECT_TRUE(CheckOneComplement(50, 500, 0, 800, 2, 0, 50, 500, 800));
891
892 // |----- i -----|
893 // |----- args -----|
894 EXPECT_TRUE(CheckOneComplement(50, 150, 100, 300, 1, 150, 300));
895
896 // |----- i -----|
897 // |----- args -----|
898 EXPECT_TRUE(CheckOneComplement(50, 150, 200, 300, 1, 200, 300));
899 }
900
901 // Helper method that copies <iset> and takes its complement,
902 // returning false if Check succeeds.
CheckComplement(const QuicIntervalSet<int> & iset,int comp_min,int comp_max,int count,...)903 static bool CheckComplement(const QuicIntervalSet<int>& iset, int comp_min,
904 int comp_max, int count, ...) {
905 QuicIntervalSet<int> iset_copy = iset;
906 iset_copy.Complement(comp_min, comp_max);
907 bool result = true;
908 va_list ap;
909 va_start(ap, count);
910 if (!VA_Check(iset_copy, count, ap)) {
911 result = false;
912 }
913 va_end(ap);
914 return result;
915 }
916
TEST_F(QuicIntervalSetTest,MultiIntervalComplement)917 TEST_F(QuicIntervalSetTest, MultiIntervalComplement) {
918 // Initialize a small test set:
919 QuicIntervalSet<int> iset;
920 iset.Add(100, 200);
921 iset.Add(300, 400);
922 iset.Add(500, 600);
923
924 // |----- i -----|
925 // |----- comp -----|
926 EXPECT_TRUE(CheckComplement(iset, 0, 50, 1, 0, 50));
927
928 // |----- i -----|
929 // |----- comp -----|
930 EXPECT_TRUE(CheckComplement(iset, 0, 200, 1, 0, 100));
931 EXPECT_TRUE(CheckComplement(iset, 0, 220, 2, 0, 100, 200, 220));
932
933 // |----- i -----|
934 // |----- comp -----|
935 EXPECT_TRUE(CheckComplement(iset, 100, 600, 2, 200, 300, 400, 500));
936
937 // |---------- i ----------|
938 // |----- comp -----|
939 EXPECT_TRUE(CheckComplement(iset, 300, 400, 0));
940 EXPECT_TRUE(CheckComplement(iset, 250, 400, 1, 250, 300));
941 EXPECT_TRUE(CheckComplement(iset, 300, 450, 1, 400, 450));
942 EXPECT_TRUE(CheckComplement(iset, 250, 450, 2, 250, 300, 400, 450));
943
944 // |----- i -----|
945 // |---------- comp ----------|
946 EXPECT_TRUE(
947 CheckComplement(iset, 0, 700, 4, 0, 100, 200, 300, 400, 500, 600, 700));
948
949 // |----- i -----|
950 // |----- comp -----|
951 EXPECT_TRUE(CheckComplement(iset, 400, 700, 2, 400, 500, 600, 700));
952 EXPECT_TRUE(CheckComplement(iset, 350, 700, 2, 400, 500, 600, 700));
953
954 // |----- i -----|
955 // |----- comp -----|
956 EXPECT_TRUE(CheckComplement(iset, 700, 800, 1, 700, 800));
957 }
958
959 // Verifies ToString, operator<< don't assert.
TEST_F(QuicIntervalSetTest,ToString)960 TEST_F(QuicIntervalSetTest, ToString) {
961 QuicIntervalSet<int> iset;
962 iset.Add(300, 400);
963 iset.Add(100, 200);
964 iset.Add(500, 600);
965 EXPECT_TRUE(!iset.ToString().empty());
966 QUIC_VLOG(2) << iset;
967 // Order and format of ToString() output is guaranteed.
968 EXPECT_EQ("{ [100, 200) [300, 400) [500, 600) }", iset.ToString());
969 EXPECT_EQ("{ [1, 2) }", QuicIntervalSet<int>(1, 2).ToString());
970 EXPECT_EQ("{ }", QuicIntervalSet<int>().ToString());
971 }
972
TEST_F(QuicIntervalSetTest,ConstructionDiscardsEmptyInterval)973 TEST_F(QuicIntervalSetTest, ConstructionDiscardsEmptyInterval) {
974 EXPECT_TRUE(QuicIntervalSet<int>(QuicInterval<int>(2, 2)).Empty());
975 EXPECT_TRUE(QuicIntervalSet<int>(2, 2).Empty());
976 EXPECT_FALSE(QuicIntervalSet<int>(QuicInterval<int>(2, 3)).Empty());
977 EXPECT_FALSE(QuicIntervalSet<int>(2, 3).Empty());
978 }
979
TEST_F(QuicIntervalSetTest,Swap)980 TEST_F(QuicIntervalSetTest, Swap) {
981 QuicIntervalSet<int> a, b;
982 a.Add(300, 400);
983 b.Add(100, 200);
984 b.Add(500, 600);
985 std::swap(a, b);
986 EXPECT_TRUE(Check(a, 2, 100, 200, 500, 600));
987 EXPECT_TRUE(Check(b, 1, 300, 400));
988 std::swap(a, b);
989 EXPECT_TRUE(Check(a, 1, 300, 400));
990 EXPECT_TRUE(Check(b, 2, 100, 200, 500, 600));
991 }
992
TEST_F(QuicIntervalSetTest,OutputReturnsOstreamRef)993 TEST_F(QuicIntervalSetTest, OutputReturnsOstreamRef) {
994 std::stringstream ss;
995 const QuicIntervalSet<int> v(QuicInterval<int>(1, 2));
996 auto return_type_is_a_ref = [](std::ostream&) {};
997 return_type_is_a_ref(ss << v);
998 }
999
1000 struct NotOstreamable {
operator <quic::test::__anon5258c8100111::NotOstreamable1001 bool operator<(const NotOstreamable&) const { return false; }
operator >quic::test::__anon5258c8100111::NotOstreamable1002 bool operator>(const NotOstreamable&) const { return false; }
operator !=quic::test::__anon5258c8100111::NotOstreamable1003 bool operator!=(const NotOstreamable&) const { return false; }
operator >=quic::test::__anon5258c8100111::NotOstreamable1004 bool operator>=(const NotOstreamable&) const { return true; }
operator <=quic::test::__anon5258c8100111::NotOstreamable1005 bool operator<=(const NotOstreamable&) const { return true; }
operator ==quic::test::__anon5258c8100111::NotOstreamable1006 bool operator==(const NotOstreamable&) const { return true; }
1007 };
1008
TEST_F(QuicIntervalSetTest,IntervalOfTypeWithNoOstreamSupport)1009 TEST_F(QuicIntervalSetTest, IntervalOfTypeWithNoOstreamSupport) {
1010 const NotOstreamable v;
1011 const QuicIntervalSet<NotOstreamable> d(QuicInterval<NotOstreamable>(v, v));
1012 // EXPECT_EQ builds a string representation of d. If d::operator<<()
1013 // would be defined then this test would not compile because NotOstreamable
1014 // objects lack the operator<<() support.
1015 EXPECT_EQ(d, d);
1016 }
1017
1018 class QuicIntervalSetInitTest : public QuicTest {
1019 protected:
1020 const std::vector<QuicInterval<int>> intervals_{{0, 1}, {2, 4}};
1021 };
1022
TEST_F(QuicIntervalSetInitTest,DirectInit)1023 TEST_F(QuicIntervalSetInitTest, DirectInit) {
1024 std::initializer_list<QuicInterval<int>> il = {{0, 1}, {2, 3}, {3, 4}};
1025 QuicIntervalSet<int> s(il);
1026 EXPECT_THAT(s, ElementsAreArray(intervals_));
1027 }
1028
TEST_F(QuicIntervalSetInitTest,CopyInit)1029 TEST_F(QuicIntervalSetInitTest, CopyInit) {
1030 std::initializer_list<QuicInterval<int>> il = {{0, 1}, {2, 3}, {3, 4}};
1031 QuicIntervalSet<int> s = il;
1032 EXPECT_THAT(s, ElementsAreArray(intervals_));
1033 }
1034
TEST_F(QuicIntervalSetInitTest,AssignIterPair)1035 TEST_F(QuicIntervalSetInitTest, AssignIterPair) {
1036 QuicIntervalSet<int> s(0, 1000); // Make sure assign clears.
1037 s.assign(intervals_.begin(), intervals_.end());
1038 EXPECT_THAT(s, ElementsAreArray(intervals_));
1039 }
1040
TEST_F(QuicIntervalSetInitTest,AssignInitList)1041 TEST_F(QuicIntervalSetInitTest, AssignInitList) {
1042 QuicIntervalSet<int> s(0, 1000); // Make sure assign clears.
1043 s.assign({{0, 1}, {2, 3}, {3, 4}});
1044 EXPECT_THAT(s, ElementsAreArray(intervals_));
1045 }
1046
TEST_F(QuicIntervalSetInitTest,AssignmentInitList)1047 TEST_F(QuicIntervalSetInitTest, AssignmentInitList) {
1048 std::initializer_list<QuicInterval<int>> il = {{0, 1}, {2, 3}, {3, 4}};
1049 QuicIntervalSet<int> s;
1050 s = il;
1051 EXPECT_THAT(s, ElementsAreArray(intervals_));
1052 }
1053
TEST_F(QuicIntervalSetInitTest,BracedInitThenBracedAssign)1054 TEST_F(QuicIntervalSetInitTest, BracedInitThenBracedAssign) {
1055 QuicIntervalSet<int> s{{0, 1}, {2, 3}, {3, 4}};
1056 s = {{0, 1}, {2, 4}};
1057 EXPECT_THAT(s, ElementsAreArray(intervals_));
1058 }
1059
1060 } // namespace
1061 } // namespace test
1062 } // namespace quic
1063