2 * Copyright 2011-present Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 #include <folly/sorted_vector_types.h>
23 #include <folly/portability/GMock.h>
24 #include <folly/portability/GTest.h>
26 using folly::sorted_vector_set;
27 using folly::sorted_vector_map;
33 bool operator()(const T& a, const T& b) const {
38 template <class Container>
39 void check_invariant(Container& c) {
47 for (; it != end; ++it, ++prev) {
48 EXPECT_TRUE(c.value_comp()(*prev, *it));
52 struct OneAtATimePolicy {
53 template <class Container>
54 void increase_capacity(Container& c) {
55 if (c.size() == c.capacity()) {
56 c.reserve(c.size() + 1);
61 struct CountCopyCtor {
62 explicit CountCopyCtor() : val_(0) {}
64 explicit CountCopyCtor(int val) : val_(val), count_(0) {}
66 CountCopyCtor(const CountCopyCtor& c)
68 , count_(c.count_ + 1)
71 bool operator<(const CountCopyCtor& o) const {
81 friend bool operator==(Opaque a, Opaque b) {
82 return a.value == b.value;
84 friend bool operator<(Opaque a, Opaque b) {
85 return a.value < b.value;
87 struct Compare : std::less<int>, std::less<Opaque> {
88 using is_transparent = void;
89 using std::less<int>::operator();
90 using std::less<Opaque>::operator();
91 bool operator()(int a, Opaque b) const {
92 return std::less<int>::operator()(a, b.value);
94 bool operator()(Opaque a, int b) const {
95 return std::less<int>::operator()(a.value, b);
102 TEST(SortedVectorTypes, SimpleSetTest) {
103 sorted_vector_set<int> s;
104 EXPECT_TRUE(s.empty());
105 for (int i = 0; i < 1000; ++i) {
106 s.insert(rand() % 100000);
108 EXPECT_FALSE(s.empty());
111 sorted_vector_set<int> s2;
112 s2.insert(s.begin(), s.end());
114 EXPECT_TRUE(s == s2);
116 auto it = s2.lower_bound(32);
119 it = s2.lower_bound(32);
122 auto oldSz = s2.size();
124 EXPECT_TRUE(s2.size() == oldSz + 1);
127 const sorted_vector_set<int>& cs2 = s2;
128 auto range = cs2.equal_range(32);
129 auto lbound = cs2.lower_bound(32);
130 auto ubound = cs2.upper_bound(32);
131 EXPECT_TRUE(range.first == lbound);
132 EXPECT_TRUE(range.second == ubound);
133 EXPECT_TRUE(range.first != cs2.end());
134 EXPECT_TRUE(range.second != cs2.end());
135 EXPECT_TRUE(cs2.count(32) == 1);
136 EXPECT_FALSE(cs2.find(32) == cs2.end());
139 s2.insert(s2.begin() + 3, 33);
140 EXPECT_TRUE(s2.find(33) != s2.begin());
141 EXPECT_TRUE(s2.find(33) != s2.end());
147 EXPECT_FALSE(it == s2.end());
149 EXPECT_TRUE(s2.size() == oldSz);
152 sorted_vector_set<int> cpy(s);
153 check_invariant(cpy);
154 EXPECT_TRUE(cpy == s);
155 sorted_vector_set<int> cpy2(s);
157 EXPECT_TRUE(cpy2 != cpy);
158 EXPECT_TRUE(cpy2 != s);
159 check_invariant(cpy2);
160 EXPECT_TRUE(cpy2.count(100001) == 1);
162 check_invariant(cpy2);
164 EXPECT_TRUE(s != cpy);
165 EXPECT_TRUE(s != cpy2);
166 EXPECT_TRUE(cpy2 == cpy);
169 TEST(SortedVectorTypes, TransparentSetTest) {
170 sorted_vector_set<Opaque, Opaque::Compare> s;
171 EXPECT_TRUE(s.empty());
172 for (int i = 0; i < 1000; ++i) {
173 s.insert(Opaque{rand() % 100000});
175 EXPECT_FALSE(s.empty());
178 sorted_vector_set<Opaque, Opaque::Compare> s2;
179 s2.insert(s.begin(), s.end());
181 EXPECT_TRUE(s == s2);
183 auto it = s2.lower_bound(32);
184 if (it->value == 32) {
186 it = s2.lower_bound(32);
189 auto oldSz = s2.size();
190 s2.insert(it, Opaque{32});
191 EXPECT_TRUE(s2.size() == oldSz + 1);
194 const sorted_vector_set<Opaque, Opaque::Compare>& cs2 = s2;
195 auto range = cs2.equal_range(32);
196 auto lbound = cs2.lower_bound(32);
197 auto ubound = cs2.upper_bound(32);
198 EXPECT_TRUE(range.first == lbound);
199 EXPECT_TRUE(range.second == ubound);
200 EXPECT_TRUE(range.first != cs2.end());
201 EXPECT_TRUE(range.second != cs2.end());
202 EXPECT_TRUE(cs2.count(32) == 1);
203 EXPECT_FALSE(cs2.find(32) == cs2.end());
206 s2.insert(s2.begin() + 3, Opaque{33});
207 EXPECT_TRUE(s2.find(33) != s2.begin());
208 EXPECT_TRUE(s2.find(33) != s2.end());
210 s2.erase(Opaque{33});
214 EXPECT_FALSE(it == s2.end());
216 EXPECT_TRUE(s2.size() == oldSz);
219 sorted_vector_set<Opaque, Opaque::Compare> cpy(s);
220 check_invariant(cpy);
221 EXPECT_TRUE(cpy == s);
222 sorted_vector_set<Opaque, Opaque::Compare> cpy2(s);
223 cpy2.insert(Opaque{100001});
224 EXPECT_TRUE(cpy2 != cpy);
225 EXPECT_TRUE(cpy2 != s);
226 check_invariant(cpy2);
227 EXPECT_TRUE(cpy2.count(100001) == 1);
229 check_invariant(cpy2);
231 EXPECT_TRUE(s != cpy);
232 EXPECT_TRUE(s != cpy2);
233 EXPECT_TRUE(cpy2 == cpy);
236 TEST(SortedVectorTypes, BadHints) {
237 for (int toInsert = -1; toInsert <= 7; ++toInsert) {
238 for (int hintPos = 0; hintPos <= 4; ++hintPos) {
239 sorted_vector_set<int> s;
240 for (int i = 0; i <= 3; ++i) {
243 s.insert(s.begin() + hintPos, toInsert);
244 size_t expectedSize = (toInsert % 2) == 0 ? 4 : 5;
245 EXPECT_EQ(s.size(), expectedSize);
251 TEST(SortedVectorTypes, SimpleMapTest) {
252 sorted_vector_map<int,float> m;
253 for (int i = 0; i < 1000; ++i) {
260 EXPECT_TRUE(m.count(32) == 1);
261 EXPECT_DOUBLE_EQ(100.0, m.at(32));
262 EXPECT_FALSE(m.find(32) == m.end());
264 EXPECT_TRUE(m.find(32) == m.end());
266 EXPECT_THROW(m.at(32), std::out_of_range);
268 sorted_vector_map<int,float> m2 = m;
269 EXPECT_TRUE(m2 == m);
270 EXPECT_FALSE(m2 != m);
271 auto it = m2.lower_bound(1 << 20);
272 EXPECT_TRUE(it == m2.end());
273 m2.insert(it, std::make_pair(1 << 20, 10.0f));
275 EXPECT_TRUE(m2.count(1 << 20) == 1);
277 EXPECT_TRUE(m <= m2);
279 const sorted_vector_map<int,float>& cm = m;
280 auto range = cm.equal_range(42);
281 auto lbound = cm.lower_bound(42);
282 auto ubound = cm.upper_bound(42);
283 EXPECT_TRUE(range.first == lbound);
284 EXPECT_TRUE(range.second == ubound);
285 EXPECT_FALSE(range.first == cm.end());
286 EXPECT_FALSE(range.second == cm.end());
287 m.erase(m.lower_bound(42));
290 sorted_vector_map<int,float> m3;
291 m3.insert(m2.begin(), m2.end());
293 EXPECT_TRUE(m3 == m2);
294 EXPECT_FALSE(m3 == m);
296 EXPECT_TRUE(m != m2);
297 EXPECT_TRUE(m2 == m3);
298 EXPECT_TRUE(m3 != m);
303 EXPECT_TRUE(m3 != m2);
304 EXPECT_TRUE(m3 != m);
305 EXPECT_TRUE(m == m2);
308 m.insert(m.begin() + 3, std::make_pair(1 << 15, 1.0f));
312 TEST(SortedVectorTypes, TransparentMapTest) {
313 sorted_vector_map<Opaque, float, Opaque::Compare> m;
314 for (int i = 0; i < 1000; ++i) {
315 m[Opaque{i}] = i / 1000.0;
319 m[Opaque{32}] = 100.0;
321 EXPECT_TRUE(m.count(32) == 1);
322 EXPECT_DOUBLE_EQ(100.0, m.at(Opaque{32}));
323 EXPECT_FALSE(m.find(32) == m.end());
325 EXPECT_TRUE(m.find(32) == m.end());
327 EXPECT_THROW(m.at(Opaque{32}), std::out_of_range);
329 sorted_vector_map<Opaque, float, Opaque::Compare> m2 = m;
330 EXPECT_TRUE(m2 == m);
331 EXPECT_FALSE(m2 != m);
332 auto it = m2.lower_bound(1 << 20);
333 EXPECT_TRUE(it == m2.end());
334 m2.insert(it, std::make_pair(Opaque{1 << 20}, 10.0f));
336 EXPECT_TRUE(m2.count(1 << 20) == 1);
338 EXPECT_TRUE(m <= m2);
340 const sorted_vector_map<Opaque, float, Opaque::Compare>& cm = m;
341 auto range = cm.equal_range(42);
342 auto lbound = cm.lower_bound(42);
343 auto ubound = cm.upper_bound(42);
344 EXPECT_TRUE(range.first == lbound);
345 EXPECT_TRUE(range.second == ubound);
346 EXPECT_FALSE(range.first == cm.end());
347 EXPECT_FALSE(range.second == cm.end());
348 m.erase(m.lower_bound(42));
351 sorted_vector_map<Opaque, float, Opaque::Compare> m3;
352 m3.insert(m2.begin(), m2.end());
354 EXPECT_TRUE(m3 == m2);
355 EXPECT_FALSE(m3 == m);
357 EXPECT_TRUE(m != m2);
358 EXPECT_TRUE(m2 == m3);
359 EXPECT_TRUE(m3 != m);
364 EXPECT_TRUE(m3 != m2);
365 EXPECT_TRUE(m3 != m);
366 EXPECT_TRUE(m == m2);
369 m.insert(m.begin() + 3, std::make_pair(Opaque{1 << 15}, 1.0f));
373 TEST(SortedVectorTypes, Sizes) {
374 EXPECT_EQ(sizeof(sorted_vector_set<int>),
375 sizeof(std::vector<int>));
376 EXPECT_EQ(sizeof(sorted_vector_map<int,int>),
377 sizeof(std::vector<std::pair<int,int> >));
379 typedef sorted_vector_set<int,std::less<int>,
380 std::allocator<int>,OneAtATimePolicy> SetT;
381 typedef sorted_vector_map<int,int,std::less<int>,
382 std::allocator<std::pair<int,int>>,OneAtATimePolicy> MapT;
384 EXPECT_EQ(sizeof(SetT), sizeof(std::vector<int>));
385 EXPECT_EQ(sizeof(MapT), sizeof(std::vector<std::pair<int,int> >));
388 TEST(SortedVectorTypes, InitializerLists) {
389 sorted_vector_set<int> empty_initialized_set{};
390 EXPECT_TRUE(empty_initialized_set.empty());
392 sorted_vector_set<int> singleton_initialized_set{1};
393 EXPECT_EQ(1, singleton_initialized_set.size());
394 EXPECT_EQ(1, *singleton_initialized_set.begin());
396 sorted_vector_set<int> forward_initialized_set{1, 2};
397 sorted_vector_set<int> backward_initialized_set{2, 1};
398 EXPECT_EQ(2, forward_initialized_set.size());
399 EXPECT_EQ(1, *forward_initialized_set.begin());
400 EXPECT_EQ(2, *forward_initialized_set.rbegin());
401 EXPECT_TRUE(forward_initialized_set == backward_initialized_set);
403 sorted_vector_map<int,int> empty_initialized_map{};
404 EXPECT_TRUE(empty_initialized_map.empty());
406 sorted_vector_map<int,int> singleton_initialized_map{{1,10}};
407 EXPECT_EQ(1, singleton_initialized_map.size());
408 EXPECT_EQ(10, singleton_initialized_map[1]);
410 sorted_vector_map<int,int> forward_initialized_map{{1,10}, {2,20}};
411 sorted_vector_map<int,int> backward_initialized_map{{2,20}, {1,10}};
412 EXPECT_EQ(2, forward_initialized_map.size());
413 EXPECT_EQ(10, forward_initialized_map[1]);
414 EXPECT_EQ(20, forward_initialized_map[2]);
415 EXPECT_TRUE(forward_initialized_map == backward_initialized_map);
418 TEST(SortedVectorTypes, CustomCompare) {
419 sorted_vector_set<int,less_invert<int> > s;
420 for (int i = 0; i < 200; ++i) {
425 sorted_vector_map<int,float,less_invert<int> > m;
426 for (int i = 0; i < 200; ++i) {
432 TEST(SortedVectorTypes, GrowthPolicy) {
433 typedef sorted_vector_set<CountCopyCtor,
434 std::less<CountCopyCtor>,
435 std::allocator<CountCopyCtor>,
440 for (int i = 0; i < 20; ++i) {
441 a.insert(CountCopyCtor(i));
444 SetT::iterator it = a.begin();
445 EXPECT_FALSE(it == a.end());
447 EXPECT_EQ(it->val_, 0);
448 // 1 copy for the initial insertion, 19 more for reallocs on the
449 // additional insertions.
450 EXPECT_EQ(it->count_, 20);
453 std::list<CountCopyCtor> v;
454 for (int i = 0; i < 20; ++i) {
455 v.emplace_back(20 + i);
457 a.insert(v.begin(), v.end());
461 EXPECT_FALSE(it == a.end());
463 EXPECT_EQ(it->val_, 0);
464 // Should be only 1 more copy for inserting this above range.
465 EXPECT_EQ(it->count_, 21);
469 TEST(SortedVectorTest, EmptyTest) {
470 sorted_vector_set<int> emptySet;
471 EXPECT_TRUE(emptySet.lower_bound(10) == emptySet.end());
472 EXPECT_TRUE(emptySet.find(10) == emptySet.end());
474 sorted_vector_map<int,int> emptyMap;
475 EXPECT_TRUE(emptyMap.lower_bound(10) == emptyMap.end());
476 EXPECT_TRUE(emptyMap.find(10) == emptyMap.end());
477 EXPECT_THROW(emptyMap.at(10), std::out_of_range);
480 TEST(SortedVectorTest, MoveTest) {
481 sorted_vector_set<std::unique_ptr<int>> s;
482 s.insert(std::make_unique<int>(5));
483 s.insert(s.end(), std::make_unique<int>(10));
484 EXPECT_EQ(s.size(), 2);
486 for (const auto& p : s) {
487 EXPECT_TRUE(*p == 5 || *p == 10);
490 sorted_vector_map<int, std::unique_ptr<int>> m;
491 m.insert(std::make_pair(5, std::make_unique<int>(5)));
492 m.insert(m.end(), std::make_pair(10, std::make_unique<int>(10)));
495 EXPECT_EQ(*m[10], 10);
498 TEST(SortedVectorTest, ShrinkTest) {
499 sorted_vector_set<int> s;
501 // Hopefully your resize policy doubles when capacity is full, or this will
503 while (s.capacity() == s.size()) {
507 // The standard does not actually enforce that this be true, but assume that
508 // vector::shrink_to_fit respects the caller.
509 EXPECT_EQ(s.capacity(), s.size());
512 TEST(SortedVectorTypes, EraseTest) {
513 sorted_vector_set<int> s1;
515 sorted_vector_set<int> s2(s1);
516 EXPECT_EQ(0, s1.erase(0));
520 std::vector<int> extractValues(sorted_vector_set<CountCopyCtor> const& in) {
521 std::vector<int> ret;
525 std::back_inserter(ret),
526 [](const CountCopyCtor& c) { return c.val_; });
530 template <typename T, typename S>
531 std::vector<T> makeVectorOfWrappers(std::vector<S> ss) {
533 ts.reserve(ss.size());
534 for (auto const& s : ss) {
540 TEST(SortedVectorTypes, TestSetBulkInsertionSortMerge) {
541 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
543 sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
544 check_invariant(vset);
546 // Add an unsorted range that will have to be merged in.
547 s = makeVectorOfWrappers<CountCopyCtor, int>({10, 7, 5, 1});
549 vset.insert(s.begin(), s.end());
550 check_invariant(vset);
551 EXPECT_EQ(vset.rbegin()->count_, 1);
555 testing::ElementsAreArray({1, 2, 4, 5, 6, 7, 8, 10}));
558 TEST(SortedVectorTypes, TestSetBulkInsertionMiddleValuesEqualDuplication) {
559 auto s = makeVectorOfWrappers<CountCopyCtor, int>({4, 6, 8});
561 sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
562 check_invariant(vset);
564 s = makeVectorOfWrappers<CountCopyCtor, int>({8, 10, 12});
566 vset.insert(s.begin(), s.end());
567 check_invariant(vset);
568 EXPECT_EQ(vset.rbegin()->count_, 1);
572 testing::ElementsAreArray({4, 6, 8, 10, 12}));
575 TEST(SortedVectorTypes, TestSetBulkInsertionSortMergeDups) {
576 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
578 sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
579 check_invariant(vset);
581 // Add an unsorted range that will have to be merged in.
582 s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2});
584 vset.insert(s.begin(), s.end());
585 check_invariant(vset);
586 EXPECT_EQ(vset.rbegin()->count_, 1);
588 extractValues(vset), testing::ElementsAreArray({2, 4, 5, 6, 8, 10}));
591 TEST(SortedVectorTypes, TestSetInsertionDupsOneByOne) {
592 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
594 sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
595 check_invariant(vset);
597 // Add an unsorted range that will have to be merged in.
598 s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2});
600 for (const auto& elem : s) {
603 check_invariant(vset);
604 EXPECT_EQ(vset.rbegin()->count_, 3);
606 extractValues(vset), testing::ElementsAreArray({2, 4, 5, 6, 8, 10}));
609 TEST(SortedVectorTypes, TestSetBulkInsertionSortNoMerge) {
610 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
612 sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
613 check_invariant(vset);
615 // Add an unsorted range that will not have to be merged in.
616 s = makeVectorOfWrappers<CountCopyCtor, int>({20, 15, 16, 13});
618 vset.insert(s.begin(), s.end());
619 check_invariant(vset);
620 EXPECT_EQ(vset.rbegin()->count_, 1);
623 testing::ElementsAreArray({2, 4, 6, 8, 13, 15, 16, 20}));
626 TEST(SortedVectorTypes, TestSetBulkInsertionNoSortMerge) {
627 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
629 sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
630 check_invariant(vset);
632 // Add a sorted range that will have to be merged in.
633 s = makeVectorOfWrappers<CountCopyCtor, int>({1, 3, 5, 9});
635 vset.insert(s.begin(), s.end());
636 check_invariant(vset);
637 EXPECT_EQ(vset.rbegin()->count_, 1);
639 extractValues(vset), testing::ElementsAreArray({1, 2, 3, 4, 5, 6, 8, 9}));
642 TEST(SortedVectorTypes, TestSetBulkInsertionNoSortNoMerge) {
643 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
645 sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
646 check_invariant(vset);
648 // Add a sorted range that will not have to be merged in.
649 s = makeVectorOfWrappers<CountCopyCtor, int>({21, 22, 23, 24});
651 vset.insert(s.begin(), s.end());
652 check_invariant(vset);
653 EXPECT_EQ(vset.rbegin()->count_, 1);
656 testing::ElementsAreArray({2, 4, 6, 8, 21, 22, 23, 24}));
659 TEST(SortedVectorTypes, TestSetBulkInsertionEmptyRange) {
660 std::vector<CountCopyCtor> s;
661 EXPECT_TRUE(s.empty());
663 // insertion of empty range into empty container.
664 sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
665 check_invariant(vset);
667 s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
669 vset.insert(s.begin(), s.end());
671 // insertion of empty range into non-empty container.
673 vset.insert(s.begin(), s.end());
674 check_invariant(vset);
676 EXPECT_THAT(extractValues(vset), testing::ElementsAreArray({2, 4, 6, 8}));
679 // This is a test of compilation - the behavior has already been tested
680 // extensively above.
681 TEST(SortedVectorTypes, TestBulkInsertionUncopyableTypes) {
682 std::vector<std::pair<int, std::unique_ptr<int>>> s;
683 s.emplace_back(1, std::make_unique<int>(0));
685 sorted_vector_map<int, std::unique_ptr<int>> vmap(
686 std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
689 s.emplace_back(3, std::make_unique<int>(0));
691 std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
694 // A moveable and copyable struct, which we use to make sure that no copy
695 // operations are performed during bulk insertion if moving is an option.
698 explicit Movable(int x) : x_(x) {}
699 Movable(const Movable&) {
700 ADD_FAILURE() << "Copy ctor should not be called";
702 Movable& operator=(const Movable&) {
703 ADD_FAILURE() << "Copy assignment should not be called";
707 Movable(Movable&&) = default;
708 Movable& operator=(Movable&&) = default;
711 TEST(SortedVectorTypes, TestBulkInsertionMovableTypes) {
712 std::vector<std::pair<int, Movable>> s;
713 s.emplace_back(3, Movable(2));
714 s.emplace_back(1, Movable(0));
716 sorted_vector_map<int, Movable> vmap(
717 std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
720 s.emplace_back(4, Movable(3));
721 s.emplace_back(2, Movable(1));
723 std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
726 TEST(SortedVectorTypes, TestSetCreationFromVector) {
727 std::vector<int> vec = {3, 1, -1, 5, 0};
728 sorted_vector_set<int> vset(std::move(vec));
729 check_invariant(vset);
730 EXPECT_THAT(vset, testing::ElementsAreArray({-1, 0, 1, 3, 5}));
733 TEST(SortedVectorTypes, TestMapCreationFromVector) {
734 std::vector<std::pair<int, int>> vec = {
735 {3, 1}, {1, 5}, {-1, 2}, {5, 3}, {0, 3}};
736 sorted_vector_map<int, int> vmap(std::move(vec));
737 check_invariant(vmap);
738 auto contents = std::vector<std::pair<int, int>>(vmap.begin(), vmap.end());
739 auto expected_contents = std::vector<std::pair<int, int>>({
740 {-1, 2}, {0, 3}, {1, 5}, {3, 1}, {5, 3},
742 EXPECT_EQ(contents, expected_contents);