matrixindexset.hh

// 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