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