Use iterators in unitialized_copy.

Previously, unitialized_copy assumed the args were pointers.
Replace the const * with iterators.

Fixed a bug, uninitialized_copy must return an iterator pass
the last element inserted in dest. Previously we were returning
the start of dest.

Fixed a bug, we can use memmove only when the types pointed are POD
but also when both source AND dest iterators are random access ones
(i.e both source and dest use a contiguous array to store the values)
The prev code would call memmove if the input was a vector<int> and
output a linked list<int> which is wrong since the list element are
stored in nodes, non contiguous area.

Added a specialization when the 2 types are pod but the iterator
are not random access ones (think linked list of ints). I was not
sure if placement new degrades to assignement in that case so I
provided a specialization that explicitly uses '='.

In limits,
added support for int and unsigned int.
replaced C style casts with static_cast.

2 files changed, 109 insertions, 29 deletions

diff --git a/include/limits b/include/limits
index f097c23..6f6d9f3 100644
--- a/include/limits
+++ b/include/limits
@@ -134,6 +134,38 @@ struct numeric_limits<double>
     static const int digits10 = __DBL_DIG__;
 };
 
+// numeric_limits<int>
+template<>
+struct numeric_limits<int>
+{
+    static const bool is_specialized = true;
+
+    static int min() { return INT_MIN; }
+    static int max() { return INT_MAX; }
+
+    static const bool is_signed = true;
+    static const bool is_integer = true;
+
+    static const int digits = static_cast<int>(sizeof(int) * CHAR_BIT);
+    static const int digits10 = digits10<int, digits, is_signed>::value;
+};
+
+// numeric_limits<unsigned int>
+template<>
+struct numeric_limits<unsigned int>
+{
+    static const bool is_specialized = true;
+
+    static unsigned int min() { return 0; }
+    static unsigned int max() { return UINT_MAX; }
+
+    static const bool is_signed = false;
+    static const bool is_integer = true;
+
+    static const int digits = static_cast<int>(sizeof(unsigned int) * CHAR_BIT);
+    static const int digits10 = digits10<int, digits, is_signed>::value;
+};
+
 // numeric_limits<long>
 template<>
 struct numeric_limits<long>
@@ -162,7 +194,7 @@ struct numeric_limits<long long>
     static const bool is_signed = true;
     static const bool is_integer = true;
 
-    static const int digits = ((int)(sizeof(long long) * CHAR_BIT));
+    static const int digits = static_cast<int>(sizeof(long long) * CHAR_BIT);
     static const int digits10 = digits10<int, digits, is_signed>::value;
 };
 
diff --git a/include/memory b/include/memory
index d83851f..d73606f 100644
--- a/include/memory
+++ b/include/memory
@@ -34,6 +34,8 @@
 #include <new>  // for placement new
 #include <cstring>
 #include <algorithm>
+#include <iterator>
+#include <limits>
 
 #if defined(_InputIterator) || defined(_ForwardIterator)
 #error "_InputIterator or _ForwardIterator are already defined."
