boost/boost/multi_array/base.hpp

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