OR-Tools  8.2
rev.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// Reversible (i.e Backtrackable) classes, used to simplify coding propagators.
15#ifndef OR_TOOLS_UTIL_REV_H_
16#define OR_TOOLS_UTIL_REV_H_
17
18#include <vector>
19
20#include "absl/container/flat_hash_map.h"
24
25namespace operations_research {
26
27// Interface for reversible objects used to maintain them in sync with a tree
28// search organized by decision levels.
30 public:
33
34 // Initially a reversible class starts at level zero. Increasing the level
35 // saves the state of the current old level. Decreasing the level restores the
36 // state to what it was at this level and all higher levels are forgotten.
37 // Everything done at level zero cannot be backtracked over.
38 //
39 // The level is assumed to be non-negative.
40 virtual void SetLevel(int level) = 0;
41};
42
43// A repository that maintains a set of reversible objects of type T.
44// This is meant to be used for small types that are efficient to copy, like
45// all the basic types, std::pair and things like this.
46template <class T>
48 public:
49 RevRepository() : stamp_(0) {}
50
51 // This works in O(level_diff) on level increase.
52 // For level decrease, it is in O(level_diff + num_restored_states).
53 void SetLevel(int level) final;
54 int Level() const { return end_of_level_.size(); }
55
56 // Saves the given object value for the current level. If this is called
57 // multiple time by level, only the value of the first call matter. This is
58 // NOT optimized for many calls by level and should mainly be used just once
59 // for a given level. If a client cannot do that efficiently, it can use the
60 // SaveStateWithStamp() function below.
61 void SaveState(T* object) {
62 if (end_of_level_.empty()) return; // Not useful for level zero.
63 stack_.push_back({object, *object});
64 }
65
66 // Calls SaveState() if the given stamp is not the same as the current one.
67 // This also sets the given stamp to the current one. The current stamp is
68 // maintained by this class and is updated on each level changes. The whole
69 // process make sure that only one SaveValue() par level will ever be called,
70 // so it is efficient to call this before each update to the object T.
71 void SaveStateWithStamp(T* object, int64* stamp) {
72 if (*stamp == stamp_) return;
73 *stamp = stamp_;
74 SaveState(object);
75 }
76
77 private:
78 int64 stamp_;
79 std::vector<int> end_of_level_; // In stack_.
80
81 // TODO(user): If we ever see this in any cpu profile, consider using two
82 // vectors for a better memory packing in case sizeof(T) is not sizeof(T*).
83 std::vector<std::pair<T*, T>> stack_;
84};
85
86// A basic reversible vector implementation.
87template <class IndexType, class T>
89 public:
90 const T& operator[](IndexType index) const { return vector_[index]; }
91
92 // TODO(user): Maybe we could have also used the [] operator, but it is harder
93 // to be 100% sure that the mutable version is only called when we modify
94 // the vector. And I had performance bug because of that.
95 T& MutableRef(IndexType index) {
96 // Save on the stack first.
97 if (!end_of_level_.empty()) stack_.push_back({index, vector_[index]});
98 return vector_[index];
99 }
100
101 int size() const { return vector_.size(); }
102
103 void Grow(int new_size) {
104 CHECK_GE(new_size, vector_.size());
105 vector_.resize(new_size);
106 }
107
108 void GrowByOne() { vector_.resize(vector_.size() + 1); }
109
110 int Level() const { return end_of_level_.size(); }
111
112 void SetLevel(int level) final {
113 DCHECK_GE(level, 0);
114 if (level == Level()) return;
115 if (level < Level()) {
116 const int index = end_of_level_[level];
117 end_of_level_.resize(level); // Shrinks.
118 for (int i = stack_.size() - 1; i >= index; --i) {
119 vector_[stack_[i].first] = stack_[i].second;
120 }
121 stack_.resize(index);
122 } else {
123 end_of_level_.resize(level, stack_.size()); // Grows.
124 }
125 }
126
127 private:
128 std::vector<int> end_of_level_; // In stack_.
129 std::vector<std::pair<IndexType, T>> stack_;
131};
132
133template <class T>
135 DCHECK_GE(level, 0);
136 if (level == Level()) return;
137 ++stamp_;
138 if (level < Level()) {
139 const int index = end_of_level_[level];
140 end_of_level_.resize(level); // Shrinks.
141 for (int i = stack_.size() - 1; i >= index; --i) {
142 *stack_[i].first = stack_[i].second;
143 }
144 stack_.resize(index);
145 } else {
146 end_of_level_.resize(level, stack_.size()); // Grows.
147 }
148}
149
150// Like a normal map but support backtrackable operations.
151//
152// This works on any class "Map" that supports: begin(), end(), find(), erase(),
153// insert(), key_type, value_type, mapped_type and const_iterator.
154template <class Map>
156 public:
157 typedef typename Map::key_type key_type;
158 typedef typename Map::mapped_type mapped_type;
159 typedef typename Map::value_type value_type;
160 typedef typename Map::const_iterator const_iterator;
161
162 // Backtracking support: changes the current "level" (always non-negative).
163 //
164 // Initially the class starts at level zero. Increasing the level works in
165 // O(level diff) and saves the state of the current old level. Decreasing the
166 // level restores the state to what it was at this level and all higher levels
167 // are forgotten. Everything done at level zero cannot be backtracked over.
168 void SetLevel(int level) final;
169 int Level() const { return first_op_index_of_next_level_.size(); }
170
171 bool ContainsKey(key_type key) const { return gtl::ContainsKey(map_, key); }
172 const mapped_type& FindOrDie(key_type key) const {
173 return gtl::FindOrDie(map_, key);
174 }
175
177 void Set(key_type key, mapped_type value); // Adds or overwrites.
178
179 // Wrapper to the underlying const map functions.
180 int size() const { return map_.size(); }
181 bool empty() const { return map_.empty(); }
182 const_iterator find(const key_type& k) const { return map_.find(k); }
183 const_iterator begin() const { return map_.begin(); }
184 const_iterator end() const { return map_.end(); }
185
186 private:
187 Map map_;
188
189 // The operation that needs to be performed to reverse one modification:
190 // - If is_deletion is true, then we need to delete the entry with given key.
191 // - Otherwise we need to add back (or overwrite) the saved entry.
192 struct UndoOperation {
193 bool is_deletion;
194 key_type key;
196 };
197
198 // TODO(user): We could merge the operations with the same key from the same
199 // level. Investigate and implement if this is worth the effort for our use
200 // case.
201 std::vector<UndoOperation> operations_;
202 std::vector<int> first_op_index_of_next_level_;
203};
204
205template <class Map>
206void RevMap<Map>::SetLevel(int level) {
207 DCHECK_GE(level, 0);
208 if (level < Level()) {
209 const int backtrack_level = first_op_index_of_next_level_[level];
210 first_op_index_of_next_level_.resize(level); // Shrinks.
211 while (operations_.size() > backtrack_level) {
212 const UndoOperation& to_undo = operations_.back();
213 if (to_undo.is_deletion) {
214 map_.erase(to_undo.key);
215 } else {
216 map_.insert({to_undo.key, to_undo.value}).first->second = to_undo.value;
217 }
218 operations_.pop_back();
219 }
220 return;
221 }
222
223 // This is ok even if level == Level().
224 first_op_index_of_next_level_.resize(level, operations_.size()); // Grows.
225}
226
227template <class Map>
229 const auto iter = map_.find(key);
230 if (iter == map_.end()) LOG(FATAL) << "key not present: '" << key << "'.";
231 if (Level() > 0) {
232 operations_.push_back({false, key, iter->second});
233 }
234 map_.erase(iter);
235}
236
237template <class Map>
239 auto insertion_result = map_.insert({key, value});
240 if (Level() > 0) {
241 if (insertion_result.second) {
242 // It is an insertion. Undo = delete.
243 operations_.push_back({true, key});
244 } else {
245 // It is a modification. Undo = change back to old value.
246 operations_.push_back({false, key, insertion_result.first->second});
247 }
248 }
249 insertion_result.first->second = value;
250}
251
252// A basic backtrackable multi map that can only grow (except on backtrack).
253template <class Key, class Value>
255 public:
256 void SetLevel(int level) final;
257
258 // Adds a new value at the given key.
259 void Add(Key key, Value value);
260
261 // Returns the list of values for a given key (can be empty).
262 const std::vector<Value>& Values(Key key) const;
263
264 private:
265 std::vector<Value> empty_values_;
266
267 // TODO(user): use inlined vectors. Another datastructure that may be more
268 // efficient is to use a linked list inside added_keys_ for the values sharing
269 // the same key.
270 absl::flat_hash_map<Key, std::vector<Value>> map_;
271
272 // Backtracking data.
273 std::vector<Key> added_keys_;
274 std::vector<int> first_added_key_of_next_level_;
275};
276
277template <class Key, class Value>
279 DCHECK_GE(level, 0);
280 if (level < first_added_key_of_next_level_.size()) {
281 const int backtrack_level = first_added_key_of_next_level_[level];
282 first_added_key_of_next_level_.resize(level); // Shrinks.
283 while (added_keys_.size() > backtrack_level) {
284 auto it = map_.find(added_keys_.back());
285 if (it->second.size() > 1) {
286 it->second.pop_back();
287 } else {
288 map_.erase(it);
289 }
290 added_keys_.pop_back();
291 }
292 return;
293 }
294
295 // This is ok even if level == Level().
296 first_added_key_of_next_level_.resize(level, added_keys_.size()); // Grows.
297}
298
299template <class Key, class Value>
301 Key key) const {
302 const auto it = map_.find(key);
303 if (it != map_.end()) return it->second;
304 return empty_values_;
305}
306
307template <class Key, class Value>
309 if (!first_added_key_of_next_level_.empty()) {
310 added_keys_.push_back(key);
311 }
312 map_[key].push_back(value);
313}
314
315} // namespace operations_research
316
317#endif // OR_TOOLS_UTIL_REV_H_
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define LOG(severity)
Definition: base/logging.h:420
void resize(size_type new_size)
size_type size() const
void SetLevel(int level) final
Definition: rev.h:278
void Add(Key key, Value value)
Definition: rev.h:308
const std::vector< Value > & Values(Key key) const
Definition: rev.h:300
int Level() const
Definition: rev.h:169
void Set(key_type key, mapped_type value)
Definition: rev.h:238
Map::value_type value_type
Definition: rev.h:159
void SetLevel(int level) final
Definition: rev.h:206
const_iterator begin() const
Definition: rev.h:183
const_iterator find(const key_type &k) const
Definition: rev.h:182
bool empty() const
Definition: rev.h:181
Map::key_type key_type
Definition: rev.h:157
bool ContainsKey(key_type key) const
Definition: rev.h:171
const mapped_type & FindOrDie(key_type key) const
Definition: rev.h:172
const_iterator end() const
Definition: rev.h:184
Map::mapped_type mapped_type
Definition: rev.h:158
void EraseOrDie(key_type key)
Definition: rev.h:228
Map::const_iterator const_iterator
Definition: rev.h:160
int size() const
Definition: rev.h:180
void SetLevel(int level) final
Definition: rev.h:134
void SaveState(T *object)
Definition: rev.h:61
void SaveStateWithStamp(T *object, int64 *stamp)
Definition: rev.h:71
void SetLevel(int level) final
Definition: rev.h:112
void Grow(int new_size)
Definition: rev.h:103
const T & operator[](IndexType index) const
Definition: rev.h:90
T & MutableRef(IndexType index)
Definition: rev.h:95
virtual void SetLevel(int level)=0
int64 value
int64_t int64
const int FATAL
Definition: log_severity.h:32
const Collection::value_type::second_type & FindOrDie(const Collection &collection, const typename Collection::value_type::first_type &key)
Definition: map_util.h:176
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
std::function< int64(const Model &)> Value(IntegerVariable v)
Definition: integer.h:1487
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int index
Definition: pack.cc:508
const int64 stamp_
Definition: search.cc:3039