00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014 #include <functional>
00015 #include <list>
00016 #include <vector>
00017 #include "base/basictypes.h"
00018 #include "base/logging.h"
00019 #include "base/macros.h"
00020
00021 #ifndef OR_TOOLS_BASE_ADJUSTABLE_PRIORITY_QUEUE_H_
00022 #define OR_TOOLS_BASE_ADJUSTABLE_PRIORITY_QUEUE_H_
00023
00024 namespace operations_research {
00025
00026 template<typename T> class AdjustablePriorityQueue {
00027 public:
00028
00029 AdjustablePriorityQueue() {}
00030
00031 void Add(T* const val) {
00032 elems_.push_back(val);
00033 AdjustUpwards(elems_.size() - 1);
00034 }
00035
00036 void Remove(T* const val) {
00037 const int i = val->GetHeapIndex();
00038 if (i == elems_.size() - 1) {
00039 elems_.pop_back();
00040 return;
00041 }
00042 elems_[i] = elems_.back();
00043 elems_[i]->SetHeapIndex(i);
00044 elems_.pop_back();
00045 NoteChangedPriority(elems_[i]);
00046 }
00047
00048 bool Contains(const T* const val) const {
00049 const int i = val->GetHeapIndex();
00050 if (i < 0 || i >= elems_.size() || elems_[i] != val) {
00051 return false;
00052 }
00053 return true;
00054 }
00055
00056 void NoteChangedPriority(T* val) {
00057 const int i = val->GetHeapIndex();
00058 const int parent = (i - 1) / 2;
00059 if (*elems_[parent] < *val) {
00060 AdjustUpwards(i);
00061 } else {
00062 AdjustDownwards(i);
00063 }
00064 }
00065
00066 T* Top() { return elems_[0]; }
00067
00068 const T* Top() const { return elems_[0]; }
00069
00070 void Pop() { Remove(Top()); }
00071
00072 int Size() const { return elems_.size(); }
00073
00074 bool IsEmpty() const { return elems_.empty(); }
00075
00076 void Clear() { elems_.clear(); }
00077
00078 void CheckValid() const {
00079 for (int i = 0; i < elems_.size(); ++i) {
00080 const int left_child = 1 + 2 * i;
00081 if (left_child < elems_.size()) {
00082 CHECK_GE(elems_[i], elems_[left_child]);
00083 }
00084 const int right_child = left_child + 1;
00085 if (right_child < elems_.size()) {
00086 CHECK_GE(elems_[i], elems_[right_child]);
00087 }
00088 }
00089 }
00090 private:
00091 void AdjustUpwards(int i) {
00092 T* const t = elems_[i];
00093 while (i > 0) {
00094 const int parent = (i - 1) / 2;
00095 if (!(*elems_[parent] < *t)) {
00096 break;
00097 }
00098 elems_[i] = elems_[parent];
00099 elems_[i]->SetHeapIndex(i);
00100 i = parent;
00101 }
00102 elems_[i] = t;
00103 t->SetHeapIndex(i);
00104 }
00105
00106 void AdjustDownwards(int i) {
00107 T* const t = elems_[i];
00108 while (true) {
00109 const int left_child = 1 + 2 * i;
00110 if (left_child >= elems_.size()) {
00111 break;
00112 }
00113 const int right_child = left_child + 1;
00114 const int next_i = (right_child < elems_.size() &&
00115 *elems_[left_child] < *elems_[right_child]) ?
00116 right_child :
00117 left_child;
00118 if (!(*t < *elems_[next_i])) {
00119 break;
00120 }
00121 elems_[i] = elems_[next_i];
00122 elems_[i]->SetHeapIndex(i);
00123 i = next_i;
00124 }
00125 elems_[i] = t;
00126 t->SetHeapIndex(i);
00127 }
00128
00129 std::vector<T*> elems_;
00130 DISALLOW_COPY_AND_ASSIGN(AdjustablePriorityQueue);
00131 };
00132 }
00133
00134 #endif // OR_TOOLS_BASE_ADJUSTABLE_PRIORITY_QUEUE_H_