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

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