// Minor modifications for C++0X emulation libraries by Terry Golubiewski
// is_convertible<> was taken from Howard Hinnant's unique_ptr<> emulation.
//
//////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright David Abrahams, Vicente Botet, Ion Gaztanaga 2009.
// Distributed under 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)
//
// See http://www.boost.org/libs/move for documentation.
//
//////////////////////////////////////////////////////////////////////////////
//
// Parts of this file come from Adobe's Move library:
//
// Copyright 2005-2007 Adobe Systems Incorporated
// Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
// or a copy at http://stlab.adobe.com/licenses.html)
//
//////////////////////////////////////////////////////////////////////////////

//! \file

#ifndef STD0X_MOVE_H
#define STD0X_MOVE_H
#pragma once

#include <boost/utility/enable_if.hpp>
#include <boost/type_traits.hpp>
#include <boost/utility/addressof.hpp>

#include <boost/mpl/if.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/mpl/and.hpp>

#include <algorithm>
#include <memory>
#include <iterator>

#include <cstddef>

#define STD0X_ENABLE_MOVE(_Type_) \
  public: \
    typedef std0x::rv<_Type_>& rv_ref; \
    operator rv_ref()  \
      { return *reinterpret_cast< std0x::rv<_Type_>* >(this); } \
    operator const std0x::rv<_Type_>&() const \
      { return *reinterpret_cast< const std0x::rv<_Type_>* >(this); } \
  private: \
//

#define STD0X_ENABLE_MOVE_ONLY(_Type_) \
  private: \
    _Type_(_Type_&); \
    _Type_& operator=(_Type_&); \
  public: \
    typedef std0x::rv<_Type_>& rv_ref; \
    operator rv_ref()  \
      { return *reinterpret_cast< std0x::rv<_Type_>* >(this); } \
    operator const std0x::rv<_Type_>&() const \
      { return *reinterpret_cast< const std0x::rv<_Type_>* >(this); } \
  private: \
//

