convert_to_compressed_sparse.hpp

Go to the documentation of this file.

#ifndef TATAMI_CONVERT_TO_COMPRESSED_SPARSE_H
#define TATAMI_CONVERT_TO_COMPRESSED_SPARSE_H
 
#include "CompressedSparseMatrix.hpp"
#include "convert_to_fragmented_sparse.hpp"
#include "../utils/parallelize.hpp"
#include "../utils/consecutive_extractor.hpp"
 
#include <memory>
#include <vector>
 
namespace tatami {
 
namespace convert_to_compressed_sparse_internal {
 
template<typename Value_, typename Index_, typename Count_>
void count_compressed_sparse_non_zeros_consistent(const tatami::Matrix<Value_, Index_>* matrix, Index_ primary, Index_ secondary, bool row, Count_* output, int threads) {
    if (matrix->is_sparse()) {
        Options opt;
        opt.sparse_extract_value = false;
        opt.sparse_extract_index = false;
        opt.sparse_ordered_index = false;
 
        parallelize([&](int, Index_ start, Index_ length) -> void {
            auto wrk = consecutive_extractor<true>(matrix, row, start, length, opt);
            for (Index_ x = 0; x < length; ++x) {
                auto range = wrk->fetch(NULL, NULL);
                output[start + x] = range.number;
            }
        }, primary, threads);
 
    } else {
        parallelize([&](int, Index_ start, Index_ length) -> void {
            std::vector<Value_> buffer_v(secondary);
            auto wrk = consecutive_extractor<false>(matrix, row, start, length);
            for (Index_ p = start, pe = start + length; p < pe; ++p) {
                auto ptr = wrk->fetch(buffer_v.data());
                Count_ count = 0;
                for (Index_ s = 0; s < secondary; ++s) {
                    count += (ptr[s] != 0);
                }
                output[p] = count;
            }
        }, primary, threads);
    }
}
 
template<typename Value_, typename Index_, typename Count_>
void count_compressed_sparse_non_zeros_inconsistent(const tatami::Matrix<Value_, Index_>* matrix, Index_ primary, Index_ secondary, bool row, Count_* output, int threads) {
    std::vector<std::vector<Count_> > nz_counts(threads - 1);
    for (auto& x : nz_counts) {
        x.resize(primary);
    }
 
    if (matrix->is_sparse()) {
        Options opt;
        opt.sparse_extract_value = false;
        opt.sparse_ordered_index = false;
 
        parallelize([&](int t, Index_ start, Index_ length) -> void {
            std::vector<Index_> buffer_i(primary);
            auto wrk = consecutive_extractor<true>(matrix, !row, start, length, opt);
            auto my_counts = (t > 0 ? nz_counts[t - 1].data() : output);
 
            for (Index_ x = 0; x < length; ++x) {
                auto range = wrk->fetch(NULL, buffer_i.data());
                for (Index_ i = 0; i < range.number; ++i) {
                    ++my_counts[range.index[i]];
                }
            }
        }, secondary, threads);
 
    } else {
        parallelize([&](int t, Index_ start, Index_ length) -> void {
            auto wrk = consecutive_extractor<false>(matrix, !row, start, length);
            std::vector<Value_> buffer_v(primary);
            auto my_counts = (t > 0 ? nz_counts[t - 1].data() : output);
 
            for (Index_ x = 0; x < length; ++x) {
                auto ptr = wrk->fetch(buffer_v.data());
                for (Index_ p = 0; p < primary; ++p) {
                    my_counts[p] += (ptr[p] != 0);
                }
            }
        }, secondary, threads);
    }
 
    for (auto& y : nz_counts) {
        for (Index_ p = 0; p < primary; ++p) {
            output[p] += y[p];
        }
    }
}
 
template<typename InputValue_, typename InputIndex_, typename Pointer_, typename StoredValue_, typename StoredIndex_>
void fill_compressed_sparse_matrix_consistent(
    const tatami::Matrix<InputValue_, InputIndex_>* matrix,
    InputIndex_ primary,
    InputIndex_ secondary,
    bool row,
    const Pointer_* pointers,
    StoredValue_* output_value,
    StoredIndex_* output_index,
    int threads)
{
    if (matrix->is_sparse()) {
        Options opt;
        opt.sparse_ordered_index = false;
 
        parallelize([&](int, InputIndex_ start, InputIndex_ length) -> void {
            std::vector<InputValue_> buffer_v(secondary);
            std::vector<InputIndex_> buffer_i(secondary);
            auto wrk = consecutive_extractor<true>(matrix, row, start, length, opt);
 
            for (InputIndex_ p = start, pe = start + length; p < pe; ++p) {
                // Resist the urge to `fetch()` straight into 'output_v'
                // and 'output_i', as implementations may assume that they
                // have the entire 'length' length to play with, and the
                // output vectors only have whatever is allocated from the
                // first pass (which might be nothing for an all-zero matrix).
                auto range = wrk->fetch(buffer_v.data(), buffer_i.data());
                auto offset = pointers[p];
                std::copy_n(range.value, range.number, output_value + offset);
                std::copy_n(range.index, range.number, output_index + offset);
            }
        }, primary, threads);
 
    } else {
        parallelize([&](int, InputIndex_ start, InputIndex_ length) -> void {
            std::vector<InputValue_> buffer_v(secondary);
            auto wrk = consecutive_extractor<false>(matrix, row, start, length);
 
            for (InputIndex_ p = start, pe = start + length; p < pe; ++p) {
                auto ptr = wrk->fetch(buffer_v.data());
                auto offset = pointers[p];
                for (InputIndex_ s = 0; s < secondary; ++s) {
                    auto val = ptr[s];
                    if (val != 0) {
                        output_value[offset] = val;
                        output_index[offset] = s;
                        ++offset;
                    }
                }
            }
        }, primary, threads);
    }
}
 
template<typename InputValue_, typename InputIndex_, typename Pointer_, typename StoredValue_, typename StoredIndex_>
void fill_compressed_sparse_matrix_inconsistent(
    const tatami::Matrix<InputValue_, InputIndex_>* matrix,
    InputIndex_ primary,
    InputIndex_ secondary,
    bool row,
    const Pointer_* pointers,
    StoredValue_* output_value,
    StoredIndex_* output_index,
    int threads)
{
    if (matrix->is_sparse()) {
        Options opt;
        opt.sparse_ordered_index = false;
 
        parallelize([&](int, InputIndex_ start, InputIndex_ length) -> void {
            std::vector<InputValue_> buffer_v(length);
            std::vector<InputIndex_> buffer_i(length);
            auto wrk = consecutive_extractor<true>(matrix, !row, static_cast<InputIndex_>(0), secondary, start, length, opt);
            std::vector<Pointer_> offset_copy(pointers + start, pointers + start + length);
 
            for (InputIndex_ x = 0; x < secondary; ++x) {
                auto range = wrk->fetch(buffer_v.data(), buffer_i.data());
                for (InputIndex_ i = 0; i < range.number; ++i) {
                    auto& pos = offset_copy[range.index[i] - start];
                    output_value[pos] = range.value[i];
                    output_index[pos] = x; 
                    ++pos;
                }
            }
        }, primary, threads);
 
    } else {
        parallelize([&](int, InputIndex_ start, InputIndex_ length) -> void {
            std::vector<InputValue_> buffer_v(length);
            auto wrk = consecutive_extractor<false>(matrix, !row, static_cast<InputIndex_>(0), secondary, start, length);
            std::vector<Pointer_> offset_copy(pointers + start, pointers + start + length);
 
            for (InputIndex_ x = 0; x < secondary; ++x) {
                auto ptr = wrk->fetch(buffer_v.data());
                for (InputIndex_ p = 0; p < length; ++p) {
                    auto val = ptr[p]; 
                    if (val != 0) {
                        auto& pos = offset_copy[p];
                        output_value[pos] = val;
                        output_index[pos] = x;
                        ++pos;
                    }
                }
            }
        }, primary, threads);
    }
}
 
}
template<typename Value_, typename Index_, typename Count_>
void count_compressed_sparse_non_zeros(const tatami::Matrix<Value_, Index_>* matrix, bool row, Count_* output, int threads) {
    Index_ NR = matrix->nrow();
    Index_ NC = matrix->ncol();
    Index_ primary = (row ? NR : NC);
    Index_ secondary = (row ? NC : NR);
    std::fill_n(output, primary, 0);
 
    if (row == matrix->prefer_rows()) {
        convert_to_compressed_sparse_internal::count_compressed_sparse_non_zeros_consistent(matrix, primary, secondary, row, output, threads);
    } else {
        convert_to_compressed_sparse_internal::count_compressed_sparse_non_zeros_inconsistent(matrix, primary, secondary, row, output, threads);
    }
}
 
template<typename InputValue_, typename InputIndex_, typename Pointer_, typename StoredValue_, typename StoredIndex_>
void fill_compressed_sparse_contents(
    const tatami::Matrix<InputValue_, InputIndex_>* matrix,
    bool row,
    const Pointer_* pointers,
    StoredValue_* output_value,
    StoredIndex_* output_index,
    int threads)
{
    InputIndex_ NR = matrix->nrow();
    InputIndex_ NC = matrix->ncol();
    InputIndex_ primary = (row ? NR : NC);
    InputIndex_ secondary = (row ? NC : NR);
 
    if (row == matrix->prefer_rows()) {
        convert_to_compressed_sparse_internal::fill_compressed_sparse_matrix_consistent(matrix, primary, secondary, row, pointers, output_value, output_index, threads);
    } else {
        convert_to_compressed_sparse_internal::fill_compressed_sparse_matrix_inconsistent(matrix, primary, secondary, row, pointers, output_value, output_index, threads);
    }
}
 
template<typename Value_, typename Index_, typename Pointer_ = size_t>
struct CompressedSparseContents {
    std::vector<Value_> value;
 
