matrixindexset.hh

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root
// SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
// vi: set et ts=4 sw=2 sts=2:
#ifndef DUNE_ISTL_MATRIXINDEXSET_HH
#define DUNE_ISTL_MATRIXINDEXSET_HH

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <set>
#include <variant>
#include <vector>

#include <dune/common/overloadset.hh>

namespace Dune {

  namespace Impl {

    class RowIndexSet {
      using Index = std::uint_least32_t;
      class Vector : public std::vector<Index> {
        // store max size within class so that variant uses less memory
        size_type maxVectorSize_;
        friend class RowIndexSet;
      };

      static Index getMaxVectorSize(const RowIndexSet::Vector& v) {
        return v.maxVectorSize_;
      }

    public:
      using size_type = Index;

      static constexpr size_type defaultMaxVectorSize = 2048;

      RowIndexSet(size_type maxVectorSize = defaultMaxVectorSize) : storage_{Vector()}
      {
        std::get<Vector>(storage_).maxVectorSize_ = maxVectorSize;
      }

      void insert(size_type col){
        std::visit(Dune::overload(
          // If row is stored as set, call insert directly
          [&](std::set<size_type>& set) {
            set.insert(col);
          },
          // If row is stored as vector only insert directly
          // if maxVectorSize_ is not reached. Otherwise switch
          // to set storage first.
          [&](Vector& sortedVector) {
            auto it = std::lower_bound(sortedVector.cbegin(), sortedVector.cend(), col);
            if (it == sortedVector.cend() or (*it != col)) {
              if (sortedVector.size() < getMaxVectorSize(sortedVector)) {
                sortedVector.insert(it, col);
              } else {
                std::set<size_type> set(sortedVector.cbegin(), sortedVector.cend());
                set.insert(col);
                storage_ = std::move(set);
              }
            }
          }
        ), storage_);
      }

      bool contains(const Index& col) const {
        return std::visit(Dune::overload(
          [&](const std::set<Index>& set) {
            return set.contains(col);
          },
          [&](const std::vector<Index>& sortedVector) {
            return std::binary_search(sortedVector.cbegin(), sortedVector.cend(), col);
          }
        ), storage_);
      }

      const auto& storage() const {
        return storage_;
      }

      size_type size() const {
        return std::visit([&](const auto& rowIndices) {
          return rowIndices.size();
        }, storage_);
      }

      void clear() {
        std::visit([&](auto& rowIndices) {
          rowIndices.clear();
        }, storage_);
      }

    private:
      std::variant<Vector, std::set<Index>> storage_;
    };
  }


  class MatrixIndexSet
  {
  public:
    using size_type = typename Impl::RowIndexSet::size_type;

    static constexpr size_type defaultMaxVectorSize = Impl::RowIndexSet::defaultMaxVectorSize;

    MatrixIndexSet(size_type maxVectorSize=defaultMaxVectorSize) noexcept : rows_(0), cols_(0), maxVectorSize_(maxVectorSize)
    {}

    MatrixIndexSet(size_type rows, size_type cols, size_type maxVectorSize=defaultMaxVectorSize) : rows_(rows), cols_(cols), maxVectorSize_(maxVectorSize)
    {
      indices_.resize(rows_, Impl::RowIndexSet(maxVectorSize_));
    }

    void resize(size_type rows, size_type cols) {
      rows_ = rows;
      cols_ = cols;
      indices_.resize(rows_, Impl::RowIndexSet(maxVectorSize_));
    }

    void add(size_type row, size_type col) {
      indices_[row].insert(col);
    }

    size_type size() const {
      size_type entries = 0;
      for (size_type i=0; i<rows_; i++)
        entries += rowsize(i);
      return entries;
    }

    size_type rows() const {return rows_;}

    size_type cols() const {return cols_;}

    const auto& columnIndices(size_type row) const {
      return indices_[row].storage();
    }

    size_type rowsize(size_type row) const {
      return indices_[row].size();
    }

    template <class MatrixType>
    void import(const MatrixType& m, size_type rowOffset=0, size_type colOffset=0) {

      typedef typename MatrixType::row_type RowType;
      typedef typename RowType::ConstIterator ColumnIterator;

      for (size_type rowIdx=0; rowIdx<m.N(); rowIdx++) {

        const RowType& row = m[rowIdx];

        ColumnIterator cIt    = row.begin();
        ColumnIterator cEndIt = row.end();

        for(; cIt!=cEndIt; ++cIt)
          add(rowIdx+rowOffset, cIt.index()+colOffset);

      }

    }

    template <class MatrixType>
    void exportIdx(MatrixType& matrix) const {

      matrix.setSize(rows_, cols_);
      matrix.setBuildMode(MatrixType::random);

      for (size_type row=0; row<rows_; row++)
        matrix.setrowsize(row, rowsize(row));

      matrix.endrowsizes();

      for (size_type row=0; row<rows_; row++) {
        std::visit([&](const auto& rowIndices) {
          matrix.setIndicesNoSort(row, rowIndices.begin(), rowIndices.end());
        }, indices_[row].storage());
      }

      matrix.endindices();

    }

  private:

    std::vector<Impl::RowIndexSet> indices_;

    size_type rows_, cols_;
    size_type maxVectorSize_;

  };


} // end namespace Dune

#endif