Google OR-Tools: ortools/base/adjustable_priority

Google OR-Tools: ortools/base/adjustable_priority_queue.h Source File

25 public:

27 bool operator()(T* a, T* b) const { return (*compare_)(*a, *b); }

29 private:

30 Comparator* compare_;

31};

35 public:

45 void Add(T* val) {

48 elems_.push_back(val);

49 AdjustUpwards(elems_.size() - 1);

50 }

53 int end = elems_.size() - 1;

54 int i = val->GetHeapIndex();

55 if (i == end) {

56 elems_.pop_back();

57 return;

58 }

59 elems_[i] = elems_[end];

60 elems_[i]->SetHeapIndex(i);

61 elems_.pop_back();

63 }

66 int i = val->GetHeapIndex();

67 return (i >= 0 && i < elems_.size() && elems_[i] == val);

68 }

72 int i = val->GetHeapIndex();

73 int parent = (i - 1) / 2;

74 if (lower_priority(elems_[parent], val)) {

75 AdjustUpwards(i);

76 } else {

77 AdjustDownwards(i);

78 }

79 }

83 T* Top() { return elems_[0]; }

85 const T* Top() const { return elems_[0]; }

87 void AllTop(std::vector<T*>* topvec) {

88 topvec->clear();

89 if (Size() == 0) return;

90 std::list<int> need_to_check_children;

91 need_to_check_children.push_back(0);

94 while (!need_to_check_children.empty()) {

95 int ind = need_to_check_children.front();

96 need_to_check_children.pop_front();

97 topvec->push_back(elems_[ind]);

98 int leftchild = 1 + 2 * ind;

99 if (leftchild < Size()) {

101 need_to_check_children.push_back(leftchild);

102 }

103 int rightchild = leftchild + 1;

104 if (rightchild < Size() &&

106 need_to_check_children.push_back(rightchild);

107 }

108 }

109 }

110 }

111

112

114

115 int Size() const { return elems_.size(); }

116

117

118 int Capacity() const { return elems_.capacity(); }

119

120

122

123 bool IsEmpty() const { return elems_.empty(); }

124

125 void Clear() { elems_.clear(); }

126

127

128

130 for (int i = 0; i < elems_.size(); ++i) {

131 int left_child = 1 + 2 * i;

132 if (left_child < elems_.size()) {

133 CHECK(

135 }

136 int right_child = left_child + 1;

137 if (right_child < elems_.size()) {

138 CHECK(

140 }

141 }

142 }

143

144

145

146

147 const std::vector<T*>* Raw() const { return &elems_; }

148

149 private:

150 void AdjustUpwards(int i) {

151 T* const t = elems_[i];

152 while (i > 0) {

153 const int parent = (i - 1) / 2;

154 if (!c_(*elems_[parent], *t)) {

155 break;

156 }

157 elems_[i] = elems_[parent];

158 elems_[i]->SetHeapIndex(i);

159 i = parent;

160 }

161 elems_[i] = t;

162 t->SetHeapIndex(i);

163 }

164

165 void AdjustDownwards(int i) {

166 T* const t = elems_[i];

167 while (true) {

168 const int left_child = 1 + 2 * i;

169 if (left_child >= elems_.size()) {

170 break;

171 }

172 const int right_child = left_child + 1;

173 const int next_i = (right_child < elems_.size() &&

174 c_(*elems_[left_child], *elems_[right_child]))

175 ? right_child

176 : left_child;

177 if (!c_(*t, *elems_[next_i])) {

178 break;

179 }

180 elems_[i] = elems_[next_i];

181 elems_[i]->SetHeapIndex(i);

182 i = next_i;

183 }

184 elems_[i] = t;

185 t->SetHeapIndex(i);

186 }

187

188 Comp c_;

189 std::vector<T*> elems_;

190};