    std::vector<Index_> index;
 
    std::vector<Pointer_> pointers;
};
 
template<typename StoredValue_, typename StoredIndex_, typename StoredPointer_ = size_t, typename InputValue_, typename InputIndex_>
CompressedSparseContents<StoredValue_, StoredIndex_, StoredPointer_> retrieve_compressed_sparse_contents(const Matrix<InputValue_, InputIndex_>* matrix, bool row, bool two_pass, int threads = 1) {
    CompressedSparseContents<StoredValue_, StoredIndex_, StoredPointer_> output;
    auto& output_v = output.value;
    auto& output_i = output.index;
    auto& output_p = output.pointers;
 
    InputIndex_ NR = matrix->nrow();
    InputIndex_ NC = matrix->ncol();
    InputIndex_ primary = (row ? NR : NC);
    InputIndex_ secondary = (row ? NC : NR);
 
    if (!two_pass) {
        // Doing a single fragmented run and then concatenating everything together.
        auto frag = retrieve_fragmented_sparse_contents<InputValue_, InputIndex_>(matrix, row, threads);
        const auto& store_v = frag.value;
        const auto& store_i = frag.index;
 
        output_p.resize(static_cast<size_t>(primary) + 1);
        for (InputIndex_ p = 0; p < primary; ++p) {
            output_p[p + 1] = output_p[p] + store_v[p].size();
        }
 
        output_v.reserve(output_p.back());
        output_i.reserve(output_p.back());
        for (InputIndex_ p = 0; p < primary; ++p) {
            output_v.insert(output_v.end(), store_v[p].begin(), store_v[p].end());
            output_i.insert(output_i.end(), store_i[p].begin(), store_i[p].end());
        }
 
    } else if (row == matrix->prefer_rows()) {
        // First pass to figure out how many non-zeros there are.
        output_p.resize(static_cast<size_t>(primary) + 1);
        convert_to_compressed_sparse_internal::count_compressed_sparse_non_zeros_consistent(matrix, primary, secondary, row, output_p.data() + 1, threads);
        for (InputIndex_ i = 1; i <= primary; ++i) {
            output_p[i] += output_p[i - 1];
        }
 
        // Second pass to actually fill our vectors.
        output_v.resize(output_p.back());
        output_i.resize(output_p.back());
        convert_to_compressed_sparse_internal::fill_compressed_sparse_matrix_consistent(
            matrix,
            primary,
            secondary,
            row,
            output_p.data(),
            output_v.data(),
            output_i.data(),
            threads
        );
 
    } else {
        // First pass to figure out how many non-zeros there are.
        output_p.resize(static_cast<size_t>(primary) + 1);
        convert_to_compressed_sparse_internal::count_compressed_sparse_non_zeros_inconsistent(matrix, primary, secondary, row, output_p.data() + 1, threads);
        for (InputIndex_ i = 1; i <= primary; ++i) {
            output_p[i] += output_p[i - 1];
        }
 
        // Second pass to actually fill our vectors.
        output_v.resize(output_p.back());
        output_i.resize(output_p.back());
        convert_to_compressed_sparse_internal::fill_compressed_sparse_matrix_inconsistent(
            matrix,
            primary,
            secondary,
            row,
            output_p.data(),
            output_v.data(),
            output_i.data(),
            threads
        );
    }
 
    return output;
}
 
template<
    typename Value_ = double,
    typename Index_ = int,
    typename StoredValue_ = Value_,
    typename StoredIndex_ = Index_,
    typename InputValue_,
    typename InputIndex_
>
std::shared_ptr<Matrix<Value_, Index_> > convert_to_compressed_sparse(const Matrix<InputValue_, InputIndex_>* matrix, bool row, bool two_pass = false, int threads = 1) {
    auto comp = retrieve_compressed_sparse_contents<StoredValue_, StoredIndex_>(matrix, row, two_pass, threads);
    return std::shared_ptr<Matrix<Value_, Index_> >(
        new CompressedSparseMatrix<
            Value_, 
            Index_,
            std::vector<StoredValue_>,
            std::vector<StoredIndex_>,
            std::vector<size_t>
        >(
            matrix->nrow(), 
            matrix->ncol(), 
            std::move(comp.value), 
            std::move(comp.index), 
            std::move(comp.pointers),
            row,
            false // no need for checks, as we guarantee correctness.
        )
    );
}
 
// Backwards compatbility.
template <bool row_, typename Value_, typename Index_, typename InputValue_, typename InputIndex_>
CompressedSparseContents<Value_, Index_> retrieve_compressed_sparse_contents(const Matrix<InputValue_, InputIndex_>* matrix, bool two_pass, int threads = 1) {
    return retrieve_compressed_sparse_contents<Value_, Index_>(matrix, row_, two_pass, threads);
}
 
template <bool row_, typename Value_, typename Index_, typename StoredValue_ = Value_, typename StoredIndex_ = Index_, typename InputValue_, typename InputIndex_>
std::shared_ptr<Matrix<Value_, Index_> > convert_to_compressed_sparse(const Matrix<InputValue_, InputIndex_>* matrix, bool two_pass = false, int threads = 1) {
    return convert_to_compressed_sparse<Value_, Index_, StoredValue_, StoredIndex_>(matrix, row_, two_pass, threads);
}
}
 
#endif