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 T_ITEM * pItem = BinarySearch(in_key, bFound); 00242 if (!bFound) 00243 { 00244 if (pItem) 00245 { 00246 unsigned int uIdx = (unsigned int)(pItem - this->m_pItems); 00247 pItem = this->Insert(uIdx); 00248 } 00249 else 00250 { 00251 pItem = this->AddLast(); 00252 } 00253 00254 if (pItem) 00255 U_KEY::Get(*pItem) = in_key; 00256 } 00257 00258 return pItem; 00259 } 00260 00261 00262 bool Unset(T_KEY in_key) 00263 { 00264 bool bFound; 00265 T_ITEM * pItem = BinarySearch(in_key, bFound); 00266 if (bFound) 00267 { 00268 typename AkArray< T_ITEM, const T_ITEM &, U_POOL, TGrowBy, TMovePolicy >::Iterator it; 00269 it.pItem = pItem; 00270 this->Erase(it); 00271 } 00272 00273 return bFound; 00274 } 00275 00276 // WARNING: Do not use on types that need constructors or destructor called on Item objects at each creation. 00277 00278 void Reorder(T_KEY in_OldKey, T_KEY in_NewKey, const T_ITEM & in_item) 00279 { 00280 bool bFound; 00281 T_ITEM * pItem = BinarySearch(in_OldKey, bFound); 00282 00283 //AKASSERT( bFound ); 00284 if (!bFound) return;// cannot be an assert for now.(WG-19496) 00285 00286 unsigned int uIdx = (unsigned int)(pItem - this->m_pItems); 00287 unsigned int uLastIdx = this->Length() - 1; 00288 00289 AKASSERT(*pItem == in_item); 00290 00291 bool bNeedReordering = false; 00292 if (uIdx > 0) // if not first 00293 { 00294 T_ITEM * pPrevItem = this->m_pItems + (uIdx - 1); 00295 if (Lesser(in_NewKey, U_KEY::Get(*pPrevItem))) 00296 { 00297 // Check one step further 00298 if (uIdx > 1) 00299 { 00300 T_ITEM * pSecondPrevItem = this->m_pItems + (uIdx - 2); 00301 if (Greater(in_NewKey, U_KEY::Get(*pSecondPrevItem))) 00302 { 00303 return Swap(pPrevItem, pItem); 00304 } 00305 else 00306 { 00307 bNeedReordering = true; 00308 } 00309 } 00310 else 00311 { 00312 return Swap(pPrevItem, pItem); 00313 } 00314 } 00315 } 00316 if (!bNeedReordering && uIdx < uLastIdx) 00317 { 00318 T_ITEM * pNextItem = this->m_pItems + (uIdx + 1); 00319 if (Greater(in_NewKey, U_KEY::Get(*pNextItem))) 00320 { 00321 // Check one step further 00322 if (uIdx < (uLastIdx - 1)) 00323 { 00324 T_ITEM * pSecondNextItem = this->m_pItems + (uIdx + 2); 00325 if (Lesser(in_NewKey, U_KEY::Get(*pSecondNextItem))) 00326 { 00327 return Swap(pNextItem, pItem); 00328 } 00329 else 00330 { 00331 bNeedReordering = true; 00332 } 00333 } 00334 else 00335 { 00336 return Swap(pNextItem, pItem); 00337 } 00338 } 00339 } 00340 00341 if (bNeedReordering) 00342 { 00343 ///////////////////////////////////////////////////////// 00344 // Faster implementation, moving only what is required. 00345 ///////////////////////////////////////////////////////// 00346 unsigned int uIdxToInsert; // non initialized 00347 T_ITEM * pTargetItem = BinarySearch(in_NewKey, bFound); 00348 if (pTargetItem) 00349 { 00350 uIdxToInsert = (unsigned int)(pTargetItem - this->m_pItems); 00351 if (uIdxToInsert > uIdx) 00352 { 00353 --uIdxToInsert;// we are still in the list, don't count the item to be moved. 00354 } 00355 } 00356 else 00357 { 00358 uIdxToInsert = uLastIdx; 00359 } 00360 00361 T_ITEM * pStartItem = this->m_pItems + uIdx; 00362 T_ITEM * pEndItem = this->m_pItems + uIdxToInsert; 00363 if (uIdxToInsert < uIdx) 00364 { 00365 // Slide backward. 00366 while (pStartItem != pEndItem) 00367 { 00368 --pStartItem; 00369 pStartItem[1] = pStartItem[0]; 00370 } 00371 } 00372 else 00373 { 00374 // Slide forward. 00375 while (pStartItem != pEndItem) 00376 { 00377 pStartItem[0] = pStartItem[1]; 00378 ++pStartItem; 00379 } 00380 } 00381 pEndItem[0] = in_item; 00382 /////////////////////////////////////////////// 00383 } 00384 } 00385 00386 // WARNING: Do not use on types that need constructors or destructor called on Item objects at each creation. 00387 00388 void ReSortArray() //To be used when the < > operator changed meaning. 00389 { 00390 AkInt32 NumItemsToReInsert = this->Length(); 00391 if (NumItemsToReInsert != 0) 00392 { 00393 // Do a re-insertion sort. 00394 // Fool the table by faking it is empty, then re-insert one by one. 00395 T_ITEM * pReinsertionItem = this->m_pItems; 00396 this->m_uLength = 0; // Faking the Array Is Empty. 00397 for (AkInt32 idx = 0; idx < NumItemsToReInsert; ++idx) 00398 { 00399 T_ITEM ItemtoReinsert = pReinsertionItem[idx]; // make a copy as the source is about to be overriden. 00400 00401 T_KEY keyToReinsert = U_KEY::Get(ItemtoReinsert); 00402 00403 T_ITEM* pInsertionEmplacement = AddNoSetKey(keyToReinsert); 00404 00405 AKASSERT(pInsertionEmplacement); 00406 *pInsertionEmplacement = ItemtoReinsert; 00407 } 00408 } 00409 } 00410 00411 00412 T_ITEM * BinarySearch( T_KEY in_key, bool & out_bFound ) const 00413 { 00414 AkInt32 uTop = 0, uBottom = this->Length() - 1; 00415 00416 // binary search for key 00417 while (uTop <= uBottom) 00418 { 00419 AkInt32 uThis = (uBottom - uTop) / 2 + uTop; 00420 if (Lesser(in_key, U_KEY::Get(this->m_pItems[uThis]))) 00421 uBottom = uThis - 1; 00422 else if (Greater(in_key, U_KEY::Get(this->m_pItems[uThis]))) 00423 uTop = uThis + 1; 00424 else 00425 { 00426 out_bFound = true; 00427 return this->m_pItems + uThis; 00428 } 00429 } 00430 00431 out_bFound = false; 00432 return this->m_pItems ? this->m_pItems + uTop : NULL; 00433 } 00434 00435 AkForceInline void Swap(T_ITEM * in_ItemA, T_ITEM * in_ItemB) 00436 { 00437 T_ITEM ItemTemp = *in_ItemA; 00438 *in_ItemA = *in_ItemB; 00439 *in_ItemB = ItemTemp; 00440 } 00441 }; 00442 00443 00444 #endif //_KEYARRAY_H_
프로젝트를 등록하세요. 아무런 조건이나 의무 사항 없이 빠른 시작을 도와드리겠습니다.
Wwise를 시작해 보세요