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
25#include "ortools/base/macros.h"
26
27template <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
37template <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
const std::vector< T * > * Raw() const
AdjustablePriorityQueue & operator=(const AdjustablePriorityQueue &)=delete
bool Contains(const T *val) const
void AllTop(std::vector< T * > *topvec)
AdjustablePriorityQueue(const AdjustablePriorityQueue &)=delete
AdjustablePriorityQueue(AdjustablePriorityQueue &&)=default
AdjustablePriorityQueue & operator=(AdjustablePriorityQueue &&)=default
bool operator()(T *a, T *b) const
LowerPriorityThan(Comparator *compare)