Table of Contents

include/AK/Tools/Common/AkHeap.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 #pragma once
00029 
00030 #include <AK/Tools/Common/AkKeyArray.h>
00031 
00032 
00033 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> >
00034 class CAkHeap : public AkArray< T_ITEM, const T_ITEM &, U_POOL, TGrowBy, TMovePolicy >
00035 {
00036     typedef AkArray< T_ITEM, const T_ITEM &, U_POOL, TGrowBy, TMovePolicy > Base;
00037 
00038 public:
00039     T_ITEM * Insert(T_KEY in_Key)
00040     {
00041         if (Base::AddLast())
00042         {
00043             int insertIdx = Base::m_uLength - 1;
00044 
00045             while (insertIdx != 0)
00046             {
00047                 int parentIdx = Parent(insertIdx);
00048 
00049                 if (Greater(U_KEY::Get(Base::m_pItems[parentIdx]), in_Key))
00050                 {
00051                     TMovePolicy::Move(Base::m_pItems[insertIdx], Base::m_pItems[parentIdx]);
00052                     insertIdx = parentIdx;
00053                 }
00054                 else
00055                 {
00056                     break;
00057                 }
00058             }
00059 
00060             T_ITEM* pItem = &Base::m_pItems[insertIdx];
00061 
00062             // Set key
00063             U_KEY::Get(*pItem) = in_Key;
00064 
00065             return pItem;
00066         }
00067 
00068         return NULL;
00069     }
00070 
00071     void RemoveRoot()
00072     {
00073         if (Base::m_uLength <= 1)
00074         {
00075             Base::m_uLength = 0;
00076             return;
00077         }
00078 
00079         Base::m_pItems[0] = Base::m_pItems[Base::m_uLength - 1];
00080         Base::m_uLength--;
00081 
00082         Heapify();
00083     }
00084 
00085     void Heapify()
00086     {
00087         AkUInt32 idx = 0;
00088 
00089         while(true)
00090         {
00091             AkUInt32 left = LeftChild(idx);
00092             AkUInt32 right = RightChild(idx);
00093             AkUInt32 smallest = idx;
00094             
00095             if (left < Base::m_uLength && Lesser(Base::m_pItems[left].key, Base::m_pItems[idx].key) )
00096                 smallest = left;
00097             
00098             if (right < Base::m_uLength && Lesser(Base::m_pItems[right].key, Base::m_pItems[smallest].key) )
00099                 smallest = right;
00100 
00101             if (smallest == idx)
00102                 break;
00103             
00104             Swap(idx, smallest);
00105 
00106             idx = smallest;
00107         }
00108     }
00109 
00110 private:
00111     AkForceInline bool Greater(T_KEY &a, T_KEY &b) const
00112     {
00113         return TComparePolicy::Greater((void*)this, a, b);
00114     }
00115 
00116     AkForceInline bool Lesser(T_KEY &a, T_KEY &b) const
00117     {
00118         return TComparePolicy::Lesser((void*)this, a, b);
00119     }
00120 
00121     AkForceInline void Swap(AkUInt32 in_i0, AkUInt32 in_i1)
00122     {
00123         T_ITEM temp;
00124         TMovePolicy::Move(temp, Base::m_pItems[in_i0]);
00125         TMovePolicy::Move(Base::m_pItems[in_i0], Base::m_pItems[in_i1]);
00126         TMovePolicy::Move(Base::m_pItems[in_i1], temp);
00127     }
00128 
00129     AkForceInline AkUInt32 Parent(AkUInt32 i) 
00130     { 
00131         return (i - 1U) / 2U; 
00132     }
00133 
00134     AkForceInline AkUInt32 LeftChild(AkUInt32 i) 
00135     { 
00136         return (2U * i + 1U); 
00137     }
00138 
00139     AkForceInline AkUInt32 RightChild(AkUInt32 i) 
00140     {
00141         return (2U * i + 2U); 
00142     }
00143 };