5#ifndef IDOL_SPARSEVECTOR_H
6#define IDOL_SPARSEVECTOR_H
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>
22 auto operator()(
const T& t_obj)
const {
return std::hash<unsigned int>()(t_obj.id()); }
26 struct equal_to_object {
27 auto operator()(
const T& t_a,
const T& t_b)
const {
return t_a.id() == t_b.id(); }
32 auto operator()(
const T& t_a,
const T& t_b)
const {
return t_a.id() < t_b.id(); }
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> {};
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> {};
47 template<
class,
class>
52#include <tsl/sparse_map.h>
53#include <tsl/ordered_map.h>
54#define IDOL_REF_VALUE(t_iterator) t_iterator.value()
56#ifdef IDOL_USE_ROBINHOOD
57#include <robin_hood.h>
58#define IDOL_REF_VALUE(t_iterator) t_iterator->second
61#define IDOL_REF_VALUE(t_iterator) t_iterator->second
65template<
class IndexT,
class ValueT>
69 using map_t = std::conditional_t<
71 tsl::sparse_map<IndexT, ValueT>,
72 tsl::ordered_map<IndexT, ValueT>
75 #ifdef IDOL_USE_ROBINHOOD
76 using map_t = robin_hood::unordered_map<IndexT, ValueT>;
78 using map_t = std::unordered_map<IndexT, ValueT>;
83 static ValueT s_zero_value;
87 SparseVector(
const IndexT& t_index,
const ValueT& t_value) : m_map({ { t_index, t_value} }) {
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);
105 [[nodiscard]]
unsigned int size()
const {
return m_map.size(); }
107 [[nodiscard]]
bool empty()
const {
return m_map.empty(); }
109 [[nodiscard]]
bool has_index(
const IndexT& t_index)
const {
return m_map.find(t_index) != m_map.end(); }
111 [[nodiscard]]
const ValueT& get(
const IndexT& t_index1)
const;
113 void set(
const IndexT& t_index,
const ValueT& t_value);
115 [[nodiscard]]
virtual bool is_zero(
double t_tolerance)
const;
117 void remove(
const IndexT& t_index) { m_map.erase(t_index); }
119 void clear() { m_map.clear(); }
121 void reserve(
unsigned int t_capacity) {
123 m_map.reserve(t_capacity);
127 using iterator =
typename map_t::iterator;
128 using const_iterator =
typename map_t::const_iterator;
130 [[nodiscard]] iterator begin() {
return m_map.begin(); }
132 [[nodiscard]] iterator end() {
return m_map.end(); }
134 [[nodiscard]] const_iterator begin()
const {
return m_map.cbegin(); }
136 [[nodiscard]] const_iterator end()
const {
return m_map.cend(); }
138 [[nodiscard]] const_iterator cbegin()
const {
return m_map.cbegin(); }
140 [[nodiscard]] const_iterator cend()
const {
return m_map.cend(); }
147template<
class IndexT,
class ValueT>
152 for (
const auto& [var, val] : m_map) {
153 result.m_map.emplace(var, -val);
159template<
class IndexT,
class ValueT>
163 std::vector<IndexT> to_be_removed;
164 to_be_removed.reserve(m_map.size());
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);
173 for (
const auto& index : to_be_removed) {
180template<
class IndexT,
class ValueT>
184 if (
this == &t_vector) {
189 for (
const auto& [var, val] : t_vector.m_map) {
192 auto [it, inserted] = m_map.emplace(var, minus_val);
194 IDOL_REF_VALUE(it) += std::move(minus_val);
195 if (::idol::is_zero(it->second, Tolerance::Sparsity)) {
204template<
class IndexT,
class ValueT>
208 std::vector<IndexT> to_be_removed;
209 to_be_removed.reserve(m_map.size());
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);
218 for (
const auto& index : to_be_removed) {
225template<
class IndexT,
class ValueT>
227 for (
const auto& [var, val] : m_map) {
228 if (!::idol::is_zero(val, t_tolerance)) {
235template<
class IndexT,
class ValueT>
239 if (
this == &t_vector) {
240 return operator*=(2.);
243 for (
const auto& [var, val] : t_vector.m_map) {
244 auto [it, inserted] = m_map.emplace(var, val);
246 IDOL_REF_VALUE(it) += val;
247 if (::idol::is_zero(it->second, Tolerance::Sparsity)) {
256template<
class IndexT,
class ValueT>
260 for (
const auto& [var, val] : t_vec.m_map) {
261 auto [it, inserted] = m_map.emplace(var, val);
263 throw Exception(
"Found conflict when explicitly merging without conflict.");
270template<
class IndexT,
class ValueT>
273 const auto it = m_map.find(t_index1);
275 if (it == m_map.end()) {
282template<
class IndexT,
class ValueT>
285 if (::idol::is_zero(t_value, Tolerance::Sparsity)) {
290 auto [it, inserted] = m_map.emplace(t_index, t_value);
293 IDOL_REF_VALUE(it) = t_value;
300 template<
class IndexT,
class ValueT>
303 for (
const auto& [index, value] : t_vector) {
304 t_stream << index <<
": " << value <<
'\n';
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;
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;
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;
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;
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;
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;