版本
menu_open
Wwise SDK 2021.1.14
AkHeap.h
浏览该文件的文档.
1 /*******************************************************************************
2 The content of this file includes portions of the AUDIOKINETIC Wwise Technology
3 released in source code form as part of the SDK installer package.
4 
5 Commercial License Usage
6 
7 Licensees holding valid commercial licenses to the AUDIOKINETIC Wwise Technology
8 may use this file in accordance with the end user license agreement provided
9 with the software or, alternatively, in accordance with the terms contained in a
10 written agreement between you and Audiokinetic Inc.
11 
12 Apache License Usage
13 
14 Alternatively, this file may be used under the Apache License, Version 2.0 (the
15 "Apache License"); you may not use this file except in compliance with the
16 Apache License. You may obtain a copy of the Apache License at
17 http://www.apache.org/licenses/LICENSE-2.0.
18 
19 Unless required by applicable law or agreed to in writing, software distributed
20 under the Apache License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES
21 OR CONDITIONS OF ANY KIND, either express or implied. See the Apache License for
22 the specific language governing permissions and limitations under the License.
23 
24 Version: v2021.1.14 Build: 6590
25 Copyright (c) 2006-2023 Audiokinetic Inc.
26 *******************************************************************************/
27 
28 #pragma once
29 
30 #include <AK/Tools/Common/AkKeyArray.h>
31 
32 
33 template <class T_KEY, class T_ITEM, class U_POOL, class U_KEY = AkGetArrayKey< T_KEY, T_ITEM >, class TGrowBy = AkGrowByPolicy_DEFAULT, class TMovePolicy = AkAssignmentMovePolicy<T_ITEM>, class TComparePolicy = AkDefaultSortedKeyCompare<T_KEY> >
34 class CAkHeap : public AkArray< T_ITEM, const T_ITEM &, U_POOL, TGrowBy, TMovePolicy >
35 {
36  typedef AkArray< T_ITEM, const T_ITEM &, U_POOL, TGrowBy, TMovePolicy > Base;
37 
38 public:
39  T_ITEM * Insert(T_KEY in_Key)
40  {
41  if (Base::AddLast())
42  {
43  int insertIdx = Base::m_uLength - 1;
44 
45  while (insertIdx != 0)
46  {
47  int parentIdx = Parent(insertIdx);
48 
49  if (Lesser(in_Key, U_KEY::Get(Base::m_pItems[parentIdx])))
50  {
51  TMovePolicy::Move(Base::m_pItems[insertIdx], Base::m_pItems[parentIdx]);
52  insertIdx = parentIdx;
53  }
54  else
55  {
56  break;
57  }
58  }
59 
60  T_ITEM* pItem = &Base::m_pItems[insertIdx];
61 
62  // Set key
63  U_KEY::Get(*pItem) = in_Key;
64 
65  return pItem;
66  }
67 
68  return NULL;
69  }
70 
71  void RemoveRoot()
72  {
73  if (Base::m_uLength <= 1)
74  {
75  Base::m_uLength = 0;
76  return;
77  }
78 
79  Base::m_pItems[0] = Base::m_pItems[Base::m_uLength - 1];
80  Base::m_uLength--;
81 
82  Heapify();
83  }
84 
85  void Heapify()
86  {
87  AkUInt32 idx = 0;
88 
89  while(true)
90  {
91  AkUInt32 left = LeftChild(idx);
92  AkUInt32 right = RightChild(idx);
93  AkUInt32 smallest = idx;
94 
95  if (left < Base::m_uLength && Lesser(Base::m_pItems[left].key, Base::m_pItems[idx].key) )
96  smallest = left;
97 
98  if (right < Base::m_uLength && Lesser(Base::m_pItems[right].key, Base::m_pItems[smallest].key) )
99  smallest = right;
100 
101  if (smallest == idx)
102  break;
103 
104  Swap(idx, smallest);
105 
106  idx = smallest;
107  }
108  }
109 
110 private:
111  AkForceInline bool Lesser(T_KEY &a, T_KEY &b) const
112  {
113  return TComparePolicy::Lesser((void*)this, a, b);
114  }
115 
116  AkForceInline void Swap(AkUInt32 in_i0, AkUInt32 in_i1)
117  {
118  T_ITEM temp;
119  TMovePolicy::Move(temp, Base::m_pItems[in_i0]);
120  TMovePolicy::Move(Base::m_pItems[in_i0], Base::m_pItems[in_i1]);
121  TMovePolicy::Move(Base::m_pItems[in_i1], temp);
122  }
123 
124  AkForceInline AkUInt32 Parent(AkUInt32 i)
125  {
126  return (i - 1U) / 2U;
127  }
128 
129  AkForceInline AkUInt32 LeftChild(AkUInt32 i)
130  {
131  return (2U * i + 1U);
132  }
133 
134  AkForceInline AkUInt32 RightChild(AkUInt32 i)
135  {
136  return (2U * i + 2U);
137  }
138 };
CAkHeap::Heapify
void Heapify()
Definition: AkHeap.h:85
AkArray
Specific implementation of array
Definition: AkArray.h:200
NULL
#define NULL
Definition: AkTypes.h:47
CAkHeap::RemoveRoot
void RemoveRoot()
Definition: AkHeap.h:71
AkArray::m_uLength
AkUInt32 m_uLength
number of items in the array.
Definition: AkArray.h:724
CAkHeap
Definition: AkHeap.h:35
AkArray::AddLast
AkForceInline T * AddLast()
Definition: AkArray.h:478
AkUInt32
uint32_t AkUInt32
Unsigned 32-bit integer
Definition: AkTypes.h:59
AkForceInline
#define AkForceInline
Definition: AkTypes.h:60
CAkHeap::Insert
T_ITEM * Insert(T_KEY in_Key)
Definition: AkHeap.h:39
AkArray::m_pItems
T * m_pItems
pointer to the beginning of the array.
Definition: AkArray.h:723

此页面对您是否有帮助？

需要技术支持？

仍有疑问？或者问题？需要更多信息？欢迎联系我们，我们可以提供帮助！

查看我们的“技术支持”页面

介绍一下自己的项目。我们会竭力为您提供帮助。

来注册自己的项目，我们帮您快速入门，不带任何附加条件！

开始 Wwise 之旅