OR-Tools  8.2
adjustable_priority_queue.h
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 #ifndef OR_TOOLS_BASE_ADJUSTABLE_PRIORITY_QUEUE_H_
15 #define OR_TOOLS_BASE_ADJUSTABLE_PRIORITY_QUEUE_H_
16 
17 #include <stddef.h>
18 
19 #include <functional>
20 #include <list>
21 #include <vector>
22 
24 #include "ortools/base/logging.h"
25 #include "ortools/base/macros.h"
26 
27 template <typename T, typename Comparator>
29  public:
30  explicit LowerPriorityThan(Comparator* compare) : compare_(compare) {}
31  bool operator()(T* a, T* b) const { return (*compare_)(*a, *b); }
32 
33  private:
34  Comparator* compare_;
35 };
36 
37 template <typename T, typename Comp = std::less<T> >
39  public:
40  // The objects references 'c' and 'm' are not required to be alive for the
41  // lifetime of this object.
43  AdjustablePriorityQueue(const Comp& c) : c_(c) {}
48 
49  void Add(T* val) {
50  // Extend the size of the vector by one. We could just use
51  // vector<T>::resize(), but maybe T is not default-constructible.
52  elems_.push_back(val);
53  AdjustUpwards(elems_.size() - 1);
54  }
55 
56  void Remove(T* val) {
57  int end = elems_.size() - 1;
58  int i = val->GetHeapIndex();
59  if (i == end) {
60  elems_.pop_back();
61  return;
62  }
63  elems_[i] = elems_[end];
64  elems_[i]->SetHeapIndex(i);
65  elems_.pop_back();
66  NoteChangedPriority(elems_[i]);
67  }
68 
69  bool Contains(const T* val) const {
70  int i = val->GetHeapIndex();
71  return (i >= 0 && i < elems_.size() && elems_[i] == val);
72  }
73 
74  void NoteChangedPriority(T* val) {
75  LowerPriorityThan<T, Comp> lower_priority(&c_);
76  int i = val->GetHeapIndex();
77  int parent = (i - 1) / 2;
78  if (lower_priority(elems_[parent], val)) {
79  AdjustUpwards(i);
80  } else {
81  AdjustDownwards(i);
82  }
83  }
84  // If val ever changes its priority, you need to call this function
85  // to notify the pq so it can move it in the heap accordingly.
86 
87  T* Top() { return elems_[0]; }
88 
89  const T* Top() const { return elems_[0]; }
90 
91  void AllTop(std::vector<T*>* topvec) {
92  topvec->clear();
93  if (Size() == 0) return;
94  std::list<int> need_to_check_children;
95  need_to_check_children.push_back(0);
96  // Implements breadth-first search down tree, stopping whenever
97  // there's an element < top
98  while (!need_to_check_children.empty()) {
99  int ind = need_to_check_children.front();
100  need_to_check_children.pop_front();
101  topvec->push_back(elems_[ind]);
102  int leftchild = 1 + 2 * ind;
103  if (leftchild < Size()) {
104  if (!LowerPriorityThan<T, Comp>(&c_)(elems_[leftchild], elems_[ind])) {
105  need_to_check_children.push_back(leftchild);
106  }
107  int rightchild = leftchild + 1;
108  if (rightchild < Size() &&
109  !LowerPriorityThan<T, Comp>(&c_)(elems_[rightchild], elems_[ind])) {
110  need_to_check_children.push_back(rightchild);
111  }
112  }
113  }
114  }
115  // If there are ties for the top, this returns all of them.
116 
117  void Pop() { Remove(Top()); }
118 
119  int Size() const { return elems_.size(); }
120 
121  // Returns the number of elements for which storage has been allocated.
122  int Capacity() const { return elems_.capacity(); }
123 
124  // Allocates storage for a given number of elements.
125  void SetCapacity(size_t c) { elems_.reserve(c); }
126 
127  bool IsEmpty() const { return elems_.empty(); }
128 
129  void Clear() { elems_.clear(); }
130 
131  // CHECKs that the heap is actually a heap (each "parent" of >=
132  // priority than its child).
133  void CheckValid() {
134  for (int i = 0; i < elems_.size(); ++i) {
135  int left_child = 1 + 2 * i;
136  if (left_child < elems_.size()) {
137  CHECK(
138  !(LowerPriorityThan<T, Comp>(&c_))(elems_[i], elems_[left_child]));
139  }
140  int right_child = left_child + 1;
141  if (right_child < elems_.size()) {
142  CHECK(
143  !(LowerPriorityThan<T, Comp>(&c_))(elems_[i], elems_[right_child]));
144  }
145  }
146  }
147 
148  // This is for debugging, e.g. the caller can use it to
149  // examine the heap for rationality w.r.t. other parts of the
150  // program.
151  const std::vector<T*>* Raw() const { return &elems_; }
152 
153  private:
154  void AdjustUpwards(int i) {
155  T* const t = elems_[i];
156  while (i > 0) {
157  const int parent = (i - 1) / 2;
158  if (!c_(*elems_[parent], *t)) {
159  break;
160  }
161  elems_[i] = elems_[parent];
162  elems_[i]->SetHeapIndex(i);
163  i = parent;
164  }
165  elems_[i] = t;
166  t->SetHeapIndex(i);
167  }
168 
169  void AdjustDownwards(int i) {
170  T* const t = elems_[i];
171  while (true) {
172  const int left_child = 1 + 2 * i;
173  if (left_child >= elems_.size()) {
174  break;
175  }
176  const int right_child = left_child + 1;
177  const int next_i = (right_child < elems_.size() &&
178  c_(*elems_[left_child], *elems_[right_child]))
179  ? right_child
180  : left_child;
181  if (!c_(*t, *elems_[next_i])) {
182  break;
183  }
184  elems_[i] = elems_[next_i];
185  elems_[i]->SetHeapIndex(i);
186  i = next_i;
187  }
188  elems_[i] = t;
189  t->SetHeapIndex(i);
190  }
191 
192  Comp c_;
193  std::vector<T*> elems_;
194 };
195 
196 #endif // OR_TOOLS_BASE_ADJUSTABLE_PRIORITY_QUEUE_H_
#define CHECK(condition)
Definition: base/logging.h:495
AdjustablePriorityQueue & operator=(const AdjustablePriorityQueue &)=delete
const std::vector< T * > * Raw() const
bool Contains(const T *val) const
AdjustablePriorityQueue & operator=(AdjustablePriorityQueue &&)=default
void AllTop(std::vector< T * > *topvec)
AdjustablePriorityQueue(const AdjustablePriorityQueue &)=delete
AdjustablePriorityQueue(AdjustablePriorityQueue &&)=default
bool operator()(T *a, T *b) const
LowerPriorityThan(Comparator *compare)