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