Table of Contents

Wwise SDK 2018.1.11
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 Greater(THIS_CLASS*, T_KEY &a, T_KEY &b)
170  {
171  return a > b;
172  }
173 
174  template<class THIS_CLASS>
175  static AkForceInline bool Lesser(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 Greater(T_KEY &a, T_KEY &b) const
188  {
189  return TComparePolicy::Greater((void*)this, a, b);
190  }
191 
192  AkForceInline bool Lesser(T_KEY &a, T_KEY &b) const
193  {
194  return TComparePolicy::Lesser((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 
247  T_ITEM * pItem = BinarySearch(in_key, out_bExists);
248  if (!out_bExists)
249  {
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  if (pItem)
261  U_KEY::Get(*pItem) = in_key;
262  }
263 
264  return pItem;
265  }
266 
267 
268  bool Unset(T_KEY in_key)
269  {
270  bool bFound;
271  T_ITEM * pItem = BinarySearch(in_key, bFound);
272  if (bFound)
273  {
275  it.pItem = pItem;
276  this->Erase(it);
277  }
278 
279  return bFound;
280  }
281 
282  // WARNING: Do not use on types that need constructors or destructor called on Item objects at each creation.
283 
284  void Reorder(T_KEY in_OldKey, T_KEY in_NewKey, const T_ITEM & in_item)
285  {
286  bool bFound;
287  T_ITEM * pItem = BinarySearch(in_OldKey, bFound);
288 
289  //AKASSERT( bFound );
290  if (!bFound) return;// cannot be an assert for now.(WG-19496)
291 
292  unsigned int uIdx = (unsigned int)(pItem - this->m_pItems);
293  unsigned int uLastIdx = this->Length() - 1;
294 
295  AKASSERT(*pItem == in_item);
296 
297  bool bNeedReordering = false;
298  if (uIdx > 0) // if not first
299  {
300  T_ITEM * pPrevItem = this->m_pItems + (uIdx - 1);
301  if (Lesser(in_NewKey, U_KEY::Get(*pPrevItem)))
302  {
303  // Check one step further
304  if (uIdx > 1)
305  {
306  T_ITEM * pSecondPrevItem = this->m_pItems + (uIdx - 2);
307  if (Greater(in_NewKey, U_KEY::Get(*pSecondPrevItem)))
308  {
309  return Swap(pPrevItem, pItem);
310  }
311  else
312  {
313  bNeedReordering = true;
314  }
315  }
316  else
317  {
318  return Swap(pPrevItem, pItem);
319  }
320  }
321  }
322  if (!bNeedReordering && uIdx < uLastIdx)
323  {
324  T_ITEM * pNextItem = this->m_pItems + (uIdx + 1);
325  if (Greater(in_NewKey, U_KEY::Get(*pNextItem)))
326  {
327  // Check one step further
328  if (uIdx < (uLastIdx - 1))
329  {
330  T_ITEM * pSecondNextItem = this->m_pItems + (uIdx + 2);
331  if (Lesser(in_NewKey, U_KEY::Get(*pSecondNextItem)))
332  {
333  return Swap(pNextItem, pItem);
334  }
335  else
336  {
337  bNeedReordering = true;
338  }
339  }
340  else
341  {
342  return Swap(pNextItem, pItem);
343  }
344  }
345  }
346 
347  if (bNeedReordering)
348  {
349  /////////////////////////////////////////////////////////
350  // Faster implementation, moving only what is required.
351  /////////////////////////////////////////////////////////
352  unsigned int uIdxToInsert; // non initialized
353  T_ITEM * pTargetItem = BinarySearch(in_NewKey, bFound);
354  if (pTargetItem)
355  {
356  uIdxToInsert = (unsigned int)(pTargetItem - this->m_pItems);
357  if (uIdxToInsert > uIdx)
358  {
359  --uIdxToInsert;// we are still in the list, don't count the item to be moved.
360  }
361  }
362  else
363  {
364  uIdxToInsert = uLastIdx;
365  }
366 
367  T_ITEM * pStartItem = this->m_pItems + uIdx;
368  T_ITEM * pEndItem = this->m_pItems + uIdxToInsert;
369  if (uIdxToInsert < uIdx)
370  {
371  // Slide backward.
372  while (pStartItem != pEndItem)
373  {
374  --pStartItem;
375  pStartItem[1] = pStartItem[0];
376  }
377  }
378  else
379  {
380  // Slide forward.
381  while (pStartItem != pEndItem)
382  {
383  pStartItem[0] = pStartItem[1];
384  ++pStartItem;
385  }
386  }
387  pEndItem[0] = in_item;
388  ///////////////////////////////////////////////
389  }
390  }
391 
392  // WARNING: Do not use on types that need constructors or destructor called on Item objects at each creation.
393 
394  void ReSortArray() //To be used when the < > operator changed meaning.
395  {
396  AkInt32 NumItemsToReInsert = this->Length();
397  if (NumItemsToReInsert != 0)
398  {
399  // Do a re-insertion sort.
400  // Fool the table by faking it is empty, then re-insert one by one.
401  T_ITEM * pReinsertionItem = this->m_pItems;
402  this->m_uLength = 0; // Faking the Array Is Empty.
403  for (AkInt32 idx = 0; idx < NumItemsToReInsert; ++idx)
404  {
405  T_ITEM ItemtoReinsert = pReinsertionItem[idx]; // make a copy as the source is about to be overriden.
406 
407  T_KEY keyToReinsert = U_KEY::Get(ItemtoReinsert);
408 
409  T_ITEM* pInsertionEmplacement = AddNoSetKey(keyToReinsert);
410 
411  AKASSERT(pInsertionEmplacement);
412  *pInsertionEmplacement = ItemtoReinsert;
413  }
414  }
415  }
416 
417 
418  T_ITEM * BinarySearch( T_KEY in_key, bool & out_bFound ) const
419  {
420  AkInt32 uTop = 0, uBottom = this->Length() - 1;
421 
422  // binary search for key
423  while (uTop <= uBottom)
424  {
425  AkInt32 uThis = (uBottom - uTop) / 2 + uTop;
426  if (Lesser(in_key, U_KEY::Get(this->m_pItems[uThis])))
427  uBottom = uThis - 1;
428  else if (Greater(in_key, U_KEY::Get(this->m_pItems[uThis])))
429  uTop = uThis + 1;
430  else
431  {
432  out_bFound = true;
433  return this->m_pItems + uThis;
434  }
435  }
436 
437  out_bFound = false;
438  return this->m_pItems ? this->m_pItems + uTop : NULL;
439  }
440 
441  AkForceInline void Swap(T_ITEM * in_ItemA, T_ITEM * in_ItemB)
442  {
443  T_ITEM ItemTemp = *in_ItemA;
444  *in_ItemA = *in_ItemB;
445  *in_ItemB = ItemTemp;
446  }
447 };
448 
449 
450 #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:175
bool Unset(T_KEY in_key)
Definition: AkKeyArray.h:268
void Reorder(T_KEY in_OldKey, T_KEY in_NewKey, const T_ITEM &in_item)
Definition: AkKeyArray.h:284
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:383
T_ITEM * Set(T_KEY in_key)
Definition: AkKeyArray.h:238
AkForceInline bool Lesser(T_KEY &a, T_KEY &b) const
Definition: AkKeyArray.h:192
AkForceInline void Swap(T_ITEM *in_ItemA, T_ITEM *in_ItemB)
Definition: AkKeyArray.h:441
T_ITEM * Set(T_KEY in_key, bool &out_bExists)
Definition: AkKeyArray.h:244
Specific implementation of array.
Definition: AkArray.h:152
T_ITEM * Add(T_KEY in_key)
Definition: AkKeyArray.h:206
#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:641
#define AkForceInline
Force inlining.
Definition: AkTypes.h:63
Key policy for AkSortedKeyArray.
Definition: AkKeyArray.h:155
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
AkUInt32 m_uLength
number of items in the array.
Definition: AkArray.h:642
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
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:418
static AkForceInline bool Greater(THIS_CLASS *, T_KEY &a, T_KEY &b)
Definition: AkKeyArray.h:169
#define NULL
Definition: AkTypes.h:49
Iterator Erase(Iterator &in_rIter)
Erase the specified iterator from the array.
Definition: AkArray.h:290
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:219
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:394
AkForceInline bool Greater(T_KEY &a, T_KEY &b) const
Definition: AkKeyArray.h:187