dim-vector.h

Go to the documentation of this file.

////////////////////////////////////////////////////////////////////////
//
// Copyright (C) 2003-2026 The Octave Project Developers
//
// See the file COPYRIGHT.md in the top-level directory of this
// or <https://octave.org/copyright/>.
//
// Copyirght (C) 2009, 2010 VZLU Prague
//
// This file is part of Octave.
//
// Octave is free software: you can redistribute it and/or modify it
// under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Octave is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Octave; see the file COPYING.  If not, see
// <https://www.gnu.org/licenses/>.
//
////////////////////////////////////////////////////////////////////////
 
#if ! defined (octave_dim_vector_h)
#define octave_dim_vector_h 1
 
#include "octave-config.h"
 
#include <algorithm>
#include <initializer_list>
#include <limits>
#include <string>
 
#include "Array-fwd.h"
#include "lo-utils.h"
#include "oct-atomic.h"
#include "oct-refcount.h"
 
//! Vector representing the dimensions (size) of an Array.
//!
//! A dim_vector is used to represent dimensions of an Array.  It is used
//! on its constructor to specify its size, or when reshaping it.
//!
//! @code{.cc}
//! // Matrix with 10 rows and 20 columns.
//! Matrix m Matrix (dim_vector (10, 20));
//!
//! // Change its size to 5 rows and 40 columns.
//! Matrix m2 = m.reshape (dim_vector (5, 40));
//!
//! // Five dimensional Array of length 10, 20, 3, 8, 7 on each dimension.
//! NDArray a (dim_vector (10, 20, 3, 8, 7));
//!
//! // Uninitialized array of same size as other.
//! NDArray b (a.dims ());
//! @endcode
//!
//! The main thing to understand about this class, is that methods such as
//! ndims() and numel(), return the value for an Array of these dimensions,
//! not the actual number of elements in the dim_vector.
//!
//! @code{.cc}
//! dim_vector d (10, 5, 3);
//! octave_idx_type n = d.numel (); // returns 150
//! octave_idx_type nd = d.ndims (); // returns 3
//! @endcode
//!
//! ## Implementation details ##
//!
//! This implementation is more tricky than Array, but the big plus is that
//! dim_vector requires only one allocation instead of two.  It is (slightly)
//! patterned after GCC's basic_string implementation.  rep is a pointer to an
//! array of memory, comprising count, length, and the data:
//!
//! @verbatim
//!        <count>
//!        <ndims>
//! rep --> <dims[0]>
//!        <dims[1]>
//!        ...
//! @endverbatim
//!
//! The inlines count(), ndims() recover this data from the rep.  Note
//! that rep points to the beginning of dims to grant faster access
//! (reinterpret_cast is assumed to be an inexpensive operation).
 
class OCTAVE_API dim_vector
{
private:
 
  octave_idx_type m_num_dims;
 
  octave_idx_type *m_dims;
 
public:
 
  //! Construct dim_vector for a N dimensional array.
  //!
  //! Each argument to constructor defines the length of an additional
  //! dimension.  A dim_vector always represents a minimum of 2 dimensions
  //! (just like an Array has at least 2 dimensions) and there is no
  //! upper limit on the number of dimensions.
  //!
  //! @code{.cc}
  //! dim_vector dv (7, 5);
  //! Matrix mat (dv);
  //! @endcode
  //!
  //! The constructed dim_vector @c dv will have two elements, @f$[7, 5]@f$,
  //! one for each dimension.  It can then be used to construct a Matrix
  //! with such dimensions, i.e., 7 rows and 5 columns.
  //!
  //! @code{.cc}
  //! NDArray x (dim_vector (7, 5, 10));
  //! @endcode
  //!
  //! This will construct a 3 dimensional NDArray of lengths 7, 5, and 10,
  //! on the first, second, and third dimension (rows, columns, and pages)
  //! respectively.
  //!
  //! Note that that there is no constructor that accepts only one
  //! dimension length to avoid confusion.  The source for such confusion
  //! is that constructor could mean:
  //!   - a column vector, i.e., assume @f$[N, 1]@f$;
  //!   - a square matrix, i.e., as is common in Octave interpreter;
  //!   - support for a 1 dimensional Array (does not exist);
  //!
  //! Using r, c, and lengths... as arguments, allow us to check at compile
  //! time that there's at least 2 dimensions specified, while maintaining
  //! type safety.
 
