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