// Copyright 2002 The Trustees of Indiana University.

// Use, modification and distribution is subject to the Boost Software 

// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at

// http://www.boost.org/LICENSE_1_0.txt)

//  Boost.MultiArray Library

//  Authors: Ronald Garcia

//           Jeremy Siek

//           Andrew Lumsdaine

//  See http://www.boost.org/libs/multi_array for documentation.

#ifndef BOOST_MULTI_ARRAY_RG071801_HPP

#define BOOST_MULTI_ARRAY_RG071801_HPP

//

// multi_array.hpp - contains the multi_array class template

// declaration and definition

//

#include "boost/multi_array/base.hpp"

#include "boost/multi_array/collection_concept.hpp"

#include "boost/multi_array/copy_array.hpp"

#include "boost/multi_array/iterator.hpp"

#include "boost/multi_array/subarray.hpp"

#include "boost/multi_array/multi_array_ref.hpp"

#include "boost/multi_array/algorithm.hpp"

#include "boost/array.hpp"

#include "boost/mpl/if.hpp"

#include "boost/type_traits.hpp"

#include <algorithm>

#include <cstddef>

#include <functional>

#include <numeric>

#include <vector>

namespace boost {

  namespace detail {

    namespace multi_array {

      struct populate_index_ranges {

        multi_array_types::index_range

        // RG: underscore on extent_ to stifle strange MSVC warning.

        operator()(multi_array_types::index base,

                   multi_array_types::size_type extent_) {

          return multi_array_types::index_range(base,base+extent_);

        }

      };

#ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING

//

// Compilers that don't support partial ordering may need help to

// disambiguate multi_array's templated constructors.  Even vc6/7 are

// capable of some limited SFINAE, so we take the most-general version

// out of the overload set with disable_multi_array_impl.

//

template <typename T, std::size_t NumDims, typename TPtr>

char is_multi_array_impl_help(const_multi_array_view<T,NumDims,TPtr>&);

template <typename T, std::size_t NumDims, typename TPtr>

char is_multi_array_impl_help(const_sub_array<T,NumDims,TPtr>&);

template <typename T, std::size_t NumDims, typename TPtr>

char is_multi_array_impl_help(const_multi_array_ref<T,NumDims,TPtr>&);

char ( &is_multi_array_impl_help(...) )[2];

template <class T>

struct is_multi_array_impl

{

    static T x;

    BOOST_STATIC_CONSTANT(bool, value = sizeof((is_multi_array_impl_help)(x)) == 1);

  typedef mpl::bool_<value> type;

};

template <bool multi_array = false>

struct disable_multi_array_impl_impl

{

    typedef int type;

};

template <>

struct disable_multi_array_impl_impl<true>

{

    // forming a pointer to a reference triggers SFINAE

    typedef int& type; 

};

template <class T>

struct disable_multi_array_impl :

  disable_multi_array_impl_impl<is_multi_array_impl<T>::value>

{ };

template <>

struct disable_multi_array_impl<int>

{

  typedef int type;

};

#endif

    } //namespace multi_array

  } // namespace detail

template<typename T, std::size_t NumDims,

  typename Allocator>

class multi_array :

