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_H_ 18 #define CHRE_UTIL_PRIORITY_QUEUE_H_ 19 20 #include <cstddef> 21 #include <functional> 22 23 #include "chre/util/dynamic_vector.h" 24 #include "chre/util/non_copyable.h" 25 26 namespace chre { 27 28 /** 29 * An implementation of a priority queue. This allows for efficient lookup of 30 * the highest priority element as defined by the CompareFunction. 31 */ 32 template<typename ElementType, typename CompareFunction = std::less<ElementType>> 33 class PriorityQueue : public NonCopyable { 34 public: 35 /** 36 * Constructs the object. 37 */ 38 PriorityQueue(); 39 40 /** 41 * Constructs the object with a compare type that provides a strict weak 42 * ordering. 43 * 44 * @param compare The comparator that returns true if left < right. 45 */ 46 PriorityQueue(const CompareFunction& compare); 47 48 /** 49 * Returns the current number of elements in the queue. 50 * 51 * @return The number of elements in the queue. 52 */ 53 size_t size() const; 54 55 /** 56 * Returns the maximum number of elements that can be stored in this queue 57 * without a resize operation. 58 * 59 * @return The capacity of the queue. 60 */ 61 size_t capacity() const; 62 63 /** 64 * Determines whether the queue is empty or not. 65 * 66 * @return true if the queue is empty. 67 */ 68 bool empty() const; 69 70 /** 71 * Pushes an element onto the queue. If the queue requires a resize and that 72 * allocation fails, this function will return false. All iterators and 73 * references are invalidated. 74 * 75 * @param element The element to push onto the queue. 76 * @return true if the element was pushed successfully. 77 */ 78 bool push(const ElementType& element); 79 80 /** 81 * Constructs an element onto the the queue. All iterators and references are 82 * invalidated. 83 * 84 * @param args The arguments to the constructor of ElementType 85 */ 86 template<typename... Args> 87 bool emplace(Args&&... args); 88 89 /* 90 * Obtains a const element of the queue given an index. It is illegal to 91 * index this queue out of bounds and the user of the API must check the 92 * size() function prior to indexing this queue to ensure that they will not 93 * read out of bounds. It returns the top element with index equal to 0 when 94 * the queue is not empty, and there is no guarantee for index > 0. 95 * 96 * @param index The index of the element. 97 * @return The element. 98 */ 99 ElementType& operator[](size_t index); 100 101 /* 102 * Obtains a const element of the queue given an index. It is illegal to 103 * index this queue out of bounds and the user of the API must check the 104 * size() function prior to indexing this queye to ensure that they will not 105 * read out of bounds. It returns the top element with index equal to 0 when 106 * the queue is not empty, and there is no guarantee for index > 0. 107 * 108 * @param index The index of the element. 109 * @return The element. 110 */ 111 const ElementType& operator[](size_t index) const; 112 113 /** 114 * Obtains the top element of the queue. It is illegal to do this when the 115 * queue is empty. The user of the API must check the size() or empty() 116 * function prior to calling this to ensure that they will not 117 * read out of bounds. 118 * 119 * @return The element. 120 */ 121 ElementType& top(); 122 123 /** 124 * Obtains the top element of the queue. It is illegal to do this when the 125 * queue is empty. The user of the API must check the size() or empty() 126 * function prior to calling this to ensure that they will not 127 * read out of bounds. 128 * 129 * @return The element. 130 */ 131 const ElementType& top() const; 132 133 /** 134 * Removes the top element from the queue if the queue is not empty. All 135 * iterators and references are invalidated. 136 */ 137 void pop(); 138 139 /** 140 * Removes an element from the queue given an index. The index passed in must 141 * be less than the size() of the queue. If the index is greater than or 142 * equal to the size no operation is performed. All iterators and references 143 * are invalidated. 144 * 145 * @param index The index to remove an element at. 146 */ 147 void remove(size_t index); 148 149 /** 150 * Random-access iterator that points to some element in the container. 151 */ 152 typedef ElementType* iterator; 153 typedef const ElementType* const_iterator; 154 155 /** 156 * @return A random-access iterator to the beginning. 157 */ 158 typename PriorityQueue<ElementType, CompareFunction>::iterator begin(); 159 typename PriorityQueue<ElementType, CompareFunction>::const_iterator begin() const; 160 typename PriorityQueue<ElementType, CompareFunction>::const_iterator cbegin() const; 161 162 /** 163 * @return A random-access iterator to the end. 164 */ 165 typename PriorityQueue<ElementType, CompareFunction>::iterator end(); 166 typename PriorityQueue<ElementType, CompareFunction>::const_iterator end() const; 167 typename PriorityQueue<ElementType, CompareFunction>::const_iterator cend() const; 168 169 170 private: 171 //! The dynamic vector that serves as the underlying container. 172 DynamicVector<ElementType> mData; 173 174 //! The comparator that is used to order the queue. 175 CompareFunction mCompare; 176 }; 177 178 } // namespace chre 179 180 #include "chre/util/priority_queue_impl.h" 181 182 #endif // CHRE_UTIL_PRIORITY_QUEUE_H_ 183