basearray.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_BASEARRAY_HH
#define DUNE_ISTL_BASEARRAY_HH

#include <cassert>
#include <cmath>
#include <cstddef>
#include <memory>
#include <algorithm>
#include <type_traits>

#include "istlexception.hh"
#include <dune/common/iteratorfacades.hh>

namespace Dune {

namespace Imp {

  template<class B, class ST=std::size_t >
  class base_array_unmanaged
  {
  public:

    //===== type definitions and constants

    typedef B member_type;

    typedef ST size_type;

    using reference = B&;

    using const_reference = const B&;

    //===== access to components

    reference operator[] (size_type i)
    {
#ifdef DUNE_ISTL_WITH_CHECKING
      if (i>=n) DUNE_THROW(ISTLError,"index out of range");
#endif
      return p[i];
    }

    const_reference operator[] (size_type i) const
    {
#ifdef DUNE_ISTL_WITH_CHECKING
      if (i>=n) DUNE_THROW(ISTLError,"index out of range");
#endif
      return p[i];
    }

    template<class T>
    class RealIterator
      :  public RandomAccessIteratorFacade<RealIterator<T>, T>
    {
    public:
      typedef typename std::remove_const<T>::type ValueType;

      friend class RandomAccessIteratorFacade<RealIterator<const ValueType>, const ValueType>;
      friend class RandomAccessIteratorFacade<RealIterator<ValueType>, ValueType>;
      friend class RealIterator<const ValueType>;
      friend class RealIterator<ValueType>;

      RealIterator () = default;

      RealIterator (const B* _p, B* _i)
        : p(_p), i(_i)
      {}

      template <class T_,
        std::enable_if_t<std::is_same_v<std::remove_const_t<T>, std::remove_const_t<T_>>, int> = 0>
      RealIterator (const RealIterator<T_>& other)
        : p(other.p), i(other.i)
      {}

      template <class T_,
        std::enable_if_t<std::is_same_v<std::remove_const_t<T>, std::remove_const_t<T_>>, int> = 0>
      RealIterator& operator= (const RealIterator<T_>& other)
      {
        p = other.p;
        i = other.i;
        return *this;
      }

      size_type index () const
      {
        return i-p;
      }

      bool equals (const RealIterator<ValueType>& other) const
      {
        assert(other.p==p);
        return i==other.i;
      }

      bool equals (const RealIterator<const ValueType>& other) const
      {
        assert(other.p==p);
        return i==other.i;
      }

      std::ptrdiff_t distanceTo(const RealIterator& o) const
      {
        return o.i-i;
      }

    private:
      void increment()
      {
        ++i;
      }

      void decrement()
      {
        --i;
      }

      // Needed for operator[] of the iterator
      reference elementAt (std::ptrdiff_t offset) const
      {
        return *(i+offset);
      }

      reference dereference () const
      {
        return *i;
      }

      void advance(std::ptrdiff_t d)
      {
        i+=d;
      }

      const B* p = nullptr;
      B* i = nullptr;
    };

    typedef RealIterator<B> iterator;


    iterator begin ()
    {
      return iterator(p,p);
    }

    iterator end ()
    {
      return iterator(p,p+n);
    }

    iterator beforeEnd ()
    {
      return iterator(p,p+n-1);
    }

    iterator beforeBegin ()
    {
      return iterator(p,p-1);
    }

    iterator find (size_type i)
    {
      return iterator(p,p+std::min(i,n));
    }

    typedef RealIterator<const B> const_iterator;

    const_iterator begin () const
    {
      return const_iterator(p,p+0);
    }

    const_iterator end () const
    {
      return const_iterator(p,p+n);
    }

    const_iterator beforeEnd () const
    {
      return const_iterator(p,p+n-1);
    }

    const_iterator beforeBegin () const
    {
      return const_iterator(p,p-1);
    }

    const_iterator find (size_type i) const
    {
      return const_iterator(p,p+std::min(i,n));
    }


    //===== sizes

    size_type size () const
    {
      return n;
    }

    const B* data() const
    {
      return p;
    }

    B* data()
    {
      return p;
    }

  protected:
    base_array_unmanaged ()
      : n(0), p(0)
    {}
    base_array_unmanaged (size_type n_, B* p_)
      : n(n_), p(p_)
    {}
    size_type n;     // number of elements in array
    B *p;      // pointer to dynamically allocated built-in array
  };



