1 /*
2 * Copyright (C) 2020 The Android Open Source Project
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
17 #ifndef ANDROID_MEDIA_ADJUSTABLE_MAX_PRIORITY_QUEUE_H
18 #define ANDROID_MEDIA_ADJUSTABLE_MAX_PRIORITY_QUEUE_H
19
20 #include <utils/Log.h>
21
22 #include <functional>
23 #include <iostream>
24 #include <vector>
25
26 namespace android {
27
28 /*
29 * AdjustableMaxPriorityQueue is a custom max priority queue that helps managing sessions for
30 * MediaTranscodingService.
31 *
32 * AdjustableMaxPriorityQueue is a wrapper template around the STL's *_heap() functions.
33 * - Internally, it uses a std::vector<T> to store elements in a heap order.
34 * - Support adjusting item's priority while maintaining the heap property.
35 * - Support removing any item in the heap while maintaining the heap property. Note that the
36 * removal complexity will be O(n) in worst case.
37 * - AdjustableMaxPriorityQueue needs T::operator<() at instantiation time
38 */
39 template <class T, class Comparator = std::less<T>>
40 class AdjustableMaxPriorityQueue {
41 public:
42 typedef typename std::vector<T>::iterator iterator;
43 typedef typename std::vector<T>::const_iterator const_iterator;
44
45 AdjustableMaxPriorityQueue();
46
47 /* Whether the queue is empty. */
48 bool empty() const;
49
50 /* Number of items in the queue. */
51 int size() const;
52
53 /* Return the top element in the queue. The queue still owns the element. */
54 const T& top() const;
55
56 /* Discards the element with highest value based on the given comparator. */
57 void pop();
58
59 /* Erases all the elements in the queue. */
60 void clear();
61
62 /*
63 * Returns the element with the highest value based on the given comparator. Queue transfer the
64 * ownership of the item to the caller. Client MUST call empty() to check whether there is
65 * element at the top before calling this.
66 */
67 T consume_top();
68
69 /* Adds an element to the heap. The queue will make a deep copy of the element. */
push(const T & item)70 bool push(const T& item) { return pushInternal(item); }
71
72 /* Adds an element to the heap. The queue will take ownership of the element. */
push(T && item)73 bool push(T&& item) { return pushInternal(std::move(item)); }
74
75 /* Adds a new element to the AdjustableMaxPriorityQueue. This new element is constructed in
76 * place passing args as the arguments for its constructor. */
77 template <class... Args>
78 bool emplace(Args&&... args);
79
80 /* Remove an element from a AdjustableMaxPriorityQueue. */
81 void erase(iterator pos);
82
83 /*
84 * Rebuild a heap based on the given comparator. This MUST be called after changing the value
85 * of items.
86 */
87 void rebuild();
88
89 /*
90 * Iterators used for accessing and changing the priority.
91 * If you change the value of items through these access iterators BE SURE to call rebuild() to
92 * ensure the integrity of the heap is maintained.
93 * NOTE: The iterator pos will change after calling rebuild().
94 */
95 const iterator begin();
96 const iterator end();
97
98 /*
99 * Iterators used for accessing the priority.
100 */
101 const const_iterator begin() const;
102 const const_iterator end() const;
103
104 /* Return the backbone storage of this PriorityQueue. Mainly used for debugging. */
getStorage()105 const std::vector<T>& getStorage() const { return mHeap; };
106
107 private:
108 std::vector<T> mHeap;
109
110 /* Implementation shared by both public push() methods. */
111 template <class Arg>
112 bool pushInternal(Arg&& item);
113 };
114
115 template <class T, class Comparator>
AdjustableMaxPriorityQueue()116 AdjustableMaxPriorityQueue<T, Comparator>::AdjustableMaxPriorityQueue() {}
117
118 template <class T, class Comparator>
empty()119 bool AdjustableMaxPriorityQueue<T, Comparator>::empty() const {
120 return mHeap.empty();
121 }
122
123 template <class T, class Comparator>
size()124 int AdjustableMaxPriorityQueue<T, Comparator>::size() const {
125 return mHeap.size();
126 }
127
128 template <class T, class Comparator>
top()129 const T& AdjustableMaxPriorityQueue<T, Comparator>::top() const {
130 DCHECK(!mHeap.empty());
131 return mHeap.front();
132 }
133
134 // Compares elements and potentially swaps (or moves) them until rearranged as a longer heap.
135 // Complexity of this: Up to logarithmic in the distance between first and last.
136 template <class T, class Comparator>
137 template <class Arg>
pushInternal(Arg && item)138 bool AdjustableMaxPriorityQueue<T, Comparator>::pushInternal(Arg&& item) {
139 mHeap.push_back(std::forward<Arg>(item));
140 std::push_heap(mHeap.begin(), mHeap.end(), Comparator());
141 return true;
142 }
143
144 template <class T, class Comparator>
145 template <class... Args>
emplace(Args &&...args)146 bool AdjustableMaxPriorityQueue<T, Comparator>::emplace(Args&&... args) {
147 mHeap.emplace_back(std::forward<Args>(args)...);
148 std::push_heap(mHeap.begin(), mHeap.end(), Comparator());
149 return true;
150 }
151
152 // Compares elements and potentially swaps (or moves) them until rearranged as a shorter heap.
153 // Complexity of this: Up to twice logarithmic in the distance between first and last.
154 template <class T, class Comparator>
pop()155 void AdjustableMaxPriorityQueue<T, Comparator>::pop() {
156 DCHECK(!mHeap.empty());
157 std::pop_heap(mHeap.begin(), mHeap.end(), Comparator());
158 mHeap.pop_back();
159 }
160
161 // Compares elements and potentially swaps (or moves) them until rearranged as a shorter heap.
162 // Complexity of this: Up to twice logarithmic in the distance between first and last.
163 template <class T, class Comparator>
consume_top()164 T AdjustableMaxPriorityQueue<T, Comparator>::consume_top() {
165 DCHECK(!mHeap.empty());
166 std::pop_heap(mHeap.begin(), mHeap.end(), Comparator());
167 T to_return = std::move(mHeap.back());
168 mHeap.pop_back();
169 return to_return;
170 }
171
172 template <class T, class Comparator>
173 const typename AdjustableMaxPriorityQueue<T, Comparator>::iterator
begin()174 AdjustableMaxPriorityQueue<T, Comparator>::begin() {
175 return mHeap.begin();
176 }
177
178 template <class T, class Comparator>
179 const typename AdjustableMaxPriorityQueue<T, Comparator>::iterator
end()180 AdjustableMaxPriorityQueue<T, Comparator>::end() {
181 return mHeap.end();
182 }
183
184 template <class T, class Comparator>
185 const typename AdjustableMaxPriorityQueue<T, Comparator>::const_iterator
begin()186 AdjustableMaxPriorityQueue<T, Comparator>::begin() const {
187 return mHeap.begin();
188 }
189
190 template <class T, class Comparator>
191 const typename AdjustableMaxPriorityQueue<T, Comparator>::const_iterator
end()192 AdjustableMaxPriorityQueue<T, Comparator>::end() const {
193 return mHeap.end();
194 }
195
196 template <class T, class Comparator>
clear()197 void AdjustableMaxPriorityQueue<T, Comparator>::clear() {
198 mHeap.erase(mHeap.begin(), mHeap.end());
199 }
200
201 // Complexity of this: At most 3*std::distance(first, last) comparisons.
202 template <class T, class Comparator>
rebuild()203 void AdjustableMaxPriorityQueue<T, Comparator>::rebuild() {
204 std::make_heap(mHeap.begin(), mHeap.end(), Comparator());
205 }
206
207 // Remove a random element from a AdjustableMaxPriorityQueue.
208 template <class T, class Comparator>
erase(iterator pos)209 void AdjustableMaxPriorityQueue<T, Comparator>::erase(iterator pos) {
210 DCHECK(!mHeap.empty());
211 mHeap.erase(pos);
212 rebuild();
213 }
214
215 } // namespace android
216 #endif // ANDROID_MEDIA_ADJUSTABLE_MAX_PRIORITY_QUEUE_H