| // Copyright 2002 The Trustees of Indiana University. |
| |
| // Use, modification and distribution is subject to the Boost Software |
| // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| |
| // Boost.MultiArray Library |
| // Authors: Ronald Garcia |
| // Jeremy Siek |
| // Andrew Lumsdaine |
| // See http://www.boost.org/libs/multi_array for documentation. |
| |
| #ifndef BASE_RG071801_HPP |
| #define BASE_RG071801_HPP |
| |
| // |
| // base.hpp - some implementation base classes for from which |
| // functionality is acquired |
| // |
| |
| #include "boost/multi_array/extent_range.hpp" |
| #include "boost/multi_array/extent_gen.hpp" |
| #include "boost/multi_array/index_range.hpp" |
| #include "boost/multi_array/index_gen.hpp" |
| #include "boost/multi_array/storage_order.hpp" |
| #include "boost/multi_array/types.hpp" |
| #include "boost/config.hpp" |
| #include "boost/multi_array/concept_checks.hpp" //for ignore_unused_... |
| #include "boost/mpl/eval_if.hpp" |
| #include "boost/mpl/if.hpp" |
| #include "boost/mpl/size_t.hpp" |
| #include "boost/mpl/aux_/msvc_eti_base.hpp" |
| #include "boost/iterator/reverse_iterator.hpp" |
| #include "boost/static_assert.hpp" |
| #include "boost/type.hpp" |
| #include "boost/assert.hpp" |
| #include <cstddef> |
| #include <memory> |
| |
| namespace boost { |
| |
| ///////////////////////////////////////////////////////////////////////// |
| // class declarations |
| ///////////////////////////////////////////////////////////////////////// |
| |
| template<typename T, std::size_t NumDims, |
| typename Allocator = std::allocator<T> > |
| class multi_array; |
| |
| // This is a public interface for use by end users! |
| namespace multi_array_types { |
| typedef boost::detail::multi_array::size_type size_type; |
| typedef std::ptrdiff_t difference_type; |
| typedef boost::detail::multi_array::index index; |
| typedef detail::multi_array::index_range<index,size_type> index_range; |
| typedef detail::multi_array::extent_range<index,size_type> extent_range; |
| typedef detail::multi_array::index_gen<0,0> index_gen; |
| typedef detail::multi_array::extent_gen<0> extent_gen; |
| } |
| |
| |
| // boost::extents and boost::indices are now a part of the public |
| // interface. That way users don't necessarily have to create their |
| // own objects. On the other hand, one may not want the overhead of |
| // object creation in small-memory environments. Thus, the objects |
| // can be left undefined by defining BOOST_MULTI_ARRAY_NO_GENERATORS |
| // before loading multi_array.hpp. |
| #if !BOOST_MULTI_ARRAY_NO_GENERATORS |
| namespace { |
| multi_array_types::extent_gen extents; |
| multi_array_types::index_gen indices; |
| } |
| #endif // BOOST_MULTI_ARRAY_NO_GENERATORS |
| |
| namespace detail { |
| namespace multi_array { |
| |
| template <typename T, std::size_t NumDims> |
| class sub_array; |
| |
| template <typename T, std::size_t NumDims, typename TPtr = const T*> |
| class const_sub_array; |
| |
| template <typename T, typename TPtr, typename NumDims, typename Reference> |
| class array_iterator; |
| |
| template <typename T, std::size_t NumDims, typename TPtr = const T*> |
| class const_multi_array_view; |
| |
| template <typename T, std::size_t NumDims> |
| class multi_array_view; |
| |
| ///////////////////////////////////////////////////////////////////////// |
| // class interfaces |
| ///////////////////////////////////////////////////////////////////////// |
| |
| class multi_array_base { |
| public: |
| typedef multi_array_types::size_type size_type; |
| typedef multi_array_types::difference_type difference_type; |
| typedef multi_array_types::index index; |
| typedef multi_array_types::index_range index_range; |
| typedef multi_array_types::extent_range extent_range; |
| typedef multi_array_types::index_gen index_gen; |
| typedef multi_array_types::extent_gen extent_gen; |
| }; |
| |
| // |
| // value_accessor_n |
| // contains the routines for accessing elements from |
| // N-dimensional views. |
| // |
| template<typename T, std::size_t NumDims> |
| class value_accessor_n : public multi_array_base { |
| typedef multi_array_base super_type; |
| public: |
| typedef typename super_type::index index; |
| |
| // |
| // public typedefs used by classes that inherit from this base |
| // |
| typedef T element; |
| typedef boost::multi_array<T,NumDims-1> value_type; |
| typedef sub_array<T,NumDims-1> reference; |
| typedef const_sub_array<T,NumDims-1> const_reference; |
| |
| protected: |
| // used by array operator[] and iterators to get reference types. |
| template <typename Reference, typename TPtr> |
| Reference access(boost::type<Reference>,index idx,TPtr base, |
| const size_type* extents, |
| const index* strides, |
| const index* index_bases) const { |
| |
| BOOST_ASSERT(idx - index_bases[0] >= 0); |
| BOOST_ASSERT(size_type(idx - index_bases[0]) < extents[0]); |
| // return a sub_array<T,NDims-1> proxy object |
| TPtr newbase = base + idx * strides[0]; |
| return Reference(newbase,extents+1,strides+1,index_bases+1); |
| |
| } |
| |
| value_accessor_n() { } |
| ~value_accessor_n() { } |
| }; |
| |
| |
| |
| // |
| // value_accessor_one |
| // contains the routines for accessing reference elements from |
| // 1-dimensional views. |
| // |
| template<typename T> |
| class value_accessor_one : public multi_array_base { |
| typedef multi_array_base super_type; |
| public: |
| typedef typename super_type::index index; |
| // |
| // public typedefs for use by classes that inherit it. |
| // |
| typedef T element; |
| typedef T value_type; |
| typedef T& reference; |
| typedef T const& const_reference; |
| |
| protected: |
| // used by array operator[] and iterators to get reference types. |
| template <typename Reference, typename TPtr> |
| Reference access(boost::type<Reference>,index idx,TPtr base, |
| const size_type* extents, |
| const index* strides, |
| const index* index_bases) const { |
| |
| ignore_unused_variable_warning(index_bases); |
| ignore_unused_variable_warning(extents); |
| BOOST_ASSERT(idx - index_bases[0] >= 0); |
| BOOST_ASSERT(size_type(idx - index_bases[0]) < extents[0]); |
| return *(base + idx * strides[0]); |
| } |
| |
| value_accessor_one() { } |
| ~value_accessor_one() { } |
| }; |
| |
| |
| ///////////////////////////////////////////////////////////////////////// |
| // choose value accessor begins |
| // |
| |
| template <typename T, std::size_t NumDims> |
| struct choose_value_accessor_n { |
| typedef value_accessor_n<T,NumDims> type; |
| }; |
| |
| template <typename T> |
| struct choose_value_accessor_one { |
| typedef value_accessor_one<T> type; |
| }; |
| |
| template <typename T, typename NumDims> |
| struct value_accessor_generator { |
| BOOST_STATIC_CONSTANT(std::size_t, dimensionality = NumDims::value); |
| |
| typedef typename |
| mpl::eval_if_c<(dimensionality == 1), |
| choose_value_accessor_one<T>, |
| choose_value_accessor_n<T,dimensionality> |
| >::type type; |
| }; |
| |
| #if BOOST_WORKAROUND(BOOST_MSVC, < 1300) |
| |
| struct eti_value_accessor |
| { |
| typedef int index; |
| typedef int size_type; |
| typedef int element; |
| typedef int index_range; |
| typedef int value_type; |
| typedef int reference; |
| typedef int const_reference; |
| }; |
| |
| template <> |
| struct value_accessor_generator<int,int> |
| { |
| typedef eti_value_accessor type; |
| }; |
| |
| template <class T, class NumDims> |
| struct associated_types |
| : mpl::aux::msvc_eti_base< |
| typename value_accessor_generator<T,NumDims>::type |
| >::type |
| {}; |
| |
| template <> |
| struct associated_types<int,int> : eti_value_accessor {}; |
| |
| #else |
| |
| template <class T, class NumDims> |
| struct associated_types |
| : value_accessor_generator<T,NumDims>::type |
| {}; |
| |
| #endif |
| |
| // |
| // choose value accessor ends |
| ///////////////////////////////////////////////////////////////////////// |
| |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| // multi_array_base |
| //////////////////////////////////////////////////////////////////////// |
| template <typename T, std::size_t NumDims> |
| class multi_array_impl_base |
| : |
| #if BOOST_WORKAROUND(BOOST_MSVC, < 1300) |
| public mpl::aux::msvc_eti_base< |
| typename value_accessor_generator<T,mpl::size_t<NumDims> >::type |
| >::type |
| #else |
| public value_accessor_generator<T,mpl::size_t<NumDims> >::type |
| #endif |
| { |
| typedef associated_types<T,mpl::size_t<NumDims> > types; |
| public: |
| typedef typename types::index index; |
| typedef typename types::size_type size_type; |
| typedef typename types::element element; |
| typedef typename types::index_range index_range; |
| typedef typename types::value_type value_type; |
| typedef typename types::reference reference; |
| typedef typename types::const_reference const_reference; |
| |
| template <std::size_t NDims> |
| struct subarray { |
| typedef boost::detail::multi_array::sub_array<T,NDims> type; |
| }; |
| |
| template <std::size_t NDims> |
| struct const_subarray { |
| typedef boost::detail::multi_array::const_sub_array<T,NDims> type; |
| }; |
| |
| template <std::size_t NDims> |
| struct array_view { |
| typedef boost::detail::multi_array::multi_array_view<T,NDims> type; |
| }; |
| |
| template <std::size_t NDims> |
| struct const_array_view { |
| public: |
| typedef boost::detail::multi_array::const_multi_array_view<T,NDims> type; |
| }; |
| |
| // |
| // iterator support |
| // |
| typedef array_iterator<T,T*,mpl::size_t<NumDims>,reference> iterator; |
| typedef array_iterator<T,T const*,mpl::size_t<NumDims>,const_reference> const_iterator; |
| |
| typedef ::boost::reverse_iterator<iterator> reverse_iterator; |
| typedef ::boost::reverse_iterator<const_iterator> const_reverse_iterator; |
| |
| BOOST_STATIC_CONSTANT(std::size_t, dimensionality = NumDims); |
| protected: |
| |
| multi_array_impl_base() { } |
| ~multi_array_impl_base() { } |
| |
| // Used by operator() in our array classes |
| template <typename Reference, typename IndexList, typename TPtr> |
| Reference access_element(boost::type<Reference>, |
| const IndexList& indices, |
| TPtr base, |
| const size_type* extents, |
| const index* strides, |
| const index* index_bases) const { |
| |
| ignore_unused_variable_warning(index_bases); |
| ignore_unused_variable_warning(extents); |
| #if !defined(NDEBUG) && !defined(BOOST_DISABLE_ASSERTS) |
| for (size_type i = 0; i != NumDims; ++i) { |
| BOOST_ASSERT(indices[i] - index_bases[i] >= 0); |
| BOOST_ASSERT(size_type(indices[i] - index_bases[i]) < extents[i]); |
| } |
| #endif |
| |
| index offset = 0; |
| for (size_type n = 0; n != NumDims; ++n) |
| offset += indices[n] * strides[n]; |
| |
| return base[offset]; |
| } |
| |
| template <typename StrideList, typename ExtentList> |
| void compute_strides(StrideList& stride_list, ExtentList& extent_list, |
| const general_storage_order<NumDims>& storage) |
| { |
| // invariant: stride = the stride for dimension n |
| index stride = 1; |
| for (size_type n = 0; n != NumDims; ++n) { |
| index stride_sign = +1; |
| |
| if (!storage.ascending(storage.ordering(n))) |
| stride_sign = -1; |
| |
| // The stride for this dimension is the product of the |
| // lengths of the ranks minor to it. |
| stride_list[storage.ordering(n)] = stride * stride_sign; |
| |
| stride *= extent_list[storage.ordering(n)]; |
| } |
| } |
| |
| // This calculates the offset to the array base pointer due to: |
| // 1. dimensions stored in descending order |
| // 2. non-zero dimension index bases |
| template <typename StrideList, typename ExtentList, typename BaseList> |
| index |
| calculate_origin_offset(const StrideList& stride_list, |
| const ExtentList& extent_list, |
| const general_storage_order<NumDims>& storage, |
| const BaseList& index_base_list) |
| { |
| return |
| calculate_descending_dimension_offset(stride_list,extent_list, |
| storage) + |
| calculate_indexing_offset(stride_list,index_base_list); |
| } |
| |
| // This calculates the offset added to the base pointer that are |
| // caused by descending dimensions |
| template <typename StrideList, typename ExtentList> |
| index |
| calculate_descending_dimension_offset(const StrideList& stride_list, |
| const ExtentList& extent_list, |
| const general_storage_order<NumDims>& storage) |
| { |
| index offset = 0; |
| if (!storage.all_dims_ascending()) |
| for (size_type n = 0; n != NumDims; ++n) |
| if (!storage.ascending(n)) |
| offset -= (extent_list[n] - 1) * stride_list[n]; |
| |
| return offset; |
| } |
| |
| // This is used to reindex array_views, which are no longer |
| // concerned about storage order (specifically, whether dimensions |
| // are ascending or descending) since the viewed array handled it. |
| |
| template <typename StrideList, typename BaseList> |
| index |
| calculate_indexing_offset(const StrideList& stride_list, |
| const BaseList& index_base_list) |
| { |
| index offset = 0; |
| for (size_type n = 0; n != NumDims; ++n) |
| offset -= stride_list[n] * index_base_list[n]; |
| return offset; |
| } |
| |
| // Slicing using an index_gen. |
| // Note that populating an index_gen creates a type that encodes |
| // both the number of dimensions in the current Array (NumDims), and |
| // the Number of dimensions for the resulting view. This allows the |
| // compiler to fail if the dimensions aren't completely accounted |
| // for. For reasons unbeknownst to me, a BOOST_STATIC_ASSERT |
| // within the member function template does not work. I should add a |
| // note to the documentation specifying that you get a damn ugly |
| // error message if you screw up in your slicing code. |
| template <typename ArrayRef, int NDims, typename TPtr> |
| ArrayRef |
| generate_array_view(boost::type<ArrayRef>, |
| const boost::detail::multi_array:: |
| index_gen<NumDims,NDims>& indices, |
| const size_type* extents, |
| const index* strides, |
| const index* index_bases, |
| TPtr base) const { |
| |
| boost::array<index,NDims> new_strides; |
| boost::array<index,NDims> new_extents; |
| |
| index offset = 0; |
| size_type dim = 0; |
| for (size_type n = 0; n != NumDims; ++n) { |
| |
| // Use array specs and input specs to produce real specs. |
| const index default_start = index_bases[n]; |
| const index default_finish = default_start+extents[n]; |
| const index_range& current_range = indices.ranges_[n]; |
| index start = current_range.get_start(default_start); |
| index finish = current_range.get_finish(default_finish); |
| index stride = current_range.stride(); |
| BOOST_ASSERT(stride != 0); |
| |
| // An index range indicates a half-open strided interval |
| // [start,finish) (with stride) which faces upward when stride |
| // is positive and downward when stride is negative, |
| |
| // RG: The following code for calculating length suffers from |
| // some representation issues: if finish-start cannot be represented as |
| // by type index, then overflow may result. |
| |
| index len; |
| if ((finish - start) / stride < 0) { |
| // [start,finish) is empty according to the direction imposed by |
| // the stride. |
| len = 0; |
| } else { |
| // integral trick for ceiling((finish-start) / stride) |
| // taking into account signs. |
| index shrinkage = stride > 0 ? 1 : -1; |
| len = (finish - start + (stride - shrinkage)) / stride; |
| } |
| |
| // start marks the closed side of the range, so it must lie |
| // exactly in the set of legal indices |
| // with a special case for empty arrays |
| BOOST_ASSERT(index_bases[n] <= start && |
| ((start <= index_bases[n]+index(extents[n])) || |
| (start == index_bases[n] && extents[n] == 0))); |
| |
| #ifndef BOOST_DISABLE_ASSERTS |
| // finish marks the open side of the range, so it can go one past |
| // the "far side" of the range (the top if stride is positive, the bottom |
| // if stride is negative). |
| index bound_adjustment = stride < 0 ? 1 : 0; |
| BOOST_ASSERT(((index_bases[n] - bound_adjustment) <= finish) && |
| (finish <= (index_bases[n] + index(extents[n]) - bound_adjustment))); |
| #endif // BOOST_DISABLE_ASSERTS |
| |
| |
| // the array data pointer is modified to account for non-zero |
| // bases during slicing (see [Garcia] for the math involved) |
| offset += start * strides[n]; |
| |
| if (!current_range.is_degenerate()) { |
| |
| // The stride for each dimension is included into the |
| // strides for the array_view (see [Garcia] for the math involved). |
| new_strides[dim] = stride * strides[n]; |
| |
| // calculate new extents |
| new_extents[dim] = len; |
| ++dim; |
| } |
| } |
| BOOST_ASSERT(dim == NDims); |
| |
| return |
| ArrayRef(base+offset, |
| new_extents, |
| new_strides); |
| } |
| |
| |
| }; |
| |
| } // namespace multi_array |
| } // namespace detail |
| |
| } // namespace boost |
| |
| #endif // BASE_RG071801_HPP |