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