priority_queue.h revision fa589941fe8c8aa1ff0d8fb9ee1445dba6382768 
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 CompareType.
31 */
32template<typename ElementType, typename CompareType = 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 CompareType& 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 Returns 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
72   * resize and that allocation fails, this function will return false.
73   *
74   * @param element The element to push onto the queue.
75   * @return Returns true if the element was pushed successfully.
76   */
77  bool push(const ElementType& element);
78
79  /**
80   * Constructs an element onto the the queue.
81   *
82   * @param args The arguments to the constructor of ElementType
83   */
84  template<typename... Args>
85  bool emplace(Args&&... args);
86
87  /*
88   * Obtains a const element of the queue given an index. It is illegal to
89   * index this queue out of bounds and the user of the API must check the
90   * size() function prior to indexing this queue to ensure that they will not
91   * read out of bounds. It returns the top element with index equal to 0 when
92   * the queue is not empty, and there is no guarantee for index > 0.
93   *
94   * @param index The index of the element.
95   * @return The element.
96   */
97  ElementType& operator[](size_t index);
98
99  /*
100   * Obtains a const element of the queue given an index. It is illegal to
101   * index this queue out of bounds and the user of the API must check the
102   * size() function prior to indexing this queye to ensure that they will not
103   * read out of bounds. It returns the top element with index equal to 0 when
104   * the queue is not empty, and there is no guarantee for index > 0.
105   *
106   * @param index The index of the element.
107   * @return The element.
108   */
109  const ElementType& operator[](size_t index) const;
110
111  /**
112   * Obtains the top element of the queue. It is illegal to do this when the
113   * queue is empty. The user of the API must check the size() or empty()
114   * function prior to calling this to ensure that they will not
115   * read out of bounds.
116   *
117   * @return The element.
118   */
119  ElementType& top();
120
121  /**
122   * Obtains the top element of the queue. It is illegal to do this when the
123   * queue is empty. The user of the API must check the size() or empty()
124   * function prior to calling this to ensure that they will not
125   * read out of bounds.
126   *
127   * @return The element.
128   */
129  const ElementType& top() const;
130
131  /**
132   * Removes the top element from the queue if the queue is not empty.
133   */
134  void pop();
135
136  /**
137   * Removes an element from the queue given an index. The index passed in must
138   * be less than the size() of the queue. If the index is greater than or
139   * equal to the size no operation is performed.
140   *
141   * @param index The index to remove an element at.
142   */
143  void remove(size_t index);
144
145 private:
146  //! The dynamic vector that serves as the underlying container.
147  DynamicVector<ElementType> mData;
148
149  //! The comparator that is used to order the queue.
150  CompareType mCompare;
151};
152
153}  // namespace chre
154
155#include "chre/util/priority_queue_impl.h"
156
157#endif  // CHRE_UTIL_PRIORITY_QUEUE_H_
158