00001 /*********************************************************************** 00002 The content of this file includes source code for the sound engine 00003 portion of the AUDIOKINETIC Wwise Technology and constitutes "Level 00004 Two Source Code" as defined in the Source Code Addendum attached 00005 with this file. Any use of the Level Two Source Code shall be 00006 subject to the terms and conditions outlined in the Source Code 00007 Addendum and the End User License Agreement for Wwise(R). 00008 00009 Version: <VERSION> Build: <BUILDNUMBER> 00010 Copyright (c) <COPYRIGHTYEAR> Audiokinetic Inc. 00011 ***********************************************************************/ 00012 00014 // 00015 // AkKeyArray.h 00016 // 00018 #ifndef _KEYARRAY_H_ 00019 #define _KEYARRAY_H_ 00020 00021 #include <AK/Tools/Common/AkArray.h> 00022 #include <AK/Tools/Common/AkKeyDef.h> 00023 00024 // The Key list is simply a list that may be referenced using a key 00025 // NOTE : 00026 template <class T_KEY, class T_ITEM, class U_POOL = ArrayPoolDefault, AkUInt32 TGrowBy = 1, class TMovePolicy = AkAssignmentMovePolicy<MapStruct<T_KEY, T_ITEM> > > 00027 class CAkKeyArray : public AkArray< MapStruct<T_KEY, T_ITEM>, const MapStruct<T_KEY, T_ITEM>&, U_POOL, TGrowBy, TMovePolicy> 00028 { 00029 public: 00030 //==================================================================================================== 00031 // Return NULL if the Key does not exisis 00032 // Return T_ITEM* otherwise 00033 //==================================================================================================== 00034 T_ITEM* Exists( T_KEY in_Key ) 00035 { 00036 typename CAkKeyArray< T_KEY, T_ITEM, U_POOL, TGrowBy, TMovePolicy >::Iterator it = this->FindEx( in_Key ); 00037 return ( it != this->End() ) ? &(it.pItem->item) : NULL; 00038 } 00039 00040 public: 00041 //==================================================================================================== 00042 // Sets the item referenced by the specified key and item 00043 // Return AK_Fail if the list max size was exceeded 00044 //==================================================================================================== 00045 T_ITEM * Set( T_KEY in_Key, T_ITEM in_Item ) 00046 { 00047 T_ITEM* pSearchedItem = Exists( in_Key ); 00048 if( pSearchedItem ) 00049 { 00050 *pSearchedItem = in_Item; 00051 } 00052 else 00053 { 00054 MapStruct<T_KEY, T_ITEM> * pStruct = this->AddLast(); 00055 if ( pStruct ) 00056 { 00057 pStruct->key = in_Key; 00058 pStruct->item = in_Item; 00059 pSearchedItem = &( pStruct->item ); 00060 } 00061 } 00062 return pSearchedItem; 00063 } 00064 00065 T_ITEM * SetFirst( T_KEY in_Key, T_ITEM in_Item ) 00066 { 00067 T_ITEM* pSearchedItem = Exists( in_Key ); 00068 if( pSearchedItem ) 00069 { 00070 *pSearchedItem = in_Item; 00071 } 00072 else 00073 { 00074 MapStruct<T_KEY, T_ITEM> * pStruct = this->Insert( 0 ); //insert at index 0 is AddFirst. 00075 if ( pStruct ) 00076 { 00077 pStruct->key = in_Key; 00078 pStruct->item = in_Item; 00079 pSearchedItem = &( pStruct->item ); 00080 } 00081 } 00082 return pSearchedItem; 00083 } 00084 00085 T_ITEM * Set( T_KEY in_Key ) 00086 { 00087 T_ITEM* pSearchedItem = Exists( in_Key ); 00088 if( !pSearchedItem ) 00089 { 00090 MapStruct<T_KEY, T_ITEM> * pStruct = this->AddLast(); 00091 if ( pStruct ) 00092 { 00093 pStruct->key = in_Key; 00094 pSearchedItem = &( pStruct->item ); 00095 } 00096 } 00097 return pSearchedItem; 00098 } 00099 00100 // NOTE: The real definition should be 00101 // typename CAkKeyArray<T_KEY,T_ITEM,TGrowBy, TMovePolicy>::Iterator FindEx( T_KEY in_Item ) const 00102 // Typenaming the base class is a workaround for bug MTWX33123 in the new Freescale CodeWarrior. 00103 typename AkArray< MapStruct<T_KEY, T_ITEM>, const MapStruct<T_KEY, T_ITEM>&, U_POOL, TGrowBy, TMovePolicy>::Iterator FindEx( T_KEY in_Item ) const 00104 { 00105 typename CAkKeyArray< T_KEY, T_ITEM, U_POOL, TGrowBy, TMovePolicy >::Iterator it = this->Begin(); 00106 00107 typename CAkKeyArray< T_KEY, T_ITEM, U_POOL, TGrowBy, TMovePolicy >::Iterator itEnd = this->End(); 00108 for ( ; it != itEnd; ++it ) 00109 { 00110 if ( (*it).key == in_Item ) 00111 break; 00112 } 00113 00114 return it; 00115 } 00116 00117 //==================================================================================================== 00118 // Remove the item referenced by the specified key 00119 //==================================================================================================== 00120 00121 void Unset( T_KEY in_Key ) 00122 { 00123 typename CAkKeyArray< T_KEY, T_ITEM, U_POOL, TGrowBy, TMovePolicy >::Iterator it = FindEx( in_Key ); 00124 if( it != this->End() ) 00125 { 00126 this->Erase( it ); 00127 } 00128 } 00129 00130 //==================================================================================================== 00131 // More efficient version of Unset when order is unimportant 00132 //==================================================================================================== 00133 00134 void UnsetSwap( T_KEY in_Key ) 00135 { 00136 typename CAkKeyArray< T_KEY, T_ITEM, U_POOL, TGrowBy, TMovePolicy >::Iterator it = FindEx( in_Key ); 00137 if( it != this->End() ) 00138 { 00139 this->EraseSwap( it ); 00140 } 00141 } 00142 }; 00143 00145 template <class T_KEY, class T_ITEM> struct AkGetArrayKey 00146 { 00148 static AkForceInline T_KEY & Get( T_ITEM & in_item ) 00149 { 00150 return in_item.key; 00151 } 00152 }; 00153 00156 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> > 00157 class AkSortedKeyArray : public AkArray< T_ITEM, const T_ITEM &, U_POOL, TGrowBy, TMovePolicy > 00158 { 00159 public: 00160 template< class P_KEY> 00161 T_ITEM* Exists( P_KEY in_key ) 00162 { 00163 bool bFound; 00164 T_ITEM * pItem = BinarySearch( in_key, bFound ); 00165 return bFound ? pItem : NULL; 00166 } 00167 00168 // Add an item to the list (allowing duplicate keys) 00169 template< class P_KEY> 00170 T_ITEM * Add( P_KEY in_key ) 00171 { 00172 T_ITEM * pItem = AddNoSetKey( in_key ); 00173 00174 // Then set the key 00175 if ( pItem ) 00176 U_KEY::Get( *pItem ) = in_key; 00177 00178 return pItem; 00179 } 00180 00181 // Add an item to the list (allowing duplicate keys) 00182 template< class P_KEY> 00183 T_ITEM * AddNoSetKey( P_KEY in_key ) 00184 { 00185 bool bFound; 00186 T_ITEM * pItem = BinarySearch( in_key, bFound ); 00187 if ( pItem ) 00188 { 00189 unsigned int uIdx = (unsigned int) ( pItem - this->m_pItems ); 00190 pItem = this->Insert( uIdx ); 00191 } 00192 else 00193 { 00194 pItem = this->AddLast(); 00195 } 00196 00197 return pItem; 00198 } 00199 00200 // Set an item in the list (returning existing item if present) 00201 template< class P_KEY> 00202 T_ITEM * Set( P_KEY in_key ) 00203 { 00204 bool bFound; 00205 T_ITEM * pItem = BinarySearch( in_key, bFound ); 00206 if ( !bFound ) 00207 { 00208 if ( pItem ) 00209 { 00210 unsigned int uIdx = (unsigned int) ( pItem - this->m_pItems ); 00211 pItem = this->Insert( uIdx ); 00212 } 00213 else 00214 { 00215 pItem = this->AddLast(); 00216 } 00217 00218 if ( pItem ) 00219 U_KEY::Get( *pItem ) = in_key; 00220 } 00221 00222 return pItem; 00223 } 00224 00225 template< class P_KEY> 00226 void Unset( P_KEY in_key ) 00227 { 00228 bool bFound; 00229 T_ITEM * pItem = BinarySearch( in_key, bFound ); 00230 if ( bFound ) 00231 { 00232 typename AkArray< T_ITEM, const T_ITEM &, U_POOL, TGrowBy, TMovePolicy >::Iterator it; 00233 it.pItem = pItem; 00234 this->Erase( it ); 00235 } 00236 } 00237 00238 // WARNING: Do not use on types that need constructors or destructor called on Item objects at each creation. 00239 template< class P_KEY> 00240 void Reorder( P_KEY in_OldKey, P_KEY in_NewKey, T_ITEM in_item ) 00241 { 00242 bool bFound; 00243 T_ITEM * pItem = BinarySearch( in_OldKey, bFound ); 00244 00245 //AKASSERT( bFound ); 00246 if( !bFound ) return;// cannot be an assert for now.(WG-19496) 00247 00248 unsigned int uIdx = (unsigned int) ( pItem - this->m_pItems ); 00249 unsigned int uLastIdx = this->Length()-1; 00250 00251 AKASSERT( *pItem == in_item ); 00252 00253 bool bNeedReordering = false; 00254 if( uIdx > 0 ) // if not first 00255 { 00256 T_ITEM * pPrevItem = this->m_pItems + (uIdx - 1); 00257 if( in_NewKey < U_KEY::Get( *pPrevItem ) ) 00258 { 00259 // Check one step further 00260 if( uIdx > 1 ) 00261 { 00262 T_ITEM * pSecondPrevItem = this->m_pItems + (uIdx - 2); 00263 if( in_NewKey > U_KEY::Get( *pSecondPrevItem ) ) 00264 { 00265 return Swap( pPrevItem, pItem ); 00266 } 00267 else 00268 { 00269 bNeedReordering = true; 00270 } 00271 } 00272 else 00273 { 00274 return Swap( pPrevItem, pItem ); 00275 } 00276 } 00277 } 00278 if( !bNeedReordering && uIdx < uLastIdx ) 00279 { 00280 T_ITEM * pNextItem = this->m_pItems + (uIdx + 1); 00281 if( in_NewKey > U_KEY::Get( *pNextItem ) ) 00282 { 00283 // Check one step further 00284 if( uIdx < (uLastIdx-1) ) 00285 { 00286 T_ITEM * pSecondNextItem = this->m_pItems + (uIdx + 2); 00287 if( in_NewKey < U_KEY::Get( *pSecondNextItem ) ) 00288 { 00289 return Swap( pNextItem, pItem ); 00290 } 00291 else 00292 { 00293 bNeedReordering = true; 00294 } 00295 } 00296 else 00297 { 00298 return Swap( pNextItem, pItem ); 00299 } 00300 } 00301 } 00302 00303 if( bNeedReordering ) 00304 { 00306 // Faster implementation, moving only what is required. 00308 unsigned int uIdxToInsert; // non initialized 00309 T_ITEM * pTargetItem = BinarySearch( in_NewKey, bFound ); 00310 if ( pTargetItem ) 00311 { 00312 uIdxToInsert = (unsigned int) ( pTargetItem - this->m_pItems ); 00313 if( uIdxToInsert > uIdx ) 00314 { 00315 --uIdxToInsert;// we are still in the list, don't count the item to be moved. 00316 } 00317 } 00318 else 00319 { 00320 uIdxToInsert = uLastIdx; 00321 } 00322 00323 T_ITEM * pStartItem = this->m_pItems + uIdx; 00324 T_ITEM * pEndItem = this->m_pItems + uIdxToInsert; 00325 if( uIdxToInsert < uIdx ) 00326 { 00327 // Slide backward. 00328 while( pStartItem != pEndItem ) 00329 { 00330 --pStartItem; 00331 pStartItem[ 1 ] = pStartItem[ 0 ]; 00332 } 00333 } 00334 else 00335 { 00336 // Slide forward. 00337 while( pStartItem != pEndItem ) 00338 { 00339 pStartItem[ 0 ] = pStartItem[ 1 ]; 00340 ++pStartItem; 00341 } 00342 } 00343 pEndItem[0] = in_item; 00345 } 00346 } 00347 00348 // WARNING: Do not use on types that need constructors or destructor called on Item objects at each creation. 00349 template<class P_KEY> 00350 void ReSortArray() //To be used when the < > operator changed meaning. 00351 { 00352 AkInt32 NumItemsToReInsert = this->Length(); 00353 if( NumItemsToReInsert != 0 ) 00354 { 00355 // Do a re-insertion sort. 00356 // Fool the table by faking it is empty, then re-insert one by one. 00357 T_ITEM * pReinsertionItem = this->m_pItems; 00358 this->m_uLength = 0; // Faking the Array Is Empty. 00359 for( AkInt32 idx = 0; idx < NumItemsToReInsert; ++idx ) 00360 { 00361 T_ITEM ItemtoReinsert = pReinsertionItem[idx]; // make a copy as the source is about to be overriden. 00362 00363 T_KEY keyToReinsert = U_KEY::Get(ItemtoReinsert); 00364 00365 T_ITEM* pInsertionEmplacement = AddNoSetKey( *reinterpret_cast<P_KEY*>(&keyToReinsert) ); 00366 00367 AKASSERT( pInsertionEmplacement ); 00368 *pInsertionEmplacement = ItemtoReinsert; 00369 } 00370 } 00371 } 00372 00373 template< class P_KEY> 00374 T_ITEM * BinarySearch( P_KEY in_key, bool & out_bFound ) 00375 { 00376 AkInt32 uTop = 0, uBottom = this->Length()-1; 00377 00378 // binary search for key 00379 while ( uTop <= uBottom ) 00380 { 00381 AkInt32 uThis = ( uBottom - uTop ) / 2 + uTop; 00382 if( in_key < U_KEY::Get( this->m_pItems[ uThis ] ) ) 00383 uBottom = uThis - 1; 00384 else if ( in_key > U_KEY::Get( this->m_pItems[ uThis ] ) ) 00385 uTop = uThis + 1; 00386 else 00387 { 00388 out_bFound = true; 00389 return this->m_pItems + uThis; 00390 } 00391 } 00392 00393 out_bFound = false; 00394 return this->m_pItems ? this->m_pItems + uTop : NULL; 00395 } 00396 00397 AkForceInline void Swap( T_ITEM * in_ItemA, T_ITEM * in_ItemB ) 00398 { 00399 T_ITEM ItemTemp = *in_ItemA; 00400 *in_ItemA = *in_ItemB; 00401 *in_ItemB = ItemTemp; 00402 } 00403 }; 00404 00405 #endif //_KEYARRAY_H_
프로젝트를 등록하세요. 아무런 조건이나 의무 사항 없이 빠른 시작을 도와드리겠습니다.
Wwise를 시작해 보세요