Debian Codegraph @

src/atlas/linalg/sparse/SparseMatrixTriplet.h

raw
1 /*
2 * (C) Crown Copyright 2025 Met Office
3 *
4 * This software is licensed under the terms of the Apache Licence Version 2.0
5 * which can be obtained at http://www.apache.org/licenses/LICENSE-2.0.
6 */
7
8 #pragma once
9
10 #include <algorithm>
11 #include <cstring>
12 #include <memory>
13 #include <tuple>
14 #include <type_traits>
15 #include <vector>
16
17 #include "atlas/linalg/sparse/SparseMatrixStorage.h"
18 #include "atlas/linalg/sparse/SparseMatrixView.h"
19
20 namespace atlas::linalg {
21
22 /// @brief A triplet which represents a non-zero entry in a sparse matrix.
23 template <typename Value, typename Index>
24 class Triplet {
25 static_assert(std::is_integral_v<Index>, "Index must be an integral type");
26
27 public:
28 Triplet() = default;
29 Triplet(Index row, Index column, Value value): row_{row}, column_{column}, value_{value} {}
30 Index row() const { return row_; }
31 Index col() const { return column_; }
32 Value value() const { return value_; }
33
34 /// @brief Less-than operator for sorting triplets.
35 bool operator<(const Triplet& other) const { return std::tie(row_, column_) < std::tie(other.row_, other.column_); }
36
37 private:
38 Index row_{};
39 Index column_{};
40 Value value_{};
41 };
42
43 namespace detail {
44 // SFINAE types/variables in place of C++20 concepts.
45 template <typename T>
46 struct is_triplet : std::false_type {};
47
48 template <typename Value, typename Index>
49 struct is_triplet<Triplet<Value, Index>> : std::true_type {};
50
51 template <typename Iter>
52 constexpr bool is_triplet_iterator = is_triplet<typename std::iterator_traits<Iter>::value_type>::value;
53
54 template <typename Iter>
55 constexpr bool is_random_access_iterator =
56 std::is_base_of_v<typename std::iterator_traits<Iter>::iterator_category, std::random_access_iterator_tag>;
57
58 template <typename Iter>
59 constexpr bool is_mutable_iterator =
60 !std::is_const_v<typename std::remove_reference_t<typename std::iterator_traits<Iter>::reference>>;
61
62 template <typename Iter>
63 constexpr bool is_sortable_iterator = is_random_access_iterator<Iter> && is_mutable_iterator<Iter>;
64 } // namespace detail
65
66 /// @brief Construct a SparseMatrixStorage from a range of triplets.
67 template <typename Iter>
68 std::enable_if_t<detail::is_triplet_iterator<Iter>, SparseMatrixStorage> make_sparse_matrix_storage_from_triplets(
69 std::size_t n_rows, std::size_t n_cols, Iter triplets_begin, Iter triplets_end) {
70 using TripletType = typename std::iterator_traits<Iter>::value_type;
71 using Index = decltype(std::declval<TripletType>().row());
72 using Value = decltype(std::declval<TripletType>().value());
73
74 const std::size_t n_non_zero = std::distance(triplets_begin, triplets_end);
75 auto outer_array = std::unique_ptr<array::Array>(array::Array::create<Index>(n_rows + 1));
76 auto inner_array = std::unique_ptr<array::Array>(array::Array::create<Index>(n_non_zero));
77 auto values_array = std::unique_ptr<array::Array>(array::Array::create<Value>(n_non_zero));
78 auto outer_view = array::make_view<Index, 1>(*outer_array);
79 auto inner_view = array::make_view<Index, 1>(*inner_array);
80 auto values_view = array::make_view<Value, 1>(*values_array);
81
82 std::size_t index = 0;
83 Iter triplet_iter = triplets_begin;
84 TripletType previous_triplet = *triplet_iter;
85 for (std::size_t row = 0; row < n_rows; ++row) {
86 outer_view(row) = index;
87 for (; triplet_iter != triplets_end && triplet_iter->row() == static_cast<Index>(row);
88 ++index, ++triplet_iter) {
89 ATLAS_ASSERT(!(triplet_iter->row() < previous_triplet.row()), "Triplets must be sorted per row.");
90 ATLAS_ASSERT(static_cast<std::size_t>(triplet_iter->col()) < n_cols, "Triplet column index out of bounds.");
91 inner_view(index) = triplet_iter->col();
92 values_view(index) = triplet_iter->value();
93 previous_triplet = *triplet_iter;
94 }
95 }
96 ATLAS_ASSERT(index == n_non_zero, "Triplet row index out of bounds.");
97 outer_view(n_rows) = n_non_zero;
98
99 return SparseMatrixStorage::make(n_rows, n_cols, n_non_zero, std::move(values_array), std::move(inner_array),
100 std::move(outer_array), std::any());
101 }
102
103 /// @brief Construct a SparseMatrixStorage from a random-access range of triplets, sorting if necessary.
104 template <typename Iter>
105 std::enable_if_t<detail::is_triplet_iterator<Iter> && detail::is_sortable_iterator<Iter>, SparseMatrixStorage>
106 make_sparse_matrix_storage_from_triplets(std::size_t n_rows, std::size_t n_cols, std::size_t n_non_zero,
107 Iter triplets_begin, bool is_sorted = false) {
108 if (!is_sorted) {
109 std::sort(triplets_begin, triplets_begin + n_non_zero);
110 }
111 return make_sparse_matrix_storage_from_triplets(n_rows, n_cols, triplets_begin, triplets_begin + n_non_zero);
112 }
113
114 /// @brief Construct a SparseMatrixStorage from a vector of triplets, sorting if necessary.
115 template <typename Value, typename Index>
116 SparseMatrixStorage make_sparse_matrix_storage_from_triplets(std::size_t n_rows, std::size_t n_cols,
117 std::vector<Triplet<Value, Index>>& triplets,
118 bool is_sorted = false) {
119 return make_sparse_matrix_storage_from_triplets(n_rows, n_cols, triplets.size(), triplets.begin(), is_sorted);
120 }
121
122 /// @brief For-each iteration over all non-zero triplets in row.
123 template <typename Value, typename Index, typename Functor>
124 std::enable_if_t<std::is_invocable_v<Functor, Index, Index, Value>> sparse_matrix_for_each_row(
125 std::size_t row, const SparseMatrixView<Value, Index>& matrix, Functor&& functor) {
126 const Index* outer = matrix.outer();
127 const Index* inner = matrix.inner();
128 const Value* values = matrix.value();
129
130 for (Index index = outer[row]; index < outer[row + 1]; ++index) {
131 const Index column = inner[index];
132 const Value value = values[index];
133 functor(static_cast<Index>(row), column, value);
134 }
135 }
136
137 /// @brief For-each iteration over all non-zero triplets in matrix.
138 template <typename Value, typename Index, typename Functor>
139 std::enable_if_t<std::is_invocable_v<Functor, Index, Index, Value>> sparse_matrix_for_each(
140 const SparseMatrixView<Value, Index>& matrix, Functor&& functor) {
141 for (std::size_t row = 0; row < matrix.rows(); ++row) {
142 sparse_matrix_for_each_row(row, matrix, functor);
143 }
144 }
145
146 } // namespace atlas::linalg