Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
key_types.h
Go to the documentation of this file.
1// Copyright 2010-2025 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// IWYU pragma: private, include "ortools/math_opt/cpp/math_opt.h"
15// IWYU pragma: friend "ortools/math_opt/cpp/.*"
16
17// This header defines the common properties of "key types" and some related
18// constants.
19//
20// Key types are types that are used as identifiers in the C++ interface where
21// the ModelStorage is using typed integers. They are pairs of (storage,
22// typed_index) where `storage` is a pointer on an ModelStorage and
23// `typed_index` is the typed integer type used in ModelStorage (or a pair of
24// typed integers for QuadraticTermKey).
25//
26// A key type K must match the following requirements:
27// - K::IdType is a value type used for indices.
28// - K has a constructor K(ModelStorageCPtr, K::IdType).
29// - K is a value-semantic type.
30// - K has a function with signature `K::IdType K::typed_id() const`.
31// - K has a function with signature `ModelStorageCPtr K::storage() const`.
32// - K::IdType is a valid key for absl::flat_hash_map or absl::flat_hash_set
33// (supports hash and ==).
34// - the is_key_type_v<> below should include them.
35// TODO(b/396580721): Those requirements are those of `ModelStorageElement`.
36// Once we've migrated most key types to `ModelStorageElement`, we should be
37// able to simplify this code.
38#ifndef OR_TOOLS_MATH_OPT_CPP_KEY_TYPES_H_
39#define OR_TOOLS_MATH_OPT_CPP_KEY_TYPES_H_
40
41#include <type_traits>
42#include <vector>
43
44#include "absl/algorithm/container.h"
45#include "absl/container/flat_hash_map.h"
46#include "absl/status/status.h"
47#include "absl/strings/string_view.h"
48#include "absl/types/span.h"
51
53
54// Forward declarations of types implementing the keys interface defined at the
55// top of this file.
56class Variable;
60class Sos1Constraint;
61class Sos2Constraint;
64class Objective;
65
66// True for types in MathOpt that implements the keys interface defined at the
67// top of this file.
68//
69// This is used in conjunction with std::enable_if_t<> to prevent Argument
70// Dependent Lookup (ADL) from selecting some overload defined in MathOpt
71// because one of the template type is in MathOpt. For example the SortedKeys()
72// function below could be selected as a valid overload in another namespace if
73// the values in the hash map are in the math_opt namespace.
74template <typename T>
75constexpr inline bool is_key_type_v =
77 std::is_same_v<T, SecondOrderConeConstraint> ||
78 std::is_same_v<T, Sos1Constraint> || std::is_same_v<T, Sos2Constraint> ||
79 std::is_same_v<T, QuadraticTermKey> || std::is_same_v<T, Objective>);
80
81// Returns the keys of the map sorted by their (storage(), type_id()).
82//
83// Implementation note: here we must use std::enable_if to prevent Argument
84// Dependent Lookup (ADL) from selecting this overload for maps which values are
85// in MathOpt but keys are not.
86template <typename Map,
87 typename = std::enable_if_t<is_key_type_v<typename Map::key_type>>>
88std::vector<typename Map::key_type> SortedKeys(const Map& map) {
89 using K = typename Map::key_type;
90 std::vector<K> result;
91 result.reserve(map.size());
92 for (const typename Map::const_reference item : map) {
93 result.push_back(item.first);
94 }
95 absl::c_sort(result, [](const K& lhs, const K& rhs) {
96 if (lhs.storage() != rhs.storage()) {
97 return lhs.storage() < rhs.storage();
98 }
99 return lhs.typed_id() < rhs.typed_id();
100 });
101 return result;
102}
103
104// Returns the elements of the set sorted by their (storage(), type_id()).
105//
106// Implementation note: here we must use std::enable_if to prevent Argument
107// Dependent Lookup (ADL) from selecting this overload for maps which values are
108// in MathOpt but keys are not.
109template <typename Set,
110 typename = std::enable_if_t<is_key_type_v<typename Set::key_type>>>
111std::vector<typename Set::key_type> SortedElements(const Set& set) {
112 using K = typename Set::key_type;
113 std::vector<K> result;
114 result.reserve(set.size());
115 for (const typename Set::const_reference item : set) {
116 result.push_back(item);
117 }
118 absl::c_sort(result, [](const K& lhs, const K& rhs) {
119 if (lhs.storage() != rhs.storage()) {
120 return lhs.storage() < rhs.storage();
121 }
122 return lhs.typed_id() < rhs.typed_id();
123 });
124 return result;
125}
126
127// Returns the values corresponding to the keys. Keys must be present in the
128// input map.
129//
130// The keys must be in a type convertible to absl::Span<const K>.
131//
132// Implementation note: here we must use std::enable_if to prevent Argument
133// Dependent Lookup (ADL) from selecting this overload for maps which values are
134// in MathOpt but keys are not.
135template <typename Map, typename Keys,
136 typename = std::enable_if_t<is_key_type_v<typename Map::key_type>>>
137std::vector<typename Map::mapped_type> Values(const Map& map,
138 const Keys& keys) {
139 using K = typename Map::key_type;
140 const absl::Span<const K> keys_span = keys;
141 std::vector<typename Map::mapped_type> result;
142 result.reserve(keys_span.size());
143 for (const K& key : keys_span) {
144 result.push_back(map.at(key));
145 }
146 return result;
147}
148
149namespace internal {
150
151// The CHECK message to use when a KeyType::storage() is nullptr.
152inline constexpr absl::string_view kKeyHasNullModelStorage =
153 "The input key has null .storage().";
154
155// The CHECK message to use when two KeyType with different storage() are used
156// in the same collection.
157inline constexpr absl::string_view kObjectsFromOtherModelStorage =
158 "The input objects belongs to another model.";
159
160// The Status message to use when an input KeyType is from an unexpected
161// storage().
162inline constexpr absl::string_view kInputFromInvalidModelStorage =
163 "the input does not belong to the same model";
164
165// Returns a failure when the input pointer is not nullptr and points to a
166// different model storage than expected_storage.
167//
168// Failure message is kInputFromInvalidModelStorage.
169inline absl::Status CheckModelStorage(const NullableModelStorageCPtr storage,
170 const ModelStorageCPtr expected_storage) {
171 // This is not allowed by the contract, but let's be safe.
172 if (expected_storage == nullptr) {
173 return absl::InternalError("expected_storage is nullptr");
174 }
175 if (storage != nullptr && storage != expected_storage) {
176 return absl::InvalidArgumentError(internal::kInputFromInvalidModelStorage);
177 }
178 return absl::OkStatus();
179}
180
181} // namespace internal
182} // namespace operations_research::math_opt
183
184#endif // OR_TOOLS_MATH_OPT_CPP_KEY_TYPES_H_
absl::Status CheckModelStorage(const NullableModelStorageCPtr storage, const ModelStorageCPtr expected_storage)
Definition key_types.h:169
constexpr absl::string_view kKeyHasNullModelStorage
The CHECK message to use when a KeyType::storage() is nullptr.
Definition key_types.h:152
constexpr absl::string_view kInputFromInvalidModelStorage
Definition key_types.h:162
constexpr absl::string_view kObjectsFromOtherModelStorage
Definition key_types.h:157
An object oriented wrapper for quadratic constraints in ModelStorage.
Definition gurobi_isv.cc:28
absl::Nonnull< const ModelStorage * > ModelStorageCPtr
std::vector< typename Set::key_type > SortedElements(const Set &set)
Definition key_types.h:111
std::vector< typename Map::mapped_type > Values(const Map &map, const Keys &keys)
Definition key_types.h:137
constexpr bool is_key_type_v
Definition key_types.h:75
std::vector< typename Map::key_type > SortedKeys(const Map &map)
Definition key_types.h:88
absl::Nullable< const ModelStorage * > NullableModelStorageCPtr