1 /* 2 * Copyright 2014 Google Inc. All rights reserved. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef FRUIT_META_SET_H 18 #define FRUIT_META_SET_H 19 20 #include <fruit/impl/fruit_assert.h> 21 #include <fruit/impl/meta/immutable_set.h> 22 #include <fruit/impl/meta/pair.h> 23 #include <fruit/impl/meta/vector.h> 24 25 namespace fruit { 26 namespace impl { 27 namespace meta { 28 29 // Set ::= Vector<Ts...>, with no duplicates. 30 31 using EmptySet = Vector<>; 32 33 template <typename T> 34 using ToSet1 = Vector<T>; 35 36 template <typename T, typename U> 37 using ToSet2 = Vector<T, U>; 38 39 using IsInSet = IsInVector; 40 41 // If S is a set with elements (T1, ..., Tn) this calculates 42 // F(InitialValue, F(T1, F(..., F(Tn) ...))). 43 // If S is EmptySet this returns InitialValue. 44 using FoldSet = FoldVector; 45 46 // If S is a set with elements (T1, ..., Tn) this calculates 47 // Combine(F(T1), Combine(F(T2),..., F(Tn) ...)). 48 // 49 // `Combine' must be associative, and CombineIdentity must be an identity value wrt Combine. 50 // Use this instead of FoldSet when possible, it shares more sub-instances when invoked multiple 51 // times with similar sets. 52 struct FoldSetWithCombine { 53 template <typename S, typename F, typename Combine, typename CombineIdentity> 54 struct apply { 55 using type = FoldVector(TransformVector(S, F), Combine, CombineIdentity); 56 }; 57 }; 58 59 // Converts a set (T1,...,Tn) to a set (F(T1), ..., F(Tn)). 60 // F(T1), ..., F(Tn) must be distinct. 61 using TransformSet = TransformVector; 62 63 using SetSize = VectorSize; 64 65 using AddToSetUnchecked = PushFront; 66 67 struct AddToSet { 68 template <typename S, typename T> 69 struct apply { 70 using type = If(IsInSet(T, S), S, AddToSetUnchecked(S, T)); 71 }; 72 }; 73 74 // Checks if S1 is contained in S2. 75 struct IsContained { 76 template <typename S1, typename S2> 77 struct apply { 78 struct Helper { 79 template <typename CurrentResult, typename T> 80 struct apply { 81 using type = And(CurrentResult, IsInSet(T, S2)); 82 }; 83 }; 84 85 using type = FoldVector(S1, Helper, Bool<true>); 86 }; 87 }; 88 89 // Checks if S1 is disjoint from S2. 90 struct IsDisjoint { 91 template <typename S1, typename S2> 92 struct apply { 93 struct Helper { 94 template <typename CurrentResult, typename T> 95 struct apply { 96 using type = Or(CurrentResult, IsInSet(T, S2)); 97 }; 98 }; 99 100 using type = Not(FoldVector(S1, Helper, Bool<false>)); 101 }; 102 }; 103 104 struct IsEmptySet { 105 template <typename S> 106 struct apply { 107 using type = Bool<false>; 108 }; 109 }; 110 111 template <> 112 struct IsEmptySet::apply<Vector<>> { 113 using type = Bool<true>; 114 }; 115 116 using SetToVector = Identity; 117 118 // The vector must have no duplicates. 119 using VectorToSetUnchecked = Identity; 120 121 struct SetDifference { 122 template <typename S1, typename S2> 123 struct apply { 124 struct Helper { 125 template <typename CurrentResult, typename T> 126 struct apply { 127 using type = If(IsInSet(T, S2), CurrentResult, AddToSetUnchecked(CurrentResult, T)); 128 }; 129 }; 130 131 using type = FoldSet(S1, Helper, EmptySet); 132 }; 133 }; 134 135 struct SetIntersection { 136 template <typename S1, typename S2> 137 struct apply { 138 struct Helper { 139 template <typename CurrentResult, typename T> 140 struct apply { 141 using type = If(IsInSet(T, S2), AddToSetUnchecked(CurrentResult, T), CurrentResult); 142 }; 143 }; 144 145 using type = If(GreaterThan(SetSize(S1), SetSize(S2)), SetIntersection(S2, S1), FoldSet(S1, Helper, EmptySet)); 146 }; 147 }; 148 149 struct SetUnion { 150 template <typename S1, typename S2> 151 struct apply { 152 using type = If(GreaterThan(SetSize(S1), SetSize(S2)), SetUnion(S2, S1), 153 FoldSet(SetDifference(S1, S2), AddToSetUnchecked, S2)); 154 }; 155 }; 156 157 using SetUncheckedUnion = ConcatVectors; 158 159 struct IsSameSet { 160 template <typename S1, typename S2> 161 struct apply { 162 using type = And(IsContained(S1, S2), IsContained(S2, S1)); 163 }; 164 }; 165 166 // Returns an arbitrary element from the given set (that must be non-empty). 167 struct GetArbitrarySetElement { 168 template <typename S> 169 struct apply; 170 171 template <typename T, typename... Ts> 172 struct apply<Vector<T, Ts...>> { 173 using type = T; 174 }; 175 }; 176 177 } // namespace meta 178 } // namespace impl 179 } // namespace fruit 180 181 #endif // FRUIT_META_SET_H 182