1 // Copyright 2022 The Chromium Authors
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/first_party_sets/addition_overlaps_union_find.h"
6
7 #include "base/containers/flat_map.h"
8 #include "base/containers/flat_set.h"
9 #include "base/test/gtest_util.h"
10 #include "testing/gmock/include/gmock/gmock.h"
11
12 namespace net {
13 namespace {
14
TEST(AdditionOverlapsUnionFindUnittest,InvalidNumSets)15 TEST(AdditionOverlapsUnionFindUnittest, InvalidNumSets) {
16 EXPECT_CHECK_DEATH(AdditionOverlapsUnionFind(-1));
17 }
18
TEST(AdditionOverlapsUnionFindUnittest,EmptyUnionFind_Union_BoundsCheckFails)19 TEST(AdditionOverlapsUnionFindUnittest, EmptyUnionFind_Union_BoundsCheckFails) {
20 AdditionOverlapsUnionFind union_find(0);
21 EXPECT_CHECK_DEATH(union_find.Union(0, 0));
22 }
23
TEST(AdditionOverlapsUnionFindUnittest,Union_BoundsCheckFails)24 TEST(AdditionOverlapsUnionFindUnittest, Union_BoundsCheckFails) {
25 AdditionOverlapsUnionFind union_find(3);
26
27 // Test lower bound of [0, |num_sets|)
28 EXPECT_CHECK_DEATH(union_find.Union(-1, 0));
29 EXPECT_CHECK_DEATH(union_find.Union(0, -1));
30
31 // Test upper bound of [0, |num_sets|)
32 EXPECT_CHECK_DEATH(union_find.Union(0, 3));
33 EXPECT_CHECK_DEATH(union_find.Union(3, 0));
34 }
35
TEST(AdditionOverlapsUnionFindUnittest,SetsAreTheirInitRepresentatives)36 TEST(AdditionOverlapsUnionFindUnittest, SetsAreTheirInitRepresentatives) {
37 EXPECT_THAT(
38 AdditionOverlapsUnionFind(4).SetsMapping(),
39 AdditionOverlapsUnionFind::SetsMap({{0, {}}, {1, {}}, {2, {}}, {3, {}}}));
40 }
41
TEST(AdditionOverlapsUnionFindUnittest,Union_ChoosesLesserSetIndex)42 TEST(AdditionOverlapsUnionFindUnittest, Union_ChoosesLesserSetIndex) {
43 AdditionOverlapsUnionFind union_find(3);
44
45 union_find.Union(1, 2);
46 EXPECT_THAT(union_find.SetsMapping(),
47 AdditionOverlapsUnionFind::SetsMap({{0, {}}, {1, {2}}}));
48
49 union_find.Union(0, 1);
50 EXPECT_THAT(union_find.SetsMapping(), AdditionOverlapsUnionFind::SetsMap({
51 {0, {1, 2}},
52 }));
53 }
54
TEST(AdditionOverlapsUnionFindUnittest,Union_NoOp_SameSet)55 TEST(AdditionOverlapsUnionFindUnittest, Union_NoOp_SameSet) {
56 AdditionOverlapsUnionFind uf(4);
57 for (int i = 0; i < 4; i++) {
58 uf.Union(i, i);
59 }
60 EXPECT_THAT(
61 AdditionOverlapsUnionFind(4).SetsMapping(),
62 AdditionOverlapsUnionFind::SetsMap({{0, {}}, {1, {}}, {2, {}}, {3, {}}}));
63 }
64
TEST(AdditionOverlapsUnionFindUnittest,Union_NoOp_SharedRepresentative)65 TEST(AdditionOverlapsUnionFindUnittest, Union_NoOp_SharedRepresentative) {
66 AdditionOverlapsUnionFind union_find(4);
67
68 union_find.Union(0, 2);
69 EXPECT_THAT(union_find.SetsMapping(),
70 AdditionOverlapsUnionFind::SetsMap({{0, {2}}, {1, {}}, {3, {}}}));
71
72 union_find.Union(0, 2);
73 EXPECT_THAT(union_find.SetsMapping(),
74 AdditionOverlapsUnionFind::SetsMap({{0, {2}}, {1, {}}, {3, {}}}));
75
76 union_find.Union(2, 0);
77 EXPECT_THAT(union_find.SetsMapping(),
78 AdditionOverlapsUnionFind::SetsMap({{0, {2}}, {1, {}}, {3, {}}}));
79 }
80
81 } // namespace
82 } // namespace net
83