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