  template <typename... Ints>
  dim_vector (const octave_idx_type r, const octave_idx_type c,
              Ints... lengths)
    : m_num_dims (2 + sizeof... (Ints)), m_dims (new octave_idx_type [m_num_dims])
  {
    std::initializer_list<octave_idx_type> all_lengths = {r, c, lengths...};
    octave_idx_type *ptr = m_dims;
    for (const octave_idx_type l: all_lengths)
      *ptr++ = l;
  }
 
  // Fast access with absolutely no checking
 
  octave_idx_type& xelem (int i) { return m_dims[i]; }
 
  octave_idx_type xelem (int i) const { return m_dims[i]; }
 
  // Safe access to to elements
 
  octave_idx_type& elem (int i)
  {
    return xelem (i);
  }
 
  octave_idx_type elem (int i) const { return xelem (i); }
 
  void chop_trailing_singletons ()
  {
    while (m_num_dims > 2 && xelem(m_num_dims-1) == 1)
      m_num_dims--;
  }
 
  OCTAVE_API void chop_all_singletons ();
 
private:
 
  explicit dim_vector (octave_idx_type ndims)
    : m_num_dims (ndims < 2 ? 2 : ndims), m_dims (new octave_idx_type [m_num_dims])
  {
    std::fill_n (m_dims, m_num_dims, 0);
  }
 
public:
 
  // The maximum allowed value for a dimension extent.  This will
  // normally be a tiny bit off the maximum value of octave_idx_type.
  // Currently, 1 is subtracted to allow safe conversion of any 2-D Array
  // into Sparse but this offset may change in the future.
 
  static constexpr octave_idx_type dim_max ()
  {
    return std::numeric_limits<octave_idx_type>::max () - 1;
  }
 
  explicit dim_vector ()
    : m_num_dims (2), m_dims (new octave_idx_type [m_num_dims])
  {
    std::fill_n (m_dims, m_num_dims, 0);
  }
 
  dim_vector (const dim_vector& dv)
    : m_num_dims (dv.m_num_dims), m_dims (new octave_idx_type [m_num_dims])
  {
    std::copy_n (dv.m_dims, m_num_dims, m_dims);
  }
 
  dim_vector (dim_vector&& dv)
    : m_num_dims (0), m_dims (nullptr)
  {
    *this = std::move (dv);
  }
 
  static dim_vector alloc (int n)
  {
    return dim_vector (n);
  }
 
  dim_vector& operator = (const dim_vector& dv)
  {
    if (&dv != this)
      {
        delete [] m_dims;
 
        m_num_dims = dv.m_num_dims;
        m_dims = new octave_idx_type [m_num_dims];
 
        std::copy_n (dv.m_dims, m_num_dims, m_dims);
      }
 
    return *this;
  }
 
  dim_vector& operator = (dim_vector&& dv)
  {
    if (&dv != this)
      {
        // Because we define a move constructor and a move assignment
        // operator, m_dims may be a nullptr here.  We should only need to
        // protect the destructor in a similar way.
 
        delete [] m_dims;
 
        m_num_dims = dv.m_num_dims;
        m_dims = dv.m_dims;
 
        dv.m_num_dims = 0;
        dv.m_dims = nullptr;
      }
 
    return *this;
  }
 
  ~dim_vector ()
  {
    // Because we define a move constructor and a move assignment
    // operator, m_dims may be a nullptr here.  We should only need to
    // protect the move assignment operator in a similar way.
 
    delete [] m_dims;
  }
 
  //! Number of dimensions.
  //!
  //! Returns the number of dimensions of the dim_vector.  This is number of
  //! elements in the dim_vector including trailing singletons.  It is also
  //! the number of dimensions an Array with this dim_vector would have.
 
  octave_idx_type ndims () const { return m_num_dims; }
 
