epoc32/include/stdapis/boost/multi_array/base.hpp
author William Roberts <williamr@symbian.org>
Tue, 16 Mar 2010 16:12:26 +0000
branchSymbian2
changeset 2 2fe1408b6811
permissions -rw-r--r--
Final list of Symbian^2 public API header files
     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