1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
// Copyright 2022 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "net/first_party_sets/addition_overlaps_union_find.h"
#include <numeric>
#include "base/check_op.h"
#include "base/containers/flat_map.h"
#include "base/containers/flat_set.h"
namespace net {
AdditionOverlapsUnionFind::AdditionOverlapsUnionFind(int num_sets) {
CHECK_GE(num_sets, 0);
representatives_.resize(num_sets);
std::iota(representatives_.begin(), representatives_.end(), 0ul);
}
AdditionOverlapsUnionFind::~AdditionOverlapsUnionFind() = default;
void AdditionOverlapsUnionFind::Union(size_t set_x, size_t set_y) {
CHECK_GE(set_x, 0ul);
CHECK_LT(set_x, representatives_.size());
CHECK_GE(set_y, 0ul);
CHECK_LT(set_y, representatives_.size());
size_t root_x = Find(set_x);
size_t root_y = Find(set_y);
if (root_x == root_y)
return;
auto [parent, child] = std::minmax(root_x, root_y);
representatives_[child] = parent;
}
AdditionOverlapsUnionFind::SetsMap AdditionOverlapsUnionFind::SetsMapping() {
SetsMap sets;
// An insert into the flat_map and flat_set has O(n) complexity and
// populating sets this way will be O(n^2).
// This can be improved by creating an intermediate vector of pairs, each
// representing an entry in sets, and then constructing the map all at once.
// The intermediate vector stores pairs, using O(1) Insert. Another vector
// the size of |num_sets| will have to be used for O(1) Lookup into the
// first vector. This means making the intermediate vector will be O(n).
// After the intermediate vector is populated, and we can use
// base::MakeFlatMap to construct the mapping all at once.
// This improvement makes this method less straightforward however.
for (size_t i = 0; i < representatives_.size(); i++) {
size_t cur_rep = Find(i);
auto it = sets.emplace(cur_rep, base::flat_set<size_t>()).first;
if (i != cur_rep) {
it->second.insert(i);
}
}
return sets;
}
size_t AdditionOverlapsUnionFind::Find(size_t set) {
CHECK_GE(set, 0ul);
CHECK_LT(set, representatives_.size());
if (representatives_[set] != set)
representatives_[set] = Find(representatives_[set]);
return representatives_[set];
}
} // namespace net
|
