14 #ifndef OR_TOOLS_BASE_ADJUSTABLE_PRIORITY_QUEUE_H_
15 #define OR_TOOLS_BASE_ADJUSTABLE_PRIORITY_QUEUE_H_
27 template <
typename T,
typename Comparator>
37 template <
typename T,
typename Comp = std::less<T> >
52 elems_.push_back(val);
53 AdjustUpwards(elems_.size() - 1);
57 int end = elems_.size() - 1;
58 int i = val->GetHeapIndex();
63 elems_[i] = elems_[end];
64 elems_[i]->SetHeapIndex(i);
70 int i = val->GetHeapIndex();
71 return (i >= 0 && i < elems_.size() && elems_[i] == val);
76 int i = val->GetHeapIndex();
77 int parent = (i - 1) / 2;
78 if (lower_priority(elems_[parent], val)) {
87 T*
Top() {
return elems_[0]; }
89 const T*
Top()
const {
return elems_[0]; }
91 void AllTop(std::vector<T*>* topvec) {
93 if (
Size() == 0)
return;
94 std::list<int> need_to_check_children;
95 need_to_check_children.push_back(0);
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()) {
105 need_to_check_children.push_back(leftchild);
107 int rightchild = leftchild + 1;
108 if (rightchild <
Size() &&
110 need_to_check_children.push_back(rightchild);
119 int Size()
const {
return elems_.size(); }
127 bool IsEmpty()
const {
return elems_.empty(); }
134 for (
int i = 0; i < elems_.size(); ++i) {
135 int left_child = 1 + 2 * i;
136 if (left_child < elems_.size()) {
140 int right_child = left_child + 1;
141 if (right_child < elems_.size()) {
151 const std::vector<T*>*
Raw()
const {
return &elems_; }
154 void AdjustUpwards(
int i) {
155 T*
const t = elems_[i];
157 const int parent = (i - 1) / 2;
158 if (!c_(*elems_[parent], *t)) {
161 elems_[i] = elems_[parent];
162 elems_[i]->SetHeapIndex(i);
169 void AdjustDownwards(
int i) {
170 T*
const t = elems_[i];
172 const int left_child = 1 + 2 * i;
173 if (left_child >= elems_.size()) {
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]))
181 if (!c_(*t, *elems_[next_i])) {
184 elems_[i] = elems_[next_i];
185 elems_[i]->SetHeapIndex(i);
193 std::vector<T*> elems_;
AdjustablePriorityQueue()
AdjustablePriorityQueue & operator=(const AdjustablePriorityQueue &)=delete
const std::vector< T * > * Raw() const
void NoteChangedPriority(T *val)
void SetCapacity(size_t c)
AdjustablePriorityQueue(const Comp &c)
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)