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 #ifndef NET_FIRST_PARTY_SETS_ADDITION_OVERLAPS_UNION_FIND_H_ 6 #define NET_FIRST_PARTY_SETS_ADDITION_OVERLAPS_UNION_FIND_H_ 7 8 #include "base/containers/flat_map.h" 9 #include "base/containers/flat_set.h" 10 #include "net/base/net_export.h" 11 12 namespace net { 13 14 // A helper class defining a Union-Find data structure that's used for merging 15 // disjoint transitively-overlapping sets together. 16 class NET_EXPORT AdditionOverlapsUnionFind { 17 public: 18 using SetsMap = base::flat_map<size_t, base::flat_set<size_t>>; 19 20 // The number of sets (num_sets) must be greater than or equal to zero. 21 explicit AdditionOverlapsUnionFind(int num_sets); 22 ~AdditionOverlapsUnionFind(); 23 24 AdditionOverlapsUnionFind(const AdditionOverlapsUnionFind&) = delete; 25 AdditionOverlapsUnionFind& operator=(const AdditionOverlapsUnionFind&) = 26 delete; 27 28 // Unions the two given sets together if they are in disjoint sets, and does 29 // nothing if they are non-disjoint. 30 // Unions are non-commutative for First-Party Sets; this method always chooses 31 // the set with the lesser index as the primary. 32 // Both set indices (set_x, set_y) must be in the range [0, num_sets) where 33 // num_sets is the argument given to the constructor. 34 // If Union is called when num_sets = 0, then this will crash. 35 void Union(size_t set_x, size_t set_y); 36 37 // Returns a mapping from an addition set index 'i' to a set of indices 38 // which all have 'i' as their representative. 39 SetsMap SetsMapping(); 40 41 private: 42 // Returns the index for the representative of the given set. 43 size_t Find(size_t set); 44 45 std::vector<size_t> representatives_; 46 }; 47 48 } // namespace net 49 50 #endif // NET_FIRST_PARTY_SETS_ADDITION_OVERLAPS_UNION_FIND_H_ 51