00001 /******************************************************************************* 00002 The content of this file includes portions of the AUDIOKINETIC Wwise Technology 00003 released in source code form as part of the SDK installer package. 00004 00005 Commercial License Usage 00006 00007 Licensees holding valid commercial licenses to the AUDIOKINETIC Wwise Technology 00008 may use this file in accordance with the end user license agreement provided 00009 with the software or, alternatively, in accordance with the terms contained in a 00010 written agreement between you and Audiokinetic Inc. 00011 00012 Apache License Usage 00013 00014 Alternatively, this file may be used under the Apache License, Version 2.0 (the 00015 "Apache License"); you may not use this file except in compliance with the 00016 Apache License. You may obtain a copy of the Apache License at 00017 http://www.apache.org/licenses/LICENSE-2.0. 00018 00019 Unless required by applicable law or agreed to in writing, software distributed 00020 under the Apache License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES 00021 OR CONDITIONS OF ANY KIND, either express or implied. See the Apache License for 00022 the specific language governing permissions and limitations under the License. 00023 00024 Version: <VERSION> Build: <BUILDNUMBER> 00025 Copyright (c) <COPYRIGHTYEAR> Audiokinetic Inc. 00026 *******************************************************************************/ 00027 00028 #ifndef _KEYARRAY_H_ 00029 #define _KEYARRAY_H_ 00030 00031 #include <AK/Tools/Common/AkArray.h> 00032 #include <AK/Tools/Common/AkKeyDef.h> 00033 00034 // The Key list is simply a list that may be referenced using a key 00035 // NOTE : 00036 template <class T_KEY, class T_ITEM, class U_POOL = ArrayPoolDefault, AkUInt32 TGrowBy = 1, class TMovePolicy = AkAssignmentMovePolicy<MapStruct<T_KEY, T_ITEM> > > 00037 class CAkKeyArray : public AkArray< MapStruct<T_KEY, T_ITEM>, const MapStruct<T_KEY, T_ITEM>&, U_POOL, TGrowBy, TMovePolicy> 00038 { 00039 public: 00040 //==================================================================================================== 00041 // Return NULL if the Key does not exisis 00042 // Return T_ITEM* otherwise 00043 //==================================================================================================== 00044 T_ITEM* Exists(T_KEY in_Key) 00045 { 00046 typename CAkKeyArray< T_KEY, T_ITEM, U_POOL, TGrowBy, TMovePolicy >::Iterator it = this->FindEx(in_Key); 00047 return (it != this->End()) ? &(it.pItem->item) : NULL; 00048 } 00049 00050 public: 00051 //==================================================================================================== 00052 // Sets the item referenced by the specified key and item 00053 // Return AK_Fail if the list max size was exceeded 00054 //==================================================================================================== 00055 T_ITEM * Set(T_KEY in_Key, const T_ITEM & in_Item) 00056 { 00057 T_ITEM* pSearchedItem = Exists(in_Key); 00058 if (pSearchedItem) 00059 { 00060 *pSearchedItem = in_Item; 00061 } 00062 else 00063 { 00064 MapStruct<T_KEY, T_ITEM> * pStruct = this->AddLast(); 00065 if (pStruct) 00066 { 00067 pStruct->key = in_Key; 00068 pStruct->item = in_Item; 00069 pSearchedItem = &(pStruct->item); 00070 } 00071 } 00072 return pSearchedItem; 00073 } 00074 00075 T_ITEM * SetFirst(T_KEY in_Key, const T_ITEM & in_Item) 00076 { 00077 T_ITEM* pSearchedItem = Exists(in_Key); 00078 if (pSearchedItem) 00079 { 00080 *pSearchedItem = in_Item; 00081 } 00082 else 00083 { 00084 MapStruct<T_KEY, T_ITEM> * pStruct = this->Insert(0); //insert at index 0 is AddFirst. 00085 if (pStruct) 00086 { 00087 pStruct->key = in_Key; 00088 pStruct->item = in_Item; 00089 pSearchedItem = &(pStruct->item); 00090 } 00091 } 00092 return pSearchedItem; 00093 } 00094 00095 T_ITEM * Set(T_KEY in_Key) 00096 { 00097 T_ITEM* pSearchedItem = Exists(in_Key); 00098 if (!pSearchedItem) 00099 { 00100 MapStruct<T_KEY, T_ITEM> * pStruct = this->AddLast(); 00101 if (pStruct) 00102 { 00103 pStruct->key = in_Key; 00104 pSearchedItem = &(pStruct->item); 00105 } 00106 } 00107 return pSearchedItem; 00108 } 00109 00110 // NOTE: The real definition should be 00111 // typename CAkKeyArray<T_KEY,T_ITEM,TGrowBy, TMovePolicy>::Iterator FindEx( T_KEY in_Item ) const 00112 // Typenaming the base class is a workaround for bug MTWX33123 in the new Freescale CodeWarrior. 00113 typename AkArray< MapStruct<T_KEY, T_ITEM>, const MapStruct<T_KEY, T_ITEM>&, U_POOL, TGrowBy, TMovePolicy>::Iterator FindEx(T_KEY in_Item) const 00114 { 00115 typename CAkKeyArray< T_KEY, T_ITEM, U_POOL, TGrowBy, TMovePolicy >::Iterator it = this->Begin(); 00116 00117 typename CAkKeyArray< T_KEY, T_ITEM, U_POOL, TGrowBy, TMovePolicy >::Iterator itEnd = this->End(); 00118 for (; it != itEnd; ++it) 00119 { 00120 if ((*it).key == in_Item) 00121 break; 00122 } 00123 00124 return it; 00125 } 00126 00127 //==================================================================================================== 00128 // Remove the item referenced by the specified key 00129 //==================================================================================================== 00130 00131 void Unset(T_KEY in_Key) 00132 { 00133 typename CAkKeyArray< T_KEY, T_ITEM, U_POOL, TGrowBy, TMovePolicy >::Iterator it = FindEx(in_Key); 00134 if (it != this->End()) 00135 { 00136 this->Erase(it); 00137 } 00138 } 00139 00140 //==================================================================================================== 00141 // More efficient version of Unset when order is unimportant 00142 //==================================================================================================== 00143 00144 void UnsetSwap(T_KEY in_Key) 00145 { 00146 typename CAkKeyArray< T_KEY, T_ITEM, U_POOL, TGrowBy, TMovePolicy >::Iterator it = FindEx(in_Key); 00147 if (it != this->End()) 00148 { 00149 this->EraseSwap(it); 00150 } 00151 } 00152 }; 00153 00154 /// Key policy for AkSortedKeyArray. 00155 template <class T_KEY, class T_ITEM> struct AkGetArrayKey 00156 { 00157 /// Default policy. 00158 static AkForceInline T_KEY & Get(T_ITEM & in_item) 00159 { 00160 return in_item.key; 00161 } 00162 }; 00163 00164 //Default comparison policy for AkSortedKeyArray. 00165 template <class T_KEY> struct AkDefaultSortedKeyCompare 00166 { 00167 public: 00168 template<class THIS_CLASS> 00169 static AkForceInline bool Greater(THIS_CLASS*, T_KEY &a, T_KEY &b) 00170 { 00171 return a > b; 00172 } 00173 00174 template<class THIS_CLASS> 00175 static AkForceInline bool Lesser(THIS_CLASS*, T_KEY &a, T_KEY &b) 00176 { 00177 return a < b; 00178 } 00179 }; 00180 00181 /// Array of items, sorted by key. Uses binary search for lookups. BEWARE WHEN 00182 /// MODIFYING THE ARRAY USING BASE CLASS METHODS. 00183 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> > 00184 class AkSortedKeyArray : public AkArray< T_ITEM, const T_ITEM &, U_POOL, TGrowBy, TMovePolicy > 00185 { 00186 public: 00187 AkForceInline bool Greater(T_KEY &a, T_KEY &b) const 00188 { 00189 return TComparePolicy::Greater((void*)this, a, b); 00190 } 00191 00192 AkForceInline bool Lesser(T_KEY &a, T_KEY &b) const 00193 { 00194 return TComparePolicy::Lesser((void*)this, a, b); 00195 } 00196 00197 T_ITEM* Exists(T_KEY in_key) const 00198 { 00199 bool bFound; 00200 T_ITEM * pItem = BinarySearch(in_key, bFound); 00201 return bFound ? pItem : NULL; 00202 } 00203 00204 // Add an item to the list (allowing duplicate keys) 00205 00206 T_ITEM * Add(T_KEY in_key) 00207 { 00208 T_ITEM * pItem = AddNoSetKey(in_key); 00209 00210 // Then set the key 00211 if (pItem) 00212 U_KEY::Get(*pItem) = in_key; 00213 00214 return pItem; 00215 } 00216 00217 // Add an item to the list (allowing duplicate keys) 00218 00219 T_ITEM * AddNoSetKey(T_KEY in_key) 00220 { 00221 bool bFound; 00222 T_ITEM * pItem = BinarySearch(in_key, bFound); 00223 if (pItem) 00224 { 00225 unsigned int uIdx = (unsigned int)(pItem - this->m_pItems); 00226 pItem = this->Insert(uIdx); 00227 } 00228 else 00229 { 00230 pItem = this->AddLast(); 00231 } 00232 00233 return pItem; 00234 } 00235 00236 // Set an item in the list (returning existing item if present) 00237 00238 T_ITEM * Set(T_KEY in_key) 00239 { 00240 bool bFound; 00241 return Set(in_key, bFound); 00242 } 00243 00244 T_ITEM * Set(T_KEY in_key, bool & out_bExists) 00245 { 00246 00247 T_ITEM * pItem = BinarySearch(in_key, out_bExists); 00248 if (!out_bExists) 00249 { 00250 if (pItem) 00251 { 00252 unsigned int uIdx = (unsigned int)(pItem - this->m_pItems); 00253 pItem = this->Insert(uIdx); 00254 } 00255 else 00256 { 00257 pItem = this->AddLast(); 00258 } 00259 00260 if (pItem) 00261 U_KEY::Get(*pItem) = in_key; 00262 } 00263 00264 return pItem; 00265 } 00266 00267 00268 bool Unset(T_KEY in_key) 00269 { 00270 bool bFound; 00271 T_ITEM * pItem = BinarySearch(in_key, bFound); 00272 if (bFound) 00273 { 00274 typename AkArray< T_ITEM, const T_ITEM &, U_POOL, TGrowBy, TMovePolicy >::Iterator it; 00275 it.pItem = pItem; 00276 this->Erase(it); 00277 } 00278 00279 return bFound; 00280 } 00281 00282 // WARNING: Do not use on types that need constructors or destructor called on Item objects at each creation. 00283 00284 void Reorder(T_KEY in_OldKey, T_KEY in_NewKey, const T_ITEM & in_item) 00285 { 00286 bool bFound; 00287 T_ITEM * pItem = BinarySearch(in_OldKey, bFound); 00288 00289 //AKASSERT( bFound ); 00290 if (!bFound) return;// cannot be an assert for now.(WG-19496) 00291 00292 unsigned int uIdx = (unsigned int)(pItem - this->m_pItems); 00293 unsigned int uLastIdx = this->Length() - 1; 00294 00295 AKASSERT(*pItem == in_item); 00296 00297 bool bNeedReordering = false; 00298 if (uIdx > 0) // if not first 00299 { 00300 T_ITEM * pPrevItem = this->m_pItems + (uIdx - 1); 00301 if (Lesser(in_NewKey, U_KEY::Get(*pPrevItem))) 00302 { 00303 // Check one step further 00304 if (uIdx > 1) 00305 { 00306 T_ITEM * pSecondPrevItem = this->m_pItems + (uIdx - 2); 00307 if (Greater(in_NewKey, U_KEY::Get(*pSecondPrevItem))) 00308 { 00309 return Swap(pPrevItem, pItem); 00310 } 00311 else 00312 { 00313 bNeedReordering = true; 00314 } 00315 } 00316 else 00317 { 00318 return Swap(pPrevItem, pItem); 00319 } 00320 } 00321 } 00322 if (!bNeedReordering && uIdx < uLastIdx) 00323 { 00324 T_ITEM * pNextItem = this->m_pItems + (uIdx + 1); 00325 if (Greater(in_NewKey, U_KEY::Get(*pNextItem))) 00326 { 00327 // Check one step further 00328 if (uIdx < (uLastIdx - 1)) 00329 { 00330 T_ITEM * pSecondNextItem = this->m_pItems + (uIdx + 2); 00331 if (Lesser(in_NewKey, U_KEY::Get(*pSecondNextItem))) 00332 { 00333 return Swap(pNextItem, pItem); 00334 } 00335 else 00336 { 00337 bNeedReordering = true; 00338 } 00339 } 00340 else 00341 { 00342 return Swap(pNextItem, pItem); 00343 } 00344 } 00345 } 00346 00347 if (bNeedReordering) 00348 { 00349 ///////////////////////////////////////////////////////// 00350 // Faster implementation, moving only what is required. 00351 ///////////////////////////////////////////////////////// 00352 unsigned int uIdxToInsert; // non initialized 00353 T_ITEM * pTargetItem = BinarySearch(in_NewKey, bFound); 00354 if (pTargetItem) 00355 { 00356 uIdxToInsert = (unsigned int)(pTargetItem - this->m_pItems); 00357 if (uIdxToInsert > uIdx) 00358 { 00359 --uIdxToInsert;// we are still in the list, don't count the item to be moved. 00360 } 00361 } 00362 else 00363 { 00364 uIdxToInsert = uLastIdx; 00365 } 00366 00367 T_ITEM * pStartItem = this->m_pItems + uIdx; 00368 T_ITEM * pEndItem = this->m_pItems + uIdxToInsert; 00369 if (uIdxToInsert < uIdx) 00370 { 00371 // Slide backward. 00372 while (pStartItem != pEndItem) 00373 { 00374 --pStartItem; 00375 pStartItem[1] = pStartItem[0]; 00376 } 00377 } 00378 else 00379 { 00380 // Slide forward. 00381 while (pStartItem != pEndItem) 00382 { 00383 pStartItem[0] = pStartItem[1]; 00384 ++pStartItem; 00385 } 00386 } 00387 pEndItem[0] = in_item; 00388 /////////////////////////////////////////////// 00389 } 00390 } 00391 00392 // WARNING: Do not use on types that need constructors or destructor called on Item objects at each creation. 00393 00394 void ReSortArray() //To be used when the < > operator changed meaning. 00395 { 00396 AkInt32 NumItemsToReInsert = this->Length(); 00397 if (NumItemsToReInsert != 0) 00398 { 00399 // Do a re-insertion sort. 00400 // Fool the table by faking it is empty, then re-insert one by one. 00401 T_ITEM * pReinsertionItem = this->m_pItems; 00402 this->m_uLength = 0; // Faking the Array Is Empty. 00403 for (AkInt32 idx = 0; idx < NumItemsToReInsert; ++idx) 00404 { 00405 T_ITEM ItemtoReinsert = pReinsertionItem[idx]; // make a copy as the source is about to be overriden. 00406 00407 T_KEY keyToReinsert = U_KEY::Get(ItemtoReinsert); 00408 00409 T_ITEM* pInsertionEmplacement = AddNoSetKey(keyToReinsert); 00410 00411 AKASSERT(pInsertionEmplacement); 00412 *pInsertionEmplacement = ItemtoReinsert; 00413 } 00414 } 00415 } 00416 00417 00418 T_ITEM * BinarySearch( T_KEY in_key, bool & out_bFound ) const 00419 { 00420 AkInt32 uTop = 0, uBottom = this->Length() - 1; 00421 00422 // binary search for key 00423 while (uTop <= uBottom) 00424 { 00425 AkInt32 uThis = (uBottom - uTop) / 2 + uTop; 00426 if (Lesser(in_key, U_KEY::Get(this->m_pItems[uThis]))) 00427 uBottom = uThis - 1; 00428 else if (Greater(in_key, U_KEY::Get(this->m_pItems[uThis]))) 00429 uTop = uThis + 1; 00430 else 00431 { 00432 out_bFound = true; 00433 return this->m_pItems + uThis; 00434 } 00435 } 00436 00437 out_bFound = false; 00438 return this->m_pItems ? this->m_pItems + uTop : NULL; 00439 } 00440 00441 AkForceInline void Swap(T_ITEM * in_ItemA, T_ITEM * in_ItemB) 00442 { 00443 T_ITEM ItemTemp = *in_ItemA; 00444 *in_ItemA = *in_ItemB; 00445 *in_ItemB = ItemTemp; 00446 } 00447 }; 00448 00449 00450 #endif //_KEYARRAY_H_
Questions? Problems? Need more info? Contact us, and we can help!
Visit our Support pageRegister your project and we'll help you get started with no strings attached!
Get started with Wwise