monolish  0.14.0
MONOlithic LIner equation Solvers for Highly-parallel architecture
at_insert_sort_coo.cpp
Go to the documentation of this file.
1 #include "../../../include/common/monolish_dense.hpp"
2 #include "../../../include/common/monolish_logger.hpp"
3 #include "../../../include/common/monolish_matrix.hpp"
4 #include "../../internal/monolish_internal.hpp"
5 
6 namespace monolish {
7 namespace matrix {
8 
9 template <typename T> T COO<T>::at(const size_t i, const size_t j) const {
10 
11  assert(i <= get_row());
12  assert(j <= get_col());
13 
14  // since last inserted element is effective elements,
15  // checking from last element is necessary
16  if (nnz != 0) {
17  for (size_t k = nnz; k > 0; --k) {
18  if (row_index[k - 1] == (int)i && col_index[k - 1] == (int)j) {
19  return val[k - 1];
20  }
21  }
22  }
23  return 0.0;
24 }
25 template double COO<double>::at(const size_t i, const size_t j) const;
26 template float COO<float>::at(const size_t i, const size_t j) const;
27 
28 // insert //
29 template <typename T>
30 void COO<T>::insert(const size_t m, const size_t n, const T value) {
31  size_t rownum = m;
32  size_t colnum = n;
33  assert(rownum <= get_row());
34  assert(colnum <= get_col());
35 
36  row_index.push_back(rownum);
37  col_index.push_back(colnum);
38  val.push_back(value);
39  ++nnz;
40 }
41 template void COO<double>::insert(const size_t m, const size_t n,
42  const double value);
43 template void COO<float>::insert(const size_t m, const size_t n,
44  const float value);
45 
46 // sort //
47 
48 template <typename T> void COO<T>::_q_sort(int lo, int hi) {
49  // Very primitive quick sort
50  if (lo >= hi) {
51  return;
52  }
53 
54  int l = lo;
55  int h = hi;
56  int p = hi;
57  int p1 = row_index[p];
58  int p2 = col_index[p];
59  double p3 = val[p];
60 
61  do {
62  while ((l < h) && ((row_index[l] != row_index[p])
63  ? (row_index[l] - row_index[p])
64  : (col_index[l] - col_index[p])) <= 0) {
65  l = l + 1;
66  }
67  while ((h > l) && ((row_index[h] != row_index[p])
68  ? (row_index[h] - row_index[p])
69  : (col_index[h] - col_index[p])) >= 0) {
70  h = h - 1;
71  }
72  if (l < h) {
73  int t = row_index[l];
74  row_index[l] = row_index[h];
75  row_index[h] = t;
76 
77  t = col_index[l];
78  col_index[l] = col_index[h];
79  col_index[h] = t;
80 
81  double td = val[l];
82  val[l] = val[h];
83  val[h] = td;
84  }
85  } while (l < h);
86 
87  row_index[p] = row_index[l];
88  row_index[l] = p1;
89 
90  col_index[p] = col_index[l];
91  col_index[l] = p2;
92 
93  val[p] = val[l];
94  val[l] = p3;
95 
96  /* Sort smaller array first for less stack usage */
97  if (l - lo < hi - l) {
98  _q_sort(lo, l - 1);
99  _q_sort(l + 1, hi);
100  } else {
101  _q_sort(l + 1, hi);
102  _q_sort(lo, l - 1);
103  }
104 }
105 template void COO<double>::_q_sort(int lo, int hi);
106 template void COO<float>::_q_sort(int lo, int hi);
107 
108 template <typename T> void COO<T>::sort(bool merge) {
109  // Sort by first Col and then Row
110  // TODO: This hand-written quick sort function should be retired
111  // after zip_iterator() (available in range-v3 library) is available in
112  // the standard (hopefully C++23)
113  Logger &logger = Logger::get_instance();
114  logger.util_in(monolish_func);
115 
116  _q_sort(0, nnz - 1);
117 
118  /* Remove duplicates */
119  if (merge) {
120  size_t k = 0;
121  for (size_t i = 1; i < nnz; i++) {
122  if ((row_index[k] != row_index[i]) || (col_index[k] != col_index[i])) {
123  k++;
124  row_index[k] = row_index[i];
125  col_index[k] = col_index[i];
126  }
127  val[k] = val[i];
128  }
129  nnz = k + 1;
130  }
131 
132  logger.util_out();
133 }
134 template void COO<double>::sort(bool merge);
135 template void COO<float>::sort(bool merge);
136 
137 } // namespace matrix
138 } // namespace monolish
monolish_func
#define monolish_func
Definition: monolish_logger.hpp:9
monolish::Logger
logger class (singleton, for developper class)
Definition: monolish_logger.hpp:19
monolish::matrix::COO::insert
void insert(const size_t m, const size_t n, const Float val)
insert element to (m, n)
Definition: at_insert_sort_coo.cpp:30
monolish::Logger::util_out
void util_out()
Definition: logger_utils.cpp:123
monolish::matrix::COO::sort
void sort(bool merge)
sort COO matrix elements (and merge elements)
Definition: at_insert_sort_coo.cpp:108
monolish::Logger::util_in
void util_in(const std::string func_name)
Definition: logger_utils.cpp:113
monolish
Definition: monolish_matrix_blas.hpp:9
monolish::matrix::COO::at
Float at(const size_t i, const size_t j) const
Get matrix element (A(i,j))
Definition: at_insert_sort_coo.cpp:9
monolish::matrix::COO::_q_sort
void _q_sort(int lo, int hi)
Definition: at_insert_sort_coo.cpp:48
monolish::Logger::get_instance
static Logger & get_instance()
Definition: monolish_logger.hpp:42