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