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
30namespace ailego {
31
32/*! Heap Adapter
33 */
34template <typename T, typename TCompare = std::less<T>,
35 typename TBase = std::vector<T>>
36class 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 */
210template <typename TKey, typename TValue, typename TCompare = std::less<TValue>>
211struct 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 */
224template <typename TKey, typename TValue, typename TCompare = std::less<TValue>>
225using KeyValueHeap =
226 Heap<std::pair<TKey, TValue>, KeyValueHeapComparer<TKey, TValue, TCompare>>;
227
228} // namespace ailego
229
230#endif //__AILEGO_CONTAINER_HEAP_H__
231