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