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