Table of Contents

include/AK/Tools/Common/AkKeyArray.h

Go to the documentation of this file.
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_