  //! Number of dimensions.
  //! Synonymous with ndims().
  //!
  //! While this method is not officially deprecated, consider using ndims()
  //! instead to avoid confusion.  Array does not have length because of its
  //! odd definition as length of the longest dimension.
 
  int length () const { return ndims (); }
 
  octave_idx_type& operator () (int i) { return elem (i); }
 
  octave_idx_type operator () (int i) const { return elem (i); }
 
  void resize (int n, int fill_value = 0)
  {
    if (n < 2)
      n = 2;
 
    if (n == m_num_dims)
      return;
 
    if (n < m_num_dims)
      {
        m_num_dims = n;
        return;
      }
 
    octave_idx_type *new_rep = new octave_idx_type [n];
 
    std::copy_n (m_dims, m_num_dims, new_rep);
    std::fill_n (new_rep + m_num_dims, n - m_num_dims, fill_value);
 
    delete [] m_dims;
 
    m_dims = new_rep;
 
    m_num_dims = n;
  }
 
  OCTAVE_API std::string str (char sep = 'x') const;
 
  bool all_zero () const
  {
    return std::all_of (m_dims, m_dims + ndims (),
                        [] (octave_idx_type dim) { return dim == 0; });
  }
 
  bool empty_2d () const
  {
    return ndims () == 2 && (xelem (0) == 0 || xelem (1) == 0);
  }
 
  bool zero_by_zero () const
  {
    return ndims () == 2 && xelem (0) == 0 && xelem (1) == 0;
  }
 
  bool any_zero () const
  {
    return std::any_of (m_dims, m_dims + ndims (),
                        [] (octave_idx_type dim) { return dim == 0; });
  }
 
  OCTAVE_API int num_ones () const;
 
  bool all_ones () const
  {
    return (num_ones () == ndims ());
  }
 
  //! Number of elements that a matrix with this dimensions would have.
  //!
  //! Return the number of elements that a matrix with this dimension
  //! vector would have, NOT the number of dimensions (elements in the
  //! dimension vector).
 
  octave_idx_type numel (int n = 0) const
  {
    int n_dims = ndims ();
 
    octave_idx_type retval = 1;
 
    for (int i = n; i < n_dims; i++)
      retval *= elem (i);
 
    return retval;
  }
 
  //! The following function will throw a std::bad_alloc ()
  //! exception if the requested size is larger than can be indexed by
  //! octave_idx_type.  This may be smaller than the actual amount of
  //! memory that can be safely allocated on a system.  However, if we
  //! don't fail here, we can end up with a mysterious crash inside a
  //! function that is iterating over an array using octave_idx_type
  //! indices.
 
  // IF we ever require C++26 we can use ckd_mul in the following
  // function and not have to check for or explicitly call
  // __builtin_mul_overflow.
  octave_idx_type safe_numel () const
  {
    octave_idx_type n = xelem(0);
 
    if (n > dim_max ())
      throw std::bad_alloc ();
 
    if (n == 0)
      return 0;
 
    for (int i = 1; i < ndims (); i++)
      {
#if defined (__has_builtin) && __has_builtin (__builtin_mul_overflow)
        bool overflow = __builtin_mul_overflow (n, xelem(i), &n);
#else
        // Function call overhead, much less efficient than using the
        // built-in function or ckd_mul (C23 / C++26)
        bool overflow = octave::math::int_multiply_overflow (n, xelem(i), &n);
#endif
 
        if (overflow || n > dim_max ())
          throw std::bad_alloc ();
 
        if (n == 0)
          return 0;
      }
 
    return n;
  }
 
  bool any_neg () const
  {
    return std::any_of (m_dims, m_dims + ndims (),
                        [] (octave_idx_type dim) { return dim < 0; });
  }
 
  OCTAVE_API dim_vector squeeze () const;
 
  //! This corresponds to cat().
  OCTAVE_API bool concat (const dim_vector& dvb, int dim);
 
  //! This corresponds to [,] (horzcat, dim = 0) and [;] (vertcat, dim = 1).
  // The rules are more relaxed here.
  OCTAVE_API bool hvcat (const dim_vector& dvb, int dim);
 