  template<class B, class ST=std::size_t >
  class compressed_base_array_unmanaged
  {
  public:

    //===== type definitions and constants

    typedef B member_type;

    typedef ST size_type;

    using reference = B&;

    using const_reference = const B&;

    //===== access to components

    reference operator[] (size_type i)
    {
      const size_type* lb = std::lower_bound(j, j+n, i);
      if (lb == j+n || *lb != i)
        DUNE_THROW(ISTLError,"index "<<i<<" not in compressed array");
      return p[lb-j];
    }

    const_reference operator[] (size_type i) const
    {
      const size_type* lb = std::lower_bound(j, j+n, i);
      if (lb == j+n || *lb != i)
        DUNE_THROW(ISTLError,"index "<<i<<" not in compressed array");
      return p[lb-j];
    }

    template<class T>
    class RealIterator
      : public BidirectionalIteratorFacade<RealIterator<T>, T>
    {
    public:
      typedef typename std::remove_const<T>::type ValueType;

      friend class BidirectionalIteratorFacade<RealIterator<const ValueType>, const ValueType>;
      friend class BidirectionalIteratorFacade<RealIterator<ValueType>, ValueType>;
      friend class RealIterator<const ValueType>;
      friend class RealIterator<ValueType>;

      RealIterator () = default;

      RealIterator (B* _p, size_type* _j, size_type _i)
        : p(_p), j(_j), i(_i)
      {}

      template <class T_,
        std::enable_if_t<std::is_same_v<std::remove_const_t<T>, std::remove_const_t<T_>>, int> = 0>
      RealIterator (const RealIterator<T_>& other)
        : p(other.p), j(other.j), i(other.i)
      {}

      template <class T_,
        std::enable_if_t<std::is_same_v<std::remove_const_t<T>, std::remove_const_t<T_>>, int> = 0>
      RealIterator& operator= (const RealIterator<T_>& other)
      {
        p = other.p;
        j = other.j;
        i = other.i;
        return *this;
      }


      bool equals (const RealIterator<ValueType>& it) const
      {
        assert(p==it.p);
        return (i)==(it.i);
      }

      bool equals (const RealIterator<const ValueType>& it) const
      {
        assert(p==it.p);
        return (i)==(it.i);
      }


      size_type index () const
      {
        return j[i];
      }

      void setindex (size_type k)
      {
        return j[i] = k;
      }

      size_type offset () const
      {
        return i;
      }

    private:
      void increment()
      {
        ++i;
      }

      void decrement()
      {
        --i;
      }

      reference dereference () const
      {
        return p[i];
      }

      B* p = nullptr;
      size_type* j = nullptr;
      size_type i = 0;
    };

    typedef RealIterator<B> iterator;

    iterator begin ()
    {
      return iterator(p,j,0);
    }

    iterator end ()
    {
      return iterator(p,j,n);
    }

    iterator beforeEnd ()
    {
      return iterator(p,j,n-1);
    }

    iterator beforeBegin ()
    {
      return iterator(p,j,-1);
    }

    iterator find (size_type i)
    {
      const size_type* lb = std::lower_bound(j, j+n, i);
      return (lb != j+n && *lb == i)
        ? iterator(p,j,lb-j)
        : end();
    }

    typedef RealIterator<const B> const_iterator;

    const_iterator begin () const
    {
      return const_iterator(p,j,0);
    }

    const_iterator end () const
    {
      return const_iterator(p,j,n);
    }

    const_iterator beforeEnd () const
    {
      return const_iterator(p,j,n-1);
    }

    const_iterator beforeBegin () const
    {
      return const_iterator(p,j,-1);
    }

    const_iterator find (size_type i) const
    {
      const size_type* lb = std::lower_bound(j, j+n, i);
      return (lb != j+n && *lb == i)
        ? const_iterator(p,j,lb-j)
        : end();
    }

    //===== sizes

    size_type size () const
    {
      return n;
    }

  protected:
    compressed_base_array_unmanaged ()
      : n(0), p(0), j(0)
    {}

    size_type n;      // number of elements in array
    B *p;       // pointer to dynamically allocated built-in array
    size_type* j;     // the index set
  };

} // end namespace Imp

} // end namespace

#endif