priority_queue_impl.h revision f9fe99d728ad476dc941be5a9dff1e20402c3754 
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
25namespace chre {
26
27template<typename ElementType, typename CompareType>
28PriorityQueue<ElementType, CompareType>::PriorityQueue() {}
29
30template<typename ElementType, typename CompareType>
31PriorityQueue<ElementType, CompareType>::PriorityQueue(const CompareType& compare)
32    : mCompare(compare) {}
33
34template<typename ElementType, typename CompareType>
35size_t PriorityQueue<ElementType, CompareType>::size() const {
36  return mData.size();
37}
38
39template<typename ElementType, typename CompareType>
40size_t PriorityQueue<ElementType, CompareType>::capacity() const {
41  return mData.capacity();
42}
43
44template<typename ElementType, typename CompareType>
45bool PriorityQueue<ElementType, CompareType>::empty() const {
46  return mData.empty();
47}
48
49template<typename ElementType, typename CompareType>
50bool PriorityQueue<ElementType, CompareType>::push(const ElementType& element) {
51  bool success = mData.push_back(element);
52  if (success) {
53    // TODO: replace by push_heap()
54    arrangeQueue();
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    // TODO: replace by push_heap()
65    arrangeQueue();
66  }
67  return success;
68}
69
70template<typename ElementType, typename CompareType>
71ElementType& PriorityQueue<ElementType, CompareType>::operator[](size_t index) {
72  return mData[index];
73}
74
75template<typename ElementType, typename CompareType>
76const ElementType& PriorityQueue<ElementType, CompareType>::operator[](size_t index) const {
77  return mData[index];
78}
79
80template<typename ElementType, typename CompareType>
81ElementType& PriorityQueue<ElementType, CompareType>::top() {
82  return mData[0];
83}
84
85template<typename ElementType, typename CompareType>
86const ElementType& PriorityQueue<ElementType, CompareType>::top() const {
87  return mData[0];
88}
89
90template<typename ElementType, typename CompareType>
91void PriorityQueue<ElementType, CompareType>::pop() {
92  if (mData.size() > 0) {
93    // TODO: replace by pop_heap() & mData.erase(mData.size() - 1)
94    remove(0);
95  }
96}
97
98template<typename ElementType, typename CompareType>
99void PriorityQueue<ElementType, CompareType>::remove(size_t index) {
100  // TODO: replace by erase_heap(index) & mData.erase(mData.size() - 1)
101  mData.erase(index);
102
103  // TODO: consider resizing the dynamic array to mData.capacity()/2
104  // when mData.size() <= mData.capacity()/4.
105}
106
107template<typename ElementType, typename CompareType>
108void PriorityQueue<ElementType, CompareType>::arrangeQueue() {
109  // Search for the index where the newly added element should be,
110  // assuming that element is at the end of the dynamic vector.
111  for (size_t i = 0; i < mData.size() - 1; ++i) {
112    if (mCompare(mData[i], mData[mData.size() - 1])) {
113      // This is not the most efficient way even for a linear array,
114      // but just something to make it work till heap is ready.
115      ElementType e = mData[mData.size() - 1];
116      mData.erase(mData.size() - 1);
117      mData.insert(i, e);
118      break;
119    }
120  }
121}
122}  // namespace chre
123
124#endif  // CHRE_UTIL_PRIORITY_QUEUE_IMPL_H_
125