Wwise SDK

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  Copyright (c) 2024 Audiokinetic Inc.

25 *******************************************************************************/

26 

27 #pragma once

28 

29 #include <AK/Tools/Common/AkKeyArray.h>

30 

31 

32 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> >

33 class CAkHeap : public AkArray< T_ITEM, const T_ITEM &, U_POOL, TGrowBy, TMovePolicy >

34 {

35  typedef AkArray< T_ITEM, const T_ITEM &, U_POOL, TGrowBy, TMovePolicy > Base;

36 

37 public:

38  T_ITEM * Insert(T_KEY in_Key)

39  {

40  if (Base::AddLast())

41  {

42  int insertIdx = Base::m_uLength - 1;

43 

44  while (insertIdx != 0)

45  {

46  int parentIdx = Parent(insertIdx);

47 

48  if (Lesser(in_Key, U_KEY::Get(Base::m_pItems[parentIdx])))

49  {

50  TMovePolicy::Move(Base::m_pItems[insertIdx], Base::m_pItems[parentIdx]);

51  insertIdx = parentIdx;

52  }

53  else

54  {

55  break;

56  }

57  }

58 

59  T_ITEM* pItem = &Base::m_pItems[insertIdx];

60 

61  // Set key

62  U_KEY::Get(*pItem) = in_Key;

63 

64  return pItem;

65  }

66 

67  return NULL;

68  }

69 

70  void RemoveRoot()

71  {

72  if (Base::m_uLength <= 1)

73  {

74  Base::m_uLength = 0;

75  return;

76  }

77 

78  Base::m_pItems[0] = Base::m_pItems[Base::m_uLength - 1];

79  Base::m_uLength--;

80 

81  Heapify();

82  }

83 

84  void Heapify()

85  {

86  AkUInt32 idx = 0;

87 

88  while(true)

89  {

90  AkUInt32 left = LeftChild(idx);

91  AkUInt32 right = RightChild(idx);

92  AkUInt32 smallest = idx;

93 

94  if (left < Base::m_uLength && Lesser(Base::m_pItems[left].key, Base::m_pItems[idx].key) )

95  smallest = left;

96 

97  if (right < Base::m_uLength && Lesser(Base::m_pItems[right].key, Base::m_pItems[smallest].key) )

98  smallest = right;

99 

100  if (smallest == idx)

101  break;

102 

103  Swap(idx, smallest);

104 

105  idx = smallest;

106  }

107  }

108 

109 private:

110  AkForceInline bool Lesser(T_KEY &a, T_KEY &b) const

111  {

112  return TComparePolicy::Lesser((void*)this, a, b);

113  }

114 

115  AkForceInline void Swap(AkUInt32 in_i0, AkUInt32 in_i1)

116  {

117  T_ITEM temp;

118  TMovePolicy::Move(temp, Base::m_pItems[in_i0]);

119  TMovePolicy::Move(Base::m_pItems[in_i0], Base::m_pItems[in_i1]);

120  TMovePolicy::Move(Base::m_pItems[in_i1], temp);

121  }

122 

123  AkForceInline AkUInt32 Parent(AkUInt32 i)

124  {

125  return (i - 1U) / 2U;

126  }

127 

128  AkForceInline AkUInt32 LeftChild(AkUInt32 i)

129  {

130  return (2U * i + 1U);

131  }

132 

133  AkForceInline AkUInt32 RightChild(AkUInt32 i)

134  {

135  return (2U * i + 2U);

136  }

137 };