バージョン
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, 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, 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 00155 template <class T_KEY, class T_ITEM> struct AkGetArrayKey 00156 { 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 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) 00188 { 00189 return TComparePolicy::Greater((void*)this, a, b); 00190 } 00191 00192 AkForceInline bool Lesser(T_KEY &a, T_KEY &b) 00193 { 00194 return TComparePolicy::Lesser((void*)this, a, b); 00195 } 00196 00197 00198 T_ITEM* Exists( T_KEY in_key ) 00199 { 00200 bool bFound; 00201 T_ITEM * pItem = BinarySearch(in_key, bFound); 00202 return bFound ? pItem : NULL; 00203 } 00204 00205 // Add an item to the list (allowing duplicate keys) 00206 00207 T_ITEM * Add( T_KEY in_key ) 00208 { 00209 T_ITEM * pItem = AddNoSetKey(in_key); 00210 00211 // Then set the key 00212 if ( pItem ) 00213 U_KEY::Get( *pItem ) = in_key; 00214 00215 return pItem; 00216 } 00217 00218 // Add an item to the list (allowing duplicate keys) 00219 00220 T_ITEM * AddNoSetKey( T_KEY in_key ) 00221 { 00222 bool bFound; 00223 T_ITEM * pItem = BinarySearch(in_key, bFound); 00224 if ( pItem ) 00225 { 00226 unsigned int uIdx = (unsigned int) ( pItem - this->m_pItems ); 00227 pItem = this->Insert( uIdx ); 00228 } 00229 else 00230 { 00231 pItem = this->AddLast(); 00232 } 00233 00234 return pItem; 00235 } 00236 00237 // Set an item in the list (returning existing item if present) 00238 00239 T_ITEM * Set( T_KEY in_key ) 00240 { 00241 bool bFound; 00242 T_ITEM * pItem = BinarySearch(in_key, bFound); 00243 if ( !bFound ) 00244 { 00245 if ( pItem ) 00246 { 00247 unsigned int uIdx = (unsigned int) ( pItem - this->m_pItems ); 00248 pItem = this->Insert( uIdx ); 00249 } 00250 else 00251 { 00252 pItem = this->AddLast(); 00253 } 00254 00255 if ( pItem ) 00256 U_KEY::Get( *pItem ) = in_key; 00257 } 00258 00259 return pItem; 00260 } 00261 00262 00263 bool Unset( T_KEY in_key ) 00264 { 00265 bool bFound; 00266 T_ITEM * pItem = BinarySearch(in_key, bFound); 00267 if ( bFound ) 00268 { 00269 typename AkArray< T_ITEM, const T_ITEM &, U_POOL, TGrowBy, TMovePolicy >::Iterator it; 00270 it.pItem = pItem; 00271 this->Erase( it ); 00272 } 00273 00274 return bFound; 00275 } 00276 00277 // WARNING: Do not use on types that need constructors or destructor called on Item objects at each creation. 00278 00279 void Reorder( T_KEY in_OldKey, T_KEY in_NewKey, T_ITEM in_item ) 00280 { 00281 bool bFound; 00282 T_ITEM * pItem = BinarySearch(in_OldKey, bFound); 00283 00284 //AKASSERT( bFound ); 00285 if( !bFound ) return;// cannot be an assert for now.(WG-19496) 00286 00287 unsigned int uIdx = (unsigned int) ( pItem - this->m_pItems ); 00288 unsigned int uLastIdx = this->Length()-1; 00289 00290 AKASSERT( *pItem == in_item ); 00291 00292 bool bNeedReordering = false; 00293 if( uIdx > 0 ) // if not first 00294 { 00295 T_ITEM * pPrevItem = this->m_pItems + (uIdx - 1); 00296 if( Lesser(in_NewKey, U_KEY::Get( *pPrevItem )) ) 00297 { 00298 // Check one step further 00299 if( uIdx > 1 ) 00300 { 00301 T_ITEM * pSecondPrevItem = this->m_pItems + (uIdx - 2); 00302 if( Greater(in_NewKey, U_KEY::Get( *pSecondPrevItem )) ) 00303 { 00304 return Swap( pPrevItem, pItem ); 00305 } 00306 else 00307 { 00308 bNeedReordering = true; 00309 } 00310 } 00311 else 00312 { 00313 return Swap( pPrevItem, pItem ); 00314 } 00315 } 00316 } 00317 if( !bNeedReordering && uIdx < uLastIdx ) 00318 { 00319 T_ITEM * pNextItem = this->m_pItems + (uIdx + 1); 00320 if( Greater(in_NewKey, U_KEY::Get( *pNextItem )) ) 00321 { 00322 // Check one step further 00323 if( uIdx < (uLastIdx-1) ) 00324 { 00325 T_ITEM * pSecondNextItem = this->m_pItems + (uIdx + 2); 00326 if( Lesser(in_NewKey, U_KEY::Get( *pSecondNextItem )) ) 00327 { 00328 return Swap( pNextItem, pItem ); 00329 } 00330 else 00331 { 00332 bNeedReordering = true; 00333 } 00334 } 00335 else 00336 { 00337 return Swap( pNextItem, pItem ); 00338 } 00339 } 00340 } 00341 00342 if( bNeedReordering ) 00343 { 00345 // Faster implementation, moving only what is required. 00347 unsigned int uIdxToInsert; // non initialized 00348 T_ITEM * pTargetItem = BinarySearch(in_NewKey, bFound); 00349 if ( pTargetItem ) 00350 { 00351 uIdxToInsert = (unsigned int) ( pTargetItem - this->m_pItems ); 00352 if( uIdxToInsert > uIdx ) 00353 { 00354 --uIdxToInsert;// we are still in the list, don't count the item to be moved. 00355 } 00356 } 00357 else 00358 { 00359 uIdxToInsert = uLastIdx; 00360 } 00361 00362 T_ITEM * pStartItem = this->m_pItems + uIdx; 00363 T_ITEM * pEndItem = this->m_pItems + uIdxToInsert; 00364 if( uIdxToInsert < uIdx ) 00365 { 00366 // Slide backward. 00367 while( pStartItem != pEndItem ) 00368 { 00369 --pStartItem; 00370 pStartItem[ 1 ] = pStartItem[ 0 ]; 00371 } 00372 } 00373 else 00374 { 00375 // Slide forward. 00376 while( pStartItem != pEndItem ) 00377 { 00378 pStartItem[ 0 ] = pStartItem[ 1 ]; 00379 ++pStartItem; 00380 } 00381 } 00382 pEndItem[0] = in_item; 00384 } 00385 } 00386 00387 // WARNING: Do not use on types that need constructors or destructor called on Item objects at each creation. 00388 00389 void ReSortArray() //To be used when the < > operator changed meaning. 00390 { 00391 AkInt32 NumItemsToReInsert = this->Length(); 00392 if( NumItemsToReInsert != 0 ) 00393 { 00394 // Do a re-insertion sort. 00395 // Fool the table by faking it is empty, then re-insert one by one. 00396 T_ITEM * pReinsertionItem = this->m_pItems; 00397 this->m_uLength = 0; // Faking the Array Is Empty. 00398 for( AkInt32 idx = 0; idx < NumItemsToReInsert; ++idx ) 00399 { 00400 T_ITEM ItemtoReinsert = pReinsertionItem[idx]; // make a copy as the source is about to be overriden. 00401 00402 T_KEY keyToReinsert = U_KEY::Get(ItemtoReinsert); 00403 00404 T_ITEM* pInsertionEmplacement = AddNoSetKey(keyToReinsert); 00405 00406 AKASSERT( pInsertionEmplacement ); 00407 *pInsertionEmplacement = ItemtoReinsert; 00408 } 00409 } 00410 } 00411 00412 00413 T_ITEM * BinarySearch( T_KEY in_key, bool & out_bFound ) 00414 { 00415 AkInt32 uTop = 0, uBottom = this->Length()-1; 00416 00417 // binary search for key 00418 while ( uTop <= uBottom ) 00419 { 00420 AkInt32 uThis = ( uBottom - uTop ) / 2 + uTop; 00421 if( Lesser(in_key, U_KEY::Get( this->m_pItems[ uThis ] )) ) 00422 uBottom = uThis - 1; 00423 else if ( Greater(in_key, U_KEY::Get( this->m_pItems[ uThis ] )) ) 00424 uTop = uThis + 1; 00425 else 00426 { 00427 out_bFound = true; 00428 return this->m_pItems + uThis; 00429 } 00430 } 00431 00432 out_bFound = false; 00433 return this->m_pItems ? this->m_pItems + uTop : NULL; 00434 } 00435 00436 AkForceInline void Swap( T_ITEM * in_ItemA, T_ITEM * in_ItemB ) 00437 { 00438 T_ITEM ItemTemp = *in_ItemA; 00439 *in_ItemA = *in_ItemB; 00440 *in_ItemB = ItemTemp; 00441 } 00442 }; 00443 00444 #endif //_KEYARRAY_H_