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