1 /**
2 * Copyright (c) 2021-2022 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 panda::verifier {
23 using std::size_t;
24
25 template <size_t N, class... Args>
26 struct pack_element {
27 using type = typename std::tuple_element<N, std::tuple<Args...>>::type;
28 };
29
30 template <size_t N, class... Args>
31 using pack_element_t = typename pack_element<N, Args...>::type;
32
33 template <typename... Args>
SetIntersection(const Args &...args)34 pack_element_t<0, Args...> SetIntersection(const Args &... args)
35 {
36 using S = pack_element_t<0, Args...>;
37 using elt_type = typename S::key_type;
38 using iter_type = typename S::const_iterator;
39 std::array<iter_type, sizeof...(Args)> iters {args.cbegin()...};
40 std::array<iter_type, sizeof...(Args)> ends {args.cend()...};
41 auto step = [&iters, &ends](bool &aligned, elt_type &val) {
42 size_t min = 0;
43 aligned = true;
44 for (size_t idx = 0; idx < iters.size(); ++idx) {
45 if (iters[idx] == ends[idx]) {
46 return false;
47 }
48 aligned = aligned && (*iters[idx] == *iters[min]);
49 if (*iters[idx] < *iters[min]) {
50 min = idx;
51 }
52 }
53 if (aligned) {
54 val = *iters[min];
55 }
56 ++iters[min];
57 return true;
58 };
59 bool store = false;
60 elt_type val;
61 S result;
62 while (step(store, val)) {
63 if (store) {
64 result.insert(val);
65 }
66 }
67 return result;
68 }
69
70 template <typename... Args>
SetUnion(const Args &...args)71 pack_element_t<0, Args...> SetUnion(const Args &... args)
72 {
73 using S = pack_element_t<0, Args...>;
74 auto un = [](const S &lhs, const S &rhs) -> S {
75 S result = lhs;
76 result.insert(rhs.cbegin(), rhs.cend());
77 return result;
78 };
79 return n_ary {un}(args...);
80 }
81
82 template <typename S>
SetDifference(const S & lhs,const S & rhs)83 S SetDifference(const S &lhs, const S &rhs)
84 {
85 S intersection = SetIntersection(lhs, rhs);
86 S result;
87 for (const auto &elt : lhs) {
88 if (rhs.count(elt) == 0) {
89 result.insert(elt);
90 }
91 }
92 return result;
93 }
94
95 template <typename Arg, typename... Args>
SetDifference(const Arg & arg,const Args &...args)96 Arg SetDifference(const Arg &arg, const Args &... args)
97 {
98 Arg sum = SetUnion(args...);
99 Arg intersection = SetIntersection(arg, sum);
100 Arg result;
101 for (const auto &elt : arg) {
102 if (intersection.count(elt) == 0) {
103 result.insert(elt);
104 }
105 }
106 return result;
107 }
108
109 template <typename S, typename C>
ToSet(const C & c)110 S ToSet(const C &c)
111 {
112 S result;
113 result.insert(c.cbegin(), c.cend());
114 return result;
115 }
116 } // namespace panda::verifier
117
118 #endif // !PANDA_VERIFIER_UTIL_SET_OPERATIONS__
119