williamr@2: // Copyright 2002 The Trustees of Indiana University.
williamr@2: 
williamr@2: // Use, modification and distribution is subject to the Boost Software 
williamr@2: // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
williamr@2: // http://www.boost.org/LICENSE_1_0.txt)
williamr@2: 
williamr@2: //  Boost.MultiArray Library
williamr@2: //  Authors: Ronald Garcia
williamr@2: //           Jeremy Siek
williamr@2: //           Andrew Lumsdaine
williamr@2: //  See http://www.boost.org/libs/multi_array for documentation.
williamr@2: 
williamr@2: #ifndef BOOST_MULTI_ARRAY_RG071801_HPP
williamr@2: #define BOOST_MULTI_ARRAY_RG071801_HPP
williamr@2: 
williamr@2: //
williamr@2: // multi_array.hpp - contains the multi_array class template
williamr@2: // declaration and definition
williamr@2: //
williamr@2: 
williamr@2: #include "boost/multi_array/base.hpp"
williamr@2: #include "boost/multi_array/collection_concept.hpp"
williamr@2: #include "boost/multi_array/copy_array.hpp"
williamr@2: #include "boost/multi_array/iterator.hpp"
williamr@2: #include "boost/multi_array/subarray.hpp"
williamr@2: #include "boost/multi_array/multi_array_ref.hpp"
williamr@2: #include "boost/multi_array/algorithm.hpp"
williamr@2: #include "boost/array.hpp"
williamr@2: #include "boost/mpl/if.hpp"
williamr@2: #include "boost/type_traits.hpp"
williamr@2: #include <algorithm>
williamr@2: #include <cstddef>
williamr@2: #include <functional>
williamr@2: #include <numeric>
williamr@2: #include <vector>
williamr@2: 
williamr@2: 
williamr@2: 
williamr@2: namespace boost {
williamr@2:   namespace detail {
williamr@2:     namespace multi_array {
williamr@2: 
williamr@2:       struct populate_index_ranges {
williamr@2:         multi_array_types::index_range
williamr@2:         // RG: underscore on extent_ to stifle strange MSVC warning.
williamr@2:         operator()(multi_array_types::index base,
williamr@2:                    multi_array_types::size_type extent_) {
williamr@2:           return multi_array_types::index_range(base,base+extent_);
williamr@2:         }
williamr@2:       };
williamr@2: 
williamr@2: #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
williamr@2: //
williamr@2: // Compilers that don't support partial ordering may need help to
williamr@2: // disambiguate multi_array's templated constructors.  Even vc6/7 are
williamr@2: // capable of some limited SFINAE, so we take the most-general version
williamr@2: // out of the overload set with disable_multi_array_impl.
williamr@2: //
williamr@2: template <typename T, std::size_t NumDims, typename TPtr>
williamr@2: char is_multi_array_impl_help(const_multi_array_view<T,NumDims,TPtr>&);
williamr@2: template <typename T, std::size_t NumDims, typename TPtr>
williamr@2: char is_multi_array_impl_help(const_sub_array<T,NumDims,TPtr>&);
williamr@2: template <typename T, std::size_t NumDims, typename TPtr>
williamr@2: char is_multi_array_impl_help(const_multi_array_ref<T,NumDims,TPtr>&);
williamr@2: 
williamr@2: char ( &is_multi_array_impl_help(...) )[2];
williamr@2: 
williamr@2: template <class T>
williamr@2: struct is_multi_array_impl
williamr@2: {
williamr@2:     static T x;
williamr@2:     BOOST_STATIC_CONSTANT(bool, value = sizeof((is_multi_array_impl_help)(x)) == 1);
williamr@2: 
williamr@2:   typedef mpl::bool_<value> type;
williamr@2: };
williamr@2: 
williamr@2: template <bool multi_array = false>
williamr@2: struct disable_multi_array_impl_impl
williamr@2: {
williamr@2:     typedef int type;
williamr@2: };
williamr@2: 
williamr@2: template <>
williamr@2: struct disable_multi_array_impl_impl<true>
williamr@2: {
williamr@2:     // forming a pointer to a reference triggers SFINAE
williamr@2:     typedef int& type; 
williamr@2: };
williamr@2: 
williamr@2: 
williamr@2: template <class T>
williamr@2: struct disable_multi_array_impl :
williamr@2:   disable_multi_array_impl_impl<is_multi_array_impl<T>::value>
williamr@2: { };
williamr@2: 
williamr@2: 
williamr@2: template <>
williamr@2: struct disable_multi_array_impl<int>
williamr@2: {
williamr@2:   typedef int type;
williamr@2: };
williamr@2: 
williamr@2: 
williamr@2: #endif
williamr@2: 
williamr@2:     } //namespace multi_array
williamr@2:   } // namespace detail
williamr@2: 
williamr@2: template<typename T, std::size_t NumDims,
williamr@2:   typename Allocator>
williamr@2: class multi_array :
williamr@2:   public multi_array_ref<T,NumDims>
williamr@2: {
williamr@2:   typedef multi_array_ref<T,NumDims> super_type;
williamr@2: public:
williamr@2:   typedef typename super_type::value_type value_type;
williamr@2:   typedef typename super_type::reference reference;
williamr@2:   typedef typename super_type::const_reference const_reference;
williamr@2:   typedef typename super_type::iterator iterator;
williamr@2:   typedef typename super_type::const_iterator const_iterator;
williamr@2:   typedef typename super_type::reverse_iterator reverse_iterator;
williamr@2:   typedef typename super_type::const_reverse_iterator const_reverse_iterator;
williamr@2:   typedef typename super_type::element element;
williamr@2:   typedef typename super_type::size_type size_type;
williamr@2:   typedef typename super_type::difference_type difference_type;
williamr@2:   typedef typename super_type::index index;
williamr@2:   typedef typename super_type::extent_range extent_range;
williamr@2: 
williamr@2: 
williamr@2:   template <std::size_t NDims>
williamr@2:   struct const_array_view {
williamr@2:     typedef boost::detail::multi_array::const_multi_array_view<T,NDims> type;
williamr@2:   };
williamr@2: 
williamr@2:   template <std::size_t NDims>
williamr@2:   struct array_view {
williamr@2:     typedef boost::detail::multi_array::multi_array_view<T,NDims> type;
williamr@2:   };
williamr@2: 
williamr@2:   explicit multi_array() :
williamr@2:     super_type((T*)initial_base_,c_storage_order(),
williamr@2:                /*index_bases=*/0, /*extents=*/0) {
williamr@2:     allocate_space(); 
williamr@2:   }
williamr@2: 
williamr@2:   template <class ExtentList>
williamr@2:   explicit multi_array(
williamr@2:       ExtentList const& extents
williamr@2: #ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
williamr@2:       , typename mpl::if_<
williamr@2:       detail::multi_array::is_multi_array_impl<ExtentList>,
williamr@2:       int&,int>::type* = 0
williamr@2: #endif
williamr@2:       ) :
williamr@2:     super_type((T*)initial_base_,extents) {
williamr@2:     boost::function_requires<
williamr@2:       detail::multi_array::CollectionConcept<ExtentList> >();
williamr@2:     allocate_space();
williamr@2:   }
williamr@2: 
williamr@2:     
williamr@2:   template <class ExtentList>
williamr@2:   explicit multi_array(ExtentList const& extents,
williamr@2:                        const general_storage_order<NumDims>& so) :
williamr@2:     super_type((T*)initial_base_,extents,so) {
williamr@2:     boost::function_requires<
williamr@2:       detail::multi_array::CollectionConcept<ExtentList> >();
williamr@2:     allocate_space();
williamr@2:   }
williamr@2: 
williamr@2:   template <class ExtentList>
williamr@2:   explicit multi_array(ExtentList const& extents,
williamr@2:                        const general_storage_order<NumDims>& so,
williamr@2:                        Allocator const& alloc) :
williamr@2:     super_type((T*)initial_base_,extents,so), allocator_(alloc) {
williamr@2:     boost::function_requires<
williamr@2:       detail::multi_array::CollectionConcept<ExtentList> >();
williamr@2:     allocate_space();
williamr@2:   }
williamr@2: 
williamr@2: 
williamr@2:   explicit multi_array(const detail::multi_array
williamr@2:                        ::extent_gen<NumDims>& ranges) :
williamr@2:     super_type((T*)initial_base_,ranges) {
williamr@2: 
williamr@2:     allocate_space();
williamr@2:   }
williamr@2: 
williamr@2: 
williamr@2:   explicit multi_array(const detail::multi_array
williamr@2:                        ::extent_gen<NumDims>& ranges,
williamr@2:                        const general_storage_order<NumDims>& so) :
williamr@2:     super_type((T*)initial_base_,ranges,so) {
williamr@2: 
williamr@2:     allocate_space();
williamr@2:   }
williamr@2: 
williamr@2: 
williamr@2:   explicit multi_array(const detail::multi_array
williamr@2:                        ::extent_gen<NumDims>& ranges,
williamr@2:                        const general_storage_order<NumDims>& so,
williamr@2:                        Allocator const& alloc) :
williamr@2:     super_type((T*)initial_base_,ranges,so), allocator_(alloc) {
williamr@2: 
williamr@2:     allocate_space();
williamr@2:   }
williamr@2: 
williamr@2:   multi_array(const multi_array& rhs) :
williamr@2:   super_type(rhs), allocator_(rhs.allocator_) {
williamr@2:     allocate_space();
williamr@2:     boost::detail::multi_array::copy_n(rhs.base_,rhs.num_elements(),base_);
williamr@2:   }
williamr@2: 
williamr@2: 
williamr@2:   //
williamr@2:   // A multi_array is constructible from any multi_array_ref, subarray, or
williamr@2:   // array_view object.  The following constructors ensure that.
williamr@2:   //
williamr@2: 
williamr@2:   // Due to limited support for partial template ordering, 
williamr@2:   // MSVC 6&7 confuse the following with the most basic ExtentList 
williamr@2:   // constructor.
williamr@2: #ifndef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
williamr@2:   template <typename OPtr>
williamr@2:   multi_array(const const_multi_array_ref<T,NumDims,OPtr>& rhs,
williamr@2:               const general_storage_order<NumDims>& so = c_storage_order())
williamr@2:     : super_type(0,so,rhs.index_bases(),rhs.shape()) 
williamr@2:   {
williamr@2:     allocate_space();
williamr@2:     // Warning! storage order may change, hence the following copy technique.
williamr@2:     std::copy(rhs.begin(),rhs.end(),this->begin());
williamr@2:   }
williamr@2: 
williamr@2:   template <typename OPtr>
williamr@2:   multi_array(const detail::multi_array::
williamr@2:               const_sub_array<T,NumDims,OPtr>& rhs,
williamr@2:               const general_storage_order<NumDims>& so = c_storage_order())
williamr@2:     : super_type(0,so,rhs.index_bases(),rhs.shape()) 
williamr@2:   {
williamr@2:     allocate_space();
williamr@2:     std::copy(rhs.begin(),rhs.end(),this->begin());
williamr@2:   }
williamr@2: 
williamr@2: 
williamr@2:   template <typename OPtr>
williamr@2:   multi_array(const detail::multi_array::
williamr@2:               const_multi_array_view<T,NumDims,OPtr>& rhs,
williamr@2:               const general_storage_order<NumDims>& so = c_storage_order())
williamr@2:     : super_type(0,so,rhs.index_bases(),rhs.shape()) 
williamr@2:   {
williamr@2:     allocate_space();
williamr@2:     std::copy(rhs.begin(),rhs.end(),this->begin());
williamr@2:   }
williamr@2: 
williamr@2: #else // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
williamr@2:   // More limited support for MSVC
williamr@2: 
williamr@2: 
williamr@2:   multi_array(const const_multi_array_ref<T,NumDims>& rhs)
williamr@2:     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape()) 
williamr@2:   {
williamr@2:     allocate_space();
williamr@2:     // Warning! storage order may change, hence the following copy technique.
williamr@2:     std::copy(rhs.begin(),rhs.end(),this->begin());
williamr@2:   }
williamr@2: 
williamr@2:   multi_array(const const_multi_array_ref<T,NumDims>& rhs,
williamr@2:               const general_storage_order<NumDims>& so)
williamr@2:     : super_type(0,so,rhs.index_bases(),rhs.shape()) 
williamr@2:   {
williamr@2:     allocate_space();
williamr@2:     // Warning! storage order may change, hence the following copy technique.
williamr@2:     std::copy(rhs.begin(),rhs.end(),this->begin());
williamr@2:   }
williamr@2: 
williamr@2:   multi_array(const detail::multi_array::
williamr@2:               const_sub_array<T,NumDims>& rhs)
williamr@2:     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape()) 
williamr@2:   {
williamr@2:     allocate_space();
williamr@2:     std::copy(rhs.begin(),rhs.end(),this->begin());
williamr@2:   }
williamr@2: 
williamr@2:   multi_array(const detail::multi_array::
williamr@2:               const_sub_array<T,NumDims>& rhs,
williamr@2:               const general_storage_order<NumDims>& so)
williamr@2:     : super_type(0,so,rhs.index_bases(),rhs.shape()) 
williamr@2:   {
williamr@2:     allocate_space();
williamr@2:     std::copy(rhs.begin(),rhs.end(),this->begin());
williamr@2:   }
williamr@2: 
williamr@2: 
williamr@2:   multi_array(const detail::multi_array::
williamr@2:               const_multi_array_view<T,NumDims>& rhs)
williamr@2:     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape()) 
williamr@2:   {
williamr@2:     allocate_space();
williamr@2:     std::copy(rhs.begin(),rhs.end(),this->begin());
williamr@2:   }
williamr@2: 
williamr@2:   multi_array(const detail::multi_array::
williamr@2:               const_multi_array_view<T,NumDims>& rhs,
williamr@2:               const general_storage_order<NumDims>& so)
williamr@2:     : super_type(0,so,rhs.index_bases(),rhs.shape()) 
williamr@2:   {
williamr@2:     allocate_space();
williamr@2:     std::copy(rhs.begin(),rhs.end(),this->begin());
williamr@2:   }
williamr@2: 
williamr@2: #endif // !BOOST_NO_FUNCTION_TEMPLATE_ORDERING
williamr@2: 
williamr@2:   // Thes constructors are necessary because of more exact template matches.
williamr@2:   multi_array(const multi_array_ref<T,NumDims>& rhs)
williamr@2:     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape()) 
williamr@2:   {
williamr@2:     allocate_space();
williamr@2:     // Warning! storage order may change, hence the following copy technique.
williamr@2:     std::copy(rhs.begin(),rhs.end(),this->begin());
williamr@2:   }
williamr@2: 
williamr@2:   multi_array(const multi_array_ref<T,NumDims>& rhs,
williamr@2:               const general_storage_order<NumDims>& so)
williamr@2:     : super_type(0,so,rhs.index_bases(),rhs.shape()) 
williamr@2:   {
williamr@2:     allocate_space();
williamr@2:     // Warning! storage order may change, hence the following copy technique.
williamr@2:     std::copy(rhs.begin(),rhs.end(),this->begin());
williamr@2:   }
williamr@2: 
williamr@2: 
williamr@2:   multi_array(const detail::multi_array::
williamr@2:               sub_array<T,NumDims>& rhs)
williamr@2:     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape()) 
williamr@2:   {
williamr@2:     allocate_space();
williamr@2:     std::copy(rhs.begin(),rhs.end(),this->begin());
williamr@2:   }
williamr@2: 
williamr@2:   multi_array(const detail::multi_array::
williamr@2:               sub_array<T,NumDims>& rhs,
williamr@2:               const general_storage_order<NumDims>& so)
williamr@2:     : super_type(0,so,rhs.index_bases(),rhs.shape()) 
williamr@2:   {
williamr@2:     allocate_space();
williamr@2:     std::copy(rhs.begin(),rhs.end(),this->begin());
williamr@2:   }
williamr@2: 
williamr@2: 
williamr@2:   multi_array(const detail::multi_array::
williamr@2:               multi_array_view<T,NumDims>& rhs)
williamr@2:     : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape()) 
williamr@2:   {
williamr@2:     allocate_space();
williamr@2:     std::copy(rhs.begin(),rhs.end(),this->begin());
williamr@2:   }
williamr@2:     
williamr@2:   multi_array(const detail::multi_array::
williamr@2:               multi_array_view<T,NumDims>& rhs,
williamr@2:               const general_storage_order<NumDims>& so)
williamr@2:     : super_type(0,so,rhs.index_bases(),rhs.shape()) 
williamr@2:   {
williamr@2:     allocate_space();
williamr@2:     std::copy(rhs.begin(),rhs.end(),this->begin());
williamr@2:   }
williamr@2:     
williamr@2:   // Since assignment is a deep copy, multi_array_ref
williamr@2:   // contains all the necessary code.
williamr@2:   template <typename ConstMultiArray>
williamr@2:   multi_array& operator=(const ConstMultiArray& other) {
williamr@2:     super_type::operator=(other);
williamr@2:     return *this;
williamr@2:   }
williamr@2: 
williamr@2:   multi_array& operator=(const multi_array& other) {
williamr@2:     if (&other != this) {
williamr@2:       super_type::operator=(other);
williamr@2:     }
williamr@2:     return *this;
williamr@2:   }
williamr@2: 
williamr@2: 
williamr@2:   template <typename ExtentList>
williamr@2:   multi_array& resize(const ExtentList& extents) {
williamr@2:     boost::function_requires<
williamr@2:       detail::multi_array::CollectionConcept<ExtentList> >();
williamr@2: 
williamr@2:     typedef detail::multi_array::extent_gen<NumDims> gen_type;
williamr@2:     gen_type ranges;
williamr@2: 
williamr@2:     for (int i=0; i != NumDims; ++i) {
williamr@2:       typedef typename gen_type::range range_type;
williamr@2:       ranges.ranges_[i] = range_type(0,extents[i]);
williamr@2:     }
williamr@2:     
williamr@2:     return this->resize(ranges);
williamr@2:   }
williamr@2: 
williamr@2: 
williamr@2: 
williamr@2:   multi_array& resize(const detail::multi_array
williamr@2:                       ::extent_gen<NumDims>& ranges) {
williamr@2: 
williamr@2: 
williamr@2:     // build a multi_array with the specs given
williamr@2:     multi_array new_array(ranges,this->storage_order());
williamr@2: 
williamr@2: 
williamr@2:     // build a view of tmp with the minimum extents
williamr@2: 
williamr@2:     // Get the minimum extents of the arrays.
williamr@2:     boost::array<size_type,NumDims> min_extents;
williamr@2: 
williamr@2:     const size_type& (*min)(const size_type&, const size_type&) =
williamr@2:       std::min;
williamr@2:     std::transform(new_array.extent_list_.begin(),new_array.extent_list_.end(),
williamr@2:                    this->extent_list_.begin(),
williamr@2:                    min_extents.begin(),
williamr@2:                    min);
williamr@2: 
williamr@2: 
williamr@2:     // typedef boost::array<index,NumDims> index_list;
williamr@2:     // Build index_gen objects to create views with the same shape
williamr@2: 
williamr@2:     // these need to be separate to handle non-zero index bases
williamr@2:     typedef detail::multi_array::index_gen<NumDims,NumDims> index_gen;
williamr@2:     index_gen old_idxes;
williamr@2:     index_gen new_idxes;
williamr@2: 
williamr@2:     std::transform(new_array.index_base_list_.begin(),
williamr@2:                    new_array.index_base_list_.end(),
williamr@2:                    min_extents.begin(),old_idxes.ranges_.begin(),
williamr@2:                    detail::multi_array::populate_index_ranges());
williamr@2: 
williamr@2:     std::transform(this->index_base_list_.begin(),
williamr@2:                    this->index_base_list_.end(),
williamr@2:                    min_extents.begin(),new_idxes.ranges_.begin(),
williamr@2:                    detail::multi_array::populate_index_ranges());
williamr@2: 
williamr@2:     // Build same-shape views of the two arrays
williamr@2:     typename
williamr@2:       multi_array::BOOST_NESTED_TEMPLATE array_view<NumDims>::type view_old = (*this)[old_idxes];
williamr@2:     typename
williamr@2:       multi_array::BOOST_NESTED_TEMPLATE array_view<NumDims>::type view_new = new_array[new_idxes];
williamr@2: 
williamr@2:     // Set the right portion of the new array
williamr@2:     view_new = view_old;
williamr@2: 
williamr@2:     using std::swap;
williamr@2:     // Swap the internals of these arrays.
williamr@2:     swap(this->super_type::base_,new_array.super_type::base_);
williamr@2:     swap(this->storage_,new_array.storage_);
williamr@2:     swap(this->extent_list_,new_array.extent_list_);
williamr@2:     swap(this->stride_list_,new_array.stride_list_);
williamr@2:     swap(this->index_base_list_,new_array.index_base_list_);
williamr@2:     swap(this->origin_offset_,new_array.origin_offset_);
williamr@2:     swap(this->directional_offset_,new_array.directional_offset_);
williamr@2:     swap(this->num_elements_,new_array.num_elements_);
williamr@2:     swap(this->allocator_,new_array.allocator_);
williamr@2:     swap(this->base_,new_array.base_);
williamr@2:     swap(this->allocated_elements_,new_array.allocated_elements_);
williamr@2: 
williamr@2:     return *this;
williamr@2:   }
williamr@2: 
williamr@2: 
williamr@2:   ~multi_array() {
williamr@2:     deallocate_space();
williamr@2:   }
williamr@2: 
williamr@2: private:
williamr@2:   void allocate_space() {
williamr@2:     typename Allocator::const_pointer no_hint=0;
williamr@2:     base_ = allocator_.allocate(this->num_elements(),no_hint);
williamr@2:     this->set_base_ptr(base_);
williamr@2:     allocated_elements_ = this->num_elements();
williamr@2:     std::uninitialized_fill_n(base_,allocated_elements_,T());
williamr@2:   }
williamr@2: 
williamr@2:   void deallocate_space() {
williamr@2:     if(base_) {
williamr@2:       for(T* i = base_; i != base_+allocated_elements_; ++i)
williamr@2:         allocator_.destroy(i);
williamr@2:       allocator_.deallocate(base_,allocated_elements_);
williamr@2:     }
williamr@2:   }
williamr@2: 
williamr@2:   typedef boost::array<size_type,NumDims> size_list;
williamr@2:   typedef boost::array<index,NumDims> index_list;
williamr@2: 
williamr@2:   Allocator allocator_;
williamr@2:   T* base_;
williamr@2:   size_type allocated_elements_;
williamr@2:   enum {initial_base_ = 0};
williamr@2: };
williamr@2: 
williamr@2: } // namespace boost
williamr@2: 
williamr@2: #endif // BOOST_MULTI_ARRAY_RG071801_HPP