Version
menu_open
Wwise SDK 2024.1.0
AkSet.h
Go to the documentation of this file.
1 /*******************************************************************************
2 The content of this file includes portions of the AUDIOKINETIC Wwise Technology
3 released in source code form as part of the SDK installer package.
4 
5 Commercial License Usage
6 
7 Licensees holding valid commercial licenses to the AUDIOKINETIC Wwise Technology
8 may use this file in accordance with the end user license agreement provided
9 with the software or, alternatively, in accordance with the terms contained in a
10 written agreement between you and Audiokinetic Inc.
11 
12 Apache License Usage
13 
14 Alternatively, this file may be used under the Apache License, Version 2.0 (the
15 "Apache License"); you may not use this file except in compliance with the
16 Apache License. You may obtain a copy of the Apache License at
17 http://www.apache.org/licenses/LICENSE-2.0.
18 
19 Unless required by applicable law or agreed to in writing, software distributed
20 under the Apache License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES
21 OR CONDITIONS OF ANY KIND, either express or implied. See the Apache License for
22 the specific language governing permissions and limitations under the License.
23 
24  Copyright (c) 2024 Audiokinetic Inc.
25 *******************************************************************************/
26 
27 //////////////////////////////////////////////////////////////////////
28 //
29 // AkSet.h
30 //
31 //////////////////////////////////////////////////////////////////////
32 #ifndef _AKSET_H_
33 #define _AKSET_H_
34 
35 #include <AK/Tools/Common/AkKeyArray.h>
36 
37 // AkSetType
38 // - An optional set type specifier which is passed into some set operations. If it is not included, SetType_Inclusion is assumed.
39 //
40 enum AkSetType
41 {
42  SetType_Inclusion, // <- An AkSet object with type SetType_Inclusion is a set where each element in the array
43  // represents an element in the set. An empty array represents the empty set.
44  SetType_Exclusion // <- An AkSet object with type SetType_Exclusion is an 'inverted' set, where each element in the array
45  // represents and element NOT in the set. An empty array represents the universal set.
46 };
47 
48 template<typename T>
49 struct AkSetGetKey{ static AkForceInline T& Get(T& in_item){ return in_item; } };
50 
51 // AkSet
52 //
53 // Set container type, implemented as a sorted array of unique items
54 //
55 template< typename T, class U_POOL = ArrayPoolDefault, class uGrowBy = AkGrowByPolicy_DEFAULT, class TMovePolicy = AkAssignmentMovePolicy<T>, class TComparePolicy = AkDefaultSortedKeyCompare<T> >
56 class AkSet : public AkSortedKeyArray < T, T, U_POOL, AkSetGetKey<T>, uGrowBy, TMovePolicy, TComparePolicy >
57 {
58 public:
59  bool Contains(T in_item) const { return AkSortedKeyArray < T, T, U_POOL, AkSetGetKey<T>, uGrowBy, TMovePolicy, TComparePolicy >::Exists(in_item) != NULL; }
60 };
61 
62 // AkDisjoint
63 // - Returns true if the intersection of A and B is the empty set.
64 //
65 template< typename T, class U_POOL = ArrayPoolDefault, class uGrowBy, class TMovePolicy, class TComparePolicy >
66 static bool AkDisjoint(const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_A, const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_B)
67 {
68  typename AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>::Iterator itA = in_A.Begin();
69  typename AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>::Iterator itB = in_B.Begin();
70  while (itA != in_A.End() && itB != in_B.End())
71  {
72  if (*itA == *itB)
73  return false;
74  else if (*itA < *itB)
75  ++itA;
76  else
77  ++itB;
78  }
79  return true;
80 }
81 
82 // AkIntersect
83 // - Return true if the intersection of A and B is not the empty set.
84 //
85 template< typename T, class U_POOL, class uGrowBy, class TMovePolicy, class TComparePolicy >
86 static bool AkIntersect(const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_A, const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_B)
87 {
88  return !AkDisjoint(in_A, in_B);
89 }
90 
91 // AkIsSubset
92 // - Return true if in_A is a subset of in_B
93 //
94 template< typename T, class U_POOL, class uGrowBy, class TMovePolicy, class TComparePolicy >
95 static bool AkIsSubset(const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_A, const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_B)
96 {
97  typename AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>::Iterator itA = in_A.Begin();
98  typename AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>::Iterator itB = in_B.Begin();
99  while (itA != in_A.End() && itB != in_B.End())
100  {
101  if (TComparePolicy::Equal(&in_A, *itA, *itB))
102  {
103  ++itA; ++itB;
104  }
105  else if (TComparePolicy::Lesser(&in_A, *itA, *itB))
106  {
107  return false;//an element of A is not in B
108  }
109  else
110  ++itB;
111  }
112  return (itA == in_A.End());
113 }
114 
115 // AkCountIntersection
116 // - Helper function to count the number of elements that are in both in_A and in_B.
117 //
118 template< typename T, class U_POOL, class uGrowBy, class TMovePolicy, class TComparePolicy >
119 static AkUInt32 AkCountIntersection(const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_A, const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_B)
120 {
121  AkUInt32 uSize = 0;
122  typename AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>::Iterator itA = in_A.Begin();
123  typename AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>::Iterator itB = in_B.Begin();
124  while (itA != in_A.End() && itB != in_B.End())
125  {
126  if (TComparePolicy::Equal(&in_A, *itA, *itB))
127  {
128  ++uSize; ++itA; ++itB;
129  }
130  else if (TComparePolicy::Lesser(&in_A, *itA, *itB))
131  {
132  ++itA;
133  }
134  else
135  {
136  ++itB;
137  }
138  }
139  return uSize;
140 }
141 
142 // AkSubtraction
143 // - In-place set subtraction ( A = A - B )
144 //
145 template< typename T, class U_POOL, class uGrowBy, class TMovePolicy, class TComparePolicy>
146 static bool AkSubtraction(AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_A, const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_B)
147 {
148  typename AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>::Iterator itAr, itAw;
149  itAr = itAw = in_A.Begin();
150  typename AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>::Iterator itB = in_B.Begin();
151  while (itAr != in_A.End())
152  {
153  if (itB == in_B.End() || TComparePolicy::Lesser(&in_A, *itAr, *itB))
154  {
155  if (itAw != itAr)
156  *itAw = *itAr;
157 
158  ++itAw;
159  ++itAr;
160  }
161  else if (TComparePolicy::Equal(&in_A, *itAr, *itB))
162  {
163  ++itB;
164  ++itAr;
165  }
166  else
167  {
168  ++itB;
169  }
170  }
171  in_A.Resize((AkUInt32)(itAw.pItem - in_A.Begin().pItem));
172  return true;
173 }
174 
175 // AkIntersection
176 // - In-place set intersection ( A = A n B )
177 //
178 template< typename T, class U_POOL, class uGrowBy, class TMovePolicy, class TComparePolicy >
179 static bool AkIntersection(AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_A, const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_B)
180 {
181  typename AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>::Iterator itAr, itAw;
182  itAr = itAw = in_A.Begin();
183  typename AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>::Iterator itB = in_B.Begin();
184  while (itAr != in_A.End() && itB != in_B.End())
185  {
186  if (TComparePolicy::Equal(&in_A, *itAr, *itB))
187  {
188  if (itAw != itAr)
189  *itAw = *itAr;
190 
191  ++itAw;
192  ++itAr;
193  ++itB;
194  }
195  else if (TComparePolicy::Lesser(&in_A, *itAr,*itB))
196  {
197  ++itAr;
198  }
199  else
200  {
201  ++itB;
202  }
203  }
204  in_A.Resize((AkUInt32)(itAw.pItem - in_A.Begin().pItem));
205  return true;
206 }
207 
208 // AkIntersection
209 // - Out-of-place set intersection ( res = A n B )
210 //
211 template< typename T, class U_POOL, class uGrowBy, class TMovePolicy, class TComparePolicy >
212 static bool AkIntersection(AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& out_res, const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_A, const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_B)
213 {
214  out_res.RemoveAll();
215 
216  typename AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>::Iterator itA = in_A.Begin();
217  typename AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>::Iterator itB = in_B.Begin();
218  while (itA != in_A.End() && itB != in_B.End())
219  {
220  if (TComparePolicy::Equal(&in_A, *itA, *itB))
221  {
222  out_res.AddLast(*itA);
223 
224  ++itA;
225  ++itB;
226  }
227  else if (TComparePolicy::Lesser(&in_A, *itA,*itB))
228  {
229  ++itA;
230  }
231  else
232  {
233  ++itB;
234  }
235  }
236  return true;
237 }
238 
239 // AkUnion
240 // - Set union ( A = A U B ).
241 // NOTE: Preforms a memory allocation and may fail.
242 //
243 template< typename T, class U_POOL, class uGrowBy, class TMovePolicy, class TComparePolicy >
244 static bool AkUnion(AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& io_A, const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_B)
245 {
246  AkInt32 uSizeNeeded = io_A.Length() + in_B.Length() - AkCountIntersection(io_A, in_B);
247  AkSet<T, U_POOL, uGrowBy> result;
248 
249  if (result.Resize(uSizeNeeded))
250  {
251  typename AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>::Iterator itRes = result.Begin();
252  typename AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>::Iterator itA = io_A.Begin();
253  typename AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>::Iterator itB = in_B.Begin();
254 
255  while (itB != in_B.End() || itA != io_A.End())
256  {
257  if ( itB != in_B.End() && (itA == io_A.End() || TComparePolicy::Lesser(&io_A, *itB, *itA)))
258  {
259  *itRes = *itB;
260  ++itB;
261  }
262  else if (itB == in_B.End() || TComparePolicy::Lesser(&io_A, *itA,*itB) )
263  {
264  *itRes = *itA;
265  ++itA;
266  }
267  else //if ( *itA == *itC)
268  {
269  *itRes = *itA;
270  ++itA;
271  ++itB;
272  }
273 
274  ++itRes;
275  }
276 
277  io_A.Transfer(result);
278  return true;
279  }
280 
281  return false;
282 }
283 
284 typedef AkSet< AkUniqueID, ArrayPoolDefault > AkUniqueIDSet;
285 
286 // AkIntersect
287 // - Return true if the intersection of in_A (a set of type in_typeA), and in_B (a set of type in_typeB) is not the empty set.
288 //
289 template< typename T, class U_POOL, class uGrowBy, class TMovePolicy, class TComparePolicy >
290 static inline bool AkIntersect(const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_A, AkSetType in_typeA, const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_B, AkSetType in_typeB)
291 {
292  if (in_typeA == SetType_Inclusion)
293  {
294  if (in_typeB == SetType_Inclusion)
295  return !AkDisjoint(in_A, in_B);
296  else//(in_typeB == SetType_Exclusion)
297  return !AkIsSubset(in_A, in_B);
298  }
299  else//(in_typeA == SetType_Exclusion)
300  {
301  if (in_typeB == SetType_Inclusion)
302  return !AkIsSubset(in_B, in_A);
303  else//(in_typeB == SetType_Exclusion)
304  return true;//Assuming an infinite space of possible elements.
305  }
306 }
307 
308 // AkContains
309 // - Return true if the element in_item is contained in in_Set, a set of type in_type.
310 //
311 template< typename T, class U_POOL, class uGrowBy, class TMovePolicy, class TComparePolicy >
312 static inline bool AkContains(const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_Set, AkSetType in_type, T in_item)
313 {
314  return (in_type == SetType_Inclusion && in_Set.Contains(in_item)) ||
315  (in_type == SetType_Exclusion && !in_Set.Contains(in_item));
316 }
317 
318 // AkSubtraction
319 // - pseudo in-place set subtraction (A = A - B) with set type specifiers.
320 // NOTE: Memory may be allocated (in AkUnion) so prepare for failure.
321 //
322 template< typename T, class U_POOL, class uGrowBy, class TMovePolicy, class TComparePolicy >
323 static inline bool AkSubtraction(AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_A, AkSetType in_typeA, const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_B, AkSetType in_typeB)
324 {
325  if (in_typeA == SetType_Inclusion)
326  {
327  if (in_typeB == SetType_Inclusion)
328  return AkSubtraction(in_A, in_B);
329  else//(in_typeB == SetType_Exclusion)
330  return AkIntersection(in_A, in_B);
331  }
332  else//(in_typeA == SetType_Exclusion)
333  {
334  if (in_typeB == SetType_Inclusion)
335  return AkUnion(in_A, in_B);
336  else//(in_typeB == SetType_Exclusion)
337  return AkIntersection(in_A, in_B);
338  }
339 }
340 
341 // AkUnion
342 // - Pseudo in-place set union (A = A + B)
343 // NOTE: Memory may be allocated (in AkUnion) so prepare for failure.
344 //
345 template< typename T, class U_POOL, class uGrowBy, class TMovePolicy, class TComparePolicy >
346 static inline bool AkUnion(AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& io_A, AkSetType& io_typeA, const AkSet<T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy>& in_B, AkSetType in_typeB)
347 {
348  if (io_typeA == SetType_Inclusion)
349  {
350  if (in_typeB == SetType_Inclusion)
351  return AkUnion(io_A, in_B);
352  else//(in_typeB == SetType_Exclusion)
353  {
354  AkSet<T, U_POOL, uGrowBy> temp;
355  temp.Transfer(io_A);
356  if (io_A.Copy(in_B) == AK_Success)
357  {
358  io_typeA = SetType_Exclusion;
359  AkSubtraction(io_A, temp);
360  temp.Term();
361  return true;
362  }
363  else
364  {
365  io_A.Transfer(temp);
366  return false;
367  }
368  }
369  }
370  else//(in_typeA == SetType_Exclusion)
371  {
372  if (in_typeB == SetType_Inclusion)
373  return AkSubtraction(io_A, in_B);
374  else//(in_typeB == SetType_Exclusion)
375  return AkIntersection(io_A, in_B);
376  }
377 }
378 
379 #endif
380 
AkContains
static bool AkContains(const AkSet< T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy > &in_Set, AkSetType in_type, T in_item)
Definition: AkSet.h:312
AkSet
Definition: AkSet.h:57
AkArray< T, const T &, ArrayPoolDefault, AkGrowByPolicy_DEFAULT, AkAssignmentMovePolicy< T > >::Copy
AKRESULT Copy(const AkArray< T, const T &, ArrayPoolDefault, AkGrowByPolicy_DEFAULT, AkAssignmentMovePolicy< T > > &in_rSource)
Definition: AkArray.h:866
AkIntersection
static bool AkIntersection(AkSet< T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy > &in_A, const AkSet< T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy > &in_B)
Definition: AkSet.h:179
AkCountIntersection
static AkUInt32 AkCountIntersection(const AkSet< T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy > &in_A, const AkSet< T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy > &in_B)
Definition: AkSet.h:119
AkUnion
static bool AkUnion(AkSet< T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy > &io_A, const AkSet< T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy > &in_B)
Definition: AkSet.h:244
NULL
#define NULL
Definition: AkTypes.h:46
AK_Success
@ AK_Success
The operation was successful.
Definition: AkTypes.h:136
AkInt32
int32_t AkInt32
Signed 32-bit integer.
Definition: AkNumeralTypes.h:43
SetType_Exclusion
@ SetType_Exclusion
Definition: AkSet.h:44
AkSetType
AkSetType
Definition: AkSet.h:41
AkArray< T, const T &, ArrayPoolDefault, AkGrowByPolicy_DEFAULT, AkAssignmentMovePolicy< T > >::Resize
bool Resize(AkUInt32 in_uiSize)
Resize the array to the specified size.
Definition: AkArray.h:823
SetType_Inclusion
@ SetType_Inclusion
Definition: AkSet.h:42
AkArray< T, const T &, ArrayPoolDefault, AkGrowByPolicy_DEFAULT, AkAssignmentMovePolicy< T > >::End
Iterator End() const
Returns the iterator to the end of the array.
Definition: AkArray.h:353
AkArray< T, const T &, ArrayPoolDefault, AkGrowByPolicy_DEFAULT, AkAssignmentMovePolicy< T > >::Transfer
void Transfer(AkArray< T, const T &, ArrayPoolDefault, AkGrowByPolicy_DEFAULT, AkAssignmentMovePolicy< T > > &in_rSource)
Definition: AkArray.h:853
AkSubtraction
static bool AkSubtraction(AkSet< T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy > &in_A, const AkSet< T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy > &in_B)
Definition: AkSet.h:146
AkArray< T, const T &, ArrayPoolDefault, AkGrowByPolicy_DEFAULT, AkAssignmentMovePolicy< T > >::Begin
Iterator Begin() const
Returns the iterator to the first item of the array, will be End() if the array is empty.
Definition: AkArray.h:345
AkArray< T, const T &, ArrayPoolDefault, AkGrowByPolicy_DEFAULT, AkAssignmentMovePolicy< T > >::Length
AkForceInline AkUInt32 Length() const
Returns the numbers of items in the array.
Definition: AkArray.h:567
AkIsSubset
static bool AkIsSubset(const AkSet< T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy > &in_A, const AkSet< T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy > &in_B)
Definition: AkSet.h:95
AkDisjoint
static bool AkDisjoint(const AkSet< T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy > &in_A, const AkSet< T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy > &in_B)
Definition: AkSet.h:66
AkUInt32
uint32_t AkUInt32
Unsigned 32-bit integer.
Definition: AkNumeralTypes.h:38
AkArray< T, const T &, ArrayPoolDefault, AkGrowByPolicy_DEFAULT, AkAssignmentMovePolicy< T > >::Term
void Term()
Term the array. Must be called before destroying the object.
Definition: AkArray.h:555
AkSet::Contains
bool Contains(T in_item) const
Definition: AkSet.h:59
AkForceInline
#define AkForceInline
Definition: AkTypes.h:63
AkUniqueIDSet
AkSet< AkUniqueID, ArrayPoolDefault > AkUniqueIDSet
Definition: AkSet.h:284
AkSetGetKey::Get
static AkForceInline T & Get(T &in_item)
Definition: AkSet.h:49
AkIntersect
static bool AkIntersect(const AkSet< T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy > &in_A, const AkSet< T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy > &in_B)
Definition: AkSet.h:86

Was this page helpful?

Need Support?

Questions? Problems? Need more info? Contact us, and we can help!

Visit our Support page

Tell us about your project. We're here to help.

Register your project and we'll help you get started with no strings attached!

Get started with Wwise