boost/boost/multi_array/base.hpp

   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/mpl/eval_if.hpp"
  29 #include "boost/mpl/if.hpp"
  30 #include "boost/mpl/size_t.hpp"
  31 #include "boost/mpl/aux_/msvc_eti_base.hpp"
  32 #include "boost/iterator/reverse_iterator.hpp"
  33 #include "boost/static_assert.hpp"
  34 #include "boost/type.hpp"
  35 #include <cassert>
  36 #include <cstddef>
  37 #include <memory>
  38
  39 namespace boost {
  40
  41 /////////////////////////////////////////////////////////////////////////
  42 // class declarations
  43 /////////////////////////////////////////////////////////////////////////
  44
  45 template<typename T, std::size_t NumDims,
  46   typename Allocator = std::allocator<T> >
  47 class multi_array;
  48
  49 // This is a public interface for use by end users!
  50 namespace multi_array_types {
  51   typedef boost::detail::multi_array::size_type size_type;
  52   typedef std::ptrdiff_t difference_type;
  53   typedef boost::detail::multi_array::index index;
  54   typedef detail::multi_array::index_range<index,size_type> index_range;
  55   typedef detail::multi_array::extent_range<index,size_type> extent_range;
  56   typedef detail::multi_array::index_gen<0,0> index_gen;
  57   typedef detail::multi_array::extent_gen<0> extent_gen;
  58 }
  59
  60
  61 // boost::extents and boost::indices are now a part of the public
  62 // interface.  That way users don't necessarily have to create their
  63 // own objects.  On the other hand, one may not want the overhead of
  64 // object creation in small-memory environments.  Thus, the objects
  65 // can be left undefined by defining BOOST_MULTI_ARRAY_NO_GENERATORS
  66 // before loading multi_array.hpp.
  67 #if !BOOST_MULTI_ARRAY_NO_GENERATORS
  68 namespace {
  69   multi_array_types::extent_gen extents;
  70   multi_array_types::index_gen indices;
  71 }
  72 #endif // BOOST_MULTI_ARRAY_NO_GENERATORS
  73
  74 namespace detail {
  75 namespace multi_array {
  76
  77 template <typename T, std::size_t NumDims>
  78 class sub_array;
  79
  80 template <typename T, std::size_t NumDims, typename TPtr = const T*>
  81 class const_sub_array;
  82
  83 template <typename T, typename TPtr, typename NumDims, typename Reference>
  84 class array_iterator;
  85
  86 template <typename T, std::size_t NumDims, typename TPtr = const T*>
  87 class const_multi_array_view;
  88
  89 template <typename T, std::size_t NumDims>
  90 class multi_array_view;
  91
  92 /////////////////////////////////////////////////////////////////////////
  93 // class interfaces
  94 /////////////////////////////////////////////////////////////////////////
  95
  96 class multi_array_base {
  97 public:
  98   typedef multi_array_types::size_type size_type;
  99   typedef multi_array_types::difference_type difference_type;
 100   typedef multi_array_types::index index;
 101   typedef multi_array_types::index_range index_range;
 102   typedef multi_array_types::extent_range extent_range;
 103   typedef multi_array_types::index_gen index_gen;
 104   typedef multi_array_types::extent_gen extent_gen;
 105 };
 106
 107 //
 108 // value_accessor_n
 109 //  contains the routines for accessing elements from
 110 //  N-dimensional views.
 111 //
 112 template<typename T, std::size_t NumDims>
 113 class value_accessor_n : public multi_array_base {
 114   typedef multi_array_base super_type;
 115 public:
 116   typedef typename super_type::index index;
 117
 118   //
 119   // public typedefs used by classes that inherit from this base
 120   //
 121   typedef T element;
 122   typedef boost::multi_array<T,NumDims-1> value_type;
 123   typedef sub_array<T,NumDims-1> reference;
 124   typedef const_sub_array<T,NumDims-1> const_reference;
 125
 126 protected:
 127   // used by array operator[] and iterators to get reference types.
 128   template <typename Reference, typename TPtr>
 129   Reference access(boost::type<Reference>,index idx,TPtr base,
 130                    const size_type* extents,
 131                    const index* strides,
 132                    const index* index_base) const {
 133
 134     // return a sub_array<T,NDims-1> proxy object
 135     TPtr newbase = base + idx * strides[0];
 136     return Reference(newbase,extents+1,strides+1,index_base+1);
 137
 138   }
 139
 140   value_accessor_n() { }
 141   ~value_accessor_n() { }
 142 };
 143
 144
 145
 146 //
 147 // value_accessor_one
 148 //  contains the routines for accessing reference elements from
 149 //  1-dimensional views.
 150 //
 151 template<typename T>
 152 class value_accessor_one : public multi_array_base {
 153   typedef multi_array_base super_type;
 154 public:
 155   typedef typename super_type::index index;
 156   //
 157   // public typedefs for use by classes that inherit it.
 158   //
 159   typedef T element;
 160   typedef T value_type;
 161   typedef T& reference;
 162   typedef T const& const_reference;
 163
 164 protected:
 165   // used by array operator[] and iterators to get reference types.
 166   template <typename Reference, typename TPtr>
 167   Reference access(boost::type<Reference>,index idx,TPtr base,
 168                    const size_type*,
 169                    const index* strides,
 170                    const index*) const {
 171     return *(base + idx * strides[0]);
 172   }
 173
 174   value_accessor_one() { }
 175   ~value_accessor_one() { }
 176 };
 177
 178
 179 /////////////////////////////////////////////////////////////////////////
 180 // choose value accessor begins
 181 //
 182
 183 template <typename T, std::size_t NumDims>
 184 struct choose_value_accessor_n {
 185   typedef value_accessor_n<T,NumDims> type;
 186 };
 187
 188 template <typename T>
 189 struct choose_value_accessor_one {
 190   typedef value_accessor_one<T> type;
 191 };
 192
 193 template <typename T, typename NumDims>
 194 struct value_accessor_generator {
 195     BOOST_STATIC_CONSTANT(std::size_t, dimensionality = NumDims::value);
 196
 197   typedef typename
 198   mpl::eval_if_c<(dimensionality == 1),
 199                   choose_value_accessor_one<T>,
 200                   choose_value_accessor_n<T,dimensionality>
 201   >::type type;
 202 };
 203
 204 #if BOOST_WORKAROUND(BOOST_MSVC, == 1200)
 205
 206 struct eti_value_accessor
 207 {
 208   typedef int index;
 209   typedef int size_type;
 210   typedef int element;
 211   typedef int index_range;
 212   typedef int value_type;
 213   typedef int reference;
 214   typedef int const_reference;
 215 };
 216
 217 template <>
 218 struct value_accessor_generator<int,int>
 219 {
 220   typedef eti_value_accessor type;
 221 };
 222
 223 template <class T, class NumDims>
 224 struct associated_types
 225   : mpl::aux::msvc_eti_base<
 226         typename value_accessor_generator<T,NumDims>::type
 227     >::type
 228 {};
 229
 230 template <>
 231 struct associated_types<int,int> : eti_value_accessor {};
 232
 233 #else
 234
 235 template <class T, class NumDims>
 236 struct associated_types
 237   : value_accessor_generator<T,NumDims>::type
 238 {};
 239
 240 #endif
 241
 242 //
 243 // choose value accessor ends
 244 /////////////////////////////////////////////////////////////////////////
 245
 246
 247
 248 ////////////////////////////////////////////////////////////////////////
 249 // multi_array_base
 250 ////////////////////////////////////////////////////////////////////////
 251 template <typename T, std::size_t NumDims>
 252 class multi_array_impl_base
 253   :
 254 #if BOOST_WORKAROUND(BOOST_MSVC, == 1200)
 255       public mpl::aux::msvc_eti_base<
 256           typename value_accessor_generator<T,mpl::size_t<NumDims> >::type
 257        >::type
 258 #else
 259       public value_accessor_generator<T,mpl::size_t<NumDims> >::type
 260 #endif
 261 {
 262   typedef associated_types<T,mpl::size_t<NumDims> > types;
 263 public:
 264   typedef typename types::index index;
 265   typedef typename types::size_type size_type;
 266   typedef typename types::element element;
 267   typedef typename types::index_range index_range;
 268   typedef typename types::value_type value_type;
 269   typedef typename types::reference reference;
 270   typedef typename types::const_reference const_reference;
 271
 272   template <std::size_t NDims>
 273   struct subarray {
 274     typedef boost::detail::multi_array::sub_array<T,NDims> type;
 275   };
 276
 277   template <std::size_t NDims>
 278   struct const_subarray {
 279     typedef boost::detail::multi_array::const_sub_array<T,NDims> type;
 280   };
 281
 282   template <std::size_t NDims>
 283   struct array_view {
 284     typedef boost::detail::multi_array::multi_array_view<T,NDims> type;
 285   };
 286
 287   template <std::size_t NDims>
 288   struct const_array_view {
 289   public:
 290     typedef boost::detail::multi_array::const_multi_array_view<T,NDims> type;
 291   };
 292
 293   //
 294   // iterator support
 295   //
 296   typedef array_iterator<T,T*,mpl::size_t<NumDims>,reference> iterator;
 297   typedef array_iterator<T,T const*,mpl::size_t<NumDims>,const_reference> const_iterator;
 298
 299   typedef ::boost::reverse_iterator<iterator> reverse_iterator;
 300   typedef ::boost::reverse_iterator<const_iterator> const_reverse_iterator;
 301
 302   BOOST_STATIC_CONSTANT(std::size_t, dimensionality = NumDims);
 303 protected:
 304
 305   multi_array_impl_base() { }
 306   ~multi_array_impl_base() { }
 307
 308   // Used by operator() in our array classes
 309   template <typename Reference, typename IndexList, typename TPtr>
 310   Reference access_element(boost::type<Reference>, TPtr base,
 311                            const IndexList& indices,
 312                            const index* strides) const {
 313     index offset = 0;
 314     for (size_type n = 0; n != NumDims; ++n)
 315       offset += indices[n] * strides[n];
 316
 317     return base[offset];
 318   }
 319
 320   template <typename StrideList, typename ExtentList>
 321   void compute_strides(StrideList& stride_list, ExtentList& extent_list,
 322                        const general_storage_order<NumDims>& storage)
 323   {
 324     // invariant: stride = the stride for dimension n
 325     index stride = 1;
 326     for (size_type n = 0; n != NumDims; ++n) {
 327       index stride_sign = +1;
 328
 329       if (!storage.ascending(storage.ordering(n)))
 330         stride_sign = -1;
 331
 332       // The stride for this dimension is the product of the
 333       // lengths of the ranks minor to it.
 334       stride_list[storage.ordering(n)] = stride * stride_sign;
 335
 336       stride *= extent_list[storage.ordering(n)];
 337     }
 338   }
 339
 340   // This calculates the offset to the array base pointer due to:
 341   // 1. dimensions stored in descending order
 342   // 2. non-zero dimension index bases
 343   template <typename StrideList, typename ExtentList, typename BaseList>
 344   index
 345   calculate_origin_offset(const StrideList& stride_list,
 346                           const ExtentList& extent_list,
 347                           const general_storage_order<NumDims>& storage,
 348                           const BaseList& index_base_list)
 349   {
 350     return
 351       calculate_descending_dimension_offset(stride_list,extent_list,
 352                                             storage) +
 353       calculate_indexing_offset(stride_list,index_base_list);
 354   }
 355
 356   // This calculates the offset added to the base pointer that are
 357   // caused by descending dimensions
 358   template <typename StrideList, typename ExtentList>
 359   index
 360   calculate_descending_dimension_offset(const StrideList& stride_list,
 361                                 const ExtentList& extent_list,
 362                                 const general_storage_order<NumDims>& storage)
 363   {
 364     index offset = 0;
 365     if (!storage.all_dims_ascending())
 366       for (size_type n = 0; n != NumDims; ++n)
 367         if (!storage.ascending(n))
 368           offset -= (extent_list[n] - 1) * stride_list[n];
 369
 370     return offset;
 371   }
 372
 373   // This is used to reindex array_views, which are no longer
 374   // concerned about storage order (specifically, whether dimensions
 375   // are ascending or descending) since the viewed array handled it.
 376
 377   template <typename StrideList, typename BaseList>
 378   index
 379   calculate_indexing_offset(const StrideList& stride_list,
 380                           const BaseList& index_base_list)
 381   {
 382     index offset = 0;
 383     for (size_type n = 0; n != NumDims; ++n)
 384         offset -= stride_list[n] * index_base_list[n];
 385     return offset;
 386   }
 387
 388   // Slicing using an index_gen.
 389   // Note that populating an index_gen creates a type that encodes
 390   // both the number of dimensions in the current Array (NumDims), and
 391   // the Number of dimensions for the resulting view.  This allows the
 392   // compiler to fail if the dimensions aren't completely accounted
 393   // for.  For reasons unbeknownst to me, a BOOST_STATIC_ASSERT
 394   // within the member function template does not work. I should add a
 395   // note to the documentation specifying that you get a damn ugly
 396   // error message if you screw up in your slicing code.
 397   template <typename ArrayRef, int NDims, typename TPtr>
 398   ArrayRef
 399   generate_array_view(boost::type<ArrayRef>,
 400                       const boost::detail::multi_array::
 401                       index_gen<NumDims,NDims>& indices,
 402                       const size_type* extents,
 403                       const index* strides,
 404                       const index* index_bases,
 405                       TPtr base) const {
 406
 407     boost::array<index,NDims> new_strides;
 408     boost::array<index,NDims> new_extents;
 409
 410     index offset = 0;
 411     size_type dim = 0;
 412     for (size_type n = 0; n != NumDims; ++n) {
 413       const index default_start = index_bases[n];
 414       const index default_finish = default_start+extents[n];
 415       const index_range& current_range = indices.ranges_[n];
 416       index start = current_range.get_start(default_start);
 417       index finish = current_range.get_finish(default_finish);
 418       index index_factor = current_range.stride();
 419       index len = (finish - start + (index_factor - 1)) / index_factor;
 420
 421       // the array data pointer is modified to account for non-zero
 422       // bases during slicing (see [Garcia] for the math involved)
 423       offset += start * strides[n];
 424
 425       if (!current_range.is_degenerate()) {
 426
 427         // The index_factor for each dimension is included into the
 428         // strides for the array_view (see [Garcia] for the math involved).
 429         new_strides[dim] = index_factor * strides[n];
 430
 431         // calculate new extents
 432         new_extents[dim] = len;
 433         ++dim;
 434       }
 435     }
 436     assert (dim == NDims);
 437
 438     return
 439       ArrayRef(base+offset,
 440                new_extents,
 441                new_strides);
 442   }
 443
 444
 445 };
 446
 447 } // namespace multi_array
 448 } // namespace detail
 449
 450 } // namespace boost
 451
 452 #endif // BASE_RG071801_HPP