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(),old_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(),new_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