  public multi_array_ref<T,NumDims>

{

  typedef multi_array_ref<T,NumDims> super_type;

public:

  typedef typename super_type::value_type value_type;

  typedef typename super_type::reference reference;

  typedef typename super_type::const_reference const_reference;

  typedef typename super_type::iterator iterator;

  typedef typename super_type::const_iterator const_iterator;

  typedef typename super_type::reverse_iterator reverse_iterator;

  typedef typename super_type::const_reverse_iterator const_reverse_iterator;

  typedef typename super_type::element element;

  typedef typename super_type::size_type size_type;

  typedef typename super_type::difference_type difference_type;

  typedef typename super_type::index index;

  typedef typename super_type::extent_range extent_range;

  template <std::size_t NDims>

  struct const_array_view {

    typedef boost::detail::multi_array::const_multi_array_view<T,NDims> type;

  };

  template <std::size_t NDims>

  struct array_view {

    typedef boost::detail::multi_array::multi_array_view<T,NDims> type;

  };

  explicit multi_array() :

    super_type((T*)initial_base_,c_storage_order(),

               /*index_bases=*/0, /*extents=*/0) {

    allocate_space(); 

  }

  template <class ExtentList>

  explicit multi_array(

      ExtentList const& extents

#ifdef BOOST_NO_FUNCTION_TEMPLATE_ORDERING

      , typename mpl::if_<

      detail::multi_array::is_multi_array_impl<ExtentList>,

      int&,int>::type* = 0

#endif

      ) :

    super_type((T*)initial_base_,extents) {

    boost::function_requires<

      detail::multi_array::CollectionConcept<ExtentList> >();

    allocate_space();

  }

  template <class ExtentList>

  explicit multi_array(ExtentList const& extents,

                       const general_storage_order<NumDims>& so) :

    super_type((T*)initial_base_,extents,so) {

    boost::function_requires<

      detail::multi_array::CollectionConcept<ExtentList> >();

    allocate_space();

  }

  template <class ExtentList>

  explicit multi_array(ExtentList const& extents,

                       const general_storage_order<NumDims>& so,

                       Allocator const& alloc) :

    super_type((T*)initial_base_,extents,so), allocator_(alloc) {

    boost::function_requires<

      detail::multi_array::CollectionConcept<ExtentList> >();

    allocate_space();

  }

  explicit multi_array(const detail::multi_array

                       ::extent_gen<NumDims>& ranges) :

    super_type((T*)initial_base_,ranges) {

    allocate_space();

  }

  explicit multi_array(const detail::multi_array

                       ::extent_gen<NumDims>& ranges,

                       const general_storage_order<NumDims>& so) :

    super_type((T*)initial_base_,ranges,so) {

    allocate_space();

  }

  explicit multi_array(const detail::multi_array

                       ::extent_gen<NumDims>& ranges,

                       const general_storage_order<NumDims>& so,

                       Allocator const& alloc) :

    super_type((T*)initial_base_,ranges,so), allocator_(alloc) {

    allocate_space();

  }

  multi_array(const multi_array& rhs) :

  super_type(rhs), allocator_(rhs.allocator_) {

    allocate_space();

    boost::detail::multi_array::copy_n(rhs.base_,rhs.num_elements(),base_);

  }

  //

  // A multi_array is constructible from any multi_array_ref, subarray, or

  // array_view object.  The following constructors ensure that.

  //

  // Due to limited support for partial template ordering, 

  // MSVC 6&7 confuse the following with the most basic ExtentList 

  // constructor.

#ifndef BOOST_NO_FUNCTION_TEMPLATE_ORDERING

  template <typename OPtr>

  multi_array(const const_multi_array_ref<T,NumDims,OPtr>& rhs,

              const general_storage_order<NumDims>& so = c_storage_order())

    : super_type(0,so,rhs.index_bases(),rhs.shape()) 

  {

    allocate_space();

    // Warning! storage order may change, hence the following copy technique.

    std::copy(rhs.begin(),rhs.end(),this->begin());

  }

  template <typename OPtr>

  multi_array(const detail::multi_array::

              const_sub_array<T,NumDims,OPtr>& rhs,

              const general_storage_order<NumDims>& so = c_storage_order())

    : super_type(0,so,rhs.index_bases(),rhs.shape()) 

  {

    allocate_space();

    std::copy(rhs.begin(),rhs.end(),this->begin());

  }

  template <typename OPtr>

  multi_array(const detail::multi_array::

              const_multi_array_view<T,NumDims,OPtr>& rhs,

              const general_storage_order<NumDims>& so = c_storage_order())

    : super_type(0,so,rhs.index_bases(),rhs.shape()) 

  {

    allocate_space();

    std::copy(rhs.begin(),rhs.end(),this->begin());

  }

#else // BOOST_NO_FUNCTION_TEMPLATE_ORDERING

  // More limited support for MSVC

  multi_array(const const_multi_array_ref<T,NumDims>& rhs)

    : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape()) 

