OR-Tools  8.2
map_util.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#ifndef OR_TOOLS_BASE_MAP_UTIL_H_
15#define OR_TOOLS_BASE_MAP_UTIL_H_
16
17#include <utility>
18
20
21namespace gtl {
22// Perform a lookup in a std::map or std::unordered_map.
23// If the key is present in the map then the value associated with that
24// key is returned, otherwise the value passed as a default is returned.
25template <class Collection>
26const typename Collection::value_type::second_type& FindWithDefault(
27 const Collection& collection,
28 const typename Collection::value_type::first_type& key,
29 const typename Collection::value_type::second_type& value) {
30 typename Collection::const_iterator it = collection.find(key);
31 if (it == collection.end()) {
32 return value;
33 }
34 return it->second;
35}
36
37// Perform a lookup in a std::map or std::unordered_map.
38// If the key is present a const pointer to the associated value is returned,
39// otherwise a NULL pointer is returned.
40template <class Collection>
41const typename Collection::value_type::second_type* FindOrNull(
42 const Collection& collection,
43 const typename Collection::value_type::first_type& key) {
44 typename Collection::const_iterator it = collection.find(key);
45 if (it == collection.end()) {
46 return 0;
47 }
48 return &it->second;
49}
50
51// Perform a lookup in a std::map or std::unordered_map.
52// Same as above but the returned pointer is not const and can be used to change
53// the stored value.
54template <class Collection>
55typename Collection::value_type::second_type* FindOrNull(
56 Collection& collection, // NOLINT
57 const typename Collection::value_type::first_type& key) {
58 typename Collection::iterator it = collection.find(key);
59 if (it == collection.end()) {
60 return 0;
61 }
62 return &it->second;
63}
64
65// Perform a lookup in a std::map or std::unordered_map whose values are
66// pointers. If the key is present a const pointer to the associated value is
67// returned, otherwise a NULL pointer is returned. This function does not
68// distinguish between a missing key and a key mapped to a NULL value.
69template <class Collection>
70const typename Collection::value_type::second_type FindPtrOrNull(
71 const Collection& collection,
72 const typename Collection::value_type::first_type& key) {
73 typename Collection::const_iterator it = collection.find(key);
74 if (it == collection.end()) {
75 return 0;
76 }
77 return it->second;
78}
79
80// Change the value associated with a particular key in a std::map or
81// std::unordered_map. If the key is not present in the map the key and value
82// are inserted, otherwise the value is updated to be a copy of the value
83// provided. True indicates that an insert took place, false indicates an
84// update.
85template <class Collection, class Key, class Value>
86bool InsertOrUpdate(Collection* const collection, const Key& key,
87 const Value& value) {
88 std::pair<typename Collection::iterator, bool> ret =
89 collection->insert(typename Collection::value_type(key, value));
90 if (!ret.second) {
91 // update
92 ret.first->second = value;
93 return false;
94 }
95 return true;
96}
97
98// Insert a new key into a set.
99// If the key is not present in the set the key is
100// inserted, otherwise nothing happens. True indicates that an insert
101// took place, false indicates the key was already present.
102template <class Collection>
103bool InsertIfNotPresent(Collection* const collection,
104 const typename Collection::value_type& value) {
105 std::pair<typename Collection::iterator, bool> ret =
106 collection->insert(value);
107 return ret.second;
108}
109
110// Insert a new key and value into a std::map or std::unordered_map.
111// If the key is not present in the map the key and value are
112// inserted, otherwise nothing happens. True indicates that an insert
113// took place, false indicates the key was already present.
114template <class Collection, class Key, class Value>
115bool InsertIfNotPresent(Collection* const collection, const Key& key,
116 const Value& value) {
117 std::pair<typename Collection::iterator, bool> ret =
118 collection->insert(typename Collection::value_type(key, value));
119 return ret.second;
120}
121
122// Inserts a new std::pair<key,value> into a std::map or std::unordered_map.
123// Insert a new key into a std::set or std::unordered_set.
124// Dies if the key is already present.
125template <class Collection>
126void InsertOrDieNoPrint(Collection* const collection,
127 const typename Collection::value_type& value) {
128 CHECK(collection->insert(value).second);
129}
130
131// Inserts a new std::pair<key,value> into a std::map or std::unordered_map.
132// Insert a new key into a std::set or std::unordered_set.
133// Dies if the key is already present.
134template <class Collection>
135void InsertOrDie(Collection* const collection,
136 const typename Collection::value_type& value) {
137 CHECK(collection->insert(value).second) << "duplicate value: " << value;
138}
139
140// Inserts a new key/value into a std::map or std::unordered_map.
141// Dies if the key is already present.
142template <class Collection>
143void InsertOrDie(Collection* const collection,
144 const typename Collection::value_type::first_type& key,
145 const typename Collection::value_type::second_type& data) {
146 typedef typename Collection::value_type value_type;
147 CHECK(collection->insert(value_type(key, data)).second)
148 << "duplicate key: " << key;
149}
150
151// Perform a lookup in std::map or std::unordered_map.
152// If the key is present and value is non-NULL then a copy of the value
153// associated with the key is made into *value. Returns whether key was present.
154template <class Collection, class Key, class Value>
155bool FindCopy(const Collection& collection, const Key& key,
156 Value* const value) {
157 typename Collection::const_iterator it = collection.find(key);
158 if (it == collection.end()) {
159 return false;
160 }
161 if (value) {
162 *value = it->second;
163 }
164 return true;
165}
166
167// Test to see if a std::set, std::map, std::unordered_set or std::unordered_map
168// contains a particular key. Returns true if the key is in the collection.
169template <class Collection, class Key>
170bool ContainsKey(const Collection& collection, const Key& key) {
171 typename Collection::const_iterator it = collection.find(key);
172 return it != collection.end();
173}
174
175template <class Collection>
176const typename Collection::value_type::second_type& FindOrDie(
177 const Collection& collection,
178 const typename Collection::value_type::first_type& key) {
179 typename Collection::const_iterator it = collection.find(key);
180 CHECK(it != collection.end()) << "Map key not found: " << key;
181 return it->second;
182}
183
184// Same as FindOrDie above, but doesn't log the key on failure.
185template <class Collection>
186const typename Collection::value_type::second_type& FindOrDieNoPrint(
187 const Collection& collection,
188 const typename Collection::value_type::first_type& key) {
189 typename Collection::const_iterator it = collection.find(key);
190 CHECK(it != collection.end()) << "Map key not found";
191 return it->second;
192}
193
194// Same as above, but returns a non-const reference.
195template <class Collection>
196typename Collection::value_type::second_type& FindOrDieNoPrint(
197 Collection& collection, // NOLINT
198 const typename Collection::value_type::first_type& key) {
199 typename Collection::iterator it = collection.find(key);
200 CHECK(it != collection.end()) << "Map key not found";
201 return it->second;
202}
203
204// Lookup a key in a std::map or std::unordered_map, insert it if it is not
205// present. Returns a reference to the value associated with the key.
206template <class Collection>
207typename Collection::value_type::second_type& LookupOrInsert(
208 Collection* const collection,
209 const typename Collection::value_type::first_type& key,
210 const typename Collection::value_type::second_type& value) {
211 std::pair<typename Collection::iterator, bool> ret =
212 collection->insert(typename Collection::value_type(key, value));
213 return ret.first->second;
214}
215} // namespace gtl
216#endif // OR_TOOLS_BASE_MAP_UTIL_H_
#define CHECK(condition)
Definition: base/logging.h:495
int64 value
bool InsertIfNotPresent(Collection *const collection, const typename Collection::value_type &value)
Definition: map_util.h:103
bool InsertOrUpdate(Collection *const collection, const Key &key, const Value &value)
Definition: map_util.h:86
const Collection::value_type::second_type & FindOrDie(const Collection &collection, const typename Collection::value_type::first_type &key)
Definition: map_util.h:176
void InsertOrDieNoPrint(Collection *const collection, const typename Collection::value_type &value)
Definition: map_util.h:126
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
Collection::value_type::second_type & LookupOrInsert(Collection *const collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
Definition: map_util.h:207
const Collection::value_type::second_type & FindOrDieNoPrint(const Collection &collection, const typename Collection::value_type::first_type &key)
Definition: map_util.h:186
void InsertOrDie(Collection *const collection, const typename Collection::value_type &value)
Definition: map_util.h:135
const Collection::value_type::second_type FindPtrOrNull(const Collection &collection, const typename Collection::value_type::first_type &key)
Definition: map_util.h:70
const Collection::value_type::second_type & FindWithDefault(const Collection &collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
Definition: map_util.h:26
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
Definition: map_util.h:155
const Collection::value_type::second_type * FindOrNull(const Collection &collection, const typename Collection::value_type::first_type &key)
Definition: map_util.h:41
std::function< int64(const Model &)> Value(IntegerVariable v)
Definition: integer.h:1487