priority_queue_impl.h revision 48080e341c2a12db12deb086adce1d487a759141 
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
26namespace chre {
27
28template<typename ElementType, typename CompareFunction>
29PriorityQueue<ElementType, CompareFunction>::PriorityQueue() {}
30
31template<typename ElementType, typename CompareFunction>
32PriorityQueue<ElementType, CompareFunction>::PriorityQueue(
33    const CompareFunction& compare)
34    : mCompare(compare) {}
35
36template<typename ElementType, typename CompareFunction>
37size_t PriorityQueue<ElementType, CompareFunction>::size() const {
38  return mData.size();
39}
40
41template<typename ElementType, typename CompareFunction>
42size_t PriorityQueue<ElementType, CompareFunction>::capacity() const {
43  return mData.capacity();
44}
45
46template<typename ElementType, typename CompareFunction>
47bool PriorityQueue<ElementType, CompareFunction>::empty() const {
48  return mData.empty();
49}
50
51template<typename ElementType, typename CompareFunction>
52bool 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
61template<typename ElementType, typename CompareFunction>
62template<typename... Args>
63bool 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
71template<typename ElementType, typename CompareFunction>
72ElementType& PriorityQueue<ElementType, CompareFunction>::operator[](
73    size_t index) {
74  return mData[index];
75}
76
77template<typename ElementType, typename CompareFunction>
78const ElementType& PriorityQueue<ElementType, CompareFunction>::operator[](
79    size_t index) const {
80  return mData[index];
81}
82
83template<typename ElementType, typename CompareFunction>
84ElementType& PriorityQueue<ElementType, CompareFunction>::top() {
85  return mData[0];
86}
87
88template<typename ElementType, typename CompareFunction>
89const ElementType& PriorityQueue<ElementType, CompareFunction>::top() const {
90  return mData[0];
91}
92
93template<typename ElementType, typename CompareFunction>
94void PriorityQueue<ElementType, CompareFunction>::pop() {
95  if (mData.size() > 0) {
96    pop_heap(mData, mCompare);
97    mData.erase(mData.size() - 1);
98  }
99}
100
101template<typename ElementType, typename CompareFunction>
102void 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
113template<typename ElementType, typename CompareFunction>
114typename PriorityQueue<ElementType, CompareFunction>::iterator
115    PriorityQueue<ElementType, CompareFunction>::begin() {
116  return mData.begin();
117}
118
119template<typename ElementType, typename CompareFunction>
120typename PriorityQueue<ElementType, CompareFunction>::iterator
121    PriorityQueue<ElementType, CompareFunction>::end() {
122  return mData.end();
123}
124
125template<typename ElementType, typename CompareFunction>
126typename PriorityQueue<ElementType, CompareFunction>::const_iterator
127    PriorityQueue<ElementType, CompareFunction>::begin() const {
128  return cbegin();
129}
130
131template<typename ElementType, typename CompareFunction>
132typename PriorityQueue<ElementType, CompareFunction>::const_iterator
133    PriorityQueue<ElementType, CompareFunction>::end() const {
134  return cend();
135}
136
137template<typename ElementType, typename CompareFunction>
138typename PriorityQueue<ElementType, CompareFunction>::const_iterator
139    PriorityQueue<ElementType, CompareFunction>::cbegin() const {
140  return mData.cbegin();
141}
142
143template<typename ElementType, typename CompareFunction>
144typename PriorityQueue<ElementType, CompareFunction>::const_iterator
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