@@ -45,54 +47,100 @@ namespace std {
 // construction need to happen in separate steps. For each instance in
 // the input range a copy is created and placed in the corresponding
 // memory pointed by dest.
-// If the input range is made of pod instances, uninitialized_copy
+// If the input range is made of pod instances AND both input and
+// destination iterators are random access ones, uninitialized_copy
 // degrades to a memmove call.
+// Returns an iterator pass the end of the destination range.
 
-template<bool> struct __uninitialized_copy
+// Default implementation used when iterators are not random access
+// and the value type are not both POD.
+template<bool, typename _InputIteratorTag, typename _ForwardIteratorTag>
+struct __uninitialized_copy
 {
     template<typename _InputIterator, typename _ForwardIterator>
-    static _ForwardIterator *uninitialized_copy(const _InputIterator *begin,
-                                                const _InputIterator *end,
-                                                _ForwardIterator *dest)
-    {
-        _ForwardIterator *result = dest;
-        for (; begin < end; ++begin, ++dest)
-            new (static_cast<void*>(dest)) _ForwardIterator(*begin);
-        return result;
+    static _ForwardIterator uninitialized_copy(_InputIterator begin,
+                                               _InputIterator end,
+                                               _ForwardIterator dest) {
+        typedef typename iterator_traits<_ForwardIterator>::
+                value_type value_type;
+        for (; begin != end; ++begin, ++dest) {
+            new (static_cast<void*>(&*dest)) value_type(*begin);
+        }
+        return dest;
     }
 };
 
-template<> struct __uninitialized_copy<true>
+// Full specialization when the src and dest types are pod && both
+// iterators are random access.
+template<>
+struct __uninitialized_copy<true,
+                            random_access_iterator_tag,
+                            random_access_iterator_tag>
 {
     template<typename _InputIterator, typename _ForwardIterator>
-    static _ForwardIterator *uninitialized_copy(const _InputIterator *begin,
-                                                const _InputIterator *end,
-                                                _ForwardIterator *dest)
+    static _ForwardIterator uninitialized_copy(_InputIterator begin,
+                                               _InputIterator end,
+                                               _ForwardIterator dest)
     {
-        const ptrdiff_t len = end - begin;
-        const size_t kMaxSizeT = ~((size_t)0);
-        const size_t kSize = sizeof(_InputIterator);
-
-        if (len > 0 && kMaxSizeT / kSize > static_cast<size_t>(len))
-        {
-            std::memmove(static_cast<void*>(dest),
-                         static_cast<const void*>(begin), kSize * len);
+        typedef typename iterator_traits<_InputIterator>::
+                difference_type difference_type;
+        const difference_type len = std::distance(begin, end);
+        const difference_type kMaxSize =
+                std::numeric_limits<difference_type>::max();
+
+        typedef typename iterator_traits<_ForwardIterator>::
+                value_type value_type;
+        const size_t kSize = sizeof(value_type);
+
+        if (len > 0 &&
+            static_cast<size_t>(kMaxSize) / kSize > static_cast<size_t>(len)) {
+            std::memmove(static_cast<void*>(&*dest),
+                         static_cast<const void*>(&*begin), kSize * len);
+            return dest + len;
+        } else {
+            return dest;
+        }
+    }
+};
+
+// TODO: If placement new degrades to assignement for POD, we can get
+// rid of this one.
+// Bothe pod but not both random access
+template<> struct __uninitialized_copy<true,
+                                       input_iterator_tag,
+                                       forward_iterator_tag>
+{
+    template<typename _InputIterator, typename _ForwardIterator>
+    static _ForwardIterator uninitialized_copy(_InputIterator begin,
+                                               _InputIterator end,
+                                               _ForwardIterator dest) {
+        for (; begin != end; ++begin, ++dest) {
+            *dest = *begin;
         }
         return dest;
     }
 };
 
-// The real STL takes iterators, we take pointers for now.
+
 template<typename _InputIterator, typename _ForwardIterator>
-inline _ForwardIterator* uninitialized_copy(const _InputIterator *begin,
-                                            const _InputIterator *end,
-                                            _ForwardIterator *dest)
+inline _ForwardIterator uninitialized_copy(_InputIterator begin,
+                                           _InputIterator end,
+                                           _ForwardIterator dest)
 {
+    typedef typename iterator_traits<_InputIterator>::value_type _ValueType1;
+    typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType2;
+
     const bool both_pod =
-            is_pod<_InputIterator>::value && is_pod<_ForwardIterator>::value;
-    return __uninitialized_copy<both_pod>::uninitialized_copy(begin, end, dest);
+            is_pod<_ValueType1>::value && is_pod<_ValueType2>::value;
+
+    return __uninitialized_copy<both_pod,
+            typename iterator_traits<_InputIterator>::iterator_category,
+            typename iterator_traits<_ForwardIterator>::iterator_category>::
+            uninitialized_copy(begin, end, dest);
 }
 
+// TODO: replace pointers with iterator below.
+
 // uninitialized_fill is used when memory allocation and object
 // construction need to happen in separate steps. uninitialized_fill
 // creates a copy of 'obj' in the location pointed by the interator,