namespace std0x {

template<class T>
class rv: public T {
  rv();
  rv(const rv&);
  rv& operator=(const rv&);
public:
  ~rv();        // Needed to make destructor public or Microsoft complained.
}
#ifdef __GNUG__
__attribute__((__may_alias__))
#endif
; // rv

/// @cond

namespace move_detail {

namespace is_conv_impl {

typedef char one;
struct two { char _[2]; };
template<typename T> one test1(const T&);
template<typename T> two test1(...);
template<typename T> one test2(T);
template<typename T> two test2(...);
template<typename T> T source();

} // is_conv_impl

template<class Fm, class To, bool = true>
struct is_convertible_helper: public boost::is_convertible<Fm, To> { };

template<class Fm, class To>
struct is_convertible_test1: public boost::mpl::bool_<
  sizeof(is_conv_impl::test1<To>(is_conv_impl::source<Fm>())) == 1>
{ };

template<class Fm, class To>
struct is_convertible_test2: public boost::mpl::bool_<
  sizeof(is_conv_impl::test2<To>(is_conv_impl::source<Fm>())) == 1>
{ };

#if defined(__GNUG__)
template<class Fm, class To>
struct is_convertible_helper<Fm, To, true>
  : public is_convertible_test1<Fm, To> { };

// For move-only types
template<class T>
struct is_convertible_helper<T, T, true>
  : public is_convertible_test2<T, T> { };

#elif defined(_MSCVER)

template <class Fm, class To>
struct is_convertible_helper<Fm, To, true>
  : public is_convertible_test2<Fm, To> { };

#endif

template<class Fm, class To>
struct is_convertible: public is_convertible_helper<Fm, To> { };

} // move_detail

/// @endcond

template<class T>
struct is_movable
  : public boost::mpl::and_< boost::is_class<T>
                           , move_detail::is_convertible< T, rv<T>& >
                           >
{ };

template<class T>
struct is_movable< rv<T> >: public boost::mpl::false_ { };

// =================== move-aware type_traits ====================

template<typename T>
struct identity {
  typedef T type;
  const T& operator()(const T& x) const { return x; }
}; // identity

template<typename>
struct is_rvalue_reference: public boost::false_type { };

template<typename T>
struct is_rvalue_reference< rv<T>& >: public boost::true_type { };

template<typename>
struct is_lvalue_reference: public boost::false_type { };

template<typename T>
struct is_lvalue_reference<T&> : public boost::true_type { };

template<typename T>
struct is_lvalue_reference< rv<T>& > : public boost::false_type { };

template<typename T>
struct remove_reference { typedef T type; };

template<typename T>
struct remove_reference<T&> { typedef T type; };

template<typename T>
struct remove_reference< rv<T>& > { typedef T type; };

using boost::is_reference;
using boost::is_pointer;

/// @cond

namespace move_detail {

template<typename T,
         bool = boost::is_object<T>::value || boost::is_function<T>::value,
         bool = is_rvalue_reference<T>::value>
struct add_lvalue_reference_helper { typedef T type; };

template<typename T>
struct add_lvalue_reference_helper<T, true, false>
{ typedef T& type; };

template<typename T>
struct add_lvalue_reference_helper<T, false, true>
{ typedef typename remove_reference<T>::type& type; };

template<typename T,
         bool = boost::is_object<T>::value || boost::is_function<T>::value>
struct add_rvalue_reference_helper { typedef T type; }; // T is ref or void

template<typename T>
struct add_rvalue_reference_helper<T, true>
  : public boost::mpl::if_< is_movable<T>, rv<T>&, T>
{ };
            
} // move_detail

/// @endcond

template<typename T>
struct add_lvalue_reference: public move_detail::add_lvalue_reference_helper<T>
{ };

template<typename T>
struct add_rvalue_reference: public move_detail::add_rvalue_reference_helper<T>
{ };

// ============================== move =================================

template<class T> inline
typename boost::disable_if<is_movable<T>, T&>::type
move(T& x) { return x; }

template<class T> inline
typename boost::disable_if< is_movable<T>, const T& >::type
move(const T& x) { return x; }

template<class T> inline
typename boost::enable_if<is_movable<T>, rv<T>&>::type
move(T& x) { return *static_cast< rv<T>* >(boost::addressof(x)); }

template<class T> inline
typename boost::enable_if<is_movable<T>, rv<T>&>::type
move(rv<T>& x) { return x; }

// ============================= forward ================================

template<class T, class U> inline
typename boost::enable_if_c<
     is_lvalue_reference<T>::value
  && move_detail::is_convertible< U*
                                , typename remove_reference<T>::type*
                                >::value
, T >::type
forward(U& u) { return static_cast<T>(u); }

template<class T, class U> inline
typename boost::enable_if_c<
     !is_reference<T>::value
  && move_detail::is_convertible< U*, T* >::value
, typename add_rvalue_reference<T>::type >::type
forward(U& u) { return move(u); }

template<class T, class U> inline
typename boost::enable_if_c<
     !is_reference<T>::value
  && move_detail::is_convertible< U* , T* >::value
, const T& >::type
forward(const U& u) { return static_cast<const T&>(u); }

template<class T, class U> inline
typename boost::enable_if_c<
     !is_reference<T>::value
  && move_detail::is_convertible< U* , T* >::value
, typename add_rvalue_reference<T>::type >::type
forward(rv<U>& u) { return move(static_cast<T&>(static_cast<U&>(u))); }

template<class T1, class T2> inline
void swap(T1& a, T2& b) {
  T1 tmp(std0x::move(a));
  a = std0x::move(b);
  b = std0x::move(tmp);
} // swap

//! Class template move_iterator is an iterator adaptor with the same behavior
//! as the underlying iterator except that its dereference operator implicitly
//! converts the value returned by the underlying iterator's dereference
//! operator to an rvalue reference.
//! Some generic algorithms can be called with move iterators to replace
//! copying with moving.
template<class Iter>
class move_iterator {
private:
  Iter _iter;

public:
  typedef Iter iterator_type;

  typedef typename std::iterator_traits<iterator_type>::value_type
      value_type;

  typedef typename boost::mpl::if_< std0x::is_movable<value_type>
                                  , std0x::rv<value_type>&
                                  , value_type&
                                  >::type
      reference;

  typedef Iter pointer;

  typedef typename std::iterator_traits<iterator_type>::difference_type
      difference_type;

  typedef typename std::iterator_traits<iterator_type>::iterator_category
      iterator_category;

  move_iterator() { }

  explicit move_iterator(Iter i) : _iter(i) { }

  template<class U>
  move_iterator(const move_iterator<U>& u) : _iter(u.base()) { }

  iterator_type base() const { return _iter; }

  reference operator*() const { return std0x::move(*_iter); }

  pointer operator->() const { return _iter; }

  move_iterator& operator++() { ++_iter; return *this; }

  move_iterator operator++(int) {
    move_iterator tmp(*this);
    ++(*this);
    return tmp;
  }

  move_iterator& operator--() { --_iter; return *this; }

  move_iterator operator--(int) {
    move_iterator tmp(*this);
    --(*this);
    return tmp;
  }

  move_iterator operator+(difference_type n) const
    { return move_iterator(_iter + n); }

