15#ifndef OR_TOOLS_UTIL_REV_H_
16#define OR_TOOLS_UTIL_REV_H_
20#include "absl/container/flat_hash_map.h"
53 int Level()
const {
return end_of_level_.size(); }
61 if (end_of_level_.empty())
return;
62 stack_.push_back({object, *
object});
71 if (*
stamp == stamp_)
return;
78 std::vector<int> end_of_level_;
82 std::vector<std::pair<T*, T>> stack_;
86template <
class IndexType,
class T>
96 if (!end_of_level_.empty()) stack_.push_back({
index, vector_[
index]});
97 return vector_[
index];
103 CHECK_GE(new_size, vector_.
size());
109 int Level()
const {
return end_of_level_.size(); }
113 if (level ==
Level())
return;
114 if (level <
Level()) {
115 const int index = end_of_level_[level];
116 end_of_level_.resize(level);
117 for (
int i = stack_.size() - 1; i >=
index; --i) {
118 vector_[stack_[i].first] = stack_[i].second;
120 stack_.resize(
index);
122 end_of_level_.resize(level, stack_.size());
127 std::vector<int> end_of_level_;
128 std::vector<std::pair<IndexType, T>> stack_;
135 if (level == Level())
return;
137 if (level < Level()) {
138 const int index = end_of_level_[level];
139 end_of_level_.resize(level);
140 for (
int i = stack_.size() - 1; i >=
index; --i) {
141 *stack_[i].first = stack_[i].second;
143 stack_.resize(
index);
145 end_of_level_.resize(level, stack_.size());
168 int Level()
const {
return first_op_index_of_next_level_.size(); }
177 int size()
const {
return map_.size(); }
178 bool empty()
const {
return map_.empty(); }
189 struct UndoOperation {
198 std::vector<UndoOperation> operations_;
199 std::vector<int> first_op_index_of_next_level_;
205 if (level < Level()) {
206 const int backtrack_level = first_op_index_of_next_level_[level];
207 first_op_index_of_next_level_.resize(level);
208 while (operations_.size() > backtrack_level) {
209 const UndoOperation& to_undo = operations_.back();
210 if (to_undo.is_deletion) {
211 map_.erase(to_undo.key);
213 map_.insert({to_undo.key, to_undo.value}).first->second = to_undo.value;
215 operations_.pop_back();
221 first_op_index_of_next_level_.resize(level, operations_.size());
226 const auto iter = map_.find(key);
227 if (iter == map_.end()) LOG(FATAL) <<
"key not present: '" << key <<
"'.";
229 operations_.push_back({
false, key, iter->second});
236 auto insertion_result = map_.insert({key,
value});
238 if (insertion_result.second) {
240 operations_.push_back({
true, key});
243 operations_.push_back({
false, key, insertion_result.first->second});
246 insertion_result.first->second =
value;
250template <
class Key,
class Value>
259 const std::vector<Value>&
Values(Key key)
const;
262 std::vector<Value> empty_values_;
267 absl::flat_hash_map<Key, std::vector<Value>> map_;
270 std::vector<Key> added_keys_;
271 std::vector<int> first_added_key_of_next_level_;
274template <
class Key,
class Value>
277 if (level < first_added_key_of_next_level_.size()) {
278 const int backtrack_level = first_added_key_of_next_level_[level];
279 first_added_key_of_next_level_.resize(level);
280 while (added_keys_.size() > backtrack_level) {
281 auto it = map_.find(added_keys_.back());
282 if (it->second.size() > 1) {
283 it->second.pop_back();
287 added_keys_.pop_back();
293 first_added_key_of_next_level_.resize(level, added_keys_.size());
296template <
class Key,
class Value>
299 const auto it = map_.find(key);
300 if (it != map_.end())
return it->second;
301 return empty_values_;
304template <
class Key,
class Value>
306 if (!first_added_key_of_next_level_.empty()) {
307 added_keys_.push_back(key);
309 map_[key].push_back(
value);
STL vector ---------------------------------------------------------------—.
void resize(size_type new_size)
A basic backtrackable multi map that can only grow (except on backtrack).
void SetLevel(int level) final
void Add(Key key, Value value)
Adds a new value at the given key.
const std::vector< Value > & Values(Key key) const
Returns the list of values for a given key (can be empty).
void EraseOrDie(key_type key)
Map::const_iterator const_iterator
bool contains(key_type key) const
Map::value_type value_type
const_iterator end() const
int size() const
Wrapper to the underlying const map functions.
const mapped_type & at(key_type key) const
const_iterator begin() const
const_iterator find(const key_type &k) const
void SetLevel(int level) final
Map::mapped_type mapped_type
void Set(key_type key, mapped_type value)
void SetLevel(int level) final
void SaveStateWithStamp(T *object, int64_t *stamp)
void SaveState(T *object)
A basic reversible vector implementation.
const T & operator[](IndexType index) const
T & MutableRef(IndexType index)
void SetLevel(int level) final
virtual ~ReversibleInterface()
virtual void SetLevel(int level)=0
In SWIG mode, we don't want anything besides these top-level includes.