1 | /** |
2 | * Copyright 2021 Alibaba, Inc. and its affiliates. All Rights Reserved. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | |
16 | * \author Hechong.xyf |
17 | * \date Jul 2018 |
18 | * \brief Interface of Heap adapter |
19 | */ |
20 | |
21 | #ifndef __AILEGO_CONTAINER_HEAP_H__ |
22 | #define __AILEGO_CONTAINER_HEAP_H__ |
23 | |
24 | #include <algorithm> |
25 | #include <functional> |
26 | #include <limits> |
27 | #include <utility> |
28 | #include <vector> |
29 | |
30 | namespace ailego { |
31 | |
32 | /*! Heap Adapter |
33 | */ |
34 | template <typename T, typename TCompare = std::less<T>, |
35 | typename TBase = std::vector<T>> |
36 | class Heap : public TBase { |
37 | public: |
38 | //! Constructor |
39 | Heap(void) |
40 | : TBase(), limit_(std::numeric_limits<size_t>::max()), compare_() {} |
41 | |
42 | //! Constructor |
43 | Heap(size_t max) : TBase(), limit_(std::max<size_t>(max, 1u)), compare_() { |
44 | TBase::reserve(limit_); |
45 | } |
46 | |
47 | //! Constructor |
48 | Heap(const Heap &rhs) : TBase(rhs), limit_(rhs.limit_), compare_() {} |
49 | |
50 | //! Constructor |
51 | Heap(Heap &&rhs) : TBase(std::move(rhs)), limit_(rhs.limit_), compare_() {} |
52 | |
53 | //! Constructor |
54 | Heap(const TBase &rhs) |
55 | : TBase(rhs), limit_(std::numeric_limits<size_t>::max()), compare_() { |
56 | std::make_heap(TBase::begin(), TBase::end(), compare_); |
57 | } |
58 | |
59 | //! Constructor |
60 | Heap(TBase &&rhs) |
61 | : TBase(std::move(rhs)), |
62 | limit_(std::numeric_limits<size_t>::max()), |
63 | compare_() { |
64 | std::make_heap(TBase::begin(), TBase::end(), compare_); |
65 | } |
66 | |
67 | //! Assignment |
68 | Heap &operator=(const Heap &rhs) { |
69 | TBase::operator=(static_cast<const TBase &>(rhs)); |
70 | limit_ = rhs.limit_; |
71 | return *this; |
72 | } |
73 | |
74 | //! Assignment |
75 | Heap &operator=(Heap &&rhs) { |
76 | TBase::operator=(std::move(static_cast<TBase &&>(rhs))); |
77 | limit_ = rhs.limit_; |
78 | return *this; |
79 | } |
80 | |
81 | //! Exchange the content |
82 | void swap(Heap &rhs) { |
83 | TBase::swap(static_cast<TBase &>(rhs)); |
84 | std::swap(limit_, rhs.limit_); |
85 | } |
86 | |
87 | //! Pop the front element |
88 | void pop(void) { |
89 | if (TBase::size() > 1) { |
90 | auto last = TBase::end() - 1; |
91 | this->replace_heap(TBase::begin(), last, std::move(*last)); |
92 | } |
93 | TBase::pop_back(); |
94 | } |
95 | |
96 | //! Insert a new element into the heap |
97 | template <class... TArgs> |
98 | void emplace(TArgs &&...args) { |
99 | if (this->full()) { |
100 | typename std::remove_reference<T>::type val(std::forward<TArgs>(args)...); |
101 | |
102 | auto first = TBase::begin(); |
103 | if (compare_(val, *first)) { |
104 | this->replace_heap(first, TBase::end(), std::move(val)); |
105 | } |
106 | } else { |
107 | TBase::emplace_back(std::forward<TArgs>(args)...); |
108 | std::push_heap(TBase::begin(), TBase::end(), compare_); |
109 | } |
110 | } |
111 | |
112 | //! Insert a new element into the heap |
113 | void push(const T &val) { |
114 | if (this->full()) { |
115 | auto first = TBase::begin(); |
116 | if (compare_(val, *first)) { |
117 | this->replace_heap(first, TBase::end(), val); |
118 | } |
119 | } else { |
120 | TBase::push_back(val); |
121 | std::push_heap(TBase::begin(), TBase::end(), compare_); |
122 | } |
123 | } |
124 | |
125 | //! Insert a new element into the heap |
126 | void push(T &&val) { |
127 | if (this->full()) { |
128 | auto first = TBase::begin(); |
129 | if (compare_(val, *first)) { |
130 | this->replace_heap(first, TBase::end(), std::move(val)); |
131 | } |
132 | } else { |
133 | TBase::push_back(std::move(val)); |
134 | std::push_heap(TBase::begin(), TBase::end(), compare_); |
135 | } |
136 | } |
137 | |
138 | //! Retrieve the limit of heap |
139 | size_t limit(void) const { |
140 | return limit_; |
141 | } |
142 | |
143 | //! Limit the heap with max size |
144 | void limit(size_t max) { |
145 | limit_ = std::max<size_t>(max, 1u); |
146 | TBase::reserve(limit_); |
147 | } |
148 | |
149 | //! Unlimit the size of heap |
150 | void unlimit(void) { |
151 | limit_ = std::numeric_limits<size_t>::max(); |
152 | } |
153 | |
154 | //! Check whether the heap is full |
155 | bool full(void) const { |
156 | return (TBase::size() == limit_); |
157 | } |
158 | |
159 | //! Update the heap |
160 | void update(void) { |
161 | std::make_heap(TBase::begin(), TBase::end(), compare_); |
162 | while (limit_ < TBase::size()) { |
163 | this->pop(); |
164 | } |
165 | } |
166 | |
167 | //! Sort the elements in the heap |
168 | void sort(void) { |
169 | std::sort(TBase::begin(), TBase::end(), compare_); |
170 | } |
171 | |
172 | protected: |
173 | //! Replace the top element of heap |
174 | template <typename TRandomIterator, typename TValue> |
175 | void replace_heap(TRandomIterator first, TRandomIterator last, TValue &&val) { |
176 | using _DistanceType = |
177 | typename std::iterator_traits<TRandomIterator>::difference_type; |
178 | |
179 | _DistanceType hole = 0; |
180 | _DistanceType count = _DistanceType(last - first); |
181 | |
182 | if (count > 1) { |
183 | _DistanceType child = (hole << 1) + 1; |
184 | |
185 | while (child < count) { |
186 | _DistanceType right_child = child + 1; |
187 | |
188 | if (right_child < count && |
189 | compare_(*(first + child), *(first + right_child))) { |
190 | child = right_child; |
191 | } |
192 | if (!compare_(val, *(first + child))) { |
193 | break; |
194 | } |
195 | *(first + hole) = std::move(*(first + child)); |
196 | hole = child; |
197 | child = (hole << 1) + 1; |
198 | } |
199 | } |
200 | *(first + hole) = std::forward<TValue>(val); |
201 | } |
202 | |
203 | private: |
204 | size_t limit_; |
205 | TCompare compare_; |
206 | }; |
207 | |
208 | /*! Key Value Heap Comparer |
209 | */ |
210 | template <typename TKey, typename TValue, typename TCompare = std::less<TValue>> |
211 | struct KeyValueHeapComparer { |
212 | //! Function call |
213 | bool operator()(const std::pair<TKey, TValue> &lhs, |
214 | const std::pair<TKey, TValue> &rhs) const { |
215 | return compare_(lhs.second, rhs.second); |
216 | } |
217 | |
218 | private: |
219 | TCompare compare_; |
220 | }; |
221 | |
222 | /*! Key Value Heap |
223 | */ |
224 | template <typename TKey, typename TValue, typename TCompare = std::less<TValue>> |
225 | using KeyValueHeap = |
226 | Heap<std::pair<TKey, TValue>, KeyValueHeapComparer<TKey, TValue, TCompare>>; |
227 | |
228 | } // namespace ailego |
229 | |
230 | #endif //__AILEGO_CONTAINER_HEAP_H__ |
231 | |