Imported Upstream version 1.61.0

Change-Id: I96a1f878d1e6164f01e9aadd5147f38fca448d90
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>

1 files changed, 127 insertions, 0 deletions

diff --git a/boost/move/algo/detail/insertion_sort.hpp b/boost/move/algo/detail/insertion_sort.hpp
new file mode 100644
index 0000000000..15df35d9d6
--- /dev/null
+++ b/boost/move/algo/detail/insertion_sort.hpp
@@ -0,0 +1,127 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2014-2014.
+// 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.
+//
+//////////////////////////////////////////////////////////////////////////////
+
+//! \file
+
+#ifndef BOOST_MOVE_DETAIL_INSERT_SORT_HPP
+#define BOOST_MOVE_DETAIL_INSERT_SORT_HPP
+
+#ifndef BOOST_CONFIG_HPP
+#  include <boost/config.hpp>
+#endif
+#
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#  pragma once
+#endif
+
+#include <boost/move/utility_core.hpp>
+#include <boost/move/algo/move.hpp>
+#include <boost/move/detail/iterator_traits.hpp>
+#include <boost/move/adl_move_swap.hpp>
+#include <boost/move/utility_core.hpp>
+#include <boost/move/detail/placement_new.hpp>
+#include <boost/move/detail/destruct_n.hpp>
+#include <boost/move/algo/detail/basic_op.hpp>
+#include <boost/move/detail/placement_new.hpp>
+
+namespace boost {  namespace movelib{
+
+// @cond
+
+template <class Compare, class ForwardIterator, class BirdirectionalIterator, class Op>
+void insertion_sort_op(ForwardIterator first1, ForwardIterator last1, BirdirectionalIterator first2, Compare comp, Op op)
+{
+   if (first1 != last1){
+      BirdirectionalIterator last2 = first2;
+      op(first1, last2);
+      for (++last2; ++first1 != last1; ++last2){
+         BirdirectionalIterator j2 = last2;
+         BirdirectionalIterator i2 = j2;
+         if (comp(*first1, *--i2)){
+            op(i2, j2);
+            for (--j2; i2 != first2 && comp(*first1, *--i2); --j2) {
+               op(i2, j2);
+            }
+         }
+         op(first1, j2);
+      }
+   }
+}
+
+template <class Compare, class ForwardIterator, class BirdirectionalIterator>
+void insertion_sort_swap(ForwardIterator first1, ForwardIterator last1, BirdirectionalIterator first2, Compare comp)
+{
+   insertion_sort_op(first1, last1, first2, comp, swap_op());
+}
+
+
+template <class Compare, class ForwardIterator, class BirdirectionalIterator>
+void insertion_sort_copy(ForwardIterator first1, ForwardIterator last1, BirdirectionalIterator first2, Compare comp)
+{
+   insertion_sort_op(first1, last1, first2, comp, move_op());
+}
+
+// @endcond
+
+template <class Compare, class BirdirectionalIterator>
+void insertion_sort(BirdirectionalIterator first, BirdirectionalIterator last, Compare comp)
+{
+   typedef typename boost::movelib::iterator_traits<BirdirectionalIterator>::value_type value_type;
+   if (first != last){
+      BirdirectionalIterator i = first;
+      for (++i; i != last; ++i){
+         BirdirectionalIterator j = i;
+         if (comp(*i,  *--j)) {
+            value_type tmp(::boost::move(*i));
+            *i = ::boost::move(*j);
+            for (BirdirectionalIterator k = j; k != first && comp(tmp,  *--k); --j) {
+               *j = ::boost::move(*k);
+            }
+            *j = ::boost::move(tmp);
+         }
+      }
+   }
+}
+
+template <class Compare, class BirdirectionalIterator>
+void insertion_sort_uninitialized_copy
+   (BirdirectionalIterator first1, BirdirectionalIterator const last1
+   , typename iterator_traits<BirdirectionalIterator>::value_type* const first2
+   , Compare comp)
+{
+   typedef typename iterator_traits<BirdirectionalIterator>::value_type value_type;
+   if (first1 != last1){
+      value_type* last2 = first2;
+      ::new(last2, boost_move_new_t()) value_type(move(*first1));
+      destruct_n<value_type> d(first2);
+      d.incr();
+      for (++last2; ++first1 != last1; ++last2){
+         value_type* j2 = last2;
+         value_type* k2 = j2;
+         if (comp(*first1, *--k2)){
+            ::new(j2, boost_move_new_t()) value_type(move(*k2));
+            d.incr();
+            for (--j2; k2 != first2 && comp(*first1, *--k2); --j2)
+               *j2 = move(*k2);
+            *j2 = move(*first1);
+         }
+         else{
+            ::new(j2, boost_move_new_t()) value_type(move(*first1));
+            d.incr();
+         }
+      }
+      d.release();
+   }
+}
+
+}} //namespace boost {  namespace movelib{
+
+#endif //#ifndef BOOST_MOVE_DETAIL_INSERT_SORT_HPP