idol
A C++ Framework for Optimization
Loading...
Searching...
No Matches
SparseVector.h
1//
2// Created by henri on 24.10.24.
3//
4
5#ifndef IDOL_SPARSEVECTOR_H
6#define IDOL_SPARSEVECTOR_H
7
8#include <vector>
9#include "idol/general/utils/exceptions/Exception.h"
10#include "idol/general/numericals.h"
11#include <idol/mixed-integer/modeling/variables/Var.h>
12#include <idol/general/utils/Map.h>
13
14namespace idol {
15 class Var;
16 class Ctr;
17
18 namespace impl {
19
20 template<class T>
21 struct hash_object {
22 auto operator()(const T& t_obj) const { return std::hash<unsigned int>()(t_obj.id()); }
23 };
24
25 template<class T>
26 struct equal_to_object {
27 auto operator()(const T& t_a, const T& t_b) const { return t_a.id() == t_b.id(); }
28 };
29
30 template<class T>
31 struct less_object {
32 auto operator()(const T& t_a, const T& t_b) const { return t_a.id() < t_b.id(); }
33 };
34
35 }
36}
37
38template<> struct std::hash<idol::Var> : public idol::impl::hash_object<idol::Var> {};
39template<> struct std::equal_to<idol::Var> : public idol::impl::equal_to_object<idol::Var> {};
40template<> struct std::less<idol::Var> : public idol::impl::less_object<idol::Var> {};
41
42template<> struct std::hash<idol::Ctr> : public idol::impl::hash_object<idol::Ctr> {};
43template<> struct std::equal_to<idol::Ctr> : public idol::impl::equal_to_object<idol::Ctr> {};
44template<> struct std::less<idol::Ctr> : public idol::impl::less_object<idol::Ctr> {};
45
46namespace idol {
47 template<class, class>
48 class SparseVector;
49}
50
51#ifdef IDOL_USE_TSL
52#include <tsl/sparse_map.h>
53#include <tsl/ordered_map.h>
54#define IDOL_REF_VALUE(t_iterator) t_iterator.value()
55#else
56#ifdef IDOL_USE_ROBINHOOD
57#include <robin_hood.h>
58#define IDOL_REF_VALUE(t_iterator) t_iterator->second
59#else
60#include <map>
61#define IDOL_REF_VALUE(t_iterator) t_iterator->second
62#endif
63#endif
64
65template<class IndexT, class ValueT>
67private:
68#ifdef IDOL_USE_TSL
69 using map_t = std::conditional_t<
70 sizeof(ValueT) < 32,
71 tsl::sparse_map<IndexT, ValueT>,
72 tsl::ordered_map<IndexT, ValueT>
73 >;
74#else
75 #ifdef IDOL_USE_ROBINHOOD
76 using map_t = robin_hood::unordered_map<IndexT, ValueT>;
77#else
78 using map_t = std::unordered_map<IndexT, ValueT>;
79#endif
80#endif
81 map_t m_map;
82
83 static ValueT s_zero_value;
84public:
85 SparseVector() = default;
86
87 SparseVector(const IndexT& t_index, const ValueT& t_value) : m_map({ { t_index, t_value} }) {
88 if (::idol::is_zero(t_value, Tolerance::Sparsity)) {
89 m_map.clear();
90 }
91 }
92
93 SparseVector(const SparseVector&) = default;
94 SparseVector(SparseVector&&) = default;
95
96 SparseVector& operator=(const SparseVector&) = default;
97 SparseVector& operator=(SparseVector&&) noexcept = default;
98
99 virtual SparseVector& operator+=(const SparseVector& t_vector);
100 virtual SparseVector& operator-=(const SparseVector& t_vector);
101 virtual SparseVector& operator*=(std::conditional_t<std::is_arithmetic_v<ValueT>, ValueT, double> t_scalar);
102 virtual SparseVector& operator/=(std::conditional_t<std::is_arithmetic_v<ValueT>, ValueT, double> t_scalar);
103 SparseVector operator-() const;
104
105 [[nodiscard]] unsigned int size() const { return m_map.size(); }
106
107 [[nodiscard]] bool empty() const { return m_map.empty(); }
108
109 [[nodiscard]] bool has_index(const IndexT& t_index) const { return m_map.find(t_index) != m_map.end(); }
110
111 [[nodiscard]] const ValueT& get(const IndexT& t_index1) const;
112
113 void set(const IndexT& t_index, const ValueT& t_value);
114
115 [[nodiscard]] virtual bool is_zero(double t_tolerance) const;
116
117 void remove(const IndexT& t_index) { m_map.erase(t_index); }
118
119 void clear() { m_map.clear(); }
120
121 void reserve(unsigned int t_capacity) {
122#ifdef IDOL_USE_TSL
123 m_map.reserve(t_capacity);
124#endif
125 }
126
127 using iterator = typename map_t::iterator;
128 using const_iterator = typename map_t::const_iterator;
129
130 [[nodiscard]] iterator begin() { return m_map.begin(); }
131
132 [[nodiscard]] iterator end() { return m_map.end(); }
133
134 [[nodiscard]] const_iterator begin() const { return m_map.cbegin(); }
135
136 [[nodiscard]] const_iterator end() const { return m_map.cend(); }
137
138 [[nodiscard]] const_iterator cbegin() const { return m_map.cbegin(); }
139
140 [[nodiscard]] const_iterator cend() const { return m_map.cend(); }
141
142 SparseVector& merge_without_conflict(const SparseVector& t_vec);
143};
144
145template<class IndexT, class ValueT> ValueT idol::SparseVector<IndexT, ValueT>::s_zero_value {};
146
147template<class IndexT, class ValueT>
150 SparseVector result;
151
152 for (const auto& [var, val] : m_map) {
153 result.m_map.emplace(var, -val);
154 }
155
156 return result;
157}
158
159template<class IndexT, class ValueT>
161idol::SparseVector<IndexT, ValueT>::operator/=(std::conditional_t<std::is_arithmetic_v<ValueT>, ValueT, double> t_scalar) {
162
163 std::vector<IndexT> to_be_removed;
164 to_be_removed.reserve(m_map.size());
165
166 for (auto it = m_map.begin(), end = m_map.end() ; it != end ; ++it) {
167 IDOL_REF_VALUE(it) /= t_scalar;
168 if (::idol::is_zero(it->second, Tolerance::Sparsity)) {
169 to_be_removed.emplace_back(it->first);
170 }
171 }
172
173 for (const auto& index : to_be_removed) {
174 m_map.erase(index);
175 }
176
177 return *this;
178}
179
180template<class IndexT, class ValueT>
182idol::SparseVector<IndexT, ValueT>::operator-=(const SparseVector &t_vector) {
183
184 if (this == &t_vector) {
185 m_map.clear();
186 return *this;
187 }
188
189 for (const auto& [var, val] : t_vector.m_map) {
190 ValueT minus_val{};
191 minus_val -= val;
192 auto [it, inserted] = m_map.emplace(var, minus_val);
193 if (!inserted) {
194 IDOL_REF_VALUE(it) += std::move(minus_val);
195 if (::idol::is_zero(it->second, Tolerance::Sparsity)) {
196 m_map.erase(it);
197 }
198 }
199 }
200
201 return *this;
202}
203
204template<class IndexT, class ValueT>
206idol::SparseVector<IndexT, ValueT>::operator*=(std::conditional_t<std::is_arithmetic_v<ValueT>, ValueT, double> t_scalar) {
207
208 std::vector<IndexT> to_be_removed;
209 to_be_removed.reserve(m_map.size());
210
211 for (auto it = m_map.begin(), end = m_map.end() ; it != end ; ++it) {
212 IDOL_REF_VALUE(it) *= t_scalar;
213 if (::idol::is_zero(it->second, Tolerance::Sparsity)) {
214 to_be_removed.emplace_back(it->first);
215 }
216 }
217
218 for (const auto& index : to_be_removed) {
219 m_map.erase(index);
220 }
221
222 return *this;
223}
224
225template<class IndexT, class ValueT>
226bool idol::SparseVector<IndexT, ValueT>::is_zero(double t_tolerance) const {
227 for (const auto& [var, val] : m_map) {
228 if (!::idol::is_zero(val, t_tolerance)) {
229 return false;
230 }
231 }
232 return true;
233}
234
235template<class IndexT, class ValueT>
237idol::SparseVector<IndexT, ValueT>::operator+=(const SparseVector &t_vector) {
238
239 if (this == &t_vector) {
240 return operator*=(2.);
241 }
242
243 for (const auto& [var, val] : t_vector.m_map) {
244 auto [it, inserted] = m_map.emplace(var, val);
245 if (!inserted) {
246 IDOL_REF_VALUE(it) += val;
247 if (::idol::is_zero(it->second, Tolerance::Sparsity)) {
248 m_map.erase(it);
249 }
250 }
251 }
252
253 return *this;
254}
255
256template<class IndexT, class ValueT>
259
260 for (const auto& [var, val] : t_vec.m_map) {
261 auto [it, inserted] = m_map.emplace(var, val);
262 if (!inserted) {
263 throw Exception("Found conflict when explicitly merging without conflict.");
264 }
265 }
266
267 return *this;
268}
269
270template<class IndexT, class ValueT>
271const ValueT& idol::SparseVector<IndexT, ValueT>::get(const IndexT &t_index1) const {
272
273 const auto it = m_map.find(t_index1);
274
275 if (it == m_map.end()) {
276 return s_zero_value;
277 }
278
279 return it->second;
280}
281
282template<class IndexT, class ValueT>
283void idol::SparseVector<IndexT, ValueT>::set(const IndexT &t_index, const ValueT &t_value) {
284
285 if (::idol::is_zero(t_value, Tolerance::Sparsity)) {
286 remove(t_index);
287 return;
288 }
289
290 auto [it, inserted] = m_map.emplace(t_index, t_value);
291
292 if (!inserted) {
293 IDOL_REF_VALUE(it) = t_value;
294 }
295
296}
297
298namespace idol {
299
300 template<class IndexT, class ValueT>
301 static std::ostream & operator<<(std::ostream &t_stream, const idol::SparseVector<IndexT, ValueT> &t_vector) {
302
303 for (const auto& [index, value] : t_vector) {
304 t_stream << index << ": " << value << '\n';
305 }
306
307 return t_stream;
308 }
309
310 template<class IndexT, class ValueT>
311 SparseVector<IndexT, ValueT> operator+(SparseVector<IndexT, ValueT>&& t_x, const SparseVector<IndexT, ValueT>& t_y) {
312 return std::move(t_x) += t_y;
313 }
314
315 template<class IndexT, class ValueT>
316 SparseVector<IndexT, ValueT> operator+(const SparseVector<IndexT, ValueT>& t_x, SparseVector<IndexT, ValueT>&& t_y) {
317 return std::move(t_y) += t_x;
318 }
319
320 template<class IndexT, class ValueT>
321 SparseVector<IndexT, ValueT> operator+(const SparseVector<IndexT, ValueT>& t_x, const SparseVector<IndexT, ValueT>& t_y) {
322 return SparseVector(t_x) += t_y;
323 }
324
325 template<class IndexT, class ValueT>
326 SparseVector<IndexT, ValueT> operator-(SparseVector<IndexT, ValueT> t_x, const SparseVector<IndexT, ValueT>& t_y) {
327 return std::move(t_x) -= t_y;
328 }
329
330 template<class IndexT, class ValueT>
331 SparseVector<IndexT, ValueT> operator+(SparseVector<IndexT, ValueT> t_x, double t_factor) {
332 return std::move(t_x) *= t_factor;
333 }
334
335 template<class IndexT, class ValueT>
336 SparseVector<IndexT, ValueT> operator+(double t_factor, SparseVector<IndexT, ValueT> t_x) {
337 return std::move(t_x) *= t_factor;
338 }
339
340}
341
342#endif //IDOL_SPARSEVECTOR_H
static double Sparsity
Definition numericals.h:37