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