Version
menu_open
Wwise SDK 2023.1.4
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 
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 //
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 >
67 {
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 >
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 >
96 {
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 >
120 {
121  AkUInt32 uSize = 0;
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>
147 {
149  itAr = itAw = in_A.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 >
180 {
182  itAr = itAw = in_A.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 >
213 {
214  out_res.RemoveAll();
215 
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 >
245 {
246  AkInt32 uSizeNeeded = io_A.Length() + in_B.Length() - AkCountIntersection(io_A, in_B);
248 
249  if (result.Resize(uSizeNeeded))
250  {
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 
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 >
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 >
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 >
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  {
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 
static bool AkContains(const AkSet< T, U_POOL, uGrowBy, TMovePolicy, TComparePolicy > &in_Set, AkSetType in_type, T in_item)
Definition: AkSet.h:312
Definition: AkSet.h:57
AKRESULT Copy(const AkArray< T, const T &, ArrayPoolDefault, AkGrowByPolicy_DEFAULT, AkAssignmentMovePolicy< T > > &in_rSource)
Definition: AkArray.h:865
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
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
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
#define NULL
Definition: AkTypes.h:46
@ AK_Success
The operation was successful.
Definition: AkTypes.h:133
int32_t AkInt32
Signed 32-bit integer.
@ SetType_Exclusion
Definition: AkSet.h:44
AkSetType
Definition: AkSet.h:41
bool Resize(AkUInt32 in_uiSize)
Resize the array to the specified size.
Definition: AkArray.h:822
@ SetType_Inclusion
Definition: AkSet.h:42
Iterator End() const
Returns the iterator to the end of the array.
Definition: AkArray.h:352
void Transfer(AkArray< T, const T &, ArrayPoolDefault, AkGrowByPolicy_DEFAULT, AkAssignmentMovePolicy< T > > &in_rSource)
Definition: AkArray.h:852
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
Iterator Begin() const
Returns the iterator to the first item of the array, will be End() if the array is empty.
Definition: AkArray.h:344
AkForceInline AkUInt32 Length() const
Returns the numbers of items in the array.
Definition: AkArray.h:566
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
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
uint32_t AkUInt32
Unsigned 32-bit integer.
void Term()
Term the array. Must be called before destroying the object.
Definition: AkArray.h:554
bool Contains(T in_item) const
Definition: AkSet.h:59
#define AkForceInline
Definition: AkTypes.h:63
AkSet< AkUniqueID, ArrayPoolDefault > AkUniqueIDSet
Definition: AkSet.h:284
static AkForceInline T & Get(T &in_item)
Definition: AkSet.h:49
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