Version
menu_open
link
Wwise SDK 2018.1.11
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  Version: <VERSION> Build: <BUILDNUMBER>
25  Copyright (c) <COPYRIGHTYEAR> Audiokinetic Inc.
26 *******************************************************************************/
27 
28 //////////////////////////////////////////////////////////////////////
29 //
30 // AkSet.h
31 //
32 //////////////////////////////////////////////////////////////////////
33 #ifndef _AKSET_H_
34 #define _AKSET_H_
35 
37 
38 // AkSetType
39 // - An optional set type specifier which is passed into some set operations. If it is not included, SetType_Inclusion is assumed.
40 //
41 enum AkSetType
42 {
43  SetType_Inclusion, // <- An AkSet object with type SetType_Inclusion is a set where each element in the array
44  // represents an element in the set. An empty array represents the empty set.
45  SetType_Exclusion // <- An AkSet object with type SetType_Exclusion is an 'inverted' set, where each element in the array
46  // represents and element NOT in the set. An empty array represents the universal set.
47 };
48 
49 template<typename T>
50 struct AkSetGetKey{ static AkForceInline T& Get(T& in_item){ return in_item; } };
51 
52 // AkSet
53 //
54 // Set container type, implemented as a sorted array of unique items
55 //
56 template< typename T, class U_POOL, AkUInt32 uGrowBy = 1 >
57 class AkSet : public AkSortedKeyArray < T, T, U_POOL, AkSetGetKey<T>, uGrowBy >
58 {
59 public:
60  bool Contains(T in_item) const { return AkSortedKeyArray < T, T, U_POOL, AkSetGetKey<T>, uGrowBy >::Exists(in_item) != NULL; }
61 };
62 
63 // AkDisjoint
64 // - Returns true if the intersection of A and B is the empty set.
65 //
66 template< typename T, class U_POOL, AkUInt32 uGrowBy >
67 static bool AkDisjoint(const AkSet<T, U_POOL, uGrowBy>& in_A, const AkSet<T, U_POOL, uGrowBy>& in_B)
68 {
69  typename AkSet<T, U_POOL, uGrowBy>::Iterator itA = in_A.Begin();
70  typename AkSet<T, U_POOL, uGrowBy>::Iterator itB = in_B.Begin();
71  while (itA != in_A.End() && itB != in_B.End())
72  {
73  if (*itA == *itB)
74  return false;
75  else if (*itA < *itB)
76  ++itA;
77  else
78  ++itB;
79  }
80  return true;
81 }
82 
83 // AkIntersect
84 // - Return true if the intersection of A and B is not the empty set.
85 //
86 template< typename T, class U_POOL, AkUInt32 uGrowBy >
88 {
89  return !AkDisjoint(in_A, in_B);
90 }
91 
92 // AkIsSubset
93 // - Return true if in_A is a subset of in_B
94 //
95 template< typename T, class U_POOL, AkUInt32 uGrowBy >
96 static bool AkIsSubset(const AkSet<T, U_POOL, uGrowBy>& in_A, const AkSet<T, U_POOL, uGrowBy>& in_B)
97 {
98  typename AkSet<T, U_POOL, uGrowBy>::Iterator itA = in_A.Begin();
99  typename AkSet<T, U_POOL, uGrowBy>::Iterator itB = in_B.Begin();
100  while (itA != in_A.End() && itB != in_B.End())
101  {
102  if (*itA == *itB)
103  {
104  ++itA; ++itB;
105  }
106  else if (*itA < *itB)
107  {
108  return false;//an element of A is not in B
109  }
110  else
111  ++itB;
112  }
113  return (itA == in_A.End());
114 }
115 
116 // AkCountIntersection
117 // - Helper function to count the number of elements that are in both in_A and in_B.
118 //
119 template< typename T, class U_POOL, AkUInt32 uGrowBy >
121 {
122  AkUInt32 uSize = 0;
123  typename AkSet<T, U_POOL, uGrowBy>::Iterator itA = in_A.Begin();
124  typename AkSet<T, U_POOL, uGrowBy>::Iterator itB = in_B.Begin();
125  while (itA != in_A.End() && itB != in_B.End())
126  {
127  if (*itA == *itB)
128  {
129  ++uSize; ++itA; ++itB;
130  }
131  else if (*itA < *itB)
132  {
133  ++itA;
134  }
135  else
136  {
137  ++itB;
138  }
139  }
140  return uSize;
141 }
142 
143 // AkSubtraction
144 // - In-place set subtraction ( A = A - B )
145 //
146 template< typename T, class U_POOL, AkUInt32 uGrowBy >
148 {
149  typename AkSet<T, U_POOL, uGrowBy>::Iterator itAr, itAw;
150  itAr = itAw = in_A.Begin();
151  typename AkSet<T, U_POOL, uGrowBy>::Iterator itB = in_B.Begin();
152  while (itAr != in_A.End())
153  {
154  if (itB == in_B.End() || *itAr < *itB)
155  {
156  if (itAw != itAr)
157  *itAw = *itAr;
158 
159  ++itAw;
160  ++itAr;
161  }
162  else if (*itAr == *itB)
163  {
164  ++itB;
165  ++itAr;
166  }
167  else
168  {
169  ++itB;
170  }
171  }
172  in_A.Resize((AkUInt32)(itAw.pItem - in_A.Begin().pItem));
173  return true;
174 }
175 
176 // AkIntersection
177 // - In-place set intersection ( A = A n B )
178 //
179 template< typename T, class U_POOL, AkUInt32 uGrowBy >
181 {
182  typename AkSet<T, U_POOL, uGrowBy>::Iterator itAr, itAw;
183  itAr = itAw = in_A.Begin();
184  typename AkSet<T, U_POOL, uGrowBy>::Iterator itB = in_B.Begin();
185  while (itAr != in_A.End() && itB != in_B.End())
186  {
187  if (*itAr == *itB)
188  {
189  if (itAw != itAr)
190  *itAw = *itAr;
191 
192  ++itAw;
193  ++itAr;
194  ++itB;
195  }
196  else if (*itAr < *itB)
197  {
198  ++itAr;
199  }
200  else
201  {
202  ++itB;
203  }
204  }
205  in_A.Resize((AkUInt32)(itAw.pItem - in_A.Begin().pItem));
206  return true;
207 }
208 
209 // AkIntersection
210 // - Out-of-place set intersection ( res = A n B )
211 //
212 template< typename T, class U_POOL, AkUInt32 uGrowBy >
214 {
215  out_res.RemoveAll();
216 
217  typename AkSet<T, U_POOL, uGrowBy>::Iterator itA = in_A.Begin();
218  typename AkSet<T, U_POOL, uGrowBy>::Iterator itB = in_B.Begin();
219  while (itA != in_A.End() && itB != in_B.End())
220  {
221  if (*itA == *itB)
222  {
223  out_res.AddLast(*itA);
224 
225  ++itA;
226  ++itB;
227  }
228  else if (*itA < *itB)
229  {
230  ++itA;
231  }
232  else
233  {
234  ++itB;
235  }
236  }
237  return true;
238 }
239 
240 // AkUnion
241 // - Set union ( A = A U B ).
242 // NOTE: Preforms a memory allocation and may fail.
243 //
244 template< typename T, class U_POOL, AkUInt32 uGrowBy >
246 {
247  AkInt32 uSizeNeeded = io_A.Length() + in_B.Length() - AkCountIntersection(io_A, in_B);
249 
250  if (result.Resize(uSizeNeeded))
251  {
252  typename AkSet<T, U_POOL, uGrowBy>::Iterator itRes = result.Begin();
253  typename AkSet<T, U_POOL, uGrowBy>::Iterator itA = io_A.Begin();
254  typename AkSet<T, U_POOL, uGrowBy>::Iterator itB = in_B.Begin();
255 
256  while (itB != in_B.End() || itA != io_A.End())
257  {
258  if ( itB != in_B.End() && (itA == io_A.End() || *itB < *itA))
259  {
260  *itRes = *itB;
261  ++itB;
262  }
263  else if (itB == in_B.End() || *itA < *itB)
264  {
265  *itRes = *itA;
266  ++itA;
267  }
268  else //if ( *itA == *itC)
269  {
270  *itRes = *itA;
271  ++itA;
272  ++itB;
273  }
274 
275  ++itRes;
276  }
277 
278  io_A.Transfer(result);
279  return true;
280  }
281 
282  return false;
283 }
284 
286 
287 // AkIntersect
288 // - 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.
289 //
290 template< typename T, class U_POOL, AkUInt32 uGrowBy >
291 static inline bool AkIntersect(const AkSet<T, U_POOL, uGrowBy>& in_A, AkSetType in_typeA, const AkSet<T, U_POOL, uGrowBy>& in_B, AkSetType in_typeB)
292 {
293  if (in_typeA == SetType_Inclusion)
294  {
295  if (in_typeB == SetType_Inclusion)
296  return !AkDisjoint(in_A, in_B);
297  else//(in_typeB == SetType_Exclusion)
298  return !AkIsSubset(in_A, in_B);
299  }
300  else//(in_typeA == SetType_Exclusion)
301  {
302  if (in_typeB == SetType_Inclusion)
303  return !AkIsSubset(in_B, in_A);
304  else//(in_typeB == SetType_Exclusion)
305  return true;//Assuming an infinite space of possible elements.
306  }
307 }
308 
309 // AkContains
310 // - Return true if the element in_item is contained in in_Set, a set of type in_type.
311 //
312 template< typename T, class U_POOL, AkUInt32 uGrowBy >
313 static inline bool AkContains(const AkSet<T, U_POOL, uGrowBy>& in_Set, AkSetType in_type, T in_item)
314 {
315  return (in_type == SetType_Inclusion && in_Set.Contains(in_item)) ||
316  (in_type == SetType_Exclusion && !in_Set.Contains(in_item));
317 }
318 
319 // AkSubtraction
320 // - pseudo in-place set subtraction (A = A - B) with set type specifiers.
321 // NOTE: Memory may be allocated (in AkUnion) so prepare for failure.
322 //
323 template< typename T, class U_POOL, AkUInt32 uGrowBy >
324 static inline bool AkSubtraction(AkSet<T, U_POOL, uGrowBy>& in_A, AkSetType in_typeA, const AkSet<T, U_POOL, uGrowBy>& in_B, AkSetType in_typeB)
325 {
326  if (in_typeA == SetType_Inclusion)
327  {
328  if (in_typeB == SetType_Inclusion)
329  return AkSubtraction(in_A, in_B);
330  else//(in_typeB == SetType_Exclusion)
331  return AkIntersection(in_A, in_B);
332  }
333  else//(in_typeA == SetType_Exclusion)
334  {
335  if (in_typeB == SetType_Inclusion)
336  return AkUnion(in_A, in_B);
337  else//(in_typeB == SetType_Exclusion)
338  return AkIntersection(in_A, in_B);
339  }
340 }
341 
342 // AkUnion
343 // - Pseudo in-place set union (A = A + B)
344 // NOTE: Memory may be allocated (in AkUnion) so prepare for failure.
345 //
346 template< typename T, class U_POOL, AkUInt32 uGrowBy >
347 static inline bool AkUnion(AkSet<T, U_POOL, uGrowBy>& io_A, AkSetType& io_typeA, const AkSet<T, U_POOL, uGrowBy>& in_B, AkSetType in_typeB)
348 {
349  if (io_typeA == SetType_Inclusion)
350  {
351  if (in_typeB == SetType_Inclusion)
352  return AkUnion(io_A, in_B);
353  else//(in_typeB == SetType_Exclusion)
354  {
356  temp.Transfer(io_A);
357  if (io_A.Copy(in_B) == AK_Success)
358  {
359  io_typeA = SetType_Exclusion;
360  AkSubtraction(io_A, temp);
361  temp.Term();
362  return true;
363  }
364  else
365  {
366  io_A.Transfer(temp);
367  return false;
368  }
369  }
370  }
371  else//(in_typeA == SetType_Exclusion)
372  {
373  if (in_typeB == SetType_Inclusion)
374  return AkSubtraction(io_A, in_B);
375  else//(in_typeB == SetType_Exclusion)
376  return AkIntersection(io_A, in_B);
377  }
378 }
379 
380 #endif
381 
The operation was successful.
Definition: AkTypes.h:129
AKRESULT Copy(const AkArray< T, const T &, U_POOL, TGrowBy, AkAssignmentMovePolicy< T > > &in_rSource)
Definition: AkArray.h:626
AkForceInline AkUInt32 Length() const
Returns the numbers of items in the array.
Definition: AkArray.h:383
Definition: AkSet.h:50
AkSet< AkUniqueID, ArrayPoolDefault > AkUniqueIDSet
Definition: AkSet.h:285
Definition: AkSet.h:57
#define AkForceInline
Force inlining.
Definition: AkTypes.h:63
static bool AkIsSubset(const AkSet< T, U_POOL, uGrowBy > &in_A, const AkSet< T, U_POOL, uGrowBy > &in_B)
Definition: AkSet.h:96
static AkForceInline T & Get(T &in_item)
Definition: AkSet.h:50
static bool AkIntersection(AkSet< T, U_POOL, uGrowBy > &in_A, const AkSet< T, U_POOL, uGrowBy > &in_B)
Definition: AkSet.h:180
int32_t AkInt32
Signed 32-bit integer.
Definition: AkTypes.h:92
Iterator End() const
Returns the iterator to the end of the array.
Definition: AkArray.h:241
static bool AkContains(const AkSet< T, U_POOL, uGrowBy > &in_Set, AkSetType in_type, T in_item)
Definition: AkSet.h:313
static bool AkDisjoint(const AkSet< T, U_POOL, uGrowBy > &in_A, const AkSet< T, U_POOL, uGrowBy > &in_B)
Definition: AkSet.h:67
static bool AkUnion(AkSet< T, U_POOL, uGrowBy > &io_A, const AkSet< T, U_POOL, uGrowBy > &in_B)
Definition: AkSet.h:245
Iterator Begin() const
Returns the iterator to the first item of the array, will be End() if the array is empty.
Definition: AkArray.h:233
void Transfer(AkArray< T, const T &, U_POOL, TGrowBy, AkAssignmentMovePolicy< T > > &in_rSource)
Definition: AkArray.h:613
#define NULL
Definition: AkTypes.h:49
static bool AkSubtraction(AkSet< T, U_POOL, uGrowBy > &in_A, const AkSet< T, U_POOL, uGrowBy > &in_B)
Definition: AkSet.h:147
uint32_t AkUInt32
Unsigned 32-bit integer.
Definition: AkTypes.h:79
static bool AkIntersect(const AkSet< T, U_POOL, uGrowBy > &in_A, const AkSet< T, U_POOL, uGrowBy > &in_B)
Definition: AkSet.h:87
void RemoveAll()
Removes all items in the array.
Definition: AkArray.h:490
bool Resize(AkUInt32 in_uiSize)
Resize the array to the specified size.
Definition: AkArray.h:583
bool Contains(T in_item) const
Definition: AkSet.h:60
AkSetType
Definition: AkSet.h:41
void Term()
Term the array. Must be called before destroying the object.
Definition: AkArray.h:371
static AkUInt32 AkCountIntersection(const AkSet< T, U_POOL, uGrowBy > &in_A, const AkSet< T, U_POOL, uGrowBy > &in_B)
Definition: AkSet.h:120

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