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