1 // Copyright 2002 The Trustees of Indiana University.

     2 

     3 // Use, modification and distribution is subject to the Boost Software 

     4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at

     5 // http://www.boost.org/LICENSE_1_0.txt)

     6 

     7 //  Boost.MultiArray Library

     8 //  Authors: Ronald Garcia

     9 //           Jeremy Siek

    10 //           Andrew Lumsdaine

    11 //  See http://www.boost.org/libs/multi_array for documentation.

    12 

    13 #ifndef BASE_RG071801_HPP

    14 #define BASE_RG071801_HPP

    15 

    16 //

    17 // base.hpp - some implementation base classes for from which

    18 // functionality is acquired

    19 //

    20 

    21 #include "boost/multi_array/extent_range.hpp"

    22 #include "boost/multi_array/extent_gen.hpp"

    23 #include "boost/multi_array/index_range.hpp"

    24 #include "boost/multi_array/index_gen.hpp"

    25 #include "boost/multi_array/storage_order.hpp"

    26 #include "boost/multi_array/types.hpp"

    27 #include "boost/config.hpp"

    28 #include "boost/multi_array/concept_checks.hpp" //for ignore_unused_...

    29 #include "boost/mpl/eval_if.hpp"

    30 #include "boost/mpl/if.hpp"

    31 #include "boost/mpl/size_t.hpp"

    32 #include "boost/mpl/aux_/msvc_eti_base.hpp"

    33 #include "boost/iterator/reverse_iterator.hpp"

    34 #include "boost/static_assert.hpp"

    35 #include "boost/type.hpp"

    36 #include "boost/assert.hpp"

    37 #include <cstddef>

    38 #include <memory>

    39 

    40 namespace boost {

    41 

    42 /////////////////////////////////////////////////////////////////////////

    43 // class declarations

    44 /////////////////////////////////////////////////////////////////////////

    45 

    46 template<typename T, std::size_t NumDims,

    47   typename Allocator = std::allocator<T> >

    48 class multi_array;

    49 

    50 // This is a public interface for use by end users!

    51 namespace multi_array_types {

    52   typedef boost::detail::multi_array::size_type size_type;

    53   typedef std::ptrdiff_t difference_type;

    54   typedef boost::detail::multi_array::index index;

    55   typedef detail::multi_array::index_range<index,size_type> index_range;

    56   typedef detail::multi_array::extent_range<index,size_type> extent_range;

    57   typedef detail::multi_array::index_gen<0,0> index_gen;

    58   typedef detail::multi_array::extent_gen<0> extent_gen;

    59 }

    60 

    61 

    62 // boost::extents and boost::indices are now a part of the public

    63 // interface.  That way users don't necessarily have to create their 

    64 // own objects.  On the other hand, one may not want the overhead of 

    65 // object creation in small-memory environments.  Thus, the objects

    66 // can be left undefined by defining BOOST_MULTI_ARRAY_NO_GENERATORS 

    67 // before loading multi_array.hpp.

    68 #if !BOOST_MULTI_ARRAY_NO_GENERATORS

    69 namespace {

    70   multi_array_types::extent_gen extents;

    71   multi_array_types::index_gen indices;

    72 }

    73 #endif // BOOST_MULTI_ARRAY_NO_GENERATORS

    74 

    75 namespace detail {

    76 namespace multi_array {

    77 

    78 template <typename T, std::size_t NumDims>

    79 class sub_array;

    80 

    81 template <typename T, std::size_t NumDims, typename TPtr = const T*>

    82 class const_sub_array;

    83 

    84 template <typename T, typename TPtr, typename NumDims, typename Reference>

    85 class array_iterator;

    86 

    87 template <typename T, std::size_t NumDims, typename TPtr = const T*>

    88 class const_multi_array_view;

    89 

    90 template <typename T, std::size_t NumDims>

    91 class multi_array_view;

    92 

    93 /////////////////////////////////////////////////////////////////////////

    94 // class interfaces

    95 /////////////////////////////////////////////////////////////////////////

    96 

    97 class multi_array_base {

    98 public:

    99   typedef multi_array_types::size_type size_type;

   100   typedef multi_array_types::difference_type difference_type;

   101   typedef multi_array_types::index index;

   102   typedef multi_array_types::index_range index_range;

   103   typedef multi_array_types::extent_range extent_range;

   104   typedef multi_array_types::index_gen index_gen;

   105   typedef multi_array_types::extent_gen extent_gen;

   106 };

   107 

   108 //

   109 // value_accessor_n

   110 //  contains the routines for accessing elements from

   111 //  N-dimensional views.

   112 //

   113 template<typename T, std::size_t NumDims>

   114 class value_accessor_n : public multi_array_base {

   115   typedef multi_array_base super_type;

   116 public:

   117   typedef typename super_type::index index;

   118 

   119   // 

   120   // public typedefs used by classes that inherit from this base

   121   //

   122   typedef T element;

   123   typedef boost::multi_array<T,NumDims-1> value_type;

   124   typedef sub_array<T,NumDims-1> reference;

   125   typedef const_sub_array<T,NumDims-1> const_reference;

   126 

   127 protected:

   128   // used by array operator[] and iterators to get reference types.

   129   template <typename Reference, typename TPtr>

   130   Reference access(boost::type<Reference>,index idx,TPtr base,

   131                    const size_type* extents,

   132                    const index* strides,

   133                    const index* index_bases) const {

   134 

   135     BOOST_ASSERT(idx - index_bases[0] >= 0);

   136     BOOST_ASSERT(size_type(idx - index_bases[0]) < extents[0]);

   137     // return a sub_array<T,NDims-1> proxy object

   138     TPtr newbase = base + idx * strides[0];

   139     return Reference(newbase,extents+1,strides+1,index_bases+1);

   140 

   141   }

   142 

   143   value_accessor_n() { }

   144   ~value_accessor_n() { }

   145 };

   146 

   147 

   148 

   149 //

   150 // value_accessor_one

   151 //  contains the routines for accessing reference elements from

   152 //  1-dimensional views.

   153 //

   154 template<typename T>

   155 class value_accessor_one : public multi_array_base {

   156   typedef multi_array_base super_type;

   157 public:

   158   typedef typename super_type::index index;

   159   //

   160   // public typedefs for use by classes that inherit it.

   161   //

   162   typedef T element;

   163   typedef T value_type;

   164   typedef T& reference;

   165   typedef T const& const_reference;

   166 

   167 protected:

   168   // used by array operator[] and iterators to get reference types.

   169   template <typename Reference, typename TPtr>

   170   Reference access(boost::type<Reference>,index idx,TPtr base,

   171                    const size_type* extents,

   172                    const index* strides,

   173                    const index* index_bases) const {

   174 

   175     ignore_unused_variable_warning(index_bases);

   176     ignore_unused_variable_warning(extents);

   177     BOOST_ASSERT(idx - index_bases[0] >= 0);

   178     BOOST_ASSERT(size_type(idx - index_bases[0]) < extents[0]);

   179     return *(base + idx * strides[0]);

   180   }

   181 

   182   value_accessor_one() { }

   183   ~value_accessor_one() { }

   184 };

   185 

   186 

   187 /////////////////////////////////////////////////////////////////////////

   188 // choose value accessor begins

   189 //

   190 

   191 template <typename T, std::size_t NumDims>

   192 struct choose_value_accessor_n {

   193   typedef value_accessor_n<T,NumDims> type;

   194 };

   195 

   196 template <typename T>

   197 struct choose_value_accessor_one {

   198   typedef value_accessor_one<T> type;

   199 };

   200 

   201 template <typename T, typename NumDims>

   202 struct value_accessor_generator {

   203     BOOST_STATIC_CONSTANT(std::size_t, dimensionality = NumDims::value);

   204     

   205   typedef typename

   206   mpl::eval_if_c<(dimensionality == 1),

   207                   choose_value_accessor_one<T>,

   208                   choose_value_accessor_n<T,dimensionality>

   209   >::type type;

   210 };

   211 

   212 #if BOOST_WORKAROUND(BOOST_MSVC, < 1300)

   213 

   214 struct eti_value_accessor

   215 {

   216   typedef int index;

   217   typedef int size_type;

   218   typedef int element;

   219   typedef int index_range;

   220   typedef int value_type;

   221   typedef int reference;

   222   typedef int const_reference;

   223 };

   224     

   225 template <>

   226 struct value_accessor_generator<int,int>

   227 {

   228   typedef eti_value_accessor type;

   229 };

   230 

   231 template <class T, class NumDims>

   232 struct associated_types

   233   : mpl::aux::msvc_eti_base<

   234         typename value_accessor_generator<T,NumDims>::type

   235     >::type

   236 {};

   237 

   238 template <>

   239 struct associated_types<int,int> : eti_value_accessor {};

   240 

   241 #else

   242 

   243 template <class T, class NumDims>

   244 struct associated_types

   245   : value_accessor_generator<T,NumDims>::type

   246 {};

   247 

   248 #endif

   249 

   250 //

   251 // choose value accessor ends

   252 /////////////////////////////////////////////////////////////////////////

   253 

   254 

   255 

   256 ////////////////////////////////////////////////////////////////////////

   257 // multi_array_base

   258 ////////////////////////////////////////////////////////////////////////

   259 template <typename T, std::size_t NumDims>

   260 class multi_array_impl_base

   261   :

   262 #if BOOST_WORKAROUND(BOOST_MSVC, < 1300)

   263       public mpl::aux::msvc_eti_base<

   264           typename value_accessor_generator<T,mpl::size_t<NumDims> >::type

   265        >::type

   266 #else

   267       public value_accessor_generator<T,mpl::size_t<NumDims> >::type

   268 #endif 

   269 {

   270   typedef associated_types<T,mpl::size_t<NumDims> > types;

   271 public:

   272   typedef typename types::index index;

   273   typedef typename types::size_type size_type;

   274   typedef typename types::element element;

   275   typedef typename types::index_range index_range;

   276   typedef typename types::value_type value_type;

   277   typedef typename types::reference reference;

   278   typedef typename types::const_reference const_reference;

   279 

   280   template <std::size_t NDims>

   281   struct subarray {

   282     typedef boost::detail::multi_array::sub_array<T,NDims> type;

   283   };

   284 

   285   template <std::size_t NDims>

   286   struct const_subarray {

   287     typedef boost::detail::multi_array::const_sub_array<T,NDims> type;

   288   };

   289 

   290   template <std::size_t NDims>

   291   struct array_view {

   292     typedef boost::detail::multi_array::multi_array_view<T,NDims> type;

   293   };

   294 

   295   template <std::size_t NDims>

   296   struct const_array_view {

   297   public:

   298     typedef boost::detail::multi_array::const_multi_array_view<T,NDims> type;

   299   };

   300 

   301   //

   302   // iterator support

   303   //

   304   typedef array_iterator<T,T*,mpl::size_t<NumDims>,reference> iterator;

   305   typedef array_iterator<T,T const*,mpl::size_t<NumDims>,const_reference> const_iterator;

   306 

   307   typedef ::boost::reverse_iterator<iterator> reverse_iterator;

   308   typedef ::boost::reverse_iterator<const_iterator> const_reverse_iterator;

   309 

   310   BOOST_STATIC_CONSTANT(std::size_t, dimensionality = NumDims);

   311 protected:

   312 

   313   multi_array_impl_base() { }

   314   ~multi_array_impl_base() { }

   315 

   316   // Used by operator() in our array classes

   317   template <typename Reference, typename IndexList, typename TPtr>

   318   Reference access_element(boost::type<Reference>,

   319                            const IndexList& indices,

   320                            TPtr base,

   321                            const size_type* extents,

   322                            const index* strides,

   323                            const index* index_bases) const {

   324 

   325     ignore_unused_variable_warning(index_bases);

   326     ignore_unused_variable_warning(extents);

   327 #if !defined(NDEBUG) && !defined(BOOST_DISABLE_ASSERTS)

   328     for (size_type i = 0; i != NumDims; ++i) {

   329       BOOST_ASSERT(indices[i] - index_bases[i] >= 0);

   330       BOOST_ASSERT(size_type(indices[i] - index_bases[i]) < extents[i]);

   331     }

   332 #endif

   333 

   334     index offset = 0;

   335     for (size_type n = 0; n != NumDims; ++n) 

   336       offset += indices[n] * strides[n];

   337     

   338     return base[offset];

   339   }

   340 

   341   template <typename StrideList, typename ExtentList>

   342   void compute_strides(StrideList& stride_list, ExtentList& extent_list,

   343                        const general_storage_order<NumDims>& storage)

   344   {

   345     // invariant: stride = the stride for dimension n

   346     index stride = 1;

   347     for (size_type n = 0; n != NumDims; ++n) {

   348       index stride_sign = +1;

   349       

   350       if (!storage.ascending(storage.ordering(n)))

   351         stride_sign = -1;

   352       

   353       // The stride for this dimension is the product of the

   354       // lengths of the ranks minor to it.

   355       stride_list[storage.ordering(n)] = stride * stride_sign;

   356       

   357       stride *= extent_list[storage.ordering(n)];

   358     } 

   359   }

   360 

   361   // This calculates the offset to the array base pointer due to:

   362   // 1. dimensions stored in descending order

   363   // 2. non-zero dimension index bases

   364   template <typename StrideList, typename ExtentList, typename BaseList>

   365   index

   366   calculate_origin_offset(const StrideList& stride_list,

   367                           const ExtentList& extent_list,

   368                           const general_storage_order<NumDims>& storage,

   369                           const BaseList& index_base_list)

   370   {

   371     return

   372       calculate_descending_dimension_offset(stride_list,extent_list,

   373                                             storage) +

   374       calculate_indexing_offset(stride_list,index_base_list);

   375   }

   376 

   377   // This calculates the offset added to the base pointer that are

   378   // caused by descending dimensions

   379   template <typename StrideList, typename ExtentList>

   380   index

   381   calculate_descending_dimension_offset(const StrideList& stride_list,

   382                                 const ExtentList& extent_list,

   383                                 const general_storage_order<NumDims>& storage)

   384   {

   385     index offset = 0;

   386     if (!storage.all_dims_ascending()) 

   387       for (size_type n = 0; n != NumDims; ++n)

   388         if (!storage.ascending(n))

   389           offset -= (extent_list[n] - 1) * stride_list[n];

   390 

   391     return offset;

   392   }

   393 

   394   // This is used to reindex array_views, which are no longer

   395   // concerned about storage order (specifically, whether dimensions

   396   // are ascending or descending) since the viewed array handled it.

   397 

   398   template <typename StrideList, typename BaseList>

   399   index

   400   calculate_indexing_offset(const StrideList& stride_list,

   401                           const BaseList& index_base_list)

   402   {

   403     index offset = 0;

   404     for (size_type n = 0; n != NumDims; ++n)

   405         offset -= stride_list[n] * index_base_list[n];

   406     return offset;

   407   }

   408 

   409   // Slicing using an index_gen.

   410   // Note that populating an index_gen creates a type that encodes

   411   // both the number of dimensions in the current Array (NumDims), and 

   412   // the Number of dimensions for the resulting view.  This allows the 

   413   // compiler to fail if the dimensions aren't completely accounted

   414   // for.  For reasons unbeknownst to me, a BOOST_STATIC_ASSERT

   415   // within the member function template does not work. I should add a 

   416   // note to the documentation specifying that you get a damn ugly

   417   // error message if you screw up in your slicing code.

   418   template <typename ArrayRef, int NDims, typename TPtr>

   419   ArrayRef

   420   generate_array_view(boost::type<ArrayRef>,

   421                       const boost::detail::multi_array::

   422                       index_gen<NumDims,NDims>& indices,

   423                       const size_type* extents,

   424                       const index* strides,

   425                       const index* index_bases,

   426                       TPtr base) const {

   427 

   428     boost::array<index,NDims> new_strides;

   429     boost::array<index,NDims> new_extents;

   430 

   431     index offset = 0;

   432     size_type dim = 0;

   433     for (size_type n = 0; n != NumDims; ++n) {

   434       const index default_start = index_bases[n];

   435       const index default_finish = default_start+extents[n];

   436       const index_range& current_range = indices.ranges_[n];

   437       index start = current_range.get_start(default_start);

   438       index finish = current_range.get_finish(default_finish);

   439       index index_factor = current_range.stride();

   440       index len = (finish - start + (index_factor - 1)) / index_factor;

   441 

   442       BOOST_ASSERT(index_bases[n] <= start &&

   443                    start <= index_bases[n]+index(extents[n]));

   444       BOOST_ASSERT(index_bases[n] <= finish &&

   445                    finish <= index_bases[n]+index(extents[n]));

   446       BOOST_ASSERT(index_factor > 0);

   447 

   448       // the array data pointer is modified to account for non-zero

   449       // bases during slicing (see [Garcia] for the math involved)

   450       offset += start * strides[n];

   451 

   452       if (!current_range.is_degenerate()) {

   453 

   454         // The index_factor for each dimension is included into the

   455         // strides for the array_view (see [Garcia] for the math involved).

   456         new_strides[dim] = index_factor * strides[n];

   457         

   458         // calculate new extents

   459         new_extents[dim] = len;

   460         ++dim;

   461       }

   462     }

   463     BOOST_ASSERT(dim == NDims);

   464 

   465     return

   466       ArrayRef(base+offset,

   467                new_extents,

   468                new_strides);

   469   }

   470                      

   471 

   472 };

   473 

   474 } // namespace multi_array

   475 } // namespace detail

   476 

   477 } // namespace boost

   478 

   479 #endif // BASE_RG071801_HPP