1#ifndef TATAMI_DELAYED_SUBSET_SORTED_HPP
2#define TATAMI_DELAYED_SUBSET_SORTED_HPP
6#include "../utils/Index_to_container.hpp"
12#include "sanisizer/sanisizer.hpp"
27namespace DelayedSubsetSorted_internal {
29template<
typename Index_>
30struct DenseParallelResults {
31 std::vector<Index_> collapsed;
32 std::vector<Index_> expansion;
35template<
typename Index_,
class SubsetStorage_,
class ToIndex_>
36DenseParallelResults<Index_> format_dense_parallel(
const SubsetStorage_& indices, Index_ len, ToIndex_ to_index) {
37 DenseParallelResults<Index_> output;
38 output.expansion.reserve(len);
39 output.collapsed.reserve(len);
42 auto last = indices[to_index(0)];
43 output.expansion.push_back(1);
44 output.collapsed.push_back(last);
46 for (Index_ i = 1; i < len; ++i) {
47 auto current = indices[to_index(i)];
48 if (current == last) {
49 ++(output.expansion.back());
52 output.expansion.push_back(1);
53 output.collapsed.push_back(last);
61template<
bool oracle_,
typename Value_,
typename Index_>
62class ParallelDense final :
public DenseExtractor<oracle_, Value_, Index_> {
64 template<
class SubsetStorage_>
65 ParallelDense(
const Matrix<Value_, Index_>* matrix,
const SubsetStorage_& subset,
bool row, MaybeOracle<oracle_, Index_> oracle,
const Options& opt) {
66 auto processed = format_dense_parallel<Index_>(subset, subset.size(), [&](Index_ i) -> Index_ { return i; });
67 initialize(matrix, std::move(processed), subset.size(), row, std::move(oracle), opt);
70 template<
class SubsetStorage_>
71 ParallelDense(
const Matrix<Value_, Index_>* matrix,
const SubsetStorage_& subset,
bool row, MaybeOracle<oracle_, Index_> oracle, Index_ block_start, Index_ block_length,
const Options& opt) {
72 auto processed = format_dense_parallel<Index_>(subset, block_length, [&](Index_ i) -> Index_ {
return i + block_start; });
73 initialize(matrix, std::move(processed), block_length, row, std::move(oracle), opt);
76 template<
class SubsetStorage_>
77 ParallelDense(
const Matrix<Value_, Index_>* matrix,
const SubsetStorage_& subset,
bool row, MaybeOracle<oracle_, Index_> oracle, VectorPtr<Index_> indices_ptr,
const Options& opt) {
78 const auto& indices = *indices_ptr;
79 auto processed = format_dense_parallel<Index_>(subset, indices.size(), [&](Index_ i) -> Index_ { return indices[i]; });
80 initialize(matrix, std::move(processed), indices.size(), row, std::move(oracle), opt);
84 void initialize(
const Matrix<Value_, Index_>* mat, DenseParallelResults<Index_> processed, Index_ extent,
bool row, MaybeOracle<oracle_, Index_> oracle,
const Options& opt) {
85 my_shift = extent - processed.collapsed.size();
86 my_ext = new_extractor<false, oracle_>(mat, row, std::move(oracle), std::move(processed.collapsed), opt);
87 my_expansion = std::move(processed.expansion);
91 const Value_* fetch(Index_ i, Value_* buffer) {
92 auto input = my_ext->fetch(i, buffer + my_shift);
102 for (
auto e : my_expansion) {
111 std::fill_n(copy, e, val);
120 std::unique_ptr<DenseExtractor<oracle_, Value_, Index_> > my_ext;
121 std::vector<Index_> my_expansion;
125template<
typename Index_>
126struct SparseParallelExpansion {
135 std::vector<Index_> start;
136 std::vector<Index_> length;
141template<
typename Index_>
142struct SparseParallelResults {
143 std::vector<Index_> collapsed;
144 SparseParallelExpansion<Index_> expansion;
147template<
typename Index_,
class SubsetStorage_,
class ToIndex_>
148SparseParallelResults<Index_> format_sparse_parallel(
const SubsetStorage_& indices, Index_ len, ToIndex_ to_index) {
149 SparseParallelResults<Index_> output;
152 output.collapsed.reserve(len);
153 auto first = indices[to_index(0)];
159 output.expansion.offset = first;
160 Index_ allocation = indices[to_index(len - 1)] - output.expansion.offset + 1;
162 output.expansion.length.resize(output.expansion.start.size());
165 output.expansion.start[0] = 0;
166 output.expansion.length[0] = 1;
167 output.collapsed.push_back(first);
170 for (Index_ i = 1; i < len; ++i) {
171 auto current = indices[to_index(i)];
172 if (current == last) {
173 ++(output.expansion.length[lookup]);
177 lookup = current - output.expansion.offset;
178 output.expansion.start[lookup] = i;
179 output.expansion.length[lookup] = 1;
180 output.collapsed.push_back(current);
188template<
bool oracle_,
typename Value_,
typename Index_>
189class ParallelSparseCore {
191 template<
class SubsetStorage_,
class ToIndex_>
192 ParallelSparseCore(
const Matrix<Value_, Index_>* matrix,
const SubsetStorage_& subset, Index_ extent,
bool row, MaybeOracle<oracle_, Index_> oracle, Options opt, ToIndex_ to_index) {
193 auto processed = format_sparse_parallel<Index_>(subset, extent, std::forward<ToIndex_>(to_index));
194 my_shift = extent - processed.collapsed.size();
196 my_needs_value = opt.sparse_extract_value;
197 my_needs_index = opt.sparse_extract_index;
198 opt.sparse_extract_index =
true;
199 if (!my_needs_index) {
204 my_ext = new_extractor<true, oracle_>(matrix, row, std::move(oracle), std::move(processed.collapsed), opt);
205 my_expansion = std::move(processed.expansion);
208 template<
class ToIndex_>
209 SparseRange<Value_, Index_> fetch(Index_ i, Value_* value_buffer, Index_* index_buffer, ToIndex_ to_index) {
212 auto vinit = (my_needs_value ? value_buffer + my_shift : NULL);
213 auto iinit = (my_needs_index ? index_buffer + my_shift : my_holding_ibuffer.data());
214 auto input = my_ext->fetch(i, vinit, iinit);
216 auto vcopy = value_buffer;
217 auto icopy = index_buffer;
220 auto vsrc = input.value;
221 bool replace_value = my_needs_value && vsrc != vcopy;
230 for (Index_ i = 0; i < input.number; ++i) {
231 auto eindex = input.index[i] - my_expansion.offset;
232 auto nexpand = my_expansion.length[eindex];
237 std::fill_n(vcopy, nexpand, v);
240 replace_value = (vcopy != vsrc);
243 if (my_needs_index) {
244 auto sexpand = my_expansion.start[eindex];
245 for (Index_ e = 0; e < nexpand; ++e, ++icopy) {
246 *icopy = to_index(sexpand + e);
251 return SparseRange<Value_, Index_>(
253 (my_needs_value ? value_buffer : NULL),
254 (my_needs_index ? index_buffer : NULL)
259 bool my_needs_value, my_needs_index;
260 std::unique_ptr<SparseExtractor<oracle_, Value_, Index_> > my_ext;
261 std::vector<Index_> my_holding_ibuffer;
262 SparseParallelExpansion<Index_> my_expansion;
266template<
bool oracle_,
typename Value_,
typename Index_>
267class ParallelFullSparse final :
public SparseExtractor<oracle_, Value_, Index_> {
269 template<
class SubsetStorage_>
270 ParallelFullSparse(
const Matrix<Value_, Index_>* matrix,
const SubsetStorage_& subset,
bool row, MaybeOracle<oracle_, Index_> oracle,
const Options& opt) :
271 my_core(matrix, subset, subset.size(), row, std::move(oracle), opt, [](Index_ i) -> Index_ { return i; }) {}
273 SparseRange<Value_, Index_> fetch(Index_ i, Value_* value_buffer, Index_* index_buffer) {
274 return my_core.fetch(i, value_buffer, index_buffer, [](Index_ i) -> Index_ {
return i; });
278 ParallelSparseCore<oracle_, Value_, Index_> my_core;
281template<
bool oracle_,
typename Value_,
typename Index_>
282class ParallelBlockSparse final :
public SparseExtractor<oracle_, Value_, Index_> {
284 template<
class SubsetStorage_>
285 ParallelBlockSparse(
const Matrix<Value_, Index_>* matrix,
const SubsetStorage_& subset,
bool row, MaybeOracle<oracle_, Index_> oracle, Index_ block_start, Index_ block_length,
const Options& opt) :
286 my_core(matrix, subset, block_length, row, std::move(oracle), opt, [&](Index_ i) -> Index_ { return i + block_start; }),
287 my_block_start(block_start)
290 SparseRange<Value_, Index_> fetch(Index_ i, Value_* value_buffer, Index_* index_buffer) {
291 return my_core.fetch(i, value_buffer, index_buffer, [&](Index_ i) -> Index_ {
return i + my_block_start; });
295 ParallelSparseCore<oracle_, Value_, Index_> my_core;
296 Index_ my_block_start;
299template<
bool oracle_,
typename Value_,
typename Index_>
300class ParallelIndexSparse final :
public SparseExtractor<oracle_, Value_, Index_> {
302 template<
class SubsetStorage_>
303 ParallelIndexSparse(
const Matrix<Value_, Index_>* matrix,
const SubsetStorage_& subset,
bool row, MaybeOracle<oracle_, Index_> oracle, VectorPtr<Index_> indices_ptr,
const Options& opt) :
304 my_core(matrix, subset, indices_ptr->size(), row, std::move(oracle), opt, [&](Index_ i) -> Index_ { return indices_ptr->operator[](i); }),
305 my_indices_ptr(std::move(indices_ptr))
308 SparseRange<Value_, Index_> fetch(Index_ i, Value_* value_buffer, Index_* index_buffer) {
309 const auto& indices = *my_indices_ptr;
310 return my_core.fetch(i, value_buffer, index_buffer, [&](Index_ i) -> Index_ {
return indices[i]; });
314 ParallelSparseCore<oracle_, Value_, Index_> my_core;
315 VectorPtr<Index_> my_indices_ptr;
334template<
typename Value_,
typename Index_,
class SubsetStorage_>
346 my_matrix(std::move(matrix)), my_subset(std::move(subset)), my_by_row(by_row)
348 sanisizer::can_cast<Index_>(my_subset.size());
350 for (Index_ i = 1, end = my_subset.size(); i < end; ++i) {
351 if (my_subset[i] < my_subset[i-1]) {
352 throw std::runtime_error(
"my_subset should be sorted");
359 std::shared_ptr<const Matrix<Value_, Index_> > my_matrix;
360 SubsetStorage_ my_subset;
363 Index_ get_mapping_dim()
const {
365 return my_matrix->nrow();
367 return my_matrix->ncol();
374 return my_subset.size();
376 return my_matrix->nrow();
382 return my_matrix->ncol();
384 return my_subset.size();
389 return my_matrix->is_sparse();
393 return my_matrix->is_sparse_proportion();
397 return my_matrix->prefer_rows();
401 return my_matrix->prefer_rows_proportion();
405 return my_matrix->uses_oracle(row);
408 using Matrix<Value_, Index_>::dense_column;
410 using Matrix<Value_, Index_>::dense_row;
412 using Matrix<Value_, Index_>::sparse_column;
414 using Matrix<Value_, Index_>::sparse_row;
420 template<
typename ... Args_>
421 std::unique_ptr<MyopicDenseExtractor<Value_, Index_> > populate_myopic_dense(
bool row, Args_&& ... args)
const {
422 if (row == my_by_row) {
423 return std::make_unique<subset_utils::MyopicPerpendicularDense<Value_, Index_, SubsetStorage_> >(my_matrix.get(), my_subset, row, std::forward<Args_>(args)...);
425 return std::make_unique<DelayedSubsetSorted_internal::ParallelDense<false, Value_, Index_> >(my_matrix.get(), my_subset, row,
false, std::forward<Args_>(args)...);
430 std::unique_ptr<MyopicDenseExtractor<Value_, Index_> >
dense(
bool row,
const Options& opt)
const {
431 return populate_myopic_dense(row, opt);
434 std::unique_ptr<MyopicDenseExtractor<Value_, Index_> >
dense(
bool row, Index_ block_start, Index_ block_length,
const Options& opt)
const {
435 return populate_myopic_dense(row, block_start, block_length, opt);
439 return populate_myopic_dense(row, std::move(indices_ptr), opt);
447 std::unique_ptr<SparseExtractor<oracle_, Value_, Index_> > populate_sparse(
bool row,
MaybeOracle<oracle_, Index_> oracle, Args_&& ... args)
const {
448 if constexpr(selection_ == DimensionSelectionType::FULL) {
449 return std::make_unique<DelayedSubsetSorted_internal::ParallelFullSparse<oracle_, Value_, Index_> >(my_matrix.get(), my_subset, row, std::move(oracle), std::forward<Args_>(args)...);
450 }
else if constexpr(selection_ == DimensionSelectionType::BLOCK) {
451 return std::make_unique<DelayedSubsetSorted_internal::ParallelBlockSparse<oracle_, Value_, Index_> >(my_matrix.get(), my_subset, row, std::move(oracle), std::forward<Args_>(args)...);
453 return std::make_unique<DelayedSubsetSorted_internal::ParallelIndexSparse<oracle_, Value_, Index_> >(my_matrix.get(), my_subset, row, std::move(oracle), std::forward<Args_>(args)...);
458 std::unique_ptr<MyopicSparseExtractor<Value_, Index_> > populate_myopic_sparse(
bool row, Args_&& ... args)
const {
459 if (row == my_by_row) {
460 return std::make_unique<subset_utils::MyopicPerpendicularSparse<Value_, Index_, SubsetStorage_> >(my_matrix.get(), my_subset, row, std::forward<Args_>(args)...);
462 return populate_sparse<selection_, false>(row,
false, std::forward<Args_>(args)...);
467 std::unique_ptr<MyopicSparseExtractor<Value_, Index_> >
sparse(
bool row,
const Options& opt)
const {
468 return populate_myopic_sparse<DimensionSelectionType::FULL>(row, opt);
471 std::unique_ptr<MyopicSparseExtractor<Value_, Index_> >
sparse(
bool row, Index_ block_start, Index_ block_length,
const Options& opt)
const {
472 return populate_myopic_sparse<DimensionSelectionType::BLOCK>(row, block_start, block_length, opt);
476 return populate_myopic_sparse<DimensionSelectionType::INDEX>(row, std::move(indices_ptr), opt);
483 template<
typename ... Args_>
484 std::unique_ptr<OracularDenseExtractor<Value_, Index_> > populate_oracular_dense(
bool row, std::shared_ptr<
const Oracle<Index_> > oracle, Args_&& ... args)
const {
485 if (row == my_by_row) {
486 return std::make_unique<subset_utils::OracularPerpendicularDense<Value_, Index_> >(my_matrix.get(), my_subset, row, std::move(oracle), std::forward<Args_>(args)...);
488 return std::make_unique<DelayedSubsetSorted_internal::ParallelDense<true, Value_, Index_> >(my_matrix.get(), my_subset, row, std::move(oracle), std::forward<Args_>(args)...);
493 std::unique_ptr<OracularDenseExtractor<Value_, Index_> >
dense(
bool row, std::shared_ptr<
const Oracle<Index_> > oracle,
const Options& opt)
const {
494 return populate_oracular_dense(row, std::move(oracle), opt);
497 std::unique_ptr<OracularDenseExtractor<Value_, Index_> >
dense(
bool row, std::shared_ptr<
const Oracle<Index_> > oracle, Index_ block_start, Index_ block_length,
const Options& opt)
const {
498 return populate_oracular_dense(row, std::move(oracle), block_start, block_length, opt);
502 return populate_oracular_dense(row, std::move(oracle), std::move(indices_ptr), opt);
510 std::unique_ptr<OracularSparseExtractor<Value_, Index_> > populate_oracular_sparse(
bool row, std::shared_ptr<
const Oracle<Index_> > oracle, Args_&& ... args)
const {
511 if (row == my_by_row) {
512 return std::make_unique<subset_utils::OracularPerpendicularSparse<Value_, Index_> >(my_matrix.get(), my_subset, row, std::move(oracle), std::forward<Args_>(args)...);
514 return populate_sparse<selection_, true>(row, std::move(oracle), std::forward<Args_>(args)...);
519 std::unique_ptr<OracularSparseExtractor<Value_, Index_> >
sparse(
bool row, std::shared_ptr<
const Oracle<Index_> > oracle,
const Options& opt)
const {
520 return populate_oracular_sparse<DimensionSelectionType::FULL>(row, std::move(oracle), opt);
523 std::unique_ptr<OracularSparseExtractor<Value_, Index_> >
sparse(
bool row, std::shared_ptr<
const Oracle<Index_> > oracle, Index_ block_start, Index_ block_length,
const Options& opt)
const {
524 return populate_oracular_sparse<DimensionSelectionType::BLOCK>(row, std::move(oracle), block_start, block_length, opt);
528 return populate_oracular_sparse<DimensionSelectionType::INDEX>(row, std::move(oracle), std::move(indices_ptr), opt);
Virtual class for a matrix of some numeric type.
Delayed subsetting of a matrix with sorted indices.
Definition DelayedSubsetSorted.hpp:335
std::unique_ptr< OracularDenseExtractor< Value_, Index_ > > dense(bool row, std::shared_ptr< const Oracle< Index_ > > oracle, Index_ block_start, Index_ block_length, const Options &opt) const
Definition DelayedSubsetSorted.hpp:497
double prefer_rows_proportion() const
Definition DelayedSubsetSorted.hpp:400
Index_ nrow() const
Definition DelayedSubsetSorted.hpp:372
bool prefer_rows() const
Definition DelayedSubsetSorted.hpp:396
DelayedSubsetSorted(std::shared_ptr< const Matrix< Value_, Index_ > > matrix, SubsetStorage_ subset, bool by_row, bool check=true)
Definition DelayedSubsetSorted.hpp:345
std::unique_ptr< OracularDenseExtractor< Value_, Index_ > > dense(bool row, std::shared_ptr< const Oracle< Index_ > > oracle, VectorPtr< Index_ > indices_ptr, const Options &opt) const
Definition DelayedSubsetSorted.hpp:501
double is_sparse_proportion() const
Definition DelayedSubsetSorted.hpp:392
bool is_sparse() const
Definition DelayedSubsetSorted.hpp:388
std::unique_ptr< MyopicSparseExtractor< Value_, Index_ > > sparse(bool row, Index_ block_start, Index_ block_length, const Options &opt) const
Definition DelayedSubsetSorted.hpp:471
std::unique_ptr< MyopicDenseExtractor< Value_, Index_ > > dense(bool row, Index_ block_start, Index_ block_length, const Options &opt) const
Definition DelayedSubsetSorted.hpp:434
std::unique_ptr< MyopicSparseExtractor< Value_, Index_ > > sparse(bool row, VectorPtr< Index_ > indices_ptr, const Options &opt) const
Definition DelayedSubsetSorted.hpp:475
std::unique_ptr< OracularSparseExtractor< Value_, Index_ > > sparse(bool row, std::shared_ptr< const Oracle< Index_ > > oracle, Index_ block_start, Index_ block_length, const Options &opt) const
Definition DelayedSubsetSorted.hpp:523
bool uses_oracle(bool row) const
Definition DelayedSubsetSorted.hpp:404
std::unique_ptr< MyopicDenseExtractor< Value_, Index_ > > dense(bool row, const Options &opt) const
Definition DelayedSubsetSorted.hpp:430
std::unique_ptr< OracularDenseExtractor< Value_, Index_ > > dense(bool row, std::shared_ptr< const Oracle< Index_ > > oracle, const Options &opt) const
Definition DelayedSubsetSorted.hpp:493
std::unique_ptr< OracularSparseExtractor< Value_, Index_ > > sparse(bool row, std::shared_ptr< const Oracle< Index_ > > oracle, const Options &opt) const
Definition DelayedSubsetSorted.hpp:519
std::unique_ptr< MyopicDenseExtractor< Value_, Index_ > > dense(bool row, VectorPtr< Index_ > indices_ptr, const Options &opt) const
Definition DelayedSubsetSorted.hpp:438
std::unique_ptr< OracularSparseExtractor< Value_, Index_ > > sparse(bool row, std::shared_ptr< const Oracle< Index_ > > oracle, VectorPtr< Index_ > indices_ptr, const Options &opt) const
Definition DelayedSubsetSorted.hpp:527
std::unique_ptr< MyopicSparseExtractor< Value_, Index_ > > sparse(bool row, const Options &opt) const
Definition DelayedSubsetSorted.hpp:467
Index_ ncol() const
Definition DelayedSubsetSorted.hpp:380
Virtual class for a matrix.
Definition Matrix.hpp:59
Predict future access requests on the target dimension.
Definition Oracle.hpp:29
Flexible representations for matrix data.
Definition Extractor.hpp:15
DimensionSelectionType
Definition Options.hpp:25
std::shared_ptr< const std::vector< Index_ > > VectorPtr
Definition Matrix.hpp:26
void resize_container_to_Index_size(Container_ &container, Index_ x)
Definition Index_to_container.hpp:86
typename std::conditional< oracle_, std::shared_ptr< const Oracle< Index_ > >, bool >::type MaybeOracle
Definition new_extractor.hpp:20
typename std::conditional< oracle_, OracularDenseExtractor< Value_, Index_ >, MyopicDenseExtractor< Value_, Index_ > >::type DenseExtractor
Definition Extractor.hpp:273
Options for accessing data from a Matrix instance.
Definition Options.hpp:30