1 /**
2 * Copyright (c) 2021-2024 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #ifndef PANDA_VERIFIER_UTIL_SET_OPERATIONS_
17 #define PANDA_VERIFIER_UTIL_SET_OPERATIONS_
18
19 #include <cstddef>
20 #include "function_traits.h"
21
22 namespace ark::verifier {
23 using std::size_t;
24
25 template <size_t N, class... Args>
26 struct PackElement {
27 // NOLINTNEXTLINE(readability-identifier-naming)
28 using type = typename std::tuple_element<N, std::tuple<Args...>>::type;
29 };
30
31 template <size_t N, class... Args>
32 using PackElementT = typename PackElement<N, Args...>::type;
33
34 template <typename... Args>
SetIntersection(const Args &...args)35 PackElementT<0, Args...> SetIntersection(const Args &...args)
36 {
37 using S = PackElementT<0, Args...>;
38 using EltType = typename S::key_type;
39 using IterType = typename S::const_iterator;
40 std::array<IterType, sizeof...(Args)> iters {args.cbegin()...};
41 std::array<IterType, sizeof...(Args)> ends {args.cend()...};
42 auto step = [&iters, &ends](bool &aligned, EltType &val) {
43 size_t min = 0;
44 aligned = true;
45 for (size_t idx = 0; idx < iters.size(); ++idx) {
46 if (iters[idx] == ends[idx]) {
47 return false;
48 }
49 aligned = aligned && (*iters[idx] == *iters[min]);
50 if (*iters[idx] < *iters[min]) {
51 min = idx;
52 }
53 }
54 if (aligned) {
55 val = *iters[min];
56 }
57 ++iters[min];
58 return true;
59 };
60 bool store = false;
61 EltType val;
62 S result;
63 while (step(store, val)) {
64 if (store) {
65 result.insert(val);
66 }
67 }
68 return result;
69 }
70
71 template <typename... Args>
SetUnion(const Args &...args)72 PackElementT<0, Args...> SetUnion(const Args &...args)
73 {
74 using S = PackElementT<0, Args...>;
75 auto un = [](const S &lhs, const S &rhs) -> S {
76 S result = lhs;
77 result.insert(rhs.cbegin(), rhs.cend());
78 return result;
79 };
80 return NAry {un}(args...);
81 }
82
83 template <typename S>
SetDifference(const S & lhs,const S & rhs)84 S SetDifference(const S &lhs, const S &rhs)
85 {
86 S intersection = SetIntersection(lhs, rhs);
87 S result;
88 for (const auto &elt : lhs) {
89 if (rhs.count(elt) == 0) {
90 result.insert(elt);
91 }
92 }
93 return result;
94 }
95
96 template <typename Arg, typename... Args>
SetDifference(const Arg & arg,const Args &...args)97 Arg SetDifference(const Arg &arg, const Args &...args)
98 {
99 Arg sum = SetUnion(args...);
100 Arg intersection = SetIntersection(arg, sum);
101 Arg result;
102 for (const auto &elt : arg) {
103 if (intersection.count(elt) == 0) {
104 result.insert(elt);
105 }
106 }
107 return result;
108 }
109
110 template <typename S, typename C>
ToSet(const C & c)111 S ToSet(const C &c)
112 {
113 S result;
114 result.insert(c.cbegin(), c.cend());
115 return result;
116 }
117 } // namespace ark::verifier
118
119 #endif // !PANDA_VERIFIER_UTIL_SET_OPERATIONS_
120