  {

    allocate_space();

    // Warning! storage order may change, hence the following copy technique.

    std::copy(rhs.begin(),rhs.end(),this->begin());

  }

  multi_array(const const_multi_array_ref<T,NumDims>& rhs,

              const general_storage_order<NumDims>& so)

    : super_type(0,so,rhs.index_bases(),rhs.shape()) 

  {

    allocate_space();

    // Warning! storage order may change, hence the following copy technique.

    std::copy(rhs.begin(),rhs.end(),this->begin());

  }

  multi_array(const detail::multi_array::

              const_sub_array<T,NumDims>& rhs)

    : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape()) 

  {

    allocate_space();

    std::copy(rhs.begin(),rhs.end(),this->begin());

  }

  multi_array(const detail::multi_array::

              const_sub_array<T,NumDims>& rhs,

              const general_storage_order<NumDims>& so)

    : super_type(0,so,rhs.index_bases(),rhs.shape()) 

  {

    allocate_space();

    std::copy(rhs.begin(),rhs.end(),this->begin());

  }

  multi_array(const detail::multi_array::

              const_multi_array_view<T,NumDims>& rhs)

    : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape()) 

  {

    allocate_space();

    std::copy(rhs.begin(),rhs.end(),this->begin());

  }

  multi_array(const detail::multi_array::

              const_multi_array_view<T,NumDims>& rhs,

              const general_storage_order<NumDims>& so)

    : super_type(0,so,rhs.index_bases(),rhs.shape()) 

  {

    allocate_space();

    std::copy(rhs.begin(),rhs.end(),this->begin());

  }