  move_iterator& operator+=(difference_type n)
    { _iter += n; return *this; }

  move_iterator operator- (difference_type n) const
    { return move_iterator(_iter - n); }

  move_iterator& operator-=(difference_type n)
    { _iter -= n; return *this; }

  reference operator[](difference_type n) const
    { return std0x::move(_iter[n]); }

  friend bool operator==(const move_iterator& x, const move_iterator& y)
    { return (x.base() == y.base()); }

  friend bool operator!=(const move_iterator& x, const move_iterator& y)
    { return (x.base() != y.base()); }

  friend bool operator<(const move_iterator& x, const move_iterator& y)
    { return (x.base() < y.base()); }

  friend bool operator<=(const move_iterator& x, const move_iterator& y)
    { return (x.base() <= y.base()); }

  friend bool operator>(const move_iterator& x, const move_iterator& y)
    { return (x.base() > y.base()); }

  friend bool operator>=(const move_iterator& x, const move_iterator& y)
    { return (x.base() >= y.base()); }

  friend difference_type operator-(
      const move_iterator& x, const move_iterator& y)
    { return (x.base() - y.base()); }

  friend move_iterator operator+(difference_type n, const move_iterator& x)
    { return move_iterator(x.base() + n); }
}; // move_iterator

namespace move_detail {

template<class Iter>
struct is_move_iterator
  : public boost::mpl::bool_<false> { };

template<class Iter>
struct is_move_iterator< std0x::move_iterator<Iter> >
  : public boost::mpl::bool_<true> { };

} // move_detail

//! <b>Returns</b>: move_iterator<Iter>(i).
template<class Iter> inline
move_iterator<Iter> make_move_iterator(const Iter &it)
  { return move_iterator<Iter>(it); }

//! A move insert iterator that move constructs elements at the
//! back of a container
template<typename Container>
class back_move_insert_iterator
  : public std::iterator<std::output_iterator_tag, void, void, void, void>
{
  Container* _container;

public:
  typedef Container container_type;

  explicit back_move_insert_iterator(Container& x) : _container(&x) { }

  back_move_insert_iterator& operator=(typename Container::reference x)
    { _container->push_back(std0x::move(x)); return *this; }

  back_move_insert_iterator& operator*()     { return *this; }
  back_move_insert_iterator& operator++()    { return *this; }
  back_move_insert_iterator& operator++(int) { return *this; }
}; // back_move_insert_iterator

//! <b>Returns</b>: back_move_insert_iterator<Container>(x).
template<typename Container> inline
back_move_insert_iterator<Container> back_move_inserter(Container& x)
  { return back_move_insert_iterator<Container>(x); }

//! A move insert iterator that move constructs elements int the
//! front of a container
template<typename Container>
class front_move_insert_iterator
  : public std::iterator<std::output_iterator_tag, void, void, void, void>
{
  Container* _container;

public:
  typedef Container container_type;

  explicit front_move_insert_iterator(Container& x) : _container(&x) { }

  front_move_insert_iterator& operator=(typename Container::reference x)
    { _container->push_front(std0x::move(x)); return *this; }

  front_move_insert_iterator& operator*()     { return *this; }
  front_move_insert_iterator& operator++()    { return *this; }
  front_move_insert_iterator& operator++(int) { return *this; }
}; // front_move_insert_iterator

//! <b>Returns</b>: front_move_insert_iterator<Container>(x).
template<typename Container> inline
front_move_insert_iterator<Container> front_move_inserter(Container& x)
  { return front_move_insert_iterator<Container>(x); }

template<typename Container>
class move_insert_iterator
  : public std::iterator<std::output_iterator_tag, void, void, void, void>
{
  Container* _container;
  typename Container::iterator _pos;

public:
  typedef Container container_type;

  explicit move_insert_iterator(Container& x, typename Container::iterator pos)
    : _container(&x), _pos(pos)
  { }

  move_insert_iterator& operator=(typename Container::reference x) {
    _pos = _container->insert(_pos, std0x::move(x));
    ++_pos;
    return *this;
  }

  move_insert_iterator& operator*()     { return *this; }
  move_insert_iterator& operator++()    { return *this; }
  move_insert_iterator& operator++(int) { return *this; }
}; // move_insert_iterator

//! <b>Returns</b>: move_insert_iterator<Container>(x, it).
template<typename Container> inline
move_insert_iterator<Container> move_inserter(Container& x,
                                              typename Container::iterator it)
  { return move_insert_iterator<Container>(x, it); }

//! <b>Effects</b>: Moves elements in the range [first,last) into the range
//! [result,result + (last - first)) starting from first and proceeding to last.
//! For each non-negative integer n < (last-first),
//!   performs *(result + n) = std0x::move (*(first + n)).
//!
//! <b>Effects</b>: result + (last - first).
//!
//! <b>Requires</b>: result shall not be in the range [first,last).
//!
//! <b>Complexity</b>: Exactly last - first move assignments.
template<typename InIter, typename OutIter>
OutIter move(InIter f, InIter l, OutIter result) {
  while (f != l) {
    *result = std0x::move(*f);
    ++f;
    ++result;
  }
  return result;
} // move

//! <b>Effects</b>: Moves elements in the range [first,last) into the range
//!   [result - (last-first),result) starting from last - 1 and proceeding to
//!   first. For each positive integer n <= (last - first),
//!   performs *(result - n) = std0x::move(*(last - n)).
//!
//! <b>Requires</b>: result shall not be in the range [first,last).
//!
//! <b>Returns</b>: result - (last - first).
//!
//! <b>Complexity</b>: Exactly last - first assignments.
template<typename BiIter, typename OutIter>
OutIter move_backward(BiIter f, BiIter l, OutIter result) {
  while (f != l) {
    --l;
    --result;
    *result = std0x::move(*l);
  }
  return result;
} // move_backward

//! <b>Effects</b>:
//!   \code
//!   for (; first != last; ++result, ++first)
//!      new (static_cast<void*>(&*result))
//!         typename iterator_traits<FwdIter>::value_type(std0x::move(*first));
//!   \endcode
//!
//! <b>Returns</b>: result
template<typename InIter, typename FwdIter>
typename boost::enable_if<
    is_movable<typename std::iterator_traits<InIter>::value_type>,
    FwdIter
  >::type
uninitialized_move(InIter f, InIter l, FwdIter r) {
  typedef typename std::iterator_traits<InIter>::value_type input_value_type;
  while (f != l) {
    ::new(static_cast<void*>(&*r)) input_value_type(std0x::move(*f));
    ++f;
    ++r;
  }
  return r;
} // uninitialized_move

/// @cond

template<typename InIter, typename FwdIter> inline
typename boost::disable_if<
    is_movable<typename std::iterator_traits<InIter>::value_type>,
    FwdIter
  >::type
uninitialized_move(InIter f, InIter l, FwdIter r)
  { return std::uninitialized_copy(f, l, r); }

namespace move_detail {

template<typename InIter, typename FwdIter> inline
typename boost::enable_if<
    is_movable<typename InIter::value_type>,
    FwdIter
  >::type
uninitialized_move_move_iterator(InIter f, InIter l, FwdIter r)
  { return std0x::uninitialized_move(f, l, r); }

template<typename InIter, typename FwdIter> inline
typename boost::disable_if<
    is_movable<typename InIter::value_type>,
    FwdIter
  >::type
uninitialized_move_move_iterator(InIter f, InIter l, FwdIter r)
  { return std::uninitialized_copy(f.base(), l.base(), r); }

} // move_detail

template<typename InIter, typename FwdIter> inline
typename boost::enable_if<
    move_detail::is_move_iterator<InIter>,
    FwdIter
  >::type
uninitialized_copy_or_move(InIter f, InIter l, FwdIter r)
  { return std0x::move_detail::uninitialized_move_move_iterator(f, l, r); }

/// @endcond

//! <b>Effects</b>:
//!   \code
//!   for (; first != last; ++result, ++first)
//!      new (static_cast<void*>(&*result))
//!         typename iterator_traits<FwdIter>::value_type(*first);
//!   \endcode
//!
//! <b>Returns</b>: result
//!
//! <b>Note</b>: This function is provided because
//!   <i>std::uninitialized_copy</i> from some STL implementations
//!    is not compatible with <i>move_iterator</i>
template<typename InIter, typename FwdIter> inline
typename boost::disable_if<
    move_detail::is_move_iterator<InIter>,
    FwdIter
  >::type
uninitialized_copy_or_move(InIter f, InIter l, FwdIter r)
  { return std::uninitialized_copy(f, l, r); }

//! If this trait yields to true
//! (<i>has_trivial_destructor_after_move_ctor &lt;T&gt;::value == true</i>)
//! means that if T is used as argument of a move construction,
//! there is no need to call T's destructor.
//! This optimization tipically is used to improve containers' performance.
//!
//! By default this trait is true if the type has trivial destructor,
//! every class should specialize this trait if it wants to improve performance
//! when inserted in containers.
template<class T>
struct has_trivial_destructor_after_move
  : public boost::has_trivial_destructor<T>
{ };

} // std0x

#endif