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_