boost/multi_array.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 BOOST_MULTI_ARRAY_RG071801_HPP
  14 #define BOOST_MULTI_ARRAY_RG071801_HPP
  15
  16 //
  17 // multi_array.hpp - contains the multi_array class template
  18 // declaration and definition
  19 //
  20
  21 #include "boost/multi_array/base.hpp"
  22 #include "boost/multi_array/collection_concept.hpp"
  23 #include "boost/multi_array/copy_array.hpp"
  24 #include "boost/multi_array/iterator.hpp"
  25 #include "boost/multi_array/subarray.hpp"
  26 #include "boost/multi_array/multi_array_ref.hpp"
  27 #include "boost/multi_array/algorithm.hpp"
  28 #include "boost/array.hpp"
  29 #include "boost/mpl/if.hpp"
  30 #include "boost/type_traits.hpp"
  31 #include <algorithm>
  32 #include <cstddef>
  33 #include <functional>
  34 #include <numeric>
  35 #include <vector>
  36
  37
  38
  39 namespace boost {
  40   namespace detail {
  41     namespace multi_array {
  42
  43       struct populate_index_ranges {
  44         multi_array_types::index_range
  45         // RG: underscore on extent_ to stifle strange MSVC warning.
  46         operator()(multi_array_types::index base,
  47                    multi_array_types::size_type extent_) {
  48           return multi_array_types::index_range(base,base+extent_);
  49         }
  50       };
  51
  52 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
  53 //
  54 // Compilers that don't support partial ordering may need help to
  55 // disambiguate multi_array's templated constructors.  Even vc6/7 are
  56 // capable of some limited SFINAE, so we take the most-general version
  57 // out of the overload set with disable_multi_array_impl.
  58 //
  59 template <typename T, std::size_t NumDims, typename TPtr>
  60 char is_multi_array_impl_help(const_multi_array_view<T,NumDims,TPtr>&);
  61 template <typename T, std::size_t NumDims, typename TPtr>
  62 char is_multi_array_impl_help(const_sub_array<T,NumDims,TPtr>&);
  63 template <typename T, std::size_t NumDims, typename TPtr>
  64 char is_multi_array_impl_help(const_multi_array_ref<T,NumDims,TPtr>&);
  65
  66 char ( &is_multi_array_impl_help(...) )[2];
  67
  68 template <class T>
  69 struct is_multi_array_impl
  70 {
  71     static T x;
  72     BOOST_STATIC_CONSTANT(bool, value = sizeof((is_multi_array_impl_help)(x)) == 1);
  73
  74   typedef mpl::bool_<value> type;
  75 };
  76
  77 template <bool multi_array = false>
  78 struct disable_multi_array_impl_impl
  79 {
  80     typedef int type;
  81 };
  82
  83 template <>
  84 struct disable_multi_array_impl_impl<true>
  85 {
  86     // forming a pointer to a reference triggers SFINAE
  87     typedef int& type;
  88 };
  89
  90
  91 template <class T>
  92 struct disable_multi_array_impl :
  93   disable_multi_array_impl_impl<is_multi_array_impl<T>::value>
  94 { };
  95
  96
  97 template <>
  98 struct disable_multi_array_impl<int>
  99 {
 100   typedef int type;
 101 };
 102
 103
 104 #endif
 105
 106     } //namespace multi_array
 107   } // namespace detail
 108
 109 template<typename T, std::size_t NumDims,
 110   typename Allocator>
 111 class multi_array :
 112   public multi_array_ref<T,NumDims>
 113 {
 114   typedef multi_array_ref<T,NumDims> super_type;
 115 public:
 116   typedef typename super_type::value_type value_type;
 117   typedef typename super_type::reference reference;
 118   typedef typename super_type::const_reference const_reference;
 119   typedef typename super_type::iterator iterator;
 120   typedef typename super_type::const_iterator const_iterator;
 121   typedef typename super_type::reverse_iterator reverse_iterator;
 122   typedef typename super_type::const_reverse_iterator const_reverse_iterator;
 123   typedef typename super_type::element element;
 124   typedef typename super_type::size_type size_type;
 125   typedef typename super_type::difference_type difference_type;
 126   typedef typename super_type::index index;
 127   typedef typename super_type::extent_range extent_range;
 128
 129
 130   template <std::size_t NDims>
 131   struct const_array_view {
 132     typedef boost::detail::multi_array::const_multi_array_view<T,NDims> type;
 133   };
 134
 135   template <std::size_t NDims>
 136   struct array_view {
 137     typedef boost::detail::multi_array::multi_array_view<T,NDims> type;
 138   };
 139
 140   explicit multi_array() :
 141     super_type((T*)initial_base_,c_storage_order(),
 142                /*index_bases=*/0, /*extents=*/0) {
 143     allocate_space();
 144   }
 145
 146   template <class ExtentList>
 147   explicit multi_array(
 148       ExtentList const& extents
 149 #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 150       , typename mpl::if_<
 151       detail::multi_array::is_multi_array_impl<ExtentList>,
 152       int&,int>::type* = 0
 153 #endif
 154       ) :
 155     super_type((T*)initial_base_,extents) {
 156     boost::function_requires<
 157       detail::multi_array::CollectionConcept<ExtentList> >();
 158     allocate_space();
 159   }
 160
 161
 162   template <class ExtentList>
 163   explicit multi_array(ExtentList const& extents,
 164                        const general_storage_order<NumDims>& so) :
 165     super_type((T*)initial_base_,extents,so) {
 166     boost::function_requires<
 167       detail::multi_array::CollectionConcept<ExtentList> >();
 168     allocate_space();
 169   }
 170
 171   template <class ExtentList>
 172   explicit multi_array(ExtentList const& extents,
 173                        const general_storage_order<NumDims>& so,
 174                        Allocator const& alloc) :
 175     super_type((T*)initial_base_,extents,so), allocator_(alloc) {
 176     boost::function_requires<
 177       detail::multi_array::CollectionConcept<ExtentList> >();
 178     allocate_space();
 179   }
 180
 181
 182   explicit multi_array(const detail::multi_array
 183                        ::extent_gen<NumDims>& ranges) :
 184     super_type((T*)initial_base_,ranges) {
 185
 186     allocate_space();
 187   }
 188
 189
 190   explicit multi_array(const detail::multi_array
 191                        ::extent_gen<NumDims>& ranges,
 192                        const general_storage_order<NumDims>& so) :
 193     super_type((T*)initial_base_,ranges,so) {
 194
 195     allocate_space();
 196   }
 197
 198
 199   explicit multi_array(const detail::multi_array
 200                        ::extent_gen<NumDims>& ranges,
 201                        const general_storage_order<NumDims>& so,
 202                        Allocator const& alloc) :
 203     super_type((T*)initial_base_,ranges,so), allocator_(alloc) {
 204
 205     allocate_space();
 206   }
 207
 208   multi_array(const multi_array& rhs) :
 209   super_type(rhs), allocator_(rhs.allocator_) {
 210     allocate_space();
 211     boost::detail::multi_array::copy_n(rhs.base_,rhs.num_elements(),base_);
 212   }
 213
 214
 215   //
 216   // A multi_array is constructible from any multi_array_ref, subarray, or
 217   // array_view object.  The following constructors ensure that.
 218   //
 219
 220   // Due to limited support for partial template ordering,
 221   // MSVC 6&7 confuse the following with the most basic ExtentList
 222   // constructor.
 223 #ifndef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 224   template <typename OPtr>
 225   multi_array(const const_multi_array_ref<T,NumDims,OPtr>& rhs,
 226               const general_storage_order<NumDims>& so = c_storage_order())
 227     : super_type(0,so,rhs.index_bases(),rhs.shape())
 228   {
 229     allocate_space();
 230     // Warning! storage order may change, hence the following copy technique.
 231     std::copy(rhs.begin(),rhs.end(),this->begin());
 232   }
 233
 234   template <typename OPtr>
 235   multi_array(const detail::multi_array::
 236               const_sub_array<T,NumDims,OPtr>& rhs,
 237               const general_storage_order<NumDims>& so = c_storage_order())
 238     : super_type(0,so,rhs.index_bases(),rhs.shape())
 239   {
 240     allocate_space();
 241     std::copy(rhs.begin(),rhs.end(),this->begin());
 242   }
 243
 244
 245   template <typename OPtr>
 246   multi_array(const detail::multi_array::
 247               const_multi_array_view<T,NumDims,OPtr>& rhs,
 248               const general_storage_order<NumDims>& so = c_storage_order())
 249     : super_type(0,so,rhs.index_bases(),rhs.shape())
 250   {
 251     allocate_space();
 252     std::copy(rhs.begin(),rhs.end(),this->begin());
 253   }
 254
 255 #else // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 256   // More limited support for MSVC
 257
 258
 259   multi_array(const const_multi_array_ref<T,NumDims>& rhs)
 260     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape())
 261   {
 262     allocate_space();
 263     // Warning! storage order may change, hence the following copy technique.
 264     std::copy(rhs.begin(),rhs.end(),this->begin());
 265   }
 266
 267   multi_array(const const_multi_array_ref<T,NumDims>& rhs,
 268               const general_storage_order<NumDims>& so)
 269     : super_type(0,so,rhs.index_bases(),rhs.shape())
 270   {
 271     allocate_space();
 272     // Warning! storage order may change, hence the following copy technique.
 273     std::copy(rhs.begin(),rhs.end(),this->begin());
 274   }
 275
 276   multi_array(const detail::multi_array::
 277               const_sub_array<T,NumDims>& rhs)
 278     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape())
 279   {
 280     allocate_space();
 281     std::copy(rhs.begin(),rhs.end(),this->begin());
 282   }
 283
 284   multi_array(const detail::multi_array::
 285               const_sub_array<T,NumDims>& rhs,
 286               const general_storage_order<NumDims>& so)
 287     : super_type(0,so,rhs.index_bases(),rhs.shape())
 288   {
 289     allocate_space();
 290     std::copy(rhs.begin(),rhs.end(),this->begin());
 291   }
 292
 293
 294   multi_array(const detail::multi_array::
 295               const_multi_array_view<T,NumDims>& rhs)
 296     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape())
 297   {
 298     allocate_space();
 299     std::copy(rhs.begin(),rhs.end(),this->begin());
 300   }
 301
 302   multi_array(const detail::multi_array::
 303               const_multi_array_view<T,NumDims>& rhs,
 304               const general_storage_order<NumDims>& so)
 305     : super_type(0,so,rhs.index_bases(),rhs.shape())
 306   {
 307     allocate_space();
 308     std::copy(rhs.begin(),rhs.end(),this->begin());
 309   }
 310
 311 #endif // !BOOST_NO_FUNCTION_TEMPLATE_ORDERING
 312
 313   // Thes constructors are necessary because of more exact template matches.
 314   multi_array(const multi_array_ref<T,NumDims>& rhs)
 315     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape())
 316   {
 317     allocate_space();
 318     // Warning! storage order may change, hence the following copy technique.
 319     std::copy(rhs.begin(),rhs.end(),this->begin());
 320   }
 321
 322   multi_array(const multi_array_ref<T,NumDims>& rhs,
 323               const general_storage_order<NumDims>& so)
 324     : super_type(0,so,rhs.index_bases(),rhs.shape())
 325   {
 326     allocate_space();
 327     // Warning! storage order may change, hence the following copy technique.
 328     std::copy(rhs.begin(),rhs.end(),this->begin());
 329   }
 330
 331
 332   multi_array(const detail::multi_array::
 333               sub_array<T,NumDims>& rhs)
 334     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape())
 335   {
 336     allocate_space();
 337     std::copy(rhs.begin(),rhs.end(),this->begin());
 338   }
 339
 340   multi_array(const detail::multi_array::
 341               sub_array<T,NumDims>& rhs,
 342               const general_storage_order<NumDims>& so)
 343     : super_type(0,so,rhs.index_bases(),rhs.shape())
 344   {
 345     allocate_space();
 346     std::copy(rhs.begin(),rhs.end(),this->begin());
 347   }
 348
 349
 350   multi_array(const detail::multi_array::
 351               multi_array_view<T,NumDims>& rhs)
 352     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape())
 353   {
 354     allocate_space();
 355     std::copy(rhs.begin(),rhs.end(),this->begin());
 356   }
 357
 358   multi_array(const detail::multi_array::
 359               multi_array_view<T,NumDims>& rhs,
 360               const general_storage_order<NumDims>& so)
 361     : super_type(0,so,rhs.index_bases(),rhs.shape())
 362   {
 363     allocate_space();
 364     std::copy(rhs.begin(),rhs.end(),this->begin());
 365   }
 366
 367   // Since assignment is a deep copy, multi_array_ref
 368   // contains all the necessary code.
 369   template <typename ConstMultiArray>
 370   multi_array& operator=(const ConstMultiArray& other) {
 371     super_type::operator=(other);
 372     return *this;
 373   }
 374
 375   multi_array& operator=(const multi_array& other) {
 376     if (&other != this) {
 377       super_type::operator=(other);
 378     }
 379     return *this;
 380   }
 381
 382
 383   template <typename ExtentList>
 384   multi_array& resize(const ExtentList& extents) {
 385     boost::function_requires<
 386       detail::multi_array::CollectionConcept<ExtentList> >();
 387
 388     typedef detail::multi_array::extent_gen<NumDims> gen_type;
 389     gen_type ranges;
 390
 391     for (int i=0; i != NumDims; ++i) {
 392       typedef typename gen_type::range range_type;
 393       ranges.ranges_[i] = range_type(0,extents[i]);
 394     }
 395
 396     return this->resize(ranges);
 397   }
 398
 399
 400
 401   multi_array& resize(const detail::multi_array
 402                       ::extent_gen<NumDims>& ranges) {
 403
 404
 405     // build a multi_array with the specs given
 406     multi_array new_array(ranges,this->storage_order());
 407
 408
 409     // build a view of tmp with the minimum extents
 410
 411     // Get the minimum extents of the arrays.
 412     boost::array<size_type,NumDims> min_extents;
 413
 414     const size_type& (*min)(const size_type&, const size_type&) =
 415       std::min;
 416     std::transform(new_array.extent_list_.begin(),new_array.extent_list_.end(),
 417                    this->extent_list_.begin(),
 418                    min_extents.begin(),
 419                    min);
 420
 421
 422     // typedef boost::array<index,NumDims> index_list;
 423     // Build index_gen objects to create views with the same shape
 424
 425     // these need to be separate to handle non-zero index bases
 426     typedef detail::multi_array::index_gen<NumDims,NumDims> index_gen;
 427     index_gen old_idxes;
 428     index_gen new_idxes;
 429
 430     std::transform(new_array.index_base_list_.begin(),
 431                    new_array.index_base_list_.end(),
 432                    min_extents.begin(),new_idxes.ranges_.begin(),
 433                    detail::multi_array::populate_index_ranges());
 434
 435     std::transform(this->index_base_list_.begin(),
 436                    this->index_base_list_.end(),
 437                    min_extents.begin(),old_idxes.ranges_.begin(),
 438                    detail::multi_array::populate_index_ranges());
 439
 440     // Build same-shape views of the two arrays
 441     typename
 442       multi_array::BOOST_NESTED_TEMPLATE array_view<NumDims>::type view_old = (*this)[old_idxes];
 443     typename
 444       multi_array::BOOST_NESTED_TEMPLATE array_view<NumDims>::type view_new = new_array[new_idxes];
 445
 446     // Set the right portion of the new array
 447     view_new = view_old;
 448
 449     using std::swap;
 450     // Swap the internals of these arrays.
 451     swap(this->super_type::base_,new_array.super_type::base_);
 452     swap(this->storage_,new_array.storage_);
 453     swap(this->extent_list_,new_array.extent_list_);
 454     swap(this->stride_list_,new_array.stride_list_);
 455     swap(this->index_base_list_,new_array.index_base_list_);
 456     swap(this->origin_offset_,new_array.origin_offset_);
 457     swap(this->directional_offset_,new_array.directional_offset_);
 458     swap(this->num_elements_,new_array.num_elements_);
 459     swap(this->allocator_,new_array.allocator_);
 460     swap(this->base_,new_array.base_);
 461     swap(this->allocated_elements_,new_array.allocated_elements_);
 462
 463     return *this;
 464   }
 465
 466
 467   ~multi_array() {
 468     deallocate_space();
 469   }
 470
 471 private:
 472   void allocate_space() {
 473     typename Allocator::const_pointer no_hint=0;
 474     base_ = allocator_.allocate(this->num_elements(),no_hint);
 475     this->set_base_ptr(base_);
 476     allocated_elements_ = this->num_elements();
 477     std::uninitialized_fill_n(base_,allocated_elements_,T());
 478   }
 479
 480   void deallocate_space() {
 481     if(base_) {
 482       for(T* i = base_; i != base_+allocated_elements_; ++i)
 483         allocator_.destroy(i);
 484       allocator_.deallocate(base_,allocated_elements_);
 485     }
 486   }
 487
 488   typedef boost::array<size_type,NumDims> size_list;
 489   typedef boost::array<index,NumDims> index_list;
 490
 491   Allocator allocator_;
 492   T* base_;
 493   size_type allocated_elements_;
 494   enum {initial_base_ = 0};
 495 };
 496
 497 } // namespace boost
 498
 499 #endif // BOOST_MULTI_ARRAY_RG071801_HPP