  //! Force certain dimensionality, preserving numel ().  Missing
  //! dimensions are set to 1, redundant are folded into the trailing
  //! one.  If n = 1, the result is 2-D and the second dim is 1
  //! (dim_vectors are always at least 2-D).
 
  OCTAVE_API dim_vector redim (int n) const;
 
  dim_vector as_column () const
  {
    if (ndims () == 2 && xelem (1) == 1)
      return *this;
    else
      return dim_vector (numel (), 1);
  }
 
  dim_vector as_row () const
  {
    if (ndims () == 2 && xelem (0) == 1)
      return *this;
    else
      return dim_vector (1, numel ());
  }
 
  bool isvector () const
  {
    return (ndims () == 2 && (xelem (0) == 1 || xelem (1) == 1));
  }
 
  bool is_nd_vector () const
  {
    int num_non_one = 0;
 
    for (int i = 0; i < ndims (); i++)
      {
        if (xelem (i) != 1)
          {
            num_non_one++;
 
            if (num_non_one > 1)
              break;
          }
      }
 
    return num_non_one == 1;
  }
 
  // Create a vector with length N.  If this object is a vector,
  // preserve the orientation, otherwise, create a column vector.
 
  dim_vector make_nd_vector (octave_idx_type n) const
  {
    dim_vector orig_dims;
 
    if (is_nd_vector ())
      {
        orig_dims = *this;
 
        for (int i = 0; i < orig_dims.ndims (); i++)
          {
            if (orig_dims(i) != 1)
              {
                orig_dims(i) = n;
                break;
              }
          }
      }
    else
      orig_dims = dim_vector (n, 1);
 
    return orig_dims;
  }
 
  int first_non_singleton (int def = 0) const
  {
    for (int i = 0; i < ndims (); i++)
      {
        if (xelem (i) != 1)
          return i;
      }
 
    return def;
  }
 
  //! Linear index from an index tuple.
  octave_idx_type compute_index (const octave_idx_type *idx) const
  { return compute_index (idx, ndims ()); }
 
  //! Linear index from an incomplete index tuple (nidx < length ()).
  octave_idx_type compute_index (const octave_idx_type *idx, int nidx) const
  {
    octave_idx_type k = 0;
    for (int i = nidx - 1; i >= 0; i--)
      k = xelem(i) * k + idx[i];
 
    return k;
  }
 
  //! Increment a multi-dimensional index tuple, optionally starting
  //! from an offset position and return the index of the last index
  //! position that was changed, or length () if just cycled over.
 
  int increment_index (octave_idx_type *idx, int start = 0) const
  {
    int i;
    for (i = start; i < ndims (); i++)
      {
        if (++(*idx) == xelem(i))
          *idx++ = 0;
        else
          break;
      }
    return i;
  }
 
  //! Return cumulative dimensions.
 
  dim_vector cumulative () const
  {
    int nd = ndims ();
    dim_vector retval = alloc (nd);
 
    octave_idx_type k = 1;
    for (int i = 0; i < nd; i++)
      retval.xelem(i) = (k *= xelem(i));
 
    return retval;
  }
 
  //! Compute a linear index from an index tuple.  Dimensions are
  //! required to be cumulative.
 
  octave_idx_type cum_compute_index (const octave_idx_type *idx) const
  {
    octave_idx_type k = idx[0];
 
    for (int i = 1; i < ndims (); i++)
      k += xelem(i-1) * idx[i];
 
    return k;
  }
 
  friend OCTAVE_API bool
  operator == (const dim_vector& a, const dim_vector& b);
 
  OCTAVE_API Array<octave_idx_type> as_array () const;
};
 
inline bool
operator == (const dim_vector& a, const dim_vector& b)
{
  // Fast case.
  if (a.m_dims == b.m_dims)
    return true;
 
  int a_len = a.ndims ();
  int b_len = b.ndims ();
 
  if (a_len != b_len)
    return false;
 
  return std::equal (a.m_dims, a.m_dims + a_len, b.m_dims);
}
 
inline bool
operator != (const dim_vector& a, const dim_vector& b)
{
  return ! operator == (a, b);
}
 
#endif