1 /*
2 * Copyright (C) 2016 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 CHRE_UTIL_PRIORITY_QUEUE_IMPL_H_
18 #define CHRE_UTIL_PRIORITY_QUEUE_IMPL_H_
19
20 // IWYU pragma: private
21 #include "chre/util/priority_queue.h"
22
23 #include <utility>
24
25 #include "chre/platform/assert.h"
26 #include "chre/util/dynamic_vector.h"
27 #include "chre/util/heap.h"
28
29 namespace chre {
30
31 template <typename ElementType, typename CompareFunction>
PriorityQueue()32 PriorityQueue<ElementType, CompareFunction>::PriorityQueue() {}
33
34 template <typename ElementType, typename CompareFunction>
PriorityQueue(const CompareFunction & compare)35 PriorityQueue<ElementType, CompareFunction>::PriorityQueue(
36 const CompareFunction &compare)
37 : mCompare(compare) {}
38
39 template <typename ElementType, typename CompareFunction>
size()40 size_t PriorityQueue<ElementType, CompareFunction>::size() const {
41 return mData.size();
42 }
43
44 template <typename ElementType, typename CompareFunction>
capacity()45 size_t PriorityQueue<ElementType, CompareFunction>::capacity() const {
46 return mData.capacity();
47 }
48
49 template <typename ElementType, typename CompareFunction>
empty()50 bool PriorityQueue<ElementType, CompareFunction>::empty() const {
51 return mData.empty();
52 }
53
54 template <typename ElementType, typename CompareFunction>
push(const ElementType & element)55 bool PriorityQueue<ElementType, CompareFunction>::push(
56 const ElementType &element) {
57 bool success = mData.push_back(element);
58 if (success) {
59 push_heap(mData, mCompare);
60 }
61 return success;
62 }
63
64 template <typename ElementType, typename CompareFunction>
65 template <typename... Args>
emplace(Args &&...args)66 bool PriorityQueue<ElementType, CompareFunction>::emplace(Args &&... args) {
67 bool success = mData.emplace_back(args...);
68 if (success) {
69 push_heap(mData, mCompare);
70 }
71 return success;
72 }
73
74 template <typename ElementType, typename CompareFunction>
75 ElementType &PriorityQueue<ElementType, CompareFunction>::operator[](
76 size_t index) {
77 return mData[index];
78 }
79
80 template <typename ElementType, typename CompareFunction>
81 const ElementType &PriorityQueue<ElementType, CompareFunction>::operator[](
82 size_t index) const {
83 return mData[index];
84 }
85
86 template <typename ElementType, typename CompareFunction>
top()87 ElementType &PriorityQueue<ElementType, CompareFunction>::top() {
88 return mData[0];
89 }
90
91 template <typename ElementType, typename CompareFunction>
top()92 const ElementType &PriorityQueue<ElementType, CompareFunction>::top() const {
93 return mData[0];
94 }
95
96 template <typename ElementType, typename CompareFunction>
pop()97 void PriorityQueue<ElementType, CompareFunction>::pop() {
98 if (mData.size() > 0) {
99 pop_heap(mData, mCompare);
100 mData.erase(mData.size() - 1);
101 }
102 }
103
104 template <typename ElementType, typename CompareFunction>
remove(size_t index)105 void PriorityQueue<ElementType, CompareFunction>::remove(size_t index) {
106 CHRE_ASSERT(index < mData.size());
107 if (index < mData.size()) {
108 remove_heap(mData, index, mCompare);
109 mData.erase(mData.size() - 1);
110 }
111
112 // TODO: consider resizing the dynamic array to mData.capacity()/2
113 // when mData.size() <= mData.capacity()/4.
114 }
115
116 template <typename ElementType, typename CompareFunction>
117 typename PriorityQueue<ElementType, CompareFunction>::iterator
begin()118 PriorityQueue<ElementType, CompareFunction>::begin() {
119 return mData.begin();
120 }
121
122 template <typename ElementType, typename CompareFunction>
123 typename PriorityQueue<ElementType, CompareFunction>::iterator
end()124 PriorityQueue<ElementType, CompareFunction>::end() {
125 return mData.end();
126 }
127
128 template <typename ElementType, typename CompareFunction>
129 typename PriorityQueue<ElementType, CompareFunction>::const_iterator
begin()130 PriorityQueue<ElementType, CompareFunction>::begin() const {
131 return cbegin();
132 }
133
134 template <typename ElementType, typename CompareFunction>
135 typename PriorityQueue<ElementType, CompareFunction>::const_iterator
end()136 PriorityQueue<ElementType, CompareFunction>::end() const {
137 return cend();
138 }
139
140 template <typename ElementType, typename CompareFunction>
141 typename PriorityQueue<ElementType, CompareFunction>::const_iterator
cbegin()142 PriorityQueue<ElementType, CompareFunction>::cbegin() const {
143 return mData.cbegin();
144 }
145
146 template <typename ElementType, typename CompareFunction>
147 typename PriorityQueue<ElementType, CompareFunction>::const_iterator
cend()148 PriorityQueue<ElementType, CompareFunction>::cend() const {
149 return mData.cend();
150 }
151
152 } // namespace chre
153
154 #endif // CHRE_UTIL_PRIORITY_QUEUE_IMPL_H_
155