#endif // !BOOST_NO_FUNCTION_TEMPLATE_ORDERING

  // Thes constructors are necessary because of more exact template matches.

  multi_array(const multi_array_ref<T,NumDims>& rhs)

    : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape()) 

  {

    allocate_space();

    // Warning! storage order may change, hence the following copy technique.

    std::copy(rhs.begin(),rhs.end(),this->begin());

  }

  multi_array(const multi_array_ref<T,NumDims>& rhs,

              const general_storage_order<NumDims>& so)

    : super_type(0,so,rhs.index_bases(),rhs.shape()) 

  {

    allocate_space();

    // Warning! storage order may change, hence the following copy technique.

    std::copy(rhs.begin(),rhs.end(),this->begin());

  }

  multi_array(const detail::multi_array::

              sub_array<T,NumDims>& rhs)

    : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape()) 

  {

    allocate_space();

    std::copy(rhs.begin(),rhs.end(),this->begin());

  }

  multi_array(const detail::multi_array::

              sub_array<T,NumDims>& rhs,

              const general_storage_order<NumDims>& so)

    : super_type(0,so,rhs.index_bases(),rhs.shape()) 

  {

    allocate_space();

    std::copy(rhs.begin(),rhs.end(),this->begin());

  }

  multi_array(const detail::multi_array::

              multi_array_view<T,NumDims>& rhs)

    : super_type(0,c_storage_order(),rhs.index_bases(),rhs.shape()) 

  {

    allocate_space();

    std::copy(rhs.begin(),rhs.end(),this->begin());

  }

  multi_array(const detail::multi_array::

              multi_array_view<T,NumDims>& rhs,

              const general_storage_order<NumDims>& so)

    : super_type(0,so,rhs.index_bases(),rhs.shape()) 

  {

    allocate_space();

    std::copy(rhs.begin(),rhs.end(),this->begin());

  }

  // Since assignment is a deep copy, multi_array_ref

  // contains all the necessary code.

  template <typename ConstMultiArray>

  multi_array& operator=(const ConstMultiArray& other) {

    super_type::operator=(other);

    return *this;

  }

  multi_array& operator=(const multi_array& other) {

    if (&other != this) {

      super_type::operator=(other);

    }

    return *this;

  }

  template <typename ExtentList>

  multi_array& resize(const ExtentList& extents) {

    boost::function_requires<

      detail::multi_array::CollectionConcept<ExtentList> >();

    typedef detail::multi_array::extent_gen<NumDims> gen_type;

    gen_type ranges;

    for (int i=0; i != NumDims; ++i) {

      typedef typename gen_type::range range_type;

      ranges.ranges_[i] = range_type(0,extents[i]);

    }

    return this->resize(ranges);

  }

  multi_array& resize(const detail::multi_array

                      ::extent_gen<NumDims>& ranges) {

    // build a multi_array with the specs given

    multi_array new_array(ranges,this->storage_order());

    // build a view of tmp with the minimum extents

    // Get the minimum extents of the arrays.

    boost::array<size_type,NumDims> min_extents;

    const size_type& (*min)(const size_type&, const size_type&) =

      std::min;

    std::transform(new_array.extent_list_.begin(),new_array.extent_list_.end(),

                   this->extent_list_.begin(),

                   min_extents.begin(),

                   min);

    // typedef boost::array<index,NumDims> index_list;

    // Build index_gen objects to create views with the same shape

    // these need to be separate to handle non-zero index bases

    typedef detail::multi_array::index_gen<NumDims,NumDims> index_gen;

    index_gen old_idxes;

    index_gen new_idxes;

    std::transform(new_array.index_base_list_.begin(),

                   new_array.index_base_list_.end(),

                   min_extents.begin(),old_idxes.ranges_.begin(),

                   detail::multi_array::populate_index_ranges());

    std::transform(this->index_base_list_.begin(),

                   this->index_base_list_.end(),

                   min_extents.begin(),new_idxes.ranges_.begin(),

                   detail::multi_array::populate_index_ranges());

    // Build same-shape views of the two arrays

    typename

      multi_array::BOOST_NESTED_TEMPLATE array_view<NumDims>::type view_old = (*this)[old_idxes];

    typename

      multi_array::BOOST_NESTED_TEMPLATE array_view<NumDims>::type view_new = new_array[new_idxes];

    // Set the right portion of the new array

    view_new = view_old;

    using std::swap;

    // Swap the internals of these arrays.

    swap(this->super_type::base_,new_array.super_type::base_);

    swap(this->storage_,new_array.storage_);

    swap(this->extent_list_,new_array.extent_list_);

    swap(this->stride_list_,new_array.stride_list_);

    swap(this->index_base_list_,new_array.index_base_list_);

    swap(this->origin_offset_,new_array.origin_offset_);

    swap(this->directional_offset_,new_array.directional_offset_);

    swap(this->num_elements_,new_array.num_elements_);

    swap(this->allocator_,new_array.allocator_);

    swap(this->base_,new_array.base_);

    swap(this->allocated_elements_,new_array.allocated_elements_);

    return *this;

  }

  ~multi_array() {

    deallocate_space();

  }

private:

  void allocate_space() {

    typename Allocator::const_pointer no_hint=0;

    base_ = allocator_.allocate(this->num_elements(),no_hint);

    this->set_base_ptr(base_);

    allocated_elements_ = this->num_elements();

    std::uninitialized_fill_n(base_,allocated_elements_,T());

  }

  void deallocate_space() {

    if(base_) {

      for(T* i = base_; i != base_+allocated_elements_; ++i)

        allocator_.destroy(i);

      allocator_.deallocate(base_,allocated_elements_);

    }

  }

  typedef boost::array<size_type,NumDims> size_list;

  typedef boost::array<index,NumDims> index_list;

  Allocator allocator_;

  T* base_;

  size_type allocated_elements_;

  enum {initial_base_ = 0};

};

} // namespace boost

#endif // BOOST_MULTI_ARRAY_RG071801_HPP