priority_queue.h revision 5ea6fa358541d4b9cc1d9856a0b9291785d7536d 
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
26namespace 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 */
32template<typename ElementType, typename CompareFunction = std::less<ElementType>>
33class 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 cbegin() const;
160
161  /**
162   * @return A random-access iterator to the end.
163   */
164  typename PriorityQueue<ElementType, CompareFunction>::iterator end();
165  typename PriorityQueue<ElementType, CompareFunction>::const_iterator cend() const;
166
167
168 private:
169  //! The dynamic vector that serves as the underlying container.
170  DynamicVector<ElementType> mData;
171
172  //! The comparator that is used to order the queue.
173  CompareFunction mCompare;
174};
175
176}  // namespace chre
177
178#include "chre/util/priority_queue_impl.h"
179
180#endif  // CHRE_UTIL_PRIORITY_QUEUE_H_
181