Table of Contents

Wwise SDK 2019.1.6
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 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>
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  AkInt32 uBottom = 0, uTop = (AkInt32)this->m_uLength;
200  while (uBottom < uTop)
201  {
202  AkInt32 uThis = uBottom + (uTop - uBottom) / 2;
203  if (Lesser(U_KEY::Get(this->m_pItems[uThis]), in_key))
204  uBottom = uThis + 1;
205  else
206  uTop = uThis;
207  }
208 
209  return (uBottom < (AkInt32)this->m_uLength) && Equal(U_KEY::Get(this->m_pItems[uBottom]), in_key) ? this->m_pItems + uBottom : NULL;
210  }
211 
212  // Add an item to the list (allowing duplicate keys)
213 
214  T_ITEM * Add(T_KEY in_key)
215  {
216  T_ITEM * pItem = AddNoSetKey(in_key);
217 
218  // Then set the key
219  if (pItem)
220  U_KEY::Get(*pItem) = in_key;
221 
222  return pItem;
223  }
224 
225  // Add an item to the list (allowing duplicate keys)
226 
227  T_ITEM * AddNoSetKey(T_KEY in_key)
228  {
229  bool bFound;
230  T_ITEM * pItem = BinarySearch(in_key, bFound);
231  if (pItem)
232  {
233  unsigned int uIdx = (unsigned int)(pItem - this->m_pItems);
234  pItem = this->Insert(uIdx);
235  }
236  else
237  {
238  pItem = this->AddLast();
239  }
240 
241  return pItem;
242  }
243 
244  // Set an item in the list (returning existing item if present)
245 
246  T_ITEM * Set(T_KEY in_key)
247  {
248  bool bFound;
249  return Set(in_key, bFound);
250  }
251 
252  T_ITEM * Set(T_KEY in_key, bool & out_bExists)
253  {
254 
255  T_ITEM * pItem = BinarySearch(in_key, out_bExists);
256  if (!out_bExists)
257  {
258  if (pItem)
259  {
260  unsigned int uIdx = (unsigned int)(pItem - this->m_pItems);
261  pItem = this->Insert(uIdx);
262  }
263  else
264  {
265  pItem = this->AddLast();
266  }
267 
268  if (pItem)
269  U_KEY::Get(*pItem) = in_key;
270  }
271 
272  return pItem;
273  }
274 
275 
276  bool Unset(T_KEY in_key)
277  {
278  T_ITEM * pItem = Exists(in_key);
279  if (pItem)
280  {
282  it.pItem = pItem;
283  this->Erase(it);
284  return true;
285  }
286 
287  return false;
288  }
289 
290  // WARNING: Do not use on types that need constructors or destructor called on Item objects at each creation.
291 
292  void Reorder(T_KEY in_OldKey, T_KEY in_NewKey, const T_ITEM & in_item)
293  {
294  bool bFound;
295  T_ITEM * pItem = BinarySearch(in_OldKey, bFound);
296 
297  //AKASSERT( bFound );
298  if (!bFound) return;// cannot be an assert for now.(WG-19496)
299 
300  unsigned int uIdx = (unsigned int)(pItem - this->m_pItems);
301  unsigned int uLastIdx = this->Length() - 1;
302 
303  AKASSERT(*pItem == in_item);
304 
305  bool bNeedReordering = false;
306  if (uIdx > 0) // if not first
307  {
308  T_ITEM * pPrevItem = this->m_pItems + (uIdx - 1);
309  if (Lesser(in_NewKey, U_KEY::Get(*pPrevItem)))
310  {
311  // Check one step further
312  if (uIdx > 1)
313  {
314  T_ITEM * pSecondPrevItem = this->m_pItems + (uIdx - 2);
315  if (Lesser(U_KEY::Get(*pSecondPrevItem), in_NewKey))
316  {
317  return Swap(pPrevItem, pItem);
318  }
319  else
320  {
321  bNeedReordering = true;
322  }
323  }
324  else
325  {
326  return Swap(pPrevItem, pItem);
327  }
328  }
329  }
330  if (!bNeedReordering && uIdx < uLastIdx)
331  {
332  T_ITEM * pNextItem = this->m_pItems + (uIdx + 1);
333  if (Lesser(U_KEY::Get(*pNextItem), in_NewKey))
334  {
335  // Check one step further
336  if (uIdx < (uLastIdx - 1))
337  {
338  T_ITEM * pSecondNextItem = this->m_pItems + (uIdx + 2);
339  if (Lesser(in_NewKey, U_KEY::Get(*pSecondNextItem)))
340  {
341  return Swap(pNextItem, pItem);
342  }
343  else
344  {
345  bNeedReordering = true;
346  }
347  }
348  else
349  {
350  return Swap(pNextItem, pItem);
351  }
352  }
353  }
354 
355  if (bNeedReordering)
356  {
357  /////////////////////////////////////////////////////////
358  // Faster implementation, moving only what is required.
359  /////////////////////////////////////////////////////////
360  unsigned int uIdxToInsert; // non initialized
361  T_ITEM * pTargetItem = BinarySearch(in_NewKey, bFound);
362  if (pTargetItem)
363  {
364  uIdxToInsert = (unsigned int)(pTargetItem - this->m_pItems);
365  if (uIdxToInsert > uIdx)
366  {
367  --uIdxToInsert;// we are still in the list, don't count the item to be moved.
368  }
369  }
370  else
371  {
372  uIdxToInsert = uLastIdx;
373  }
374 
375  T_ITEM * pStartItem = this->m_pItems + uIdx;
376  T_ITEM * pEndItem = this->m_pItems + uIdxToInsert;
377  if (uIdxToInsert < uIdx)
378  {
379  // Slide backward.
380  while (pStartItem != pEndItem)
381  {
382  --pStartItem;
383  pStartItem[1] = pStartItem[0];
384  }
385  }
386  else
387  {
388  // Slide forward.
389  while (pStartItem != pEndItem)
390  {
391  pStartItem[0] = pStartItem[1];
392  ++pStartItem;
393  }
394  }
395  pEndItem[0] = in_item;
396  ///////////////////////////////////////////////
397  }
398  }
399 
400  // WARNING: Do not use on types that need constructors or destructor called on Item objects at each creation.
401 
402  void ReSortArray() //To be used when the < > operator changed meaning.
403  {
404  AkInt32 NumItemsToReInsert = this->Length();
405  if (NumItemsToReInsert != 0)
406  {
407  // Do a re-insertion sort.
408  // Fool the table by faking it is empty, then re-insert one by one.
409  T_ITEM * pReinsertionItem = this->m_pItems;
410  this->m_uLength = 0; // Faking the Array Is Empty.
411  for (AkInt32 idx = 0; idx < NumItemsToReInsert; ++idx)
412  {
413  T_ITEM ItemtoReinsert = pReinsertionItem[idx]; // make a copy as the source is about to be overriden.
414 
415  T_KEY keyToReinsert = U_KEY::Get(ItemtoReinsert);
416 
417  T_ITEM* pInsertionEmplacement = AddNoSetKey(keyToReinsert);
418 
419  AKASSERT(pInsertionEmplacement);
420  *pInsertionEmplacement = ItemtoReinsert;
421  }
422  }
423  }
424 
425  //If found, returns the item, if not, returns the insertion point.
426  T_ITEM * BinarySearch( T_KEY in_key, bool & out_bFound ) const
427  {
428  AkInt32 uTop = 0, uBottom = this->Length() - 1;
429  while (uTop <= uBottom)
430  {
431  AkInt32 uThis = (uBottom - uTop) / 2 + uTop;
432  if (Lesser(in_key, U_KEY::Get(this->m_pItems[uThis])))
433  uBottom = uThis - 1;
434  else if (Lesser(U_KEY::Get(this->m_pItems[uThis]), in_key))
435  uTop = uThis + 1;
436  else
437  {
438  out_bFound = true;
439  return this->m_pItems + uThis;
440  }
441  }
442 
443  out_bFound = false;
444  return this->m_pItems ? this->m_pItems + uTop : NULL;
445  }
446 
447  AkForceInline void Swap(T_ITEM * in_ItemA, T_ITEM * in_ItemB)
448  {
449  T_ITEM ItemTemp = *in_ItemA;
450  *in_ItemA = *in_ItemB;
451  *in_ItemB = ItemTemp;
452  }
453 };
454 
455 
456 #endif //_KEYARRAY_H_
T_ITEM * Set(T_KEY in_Key)
Definition: AkKeyArray.h:95
static AkForceInline bool Lesser(THIS_CLASS *, T_KEY &a, T_KEY &b)
Definition: AkKeyArray.h:169
AkForceInline bool Equal(T_KEY &a, T_KEY &b) const
Definition: AkKeyArray.h:192
bool Unset(T_KEY in_key)
Definition: AkKeyArray.h:276
void Reorder(T_KEY in_OldKey, T_KEY in_NewKey, const T_ITEM &in_item)
Definition: AkKeyArray.h:292
void UnsetSwap(T_KEY in_Key)
Definition: AkKeyArray.h:144
AkForceInline AkUInt32 Length() const
Returns the numbers of items in the array.
Definition: AkArray.h:420
T_ITEM * Set(T_KEY in_key)
Definition: AkKeyArray.h:246
AkForceInline bool Lesser(T_KEY &a, T_KEY &b) const
Definition: AkKeyArray.h:187
AkForceInline void Swap(T_ITEM *in_ItemA, T_ITEM *in_ItemB)
Definition: AkKeyArray.h:447
T_ITEM * Set(T_KEY in_key, bool &out_bExists)
Definition: AkKeyArray.h:252
Specific implementation of array.
Definition: AkArray.h:189
static AkForceInline bool Equal(THIS_CLASS *, T_KEY &a, T_KEY &b)
Definition: AkKeyArray.h:175
T_ITEM * Add(T_KEY in_key)
Definition: AkKeyArray.h:214
#define AKASSERT(Condition)
Definition: AkAssert.h:69
T_KEY key
Definition: AkKeyDef.h:36
T_ITEM * m_pItems
pointer to the beginning of the array.
Definition: AkArray.h:685
#define AkForceInline
Force inlining.
Definition: AkTypes.h:62
Key policy for AkSortedKeyArray.
Definition: AkKeyArray.h:155
int32_t AkInt32
Signed 32-bit integer.
Definition: AkTypes.h:91
Iterator End() const
Returns the iterator to the end of the array.
Definition: AkArray.h:278
AkUInt32 m_uLength
number of items in the array.
Definition: AkArray.h:686
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
T_ITEM * SetFirst(T_KEY in_Key, const T_ITEM &in_Item)
Definition: AkKeyArray.h:75
T_ITEM * BinarySearch(T_KEY in_key, bool &out_bFound) const
Definition: AkKeyArray.h:426
#define NULL
Definition: AkTypes.h:49
Iterator Erase(Iterator &in_rIter)
Erase the specified iterator from the array.
Definition: AkArray.h:327
void Unset(T_KEY in_Key)
Definition: AkKeyArray.h:131
static AkForceInline T_KEY & Get(T_ITEM &in_item)
Default policy.
Definition: AkKeyArray.h:158
Definition: AkKeyDef.h:34
T_ITEM item
Definition: AkKeyDef.h:37
T_ITEM * Exists(T_KEY in_key) const
Definition: AkKeyArray.h:197
T_ITEM * Set(T_KEY in_Key, const T_ITEM &in_Item)
Definition: AkKeyArray.h:55
T_ITEM * AddNoSetKey(T_KEY in_key)
Definition: AkKeyArray.h:227
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 * Exists(T_KEY in_Key)
Definition: AkKeyArray.h:44
void ReSortArray()
Definition: AkKeyArray.h:402