Table of Contents

include/AK/Tools/Common/AkKeyArray.h

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