Version
menu_open
link
Wwise SDK 2022.1.8
AkKeyArray.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) 2023 Audiokinetic Inc.
25 *******************************************************************************/
26 
27 #ifndef _KEYARRAY_H_
28 #define _KEYARRAY_H_
29 
30 #include <AK/Tools/Common/AkArray.h>
31 #include <AK/Tools/Common/AkKeyDef.h>
32 
33 // The Key list is simply a list that may be referenced using a key
34 // NOTE :
35 template <class T_KEY, class T_ITEM, class U_POOL = ArrayPoolDefault, class TGrowBy = AkGrowByPolicy_DEFAULT, class TMovePolicy = AkAssignmentMovePolicy<MapStruct<T_KEY, T_ITEM> > >
36 class CAkKeyArray : public AkArray< MapStruct<T_KEY, T_ITEM>, const MapStruct<T_KEY, T_ITEM>&, U_POOL, TGrowBy, TMovePolicy>
37 {
38 public:
39  //====================================================================================================
40  // Return NULL if the Key does not exisis
41  // Return T_ITEM* otherwise
42  //====================================================================================================
43  T_ITEM* Exists(T_KEY in_Key) const
44  {
45  typename CAkKeyArray< T_KEY, T_ITEM, U_POOL, TGrowBy, TMovePolicy >::Iterator it = this->FindEx(in_Key);
46  return (it != this->End()) ? &(it.pItem->item) : NULL;
47  }
48 
49 public:
50  //====================================================================================================
51  // Sets the item referenced by the specified key and item
52  // Return AK_Fail if the list max size was exceeded
53  //====================================================================================================
54  T_ITEM * Set(T_KEY in_Key, const T_ITEM & in_Item)
55  {
56  T_ITEM* pSearchedItem = Exists(in_Key);
57  if (pSearchedItem)
58  {
59  *pSearchedItem = in_Item;
60  }
61  else
62  {
63  MapStruct<T_KEY, T_ITEM> * pStruct = this->AddLast();
64  if (pStruct)
65  {
66  pStruct->key = in_Key;
67  pStruct->item = in_Item;
68  pSearchedItem = &(pStruct->item);
69  }
70  }
71  return pSearchedItem;
72  }
73 
74  T_ITEM * SetFirst(T_KEY in_Key, const T_ITEM & in_Item)
75  {
76  T_ITEM* pSearchedItem = Exists(in_Key);
77  if (pSearchedItem)
78  {
79  *pSearchedItem = in_Item;
80  }
81  else
82  {
83  MapStruct<T_KEY, T_ITEM> * pStruct = this->Insert(0); //insert at index 0 is AddFirst.
84  if (pStruct)
85  {
86  pStruct->key = in_Key;
87  pStruct->item = in_Item;
88  pSearchedItem = &(pStruct->item);
89  }
90  }
91  return pSearchedItem;
92  }
93 
94  T_ITEM * Set(T_KEY in_Key)
95  {
96  T_ITEM* pSearchedItem = Exists(in_Key);
97  if (!pSearchedItem)
98  {
99  MapStruct<T_KEY, T_ITEM> * pStruct = this->AddLast();
100  if (pStruct)
101  {
102  pStruct->key = in_Key;
103  pSearchedItem = &(pStruct->item);
104  }
105  }
106  return pSearchedItem;
107  }
108 
109  // NOTE: The real definition should be
110  // typename CAkKeyArray<T_KEY,T_ITEM,TGrowBy, TMovePolicy>::Iterator FindEx( T_KEY in_Item ) const
111  // Typenaming the base class is a workaround for bug MTWX33123 in the new Freescale CodeWarrior.
112  typename AkArray< MapStruct<T_KEY, T_ITEM>, const MapStruct<T_KEY, T_ITEM>&, U_POOL, TGrowBy, TMovePolicy>::Iterator FindEx(T_KEY in_Item) const
113  {
114  typename CAkKeyArray< T_KEY, T_ITEM, U_POOL, TGrowBy, TMovePolicy >::Iterator it = this->Begin();
115 
116  typename CAkKeyArray< T_KEY, T_ITEM, U_POOL, TGrowBy, TMovePolicy >::Iterator itEnd = this->End();
117  for (; it != itEnd; ++it)
118  {
119  if ((*it).key == in_Item)
120  break;
121  }
122 
123  return it;
124  }
125 
126  //====================================================================================================
127  // Remove the item referenced by the specified key
128  //====================================================================================================
129 
130  void Unset(T_KEY in_Key)
131  {
132  typename CAkKeyArray< T_KEY, T_ITEM, U_POOL, TGrowBy, TMovePolicy >::Iterator it = FindEx(in_Key);
133  if (it != this->End())
134  {
135  this->Erase(it);
136  }
137  }
138 
139  //====================================================================================================
140  // More efficient version of Unset when order is unimportant
141  //====================================================================================================
142 
143  void UnsetSwap(T_KEY in_Key)
144  {
145  typename CAkKeyArray< T_KEY, T_ITEM, U_POOL, TGrowBy, TMovePolicy >::Iterator it = FindEx(in_Key);
146  if (it != this->End())
147  {
148  this->EraseSwap(it);
149  }
150  }
151 };
152 
153 /// Key policy for AkSortedKeyArray.
154 template <class T_KEY, class T_ITEM> struct AkGetArrayKey
155 {
156  /// Default policy.
157  static AkForceInline T_KEY & Get(T_ITEM & in_item)
158  {
159  return in_item.key;
160  }
161 };
162 
163 template <class T_KEY, class T_ITEM> struct AkGetArrayKeyFunc
164 {
165  /// Default policy.
166  static AkForceInline T_KEY& Get(T_ITEM& in_item)
167  {
168  return in_item.Key();
169  }
170 };
171 
172 /// Trivial key policy for AkSortedKeyArray, when T_KEY is T_ITEM.
173 struct AkGetArrayKeyTrivial
174 {
175  /// Default policy.
176  template <class T_KEY>
177  static AkForceInline T_KEY& Get(T_KEY& in_item)
178  {
179  return in_item;
180  }
181 };
182 
183 //Default comparison policy for AkSortedKeyArray.
184 template <class T_KEY> struct AkDefaultSortedKeyCompare
185 {
186 public:
187  template<class THIS_CLASS>
188  static AkForceInline bool Lesser(THIS_CLASS*, T_KEY &a, T_KEY &b)
189  {
190  return a < b;
191  }
192 
193  template<class THIS_CLASS>
194  static AkForceInline bool Equal(THIS_CLASS*, T_KEY &a, T_KEY &b)
195  {
196  return a == b;
197  }
198 };
199 
200 /// Array of items, sorted by key. Uses binary search for lookups. BEWARE WHEN
201 /// MODIFYING THE ARRAY USING BASE CLASS METHODS.
202 template <class T_KEY, class T_ITEM, class U_POOL = ArrayPoolDefault, class U_KEY = AkGetArrayKey< T_KEY, T_ITEM >, class TGrowBy = AkGrowByPolicy_DEFAULT, class TMovePolicy = AkAssignmentMovePolicy<T_ITEM>, class TComparePolicy = AkDefaultSortedKeyCompare<T_KEY> >
203 class AkSortedKeyArray : public AkArray< T_ITEM, const T_ITEM &, U_POOL, TGrowBy, TMovePolicy >
204 {
205 public:
206  using base = AkArray<T_ITEM, const T_ITEM&, U_POOL, TGrowBy, TMovePolicy>;
207  using Iterator = typename base::Iterator;
208 
209  AkForceInline bool Lesser(T_KEY &a, T_KEY &b) const
210  {
211  return TComparePolicy::Lesser((void*)this, a, b);
212  }
213 
214  AkForceInline bool Equal(T_KEY &a, T_KEY &b) const
215  {
216  return TComparePolicy::Equal((void*)this, a, b);
217  }
218 
219  T_ITEM* Exists(T_KEY in_key) const
220  {
221  bool bFound;
222  T_ITEM* pItem = BinarySearch(in_key, bFound);
223  return bFound ? pItem : NULL;
224  }
225 
226  // Add an item to the list (allowing duplicate keys)
227 
228  T_ITEM * Add(T_KEY in_key)
229  {
230  T_ITEM * pItem = AddNoSetKey(in_key);
231 
232  // Then set the key
233  if (pItem)
234  U_KEY::Get(*pItem) = in_key;
235 
236  return pItem;
237  }
238 
239  // Add an item to the list (allowing duplicate keys)
240 
241  T_ITEM * AddNoSetKey(T_KEY in_key)
242  {
243  bool bFound;
244  return AddNoSetKey(in_key, bFound);
245  }
246 
247  T_ITEM * AddNoSetKey(T_KEY in_key, bool& out_bFound)
248  {
249  T_ITEM * pItem = BinarySearch(in_key, out_bFound);
250  if (pItem)
251  {
252  unsigned int uIdx = (unsigned int)(pItem - this->m_pItems);
253  pItem = this->Insert(uIdx);
254  }
255  else
256  {
257  pItem = this->AddLast();
258  }
259 
260  return pItem;
261  }
262 
263  // Set an item in the list (returning existing item if present)
264 
265  T_ITEM * Set(T_KEY in_key)
266  {
267  bool bFound;
268  return Set(in_key, bFound);
269  }
270 
271  T_ITEM * Set(T_KEY in_key, bool & out_bExists)
272  {
273  T_ITEM * pItem = BinarySearch(in_key, out_bExists);
274  if (!out_bExists)
275  {
276  if (pItem)
277  {
278  unsigned int uIdx = (unsigned int)(pItem - this->m_pItems);
279  pItem = this->Insert(uIdx);
280  }
281  else
282  {
283  pItem = this->AddLast();
284  }
285 
286  if (pItem)
287  U_KEY::Get(*pItem) = in_key;
288  }
289 
290  return pItem;
291  }
292 
293 
294  bool Unset(T_KEY in_key)
295  {
296  T_ITEM * pItem = Exists(in_key);
297  if (pItem)
298  {
299  Iterator it;
300  it.pItem = pItem;
301  this->Erase(it);
302  return true;
303  }
304 
305  return false;
306  }
307 
308  // WARNING: Do not use on types that need constructors or destructor called on Item objects at each creation.
309 
310  void Reorder(T_KEY in_OldKey, T_KEY in_NewKey, const T_ITEM & in_item)
311  {
312  bool bFound;
313  T_ITEM * pItem = BinarySearch(in_OldKey, bFound);
314 
315  //AKASSERT( bFound );
316  if (!bFound) return;// cannot be an assert for now.(WG-19496)
317 
318  unsigned int uIdx = (unsigned int)(pItem - this->m_pItems);
319  unsigned int uLastIdx = this->Length() - 1;
320 
321  AKASSERT(*pItem == in_item);
322 
323  bool bNeedReordering = false;
324  if (uIdx > 0) // if not first
325  {
326  T_ITEM * pPrevItem = this->m_pItems + (uIdx - 1);
327  if (Lesser(in_NewKey, U_KEY::Get(*pPrevItem)))
328  {
329  // Check one step further
330  if (uIdx > 1)
331  {
332  T_ITEM * pSecondPrevItem = this->m_pItems + (uIdx - 2);
333  if (Lesser(U_KEY::Get(*pSecondPrevItem), in_NewKey))
334  {
335  return Swap(pPrevItem, pItem);
336  }
337  else
338  {
339  bNeedReordering = true;
340  }
341  }
342  else
343  {
344  return Swap(pPrevItem, pItem);
345  }
346  }
347  }
348  if (!bNeedReordering && uIdx < uLastIdx)
349  {
350  T_ITEM * pNextItem = this->m_pItems + (uIdx + 1);
351  if (Lesser(U_KEY::Get(*pNextItem), in_NewKey))
352  {
353  // Check one step further
354  if (uIdx < (uLastIdx - 1))
355  {
356  T_ITEM * pSecondNextItem = this->m_pItems + (uIdx + 2);
357  if (Lesser(in_NewKey, U_KEY::Get(*pSecondNextItem)))
358  {
359  return Swap(pNextItem, pItem);
360  }
361  else
362  {
363  bNeedReordering = true;
364  }
365  }
366  else
367  {
368  return Swap(pNextItem, pItem);
369  }
370  }
371  }
372 
373  if (bNeedReordering)
374  {
375  /////////////////////////////////////////////////////////
376  // Faster implementation, moving only what is required.
377  /////////////////////////////////////////////////////////
378  unsigned int uIdxToInsert; // non initialized
379  T_ITEM * pTargetItem = BinarySearch(in_NewKey, bFound);
380  if (pTargetItem)
381  {
382  uIdxToInsert = (unsigned int)(pTargetItem - this->m_pItems);
383  if (uIdxToInsert > uIdx)
384  {
385  --uIdxToInsert;// we are still in the list, don't count the item to be moved.
386  }
387  }
388  else
389  {
390  uIdxToInsert = uLastIdx;
391  }
392 
393  T_ITEM * pStartItem = this->m_pItems + uIdx;
394  T_ITEM * pEndItem = this->m_pItems + uIdxToInsert;
395  if (uIdxToInsert < uIdx)
396  {
397  // Slide backward.
398  while (pStartItem != pEndItem)
399  {
400  --pStartItem;
401  pStartItem[1] = pStartItem[0];
402  }
403  }
404  else
405  {
406  // Slide forward.
407  while (pStartItem != pEndItem)
408  {
409  pStartItem[0] = pStartItem[1];
410  ++pStartItem;
411  }
412  }
413  pEndItem[0] = in_item;
414  ///////////////////////////////////////////////
415  }
416  }
417 
418  // WARNING: Do not use on types that need constructors or destructor called on Item objects at each creation.
419 
420  void ReSortArray() //To be used when the < > operator changed meaning.
421  {
422  AkInt32 NumItemsToReInsert = this->Length();
423  if (NumItemsToReInsert != 0)
424  {
425  // Do a re-insertion sort.
426  // Fool the table by faking it is empty, then re-insert one by one.
427  T_ITEM * pReinsertionItem = this->m_pItems;
428  this->m_uLength = 0; // Faking the Array Is Empty.
429  for (AkInt32 idx = 0; idx < NumItemsToReInsert; ++idx)
430  {
431  T_ITEM ItemtoReinsert = pReinsertionItem[idx]; // make a copy as the source is about to be overriden.
432 
433  T_KEY keyToReinsert = U_KEY::Get(ItemtoReinsert);
434 
435  T_ITEM* pInsertionEmplacement = AddNoSetKey(keyToReinsert);
436 
437  AKASSERT(pInsertionEmplacement);
438  *pInsertionEmplacement = ItemtoReinsert;
439  }
440  }
441  }
442 
443  // If found, returns the first item it encounters, if not, returns the insertion point.
444  T_ITEM * BinarySearch( T_KEY in_key, bool & out_bFound ) const
445  {
446  AkUInt32 uNumToSearch = this->Length();
447  AkInt32 iBase = 0;
448  AkInt32 iPivot = 0;
449 
450  while ( uNumToSearch > 0 )
451  {
452  iPivot = iBase + ( uNumToSearch >> 1 );
453  T_KEY pivotKey = U_KEY::Get( this->m_pItems[ iPivot ] );
454  if ( Equal( pivotKey, in_key ) )
455  {
456  out_bFound = true;
457  return this->m_pItems + iPivot;
458  }
459 
460  if ( Lesser( pivotKey, in_key ) )
461  {
462  iBase = iPivot + 1;
463  uNumToSearch--;
464  }
465  uNumToSearch >>= 1;
466  }
467 
468  out_bFound = false;
469  return this->m_pItems + iBase;
470  }
471 
472  T_ITEM* LowerBounds(T_KEY in_key) const
473  {
474  return LowerBounds(in_key, this->Begin(), this->End());
475  }
476 
477  // Returns the first item in the array that is not less than the key,
478  // or the insertion point, if no key is less then in_key.
479  T_ITEM* LowerBounds(T_KEY in_key, Iterator in_from, Iterator in_to) const
480  {
481  AKASSERT(in_to.pItem >= in_from.pItem);
482  AkUInt32 uBase = (AkUInt32)(in_from.pItem - this->m_pItems);
483  AkInt64 uNumToSearch = (AkInt64)(in_to.pItem - in_from.pItem);
484  AkUInt32 uPivot;
485 
486  while (uNumToSearch > 0)
487  {
488  uPivot = uBase + (AkUInt32)(uNumToSearch >> 1);
489  T_KEY pivotKey = U_KEY::Get(this->m_pItems[uPivot]);
490  if (Lesser(pivotKey, in_key))
491  {
492  uBase = uPivot + 1;
493  uNumToSearch--;
494  }
495  uNumToSearch >>= 1;
496  }
497 
498  return this->m_pItems + uBase;
499  }
500 
501  AkForceInline void Swap(T_ITEM * in_ItemA, T_ITEM * in_ItemB)
502  {
503  T_ITEM ItemTemp = *in_ItemA;
504  *in_ItemA = *in_ItemB;
505  *in_ItemB = ItemTemp;
506  }
507 };
508 
509 
510 #endif //_KEYARRAY_H_
CAkKeyArray::Exists
T_ITEM * Exists(T_KEY in_Key) const
Definition: AkKeyArray.h:43
CAkKeyArray::Set
T_ITEM * Set(T_KEY in_Key, const T_ITEM &in_Item)
Definition: AkKeyArray.h:54
CAkKeyArray::FindEx
AkArray< MapStruct< T_KEY, T_ITEM >, const MapStruct< T_KEY, T_ITEM > &, U_POOL, TGrowBy, TMovePolicy >::Iterator FindEx(T_KEY in_Item) const
Definition: AkKeyArray.h:112
AkSortedKeyArray::Set
T_ITEM * Set(T_KEY in_key, bool &out_bExists)
Definition: AkKeyArray.h:271
CAkKeyArray::Set
T_ITEM * Set(T_KEY in_Key)
Definition: AkKeyArray.h:94
AkGetArrayKey
Key policy for AkSortedKeyArray.
Definition: AkKeyArray.h:155
AkSortedKeyArray::LowerBounds
T_ITEM * LowerBounds(T_KEY in_key, Iterator in_from, Iterator in_to) const
Definition: AkKeyArray.h:479
AkSortedKeyArray::Exists
T_ITEM * Exists(T_KEY in_key) const
Definition: AkKeyArray.h:219
AkSortedKeyArray::LowerBounds
T_ITEM * LowerBounds(T_KEY in_key) const
Definition: AkKeyArray.h:472
AkArray
Specific implementation of array.
Definition: AkArray.h:241
NULL
#define NULL
Definition: AkTypes.h:46
AkInt32
int32_t AkInt32
Signed 32-bit integer.
Definition: AkNumeralTypes.h:43
MapStruct::item
T_ITEM item
Definition: AkKeyDef.h:36
AkSortedKeyArray::BinarySearch
T_ITEM * BinarySearch(T_KEY in_key, bool &out_bFound) const
Definition: AkKeyArray.h:444
MapStruct
Definition: AkKeyDef.h:34
AkSortedKeyArray::AddNoSetKey
T_ITEM * AddNoSetKey(T_KEY in_key, bool &out_bFound)
Definition: AkKeyArray.h:247
AkSortedKeyArray::Swap
AkForceInline void Swap(T_ITEM *in_ItemA, T_ITEM *in_ItemB)
Definition: AkKeyArray.h:501
AKASSERT
#define AKASSERT(Condition)
Definition: AkAssert.h:67
CAkKeyArray::SetFirst
T_ITEM * SetFirst(T_KEY in_Key, const T_ITEM &in_Item)
Definition: AkKeyArray.h:74
AkGetArrayKeyTrivial
Trivial key policy for AkSortedKeyArray, when T_KEY is T_ITEM.
Definition: AkKeyArray.h:174
AkSortedKeyArray::Equal
AkForceInline bool Equal(T_KEY &a, T_KEY &b) const
Definition: AkKeyArray.h:214
AkSortedKeyArray::Add
T_ITEM * Add(T_KEY in_key)
Definition: AkKeyArray.h:228
AkDefaultSortedKeyCompare::Lesser
static AkForceInline bool Lesser(THIS_CLASS *, T_KEY &a, T_KEY &b)
Definition: AkKeyArray.h:188
AkArray< MapStruct< T_KEY, T_ITEM >, const MapStruct< T_KEY, T_ITEM > &, ArrayPoolDefault, AkGrowByPolicy_DEFAULT, AkAssignmentMovePolicy< MapStruct< T_KEY, T_ITEM > > >::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:327
AkInt64
int64_t AkInt64
Signed 64-bit integer.
Definition: AkNumeralTypes.h:44
AkArray< T_ITEM, const T_ITEM &, ArrayPoolDefault, AkGrowByPolicy_DEFAULT, AkAssignmentMovePolicy< T_ITEM > >::Length
AkForceInline AkUInt32 Length() const
Returns the numbers of items in the array.
Definition: AkArray.h:549
AkGetArrayKeyFunc::Get
static AkForceInline T_KEY & Get(T_ITEM &in_item)
Default policy.
Definition: AkKeyArray.h:166
AkDefaultSortedKeyCompare::Equal
static AkForceInline bool Equal(THIS_CLASS *, T_KEY &a, T_KEY &b)
Definition: AkKeyArray.h:194
AkGetArrayKey::Get
static AkForceInline T_KEY & Get(T_ITEM &in_item)
Default policy.
Definition: AkKeyArray.h:157
AkUInt32
uint32_t AkUInt32
Unsigned 32-bit integer.
Definition: AkNumeralTypes.h:38
AkSortedKeyArray::AddNoSetKey
T_ITEM * AddNoSetKey(T_KEY in_key)
Definition: AkKeyArray.h:241
CAkKeyArray::UnsetSwap
void UnsetSwap(T_KEY in_Key)
Definition: AkKeyArray.h:143
AkSortedKeyArray::ReSortArray
void ReSortArray()
Definition: AkKeyArray.h:420
AkSortedKeyArray::Unset
bool Unset(T_KEY in_key)
Definition: AkKeyArray.h:294
AkSortedKeyArray::Lesser
AkForceInline bool Lesser(T_KEY &a, T_KEY &b) const
Definition: AkKeyArray.h:209
CAkKeyArray::Unset
void Unset(T_KEY in_Key)
Definition: AkKeyArray.h:130
AkGetArrayKeyTrivial::Get
static AkForceInline T_KEY & Get(T_KEY &in_item)
Default policy.
Definition: AkKeyArray.h:177
AkForceInline
#define AkForceInline
Definition: AkTypes.h:61
AkSortedKeyArray::Reorder
void Reorder(T_KEY in_OldKey, T_KEY in_NewKey, const T_ITEM &in_item)
Definition: AkKeyArray.h:310
MapStruct::key
T_KEY key
Definition: AkKeyDef.h:35
AkSortedKeyArray::Set
T_ITEM * Set(T_KEY in_key)
Definition: AkKeyArray.h:265

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