Import libs 4 (#758)

1 files changed, 502 insertions, 553 deletions

diff --git a/contrib/restricted/boost/filesystem/src/path.cpp b/contrib/restricted/boost/filesystem/src/path.cpp
index 27b32e57c5..1d9748cac7 100644
--- a/contrib/restricted/boost/filesystem/src/path.cpp
+++ b/contrib/restricted/boost/filesystem/src/path.cpp
@@ -1,7 +1,7 @@
 //  filesystem path.cpp  -------------------------------------------------------------  //
 
 //  Copyright Beman Dawes 2008
-//  Copyright Andrey Semashev 2021
+//  Copyright Andrey Semashev 2021-2023
 
 //  Distributed under the Boost Software License, Version 1.0.
 //  See http://www.boost.org/LICENSE_1_0.txt
@@ -12,7 +12,7 @@
 
 #include <boost/filesystem/config.hpp>
 #include <boost/filesystem/path.hpp>
-#include <boost/filesystem/path_traits.hpp> // codecvt_error_category()
+#include <boost/filesystem/detail/path_traits.hpp> // codecvt_error_category()
 #include <boost/scoped_array.hpp>
 #include <boost/system/error_category.hpp> // for BOOST_SYSTEM_HAS_CONSTEXPR
 #include <boost/assert.hpp>
@@ -60,7 +60,6 @@ namespace {
 typedef path::value_type value_type;
 typedef path::string_type string_type;
 typedef string_type::size_type size_type;
-using boost::filesystem::path_detail::substring;
 
 #ifdef BOOST_WINDOWS_API
 
@@ -151,110 +150,247 @@ inline void first_element(string_type const& src, size_type& element_pos, size_t
 
 namespace boost {
 namespace filesystem {
+namespace detail {
 
-BOOST_FILESYSTEM_DECL void path::append_v3(path const& p)
+// C++14 provides a mismatch algorithm with four iterator arguments(), but earlier
+// standard libraries didn't, so provide this needed functionality.
+inline std::pair< path::iterator, path::iterator > mismatch(path::iterator it1, path::iterator it1end, path::iterator it2, path::iterator it2end)
 {
-    if (!p.empty())
+    for (; it1 != it1end && it2 != it2end && path_algorithms::compare_v4(*it1, *it2) == 0;)
     {
-        if (BOOST_LIKELY(this != &p))
-        {
-            if (!detail::is_directory_separator(*p.m_pathname.begin()))
-                append_separator_if_needed();
-            m_pathname += p.m_pathname;
-        }
-        else
-        {
-            // self-append
-            path rhs(p);
-            append_v3(rhs);
-        }
+        path_algorithms::increment_v4(it1);
+        path_algorithms::increment_v4(it2);
     }
+    return std::make_pair(it1, it2);
 }
 
-BOOST_FILESYSTEM_DECL void path::append_v3(const value_type* begin, const value_type* end)
+//  normal  --------------------------------------------------------------------------//
+
+BOOST_FILESYSTEM_DECL path path_algorithms::lexically_normal_v3(path const& p)
 {
-    if (begin != end)
+    const value_type* const pathname = p.m_pathname.c_str();
+    const size_type pathname_size = p.m_pathname.size();
+    size_type root_name_size = 0;
+    size_type root_dir_pos = find_root_directory_start(pathname, pathname_size, root_name_size);
+    path normal(pathname, pathname + root_name_size);
+
+#if defined(BOOST_WINDOWS_API)
+    for (size_type i = 0; i < root_name_size; ++i)
+    {
+        if (normal.m_pathname[i] == path::separator)
+            normal.m_pathname[i] = path::preferred_separator;
+    }
+#endif
+
+    size_type root_path_size = root_name_size;
+    if (root_dir_pos < pathname_size)
     {
-        if (BOOST_LIKELY(begin < m_pathname.data() || begin >= (m_pathname.data() + m_pathname.size())))
+        root_path_size = root_dir_pos + 1;
+        normal.m_pathname.push_back(path::preferred_separator);
+    }
+
+    size_type i = root_path_size;
+
+    // Skip redundant directory separators after the root directory
+    while (i < pathname_size && detail::is_directory_separator(pathname[i]))
+        ++i;
+
+    if (i < pathname_size)
+    {
+        bool last_element_was_dot = false;
+        while (true)
         {
-            if (!detail::is_directory_separator(*begin))
-                append_separator_if_needed();
-            m_pathname.append(begin, end);
+            {
+                const size_type start_pos = i;
+
+                // Find next separator
+                i += find_separator(pathname + i, pathname_size - i);
+
+                const size_type size = i - start_pos;
+
+                // Skip dot elements
+                if (size == 1u && pathname[start_pos] == path::dot)
+                {
+                    last_element_was_dot = true;
+                    goto skip_append;
+                }
+
+                last_element_was_dot = false;
+
+                // Process dot dot elements
+                if (size == 2u && pathname[start_pos] == path::dot && pathname[start_pos + 1] == path::dot && normal.m_pathname.size() > root_path_size)
+                {
+                    // Don't remove previous dot dot elements
+                    const size_type normal_size = normal.m_pathname.size();
+                    size_type filename_size = find_filename_size(normal.m_pathname, root_path_size, normal_size);
+                    size_type pos = normal_size - filename_size;
+                    if (filename_size != 2u || normal.m_pathname[pos] != path::dot || normal.m_pathname[pos + 1] != path::dot)
+                    {
+                        if (pos > root_path_size && detail::is_directory_separator(normal.m_pathname[pos - 1]))
+                            --pos;
+                        normal.m_pathname.erase(normal.m_pathname.begin() + pos , normal.m_pathname.end());
+                        goto skip_append;
+                    }
+                }
+
+                // Append the element
+                path_algorithms::append_separator_if_needed(normal);
+                normal.m_pathname.append(pathname + start_pos, size);
+            }
+
+        skip_append:
+            if (i == pathname_size)
+                break;
+
+            // Skip directory separators, including duplicates
+            while (i < pathname_size && detail::is_directory_separator(pathname[i]))
+                ++i;
+
+            if (i == pathname_size)
+            {
+                // If a path ends with a separator, add a trailing dot element
+                goto append_trailing_dot;
+            }
         }
-        else
+
+        if (normal.empty() || last_element_was_dot)
         {
-            // overlapping source
-            path rhs(begin, end);
-            append_v3(rhs);
+        append_trailing_dot:
+            path_algorithms::append_separator_if_needed(normal);
+            normal.m_pathname.push_back(path::dot);
         }
     }
+
+    return normal;
 }
 
-BOOST_FILESYSTEM_DECL void path::append_v4(path const& p)
+BOOST_FILESYSTEM_DECL path path_algorithms::lexically_normal_v4(path const& p)
 {
-    if (!p.empty())
-    {
-        if (BOOST_LIKELY(this != &p))
-        {
-            const size_type that_size = p.m_pathname.size();
-            size_type that_root_name_size = 0;
-            size_type that_root_dir_pos = find_root_directory_start(p.m_pathname.c_str(), that_size, that_root_name_size);
+    const value_type* const pathname = p.m_pathname.c_str();
+    const size_type pathname_size = p.m_pathname.size();
+    size_type root_name_size = 0;
+    size_type root_dir_pos = find_root_directory_start(pathname, pathname_size, root_name_size);
+    path normal(pathname, pathname + root_name_size);
 
-            // if (p.is_absolute())
-            if
-            (
-#if defined(BOOST_WINDOWS_API) && !defined(UNDER_CE)
-                that_root_name_size > 0 &&
+#if defined(BOOST_WINDOWS_API)
+    for (size_type i = 0; i < root_name_size; ++i)
+    {
+        if (normal.m_pathname[i] == path::separator)
+            normal.m_pathname[i] = path::preferred_separator;
+    }
 #endif
-                that_root_dir_pos < that_size
-            )
+
+    size_type root_path_size = root_name_size;
+    if (root_dir_pos < pathname_size)
+    {
+        root_path_size = root_dir_pos + 1;
+        normal.m_pathname.push_back(path::preferred_separator);
+    }
+
+    size_type i = root_path_size;
+
+    // Skip redundant directory separators after the root directory
+    while (i < pathname_size && detail::is_directory_separator(pathname[i]))
+        ++i;
+
+    if (i < pathname_size)
+    {
+        while (true)
+        {
+            bool last_element_was_dot = false;
             {
-            return_assign:
-                assign(p);
-                return;
-            }
+                const size_type start_pos = i;
 
-            size_type this_root_name_size = 0;
-            find_root_directory_start(m_pathname.c_str(), m_pathname.size(), this_root_name_size);
+                // Find next separator
+                i += find_separator(pathname + i, pathname_size - i);
 
-            if
-            (
-                that_root_name_size > 0 &&
-                (that_root_name_size != this_root_name_size || std::memcmp(m_pathname.c_str(), p.m_pathname.c_str(), this_root_name_size * sizeof(value_type)) != 0)
-            )
+                const size_type size = i - start_pos;
+
+                // Skip dot elements
+                if (size == 1u && pathname[start_pos] == path::dot)
+                {
+                    last_element_was_dot = true;
+                    goto skip_append;
+                }
+
+                // Process dot dot elements
+                if (size == 2u && pathname[start_pos] == path::dot && pathname[start_pos + 1] == path::dot && normal.m_pathname.size() > root_path_size)
+                {
+                    // Don't remove previous dot dot elements
+                    const size_type normal_size = normal.m_pathname.size();
+                    size_type filename_size = find_filename_size(normal.m_pathname, root_path_size, normal_size);
+                    size_type pos = normal_size - filename_size;
+                    if (filename_size != 2u || normal.m_pathname[pos] != path::dot || normal.m_pathname[pos + 1] != path::dot)
+                    {
+                        if (pos > root_path_size && detail::is_directory_separator(normal.m_pathname[pos - 1]))
+                            --pos;
+                        normal.m_pathname.erase(normal.m_pathname.begin() + pos, normal.m_pathname.end());
+                        goto skip_append;
+                    }
+                }
+
+                // Append the element
+                path_algorithms::append_separator_if_needed(normal);
+                normal.m_pathname.append(pathname + start_pos, size);
+            }
+
+        skip_append:
+            if (i == pathname_size)
             {
-                goto return_assign;
+                // If a path ends with a trailing dot after a directory element, add a trailing separator
+                if (last_element_was_dot && !normal.empty() && !normal.filename_is_dot_dot())
+                    path_algorithms::append_separator_if_needed(normal);
+
+                break;
             }
 
-            if (that_root_dir_pos < that_size)
+            // Skip directory separators, including duplicates
+            while (i < pathname_size && detail::is_directory_separator(pathname[i]))
+                ++i;
+
+            if (i == pathname_size)
             {
-                // Remove root directory (if any) and relative path to replace with those from p
-                m_pathname.erase(m_pathname.begin() + this_root_name_size, m_pathname.end());
+                // If a path ends with a separator, add a trailing separator
+                if (!normal.empty() && !normal.filename_is_dot_dot())
+                    path_algorithms::append_separator_if_needed(normal);
+                break;
             }
+        }
 
-            const value_type* const that_path = p.m_pathname.c_str() + that_root_name_size;
-            if (!detail::is_directory_separator(*that_path))
-                append_separator_if_needed();
-            m_pathname.append(that_path, that_size - that_root_name_size);
+        // If the original path was not empty and normalized ended up being empty, make it a dot
+        if (normal.empty())
+            normal.m_pathname.push_back(path::dot);
+    }
+
+    return normal;
+}
+
+//  append  --------------------------------------------------------------------------//
+
+BOOST_FILESYSTEM_DECL void path_algorithms::append_v3(path& p, const value_type* begin, const value_type* end)
+{
+    if (begin != end)
+    {
+        if (BOOST_LIKELY(begin < p.m_pathname.data() || begin >= (p.m_pathname.data() + p.m_pathname.size())))
+        {
+            if (!detail::is_directory_separator(*begin))
+                path_algorithms::append_separator_if_needed(p);
+            p.m_pathname.append(begin, end);
         }
         else
         {
-            // self-append
-            path rhs(p);
-            append_v4(rhs);
+            // overlapping source
+            string_type rhs(begin, end);
+            path_algorithms::append_v3(p, rhs.data(), rhs.data() + rhs.size());
         }
     }
-    else if (has_filename_v4())
-    {
-        m_pathname.push_back(preferred_separator);
-    }
 }
 
-BOOST_FILESYSTEM_DECL void path::append_v4(const value_type* begin, const value_type* end)
+BOOST_FILESYSTEM_DECL void path_algorithms::append_v4(path& p, const value_type* begin, const value_type* end)
 {
     if (begin != end)
     {
-        if (BOOST_LIKELY(begin < m_pathname.data() || begin >= (m_pathname.data() + m_pathname.size())))
+        if (BOOST_LIKELY(begin < p.m_pathname.data() || begin >= (p.m_pathname.data() + p.m_pathname.size())))
         {
             const size_type that_size = end - begin;
             size_type that_root_name_size = 0;
@@ -270,17 +406,17 @@ BOOST_FILESYSTEM_DECL void path::append_v4(const value_type* begin, const value_
             )
             {
             return_assign:
-                assign(begin, end);
+                p.assign(begin, end);
                 return;
             }
 
             size_type this_root_name_size = 0;
-            find_root_directory_start(m_pathname.c_str(), m_pathname.size(), this_root_name_size);
+            find_root_directory_start(p.m_pathname.c_str(), p.m_pathname.size(), this_root_name_size);
 
             if
             (
                 that_root_name_size > 0 &&
-                (that_root_name_size != this_root_name_size || std::memcmp(m_pathname.c_str(), begin, this_root_name_size * sizeof(value_type)) != 0)
+                (that_root_name_size != this_root_name_size || std::memcmp(p.m_pathname.c_str(), begin, this_root_name_size * sizeof(value_type)) != 0)
             )
             {
                 goto return_assign;
@@ -289,197 +425,219 @@ BOOST_FILESYSTEM_DECL void path::append_v4(const value_type* begin, const value_
             if (that_root_dir_pos < that_size)
             {
                 // Remove root directory (if any) and relative path to replace with those from p
-                m_pathname.erase(m_pathname.begin() + this_root_name_size, m_pathname.end());
+                p.m_pathname.erase(p.m_pathname.begin() + this_root_name_size, p.m_pathname.end());
             }
 
             const value_type* const that_path = begin + that_root_name_size;
             if (!detail::is_directory_separator(*that_path))
-                append_separator_if_needed();
-            m_pathname.append(that_path, end);
+                path_algorithms::append_separator_if_needed(p);
+            p.m_pathname.append(that_path, end);
         }
         else
         {
             // overlapping source
-            path rhs(begin, end);
-            append_v4(rhs);
+            string_type rhs(begin, end);
+            path_algorithms::append_v4(p, rhs.data(), rhs.data() + rhs.size());
         }
     }
-    else if (has_filename_v4())
+    else if (path_algorithms::has_filename_v4(p))
     {
-        m_pathname.push_back(preferred_separator);
+        p.m_pathname.push_back(path::preferred_separator);
     }
 }
 
-#ifdef BOOST_WINDOWS_API
+//  compare  -------------------------------------------------------------------------//
 
-BOOST_FILESYSTEM_DECL path path::generic_path() const
+BOOST_FILESYSTEM_DECL int path_algorithms::lex_compare_v3
+(
+    path_detail::path_iterator first1, path_detail::path_iterator const& last1,
+    path_detail::path_iterator first2, path_detail::path_iterator const& last2
+)
 {
-    path tmp(*this);
-    std::replace(tmp.m_pathname.begin(), tmp.m_pathname.end(), L'\\', L'/');
-    return tmp;
+    for (; first1 != last1 && first2 != last2;)
+    {
+        if (first1->native() < first2->native())
+            return -1;
+        if (first2->native() < first1->native())
+            return 1;
+        BOOST_ASSERT(first2->native() == first1->native());
+        path_algorithms::increment_v3(first1);
+        path_algorithms::increment_v3(first2);
+    }
+    if (first1 == last1 && first2 == last2)
+        return 0;
+    return first1 == last1 ? -1 : 1;
 }
 
-#endif // BOOST_WINDOWS_API
+BOOST_FILESYSTEM_DECL int path_algorithms::lex_compare_v4
+(
+    path_detail::path_iterator first1, path_detail::path_iterator const& last1,
+    path_detail::path_iterator first2, path_detail::path_iterator const& last2
+)
+{
+    for (; first1 != last1 && first2 != last2;)
+    {
+        if (first1->native() < first2->native())
+            return -1;
+        if (first2->native() < first1->native())
+            return 1;
+        BOOST_ASSERT(first2->native() == first1->native());
+        path_algorithms::increment_v4(first1);
+        path_algorithms::increment_v4(first2);
+    }
+    if (first1 == last1 && first2 == last2)
+        return 0;
+    return first1 == last1 ? -1 : 1;
+}
 
-BOOST_FILESYSTEM_DECL int path::compare_v3(path const& p) const BOOST_NOEXCEPT
+BOOST_FILESYSTEM_DECL int path_algorithms::compare_v3(path const& left, path const& right)
 {
-    return detail::lex_compare_v3(begin(), end(), p.begin(), p.end());
+    return path_algorithms::lex_compare_v3(left.begin(), left.end(), right.begin(), right.end());
 }
 
-BOOST_FILESYSTEM_DECL int path::compare_v4(path const& p) const BOOST_NOEXCEPT
+BOOST_FILESYSTEM_DECL int path_algorithms::compare_v4(path const& left, path const& right)
 {
-    return detail::lex_compare_v4(begin(), end(), p.begin(), p.end());
+    return path_algorithms::lex_compare_v4(left.begin(), left.end(), right.begin(), right.end());
 }
 
-//  append_separator_if_needed  ----------------------------------------------------//
+//  append_separator_if_needed  ------------------------------------------------------//
 
-BOOST_FILESYSTEM_DECL path::string_type::size_type path::append_separator_if_needed()
+BOOST_FILESYSTEM_DECL path_algorithms::string_type::size_type path_algorithms::append_separator_if_needed(path& p)
 {
-    if (!m_pathname.empty() &&
+    if (!p.m_pathname.empty() &&
 #ifdef BOOST_WINDOWS_API
-        *(m_pathname.end() - 1) != colon &&
+        *(p.m_pathname.end() - 1) != colon &&
 #endif
-        !detail::is_directory_separator(*(m_pathname.end() - 1)))
+        !detail::is_directory_separator(*(p.m_pathname.end() - 1)))
     {
-        string_type::size_type tmp(m_pathname.size());
-        m_pathname += preferred_separator;
+        string_type::size_type tmp(p.m_pathname.size());
+        p.m_pathname.push_back(path::preferred_separator);
         return tmp;
     }
     return 0;
 }
 
-//  erase_redundant_separator  -----------------------------------------------------//
+//  erase_redundant_separator  -------------------------------------------------------//
 
-BOOST_FILESYSTEM_DECL void path::erase_redundant_separator(string_type::size_type sep_pos)
+BOOST_FILESYSTEM_DECL void path_algorithms::erase_redundant_separator(path& p, string_type::size_type sep_pos)
 {
-    if (sep_pos                                  // a separator was added
-        && sep_pos < m_pathname.size()           // and something was appended
-        && (m_pathname[sep_pos + 1] == separator // and it was also separator
+    if (sep_pos                                          // a separator was added
+        && sep_pos < p.m_pathname.size()                 // and something was appended
+        && (p.m_pathname[sep_pos + 1] == path::separator // and it was also separator
 #ifdef BOOST_WINDOWS_API
-            || m_pathname[sep_pos + 1] == preferred_separator // or preferred_separator
+            || p.m_pathname[sep_pos + 1] == path::preferred_separator // or preferred_separator
 #endif
             ))
     {
-        m_pathname.erase(m_pathname.begin() + sep_pos); // erase the added separator
+        p.m_pathname.erase(p.m_pathname.begin() + sep_pos); // erase the added separator
     }
 }
 
 //  modifiers  -----------------------------------------------------------------------//
 
-#ifdef BOOST_WINDOWS_API
-BOOST_FILESYSTEM_DECL path& path::make_preferred()
+BOOST_FILESYSTEM_DECL void path_algorithms::remove_filename_v3(path& p)
 {
-    std::replace(m_pathname.begin(), m_pathname.end(), L'/', L'\\');
-    return *this;
+    p.remove_filename_and_trailing_separators();
 }
-#endif
 
-BOOST_FILESYSTEM_DECL path& path::remove_filename()
+BOOST_FILESYSTEM_DECL void path_algorithms::remove_filename_v4(path& p)
 {
-    size_type end_pos = find_parent_path_size();
-    m_pathname.erase(m_pathname.begin() + end_pos, m_pathname.end());
-    return *this;
+    size_type filename_size = path_algorithms::find_filename_v4_size(p);
+    p.m_pathname.erase(p.m_pathname.begin() + (p.m_pathname.size() - filename_size), p.m_pathname.end());
 }
 
-BOOST_FILESYSTEM_DECL path& path::remove_trailing_separator()
-{
-    if (!m_pathname.empty() && detail::is_directory_separator(m_pathname[m_pathname.size() - 1]))
-        m_pathname.erase(m_pathname.end() - 1);
-    return *this;
-}
-
-BOOST_FILESYSTEM_DECL void path::replace_extension_v3(path const& new_extension)
+BOOST_FILESYSTEM_DECL void path_algorithms::replace_extension_v3(path& p, path const& new_extension)
 {
     // erase existing extension, including the dot, if any
-    size_type ext_pos = m_pathname.size() - extension_v3().m_pathname.size();
-    m_pathname.erase(m_pathname.begin() + ext_pos, m_pathname.end());
+    size_type ext_pos = p.m_pathname.size() - path_algorithms::extension_v3(p).m_pathname.size();
+    p.m_pathname.erase(p.m_pathname.begin() + ext_pos, p.m_pathname.end());
 
     if (!new_extension.empty())
     {
         // append new_extension, adding the dot if necessary
-        if (new_extension.m_pathname[0] != dot)
-            m_pathname.push_back(dot);
-        m_pathname.append(new_extension.m_pathname);
+        if (new_extension.m_pathname[0] != path::dot)
+            p.m_pathname.push_back(path::dot);
+        p.m_pathname.append(new_extension.m_pathname);
     }
 }
 
-BOOST_FILESYSTEM_DECL void path::replace_extension_v4(path const& new_extension)
+BOOST_FILESYSTEM_DECL void path_algorithms::replace_extension_v4(path& p, path const& new_extension)
 {
     // erase existing extension, including the dot, if any
-    size_type ext_pos = m_pathname.size() - find_extension_v4_size();
-    m_pathname.erase(m_pathname.begin() + ext_pos, m_pathname.end());
+    size_type ext_pos = p.m_pathname.size() - path_algorithms::find_extension_v4_size(p);
+    p.m_pathname.erase(p.m_pathname.begin() + ext_pos, p.m_pathname.end());
 
     if (!new_extension.empty())
     {
         // append new_extension, adding the dot if necessary
-        if (new_extension.m_pathname[0] != dot)
-            m_pathname.push_back(dot);
-        m_pathname.append(new_extension.m_pathname);
+        if (new_extension.m_pathname[0] != path::dot)
+            p.m_pathname.push_back(path::dot);
+        p.m_pathname.append(new_extension.m_pathname);
     }
 }
 
 //  decomposition  -------------------------------------------------------------------//
 
-BOOST_FILESYSTEM_DECL size_type path::find_root_name_size() const
+BOOST_FILESYSTEM_DECL size_type path_algorithms::find_root_name_size(path const& p)
 {
     size_type root_name_size = 0;
-    find_root_directory_start(m_pathname.c_str(), m_pathname.size(), root_name_size);
+    find_root_directory_start(p.m_pathname.c_str(), p.m_pathname.size(), root_name_size);
     return root_name_size;
 }
 
-BOOST_FILESYSTEM_DECL size_type path::find_root_path_size() const
+BOOST_FILESYSTEM_DECL size_type path_algorithms::find_root_path_size(path const& p)
 {
     size_type root_name_size = 0;
-    size_type root_dir_pos = find_root_directory_start(m_pathname.c_str(), m_pathname.size(), root_name_size);
+    size_type root_dir_pos = find_root_directory_start(p.m_pathname.c_str(), p.m_pathname.size(), root_name_size);
 
     size_type size = root_name_size;
-    if (root_dir_pos < m_pathname.size())
+    if (root_dir_pos < p.m_pathname.size())
         size = root_dir_pos + 1;
 
     return size;
 }
 
-BOOST_FILESYSTEM_DECL substring path::find_root_directory() const
+BOOST_FILESYSTEM_DECL path_algorithms::substring path_algorithms::find_root_directory(path const& p)
 {
     substring root_dir;
     size_type root_name_size = 0;
-    root_dir.pos = find_root_directory_start(m_pathname.c_str(), m_pathname.size(), root_name_size);
-    root_dir.size = static_cast< std::size_t >(root_dir.pos < m_pathname.size());
+    root_dir.pos = find_root_directory_start(p.m_pathname.c_str(), p.m_pathname.size(), root_name_size);
+    root_dir.size = static_cast< std::size_t >(root_dir.pos < p.m_pathname.size());
     return root_dir;
 }
 
-BOOST_FILESYSTEM_DECL substring path::find_relative_path() const
+BOOST_FILESYSTEM_DECL path_algorithms::substring path_algorithms::find_relative_path(path const& p)
 {
     size_type root_name_size = 0;
-    size_type root_dir_pos = find_root_directory_start(m_pathname.c_str(), m_pathname.size(), root_name_size);
+    size_type root_dir_pos = find_root_directory_start(p.m_pathname.c_str(), p.m_pathname.size(), root_name_size);
 
     // Skip root name, root directory and any duplicate separators
     size_type size = root_name_size;
-    if (root_dir_pos < m_pathname.size())
+    if (root_dir_pos < p.m_pathname.size())
     {
         size = root_dir_pos + 1;
 
-        for (size_type n = m_pathname.size(); size < n; ++size)
+        for (size_type n = p.m_pathname.size(); size < n; ++size)
         {
-            if (!detail::is_directory_separator(m_pathname[size]))
+            if (!detail::is_directory_separator(p.m_pathname[size]))
                 break;
         }
     }
 
     substring rel_path;
     rel_path.pos = size;
-    rel_path.size = m_pathname.size() - size;
+    rel_path.size = p.m_pathname.size() - size;
 
     return rel_path;
 }
 
-BOOST_FILESYSTEM_DECL string_type::size_type path::find_parent_path_size() const
+BOOST_FILESYSTEM_DECL path_algorithms::string_type::size_type path_algorithms::find_parent_path_size(path const& p)
 {
-    const size_type size = m_pathname.size();
+    const size_type size = p.m_pathname.size();
     size_type root_name_size = 0;
-    size_type root_dir_pos = find_root_directory_start(m_pathname.c_str(), size, root_name_size);
+    size_type root_dir_pos = find_root_directory_start(p.m_pathname.c_str(), size, root_name_size);
 
-    size_type filename_size = find_filename_size(m_pathname, root_name_size, size);
+    size_type filename_size = find_filename_size(p.m_pathname, root_name_size, size);
     size_type end_pos = size - filename_size;
     while (true)
     {
@@ -493,7 +651,7 @@ BOOST_FILESYSTEM_DECL string_type::size_type path::find_parent_path_size() const
 
         --end_pos;
 
-        if (!detail::is_directory_separator(m_pathname[end_pos]))
+        if (!detail::is_directory_separator(p.m_pathname[end_pos]))
         {
             ++end_pos;
             break;
@@ -510,13 +668,13 @@ BOOST_FILESYSTEM_DECL string_type::size_type path::find_parent_path_size() const
     return end_pos;
 }
 
-BOOST_FILESYSTEM_DECL path path::filename_v3() const
+BOOST_FILESYSTEM_DECL path path_algorithms::filename_v3(path const& p)
 {
-    const size_type size = m_pathname.size();
+    const size_type size = p.m_pathname.size();
     size_type root_name_size = 0;
-    size_type root_dir_pos = find_root_directory_start(m_pathname.c_str(), size, root_name_size);
+    size_type root_dir_pos = find_root_directory_start(p.m_pathname.c_str(), size, root_name_size);
     size_type filename_size, pos;
-    if (root_dir_pos < size && detail::is_directory_separator(m_pathname[size - 1]) && is_root_separator(m_pathname, root_dir_pos, size - 1))
+    if (root_dir_pos < size && detail::is_directory_separator(p.m_pathname[size - 1]) && is_root_separator(p.m_pathname, root_dir_pos, size - 1))
     {
         // Return root directory
         pos = root_dir_pos;
@@ -530,77 +688,77 @@ BOOST_FILESYSTEM_DECL path path::filename_v3() const
     }
     else
     {
-        filename_size = find_filename_size(m_pathname, root_name_size, size);
+        filename_size = find_filename_size(p.m_pathname, root_name_size, size);
         pos = size - filename_size;
-        if (filename_size == 0u && pos > root_name_size && detail::is_directory_separator(m_pathname[pos - 1]) && !is_root_separator(m_pathname, root_dir_pos, pos - 1))
+        if (filename_size == 0u && pos > root_name_size && detail::is_directory_separator(p.m_pathname[pos - 1]) && !is_root_separator(p.m_pathname, root_dir_pos, pos - 1))
             return detail::dot_path();
     }
 
-    const value_type* p = m_pathname.c_str() + pos;
-    return path(p, p + filename_size);
+    const value_type* ptr = p.m_pathname.c_str() + pos;
+    return path(ptr, ptr + filename_size);
 }
 
-BOOST_FILESYSTEM_DECL string_type::size_type path::find_filename_v4_size() const
+BOOST_FILESYSTEM_DECL path_algorithms::string_type::size_type path_algorithms::find_filename_v4_size(path const& p)
 {
-    const size_type size = m_pathname.size();
+    const size_type size = p.m_pathname.size();
     size_type root_name_size = 0;
-    find_root_directory_start(m_pathname.c_str(), size, root_name_size);
-    return find_filename_size(m_pathname, root_name_size, size);
+    find_root_directory_start(p.m_pathname.c_str(), size, root_name_size);
+    return find_filename_size(p.m_pathname, root_name_size, size);
 }
 
-BOOST_FILESYSTEM_DECL path path::stem_v3() const
+BOOST_FILESYSTEM_DECL path path_algorithms::stem_v3(path const& p)
 {
-    path name(filename_v3());
-    if (name != detail::dot_path() && name != detail::dot_dot_path())
+    path name(path_algorithms::filename_v3(p));
+    if (path_algorithms::compare_v4(name, detail::dot_path()) != 0 && path_algorithms::compare_v4(name, detail::dot_dot_path()) != 0)
     {
-        size_type pos = name.m_pathname.rfind(dot);
+        size_type pos = name.m_pathname.rfind(path::dot);
         if (pos != string_type::npos)
             name.m_pathname.erase(name.m_pathname.begin() + pos, name.m_pathname.end());
     }
     return name;
 }
 
-BOOST_FILESYSTEM_DECL path path::stem_v4() const
+BOOST_FILESYSTEM_DECL path path_algorithms::stem_v4(path const& p)
 {
-    path name(filename_v4());
-    if (name != detail::dot_path() && name != detail::dot_dot_path())
+    path name(path_algorithms::filename_v4(p));
+    if (path_algorithms::compare_v4(name, detail::dot_path()) != 0 && path_algorithms::compare_v4(name, detail::dot_dot_path()) != 0)
     {
-        size_type pos = name.m_pathname.rfind(dot);
+        size_type pos = name.m_pathname.rfind(path::dot);
         if (pos != 0 && pos != string_type::npos)
             name.m_pathname.erase(name.m_pathname.begin() + pos, name.m_pathname.end());
     }
     return name;
 }
 
-BOOST_FILESYSTEM_DECL path path::extension_v3() const
+BOOST_FILESYSTEM_DECL path path_algorithms::extension_v3(path const& p)
 {
-    path name(filename_v3());
-    if (name == detail::dot_path() || name == detail::dot_dot_path())
+    path name(path_algorithms::filename_v3(p));
+    if (path_algorithms::compare_v4(name, detail::dot_path()) == 0 || path_algorithms::compare_v4(name, detail::dot_dot_path()) == 0)
         return path();
-    size_type pos(name.m_pathname.rfind(dot));
+    size_type pos(name.m_pathname.rfind(path::dot));
     return pos == string_type::npos ? path() : path(name.m_pathname.c_str() + pos);
 }
 
-BOOST_FILESYSTEM_DECL string_type::size_type path::find_extension_v4_size() const
+BOOST_FILESYSTEM_DECL path_algorithms::string_type::size_type path_algorithms::find_extension_v4_size(path const& p)
 {
-    const size_type size = m_pathname.size();
+    const size_type size = p.m_pathname.size();
     size_type root_name_size = 0;
-    find_root_directory_start(m_pathname.c_str(), size, root_name_size);
-    size_type filename_size = find_filename_size(m_pathname, root_name_size, size);
+    find_root_directory_start(p.m_pathname.c_str(), size, root_name_size);
+    size_type filename_size = find_filename_size(p.m_pathname, root_name_size, size);
     size_type filename_pos = size - filename_size;
     if
     (
         filename_size > 0u &&
         // Check for "." and ".." filenames
-        !(m_pathname[filename_pos] == dot &&
-            (filename_size == 1u || (filename_size == 2u && m_pathname[filename_pos + 1u] == dot)))
+        !(p.m_pathname[filename_pos] == path::dot &&
+            (filename_size == 1u || (filename_size == 2u && p.m_pathname[filename_pos + 1u] == path::dot)))
     )
     {
         size_type ext_pos = size;
         while (ext_pos > filename_pos)
         {
             --ext_pos;
-            if (m_pathname[ext_pos] == dot)
+            if (p.m_pathname[ext_pos] == path::dot)
                 break;
         }
 
@@ -611,21 +769,30 @@ BOOST_FILESYSTEM_DECL string_type::size_type path::find_extension_v4_size() cons
     return 0u;
 }
 
-//  lexical operations  --------------------------------------------------------------//
+} // namespace detail
 
-namespace detail {
-// C++14 provides a mismatch algorithm with four iterator arguments(), but earlier
-// standard libraries didn't, so provide this needed functionality.
-inline std::pair< path::iterator, path::iterator > mismatch(path::iterator it1, path::iterator it1end, path::iterator it2, path::iterator it2end)
+BOOST_FILESYSTEM_DECL path& path::remove_filename_and_trailing_separators()
 {
-    for (; it1 != it1end && it2 != it2end && *it1 == *it2;)
-    {
-        ++it1;
-        ++it2;
-    }
-    return std::make_pair(it1, it2);
+    size_type end_pos = detail::path_algorithms::find_parent_path_size(*this);
+    m_pathname.erase(m_pathname.begin() + end_pos, m_pathname.end());
+    return *this;
 }
-} // namespace detail
+
+BOOST_FILESYSTEM_DECL path& path::remove_trailing_separator()
+{
+    if (!m_pathname.empty() && detail::is_directory_separator(m_pathname[m_pathname.size() - 1]))
+        m_pathname.erase(m_pathname.end() - 1);
+    return *this;
+}
+
+BOOST_FILESYSTEM_DECL path& path::replace_filename(path const& replacement)
+{
+    detail::path_algorithms::remove_filename_v4(*this);
+    detail::path_algorithms::append_v4(*this, replacement.m_pathname.data(), replacement.m_pathname.data() + replacement.m_pathname.size());
+    return *this;
+}
+
+//  lexical operations  --------------------------------------------------------------//
 
 BOOST_FILESYSTEM_DECL path path::lexically_relative(path const& base) const
 {
@@ -637,12 +804,12 @@ BOOST_FILESYSTEM_DECL path path::lexically_relative(path const& base) const
         return detail::dot_path();
 
     std::ptrdiff_t n = 0;
-    for (; mm.second != base_e; ++mm.second)
+    for (; mm.second != base_e; detail::path_algorithms::increment_v4(mm.second))
     {
         path const& p = *mm.second;
-        if (p == detail::dot_dot_path())
+        if (detail::path_algorithms::compare_v4(p, detail::dot_dot_path()) == 0)
             --n;
-        else if (!p.empty() && p != detail::dot_path())
+        else if (!p.empty() && detail::path_algorithms::compare_v4(p, detail::dot_path()) != 0)
             ++n;
     }
     if (n < 0)
@@ -652,213 +819,29 @@ BOOST_FILESYSTEM_DECL path path::lexically_relative(path const& base) const
 
     path tmp;
     for (; n > 0; --n)
-        tmp /= detail::dot_dot_path();
-    for (; mm.first != e; ++mm.first)
-        tmp /= *mm.first;
+        detail::path_algorithms::append_v4(tmp, detail::dot_dot_path());
+    for (; mm.first != e; detail::path_algorithms::increment_v4(mm.first))
+        detail::path_algorithms::append_v4(tmp, *mm.first);
     return tmp;
 }
 
-//  normal  --------------------------------------------------------------------------//
-
-BOOST_FILESYSTEM_DECL path path::lexically_normal_v3() const
-{
-    const value_type* const pathname = m_pathname.c_str();
-    const size_type pathname_size = m_pathname.size();
-    size_type root_name_size = 0;
-    size_type root_dir_pos = find_root_directory_start(pathname, pathname_size, root_name_size);
-    path normal(pathname, pathname + root_name_size);
-
 #if defined(BOOST_WINDOWS_API)
-    for (size_type i = 0; i < root_name_size; ++i)
-    {
-        if (normal.m_pathname[i] == path::separator)
-            normal.m_pathname[i] = path::preferred_separator;
-    }
-#endif
-
-    size_type root_path_size = root_name_size;
-    if (root_dir_pos < pathname_size)
-    {
-        root_path_size = root_dir_pos + 1;
-        normal.m_pathname.push_back(preferred_separator);
-    }
-
-    size_type i = root_path_size;
-
-    // Skip redundant directory separators after the root directory
-    while (i < pathname_size && detail::is_directory_separator(pathname[i]))
-        ++i;
-
-    if (i < pathname_size)
-    {
-        bool last_element_was_dot = false;
-        while (true)
-        {
-            {
-                const size_type start_pos = i;
-
-                // Find next separator
-                i += find_separator(pathname + i, pathname_size - i);
-
-                const size_type size = i - start_pos;
-
-                // Skip dot elements
-                if (size == 1u && pathname[start_pos] == dot)
-                {
-                    last_element_was_dot = true;
-                    goto skip_append;
-                }
-
-                last_element_was_dot = false;
-
-                // Process dot dot elements
-                if (size == 2u && pathname[start_pos] == dot && pathname[start_pos + 1] == dot && normal.m_pathname.size() > root_path_size)
-                {
-                    // Don't remove previous dot dot elements
-                    const size_type normal_size = normal.m_pathname.size();
-                    size_type filename_size = find_filename_size(normal.m_pathname, root_path_size, normal_size);
-                    size_type pos = normal_size - filename_size;
-                    if (filename_size != 2u || normal.m_pathname[pos] != dot || normal.m_pathname[pos + 1] != dot)
-                    {
-                        if (pos > root_path_size && detail::is_directory_separator(normal.m_pathname[pos - 1]))
-                            --pos;
-                        normal.m_pathname.erase(normal.m_pathname.begin() + pos , normal.m_pathname.end());
-                        goto skip_append;
-                    }
-                }
-
-                // Append the element
-                normal.append_separator_if_needed();
-                normal.m_pathname.append(pathname + start_pos, size);
-            }
-
-        skip_append:
-            if (i == pathname_size)
-                break;
-
-            // Skip directory separators, including duplicates
-            while (i < pathname_size && detail::is_directory_separator(pathname[i]))
-                ++i;
 
-            if (i == pathname_size)
-            {
-                // If a path ends with a separator, add a trailing dot element
-                goto append_trailing_dot;
-            }
-        }
-
-        if (normal.empty() || last_element_was_dot)
-        {
-        append_trailing_dot:
-            normal.append_separator_if_needed();
-            normal.m_pathname.push_back(dot);
-        }
-    }
-
-    return normal;
+BOOST_FILESYSTEM_DECL path path::generic_path() const
+{
+    path tmp(*this);
+    std::replace(tmp.m_pathname.begin(), tmp.m_pathname.end(), L'\\', L'/');
+    return tmp;
 }
 
-BOOST_FILESYSTEM_DECL path path::lexically_normal_v4() const
+BOOST_FILESYSTEM_DECL path& path::make_preferred()
 {
-    const value_type* const pathname = m_pathname.c_str();
-    const size_type pathname_size = m_pathname.size();
-    size_type root_name_size = 0;
-    size_type root_dir_pos = find_root_directory_start(pathname, pathname_size, root_name_size);
-    path normal(pathname, pathname + root_name_size);
-
-#if defined(BOOST_WINDOWS_API)
-    for (size_type i = 0; i < root_name_size; ++i)
-    {
-        if (normal.m_pathname[i] == path::separator)
-            normal.m_pathname[i] = path::preferred_separator;
-    }
-#endif
-
-    size_type root_path_size = root_name_size;
-    if (root_dir_pos < pathname_size)
-    {
-        root_path_size = root_dir_pos + 1;
-        normal.m_pathname.push_back(preferred_separator);
-    }
-
-    size_type i = root_path_size;
-
-    // Skip redundant directory separators after the root directory
-    while (i < pathname_size && detail::is_directory_separator(pathname[i]))
-        ++i;
-
-    if (i < pathname_size)
-    {
-        while (true)
-        {
-            bool last_element_was_dot = false;
-            {
-                const size_type start_pos = i;
-
-                // Find next separator
-                i += find_separator(pathname + i, pathname_size - i);
-
-                const size_type size = i - start_pos;
-
-                // Skip dot elements
-                if (size == 1u && pathname[start_pos] == dot)
-                {
-                    last_element_was_dot = true;
-                    goto skip_append;
-                }
-
-                // Process dot dot elements
-                if (size == 2u && pathname[start_pos] == dot && pathname[start_pos + 1] == dot && normal.m_pathname.size() > root_path_size)
-                {
-                    // Don't remove previous dot dot elements
-                    const size_type normal_size = normal.m_pathname.size();
-                    size_type filename_size = find_filename_size(normal.m_pathname, root_path_size, normal_size);
-                    size_type pos = normal_size - filename_size;
-                    if (filename_size != 2u || normal.m_pathname[pos] != dot || normal.m_pathname[pos + 1] != dot)
-                    {
-                        if (pos > root_path_size && detail::is_directory_separator(normal.m_pathname[pos - 1]))
-                            --pos;
-                        normal.m_pathname.erase(normal.m_pathname.begin() + pos, normal.m_pathname.end());
-                        goto skip_append;
-                    }
-                }
-
-                // Append the element
-                normal.append_separator_if_needed();
-                normal.m_pathname.append(pathname + start_pos, size);
-            }
-
-        skip_append:
-            if (i == pathname_size)
-            {
-                // If a path ends with a trailing dot after a directory element, add a trailing separator
-                if (last_element_was_dot && !normal.empty() && !normal.filename_is_dot_dot())
-                    normal.append_separator_if_needed();
-
-                break;
-            }
-
-            // Skip directory separators, including duplicates
-            while (i < pathname_size && detail::is_directory_separator(pathname[i]))
-                ++i;
-
-            if (i == pathname_size)
-            {
-                // If a path ends with a separator, add a trailing separator
-                if (!normal.empty() && !normal.filename_is_dot_dot())
-                    normal.append_separator_if_needed();
-                break;
-            }
-        }
-
-        // If the original path was not empty and normalized ended up being empty, make it a dot
-        if (normal.empty())
-            normal.m_pathname.push_back(dot);
-    }
-
-    return normal;
+    std::replace(m_pathname.begin(), m_pathname.end(), L'/', L'\\');
+    return *this;
 }
 
+#endif // defined(BOOST_WINDOWS_API)
+
 } // namespace filesystem
 } // namespace boost
 
@@ -1001,7 +984,13 @@ find_next_separator:
     return pos;
 }
 
-//  first_element --------------------------------------------------------------------//
+//--------------------------------------------------------------------------------------//
+//                                                                                      //
+//                        class path::iterator implementation                           //
+//                                                                                      //
+//--------------------------------------------------------------------------------------//
+
+//  first_element ----------------------------------------------------------------------//
 
 //   sets pos and len of first element, excluding extra separators
 //   if src.empty(), sets pos,len, to 0,0.
@@ -1043,225 +1032,153 @@ namespace boost {
 namespace filesystem {
 namespace detail {
 
-BOOST_FILESYSTEM_DECL
-int lex_compare_v3(path::iterator first1, path::iterator last1, path::iterator first2, path::iterator last2)
-{
-    for (; first1 != last1 && first2 != last2;)
-    {
-        if (first1->native() < first2->native())
-            return -1;
-        if (first2->native() < first1->native())
-            return 1;
-        BOOST_ASSERT(first2->native() == first1->native());
-        first1.increment_v3();
-        first2.increment_v3();
-    }
-    if (first1 == last1 && first2 == last2)
-        return 0;
-    return first1 == last1 ? -1 : 1;
-}
-
-BOOST_FILESYSTEM_DECL
-int lex_compare_v4(path::iterator first1, path::iterator last1, path::iterator first2, path::iterator last2)
-{
-    for (; first1 != last1 && first2 != last2;)
-    {
-        if (first1->native() < first2->native())
-            return -1;
-        if (first2->native() < first1->native())
-            return 1;
-        BOOST_ASSERT(first2->native() == first1->native());
-        ++first1;
-        ++first2;
-    }
-    if (first1 == last1 && first2 == last2)
-        return 0;
-    return first1 == last1 ? -1 : 1;
-}
-
-} // namespace detail
-
-//--------------------------------------------------------------------------------------//
-//                                                                                      //
-//                        class path::iterator implementation                           //
-//                                                                                      //
-//--------------------------------------------------------------------------------------//
-
-BOOST_FILESYSTEM_DECL path::iterator path::begin() const
+BOOST_FILESYSTEM_DECL void path_algorithms::increment_v3(path_detail::path_iterator& it)
 {
-    iterator itr;
-    itr.m_path_ptr = this;
-
-    size_type element_size;
-    first_element(m_pathname, itr.m_pos, element_size);
-
-    if (element_size > 0)
-    {
-        itr.m_element = m_pathname.substr(itr.m_pos, element_size);
-#ifdef BOOST_WINDOWS_API
-        if (itr.m_element.m_pathname.size() == 1u && itr.m_element.m_pathname[0] == preferred_separator)
-            itr.m_element.m_pathname[0] = separator;
-#endif
-    }
-
-    return itr;
-}
-
-BOOST_FILESYSTEM_DECL path::iterator path::end() const
-{
-    iterator itr;
-    itr.m_path_ptr = this;
-    itr.m_pos = m_pathname.size();
-    return itr;
-}
-
-BOOST_FILESYSTEM_DECL void path::iterator::increment_v3()
-{
-    const size_type size = m_path_ptr->m_pathname.size();
-    BOOST_ASSERT_MSG(m_pos < size, "path::iterator increment past end()");
+    const size_type size = it.m_path_ptr->m_pathname.size();
+    BOOST_ASSERT_MSG(it.m_pos < size, "path::iterator increment past end()");
 
     // increment to position past current element; if current element is implicit dot,
     // this will cause m_pos to represent the end iterator
-    m_pos += m_element.m_pathname.size();
+    it.m_pos += it.m_element.m_pathname.size();
 
     // if the end is reached, we are done
-    if (m_pos >= size)
+    if (it.m_pos >= size)
     {
-        BOOST_ASSERT_MSG(m_pos == size, "path::iterator increment after the referenced path was modified");
-        m_element.clear(); // aids debugging
+        BOOST_ASSERT_MSG(it.m_pos == size, "path::iterator increment after the referenced path was modified");
+        it.m_element.clear(); // aids debugging
         return;
     }
 
     // process separator (Windows drive spec is only case not a separator)
-    if (detail::is_directory_separator(m_path_ptr->m_pathname[m_pos]))
+    if (detail::is_directory_separator(it.m_path_ptr->m_pathname[it.m_pos]))
     {
         size_type root_name_size = 0;
-        size_type root_dir_pos = find_root_directory_start(m_path_ptr->m_pathname.c_str(), size, root_name_size);
+        size_type root_dir_pos = find_root_directory_start(it.m_path_ptr->m_pathname.c_str(), size, root_name_size);
 
         // detect root directory and set iterator value to the separator if it is
-        if (m_pos == root_dir_pos && m_element.m_pathname.size() == root_name_size)
+        if (it.m_pos == root_dir_pos && it.m_element.m_pathname.size() == root_name_size)
         {
-            m_element.m_pathname = separator; // generic format; see docs
+            it.m_element.m_pathname = path::separator; // generic format; see docs
             return;
         }
 
         // skip separators until m_pos points to the start of the next element
-        while (m_pos != size && detail::is_directory_separator(m_path_ptr->m_pathname[m_pos]))
+        while (it.m_pos != size && detail::is_directory_separator(it.m_path_ptr->m_pathname[it.m_pos]))
         {
-            ++m_pos;
+            ++it.m_pos;
         }
 
         // detect trailing separator, and treat it as ".", per POSIX spec
-        if (m_pos == size &&
-            !is_root_separator(m_path_ptr->m_pathname, root_dir_pos, m_pos - 1))
+        if (it.m_pos == size &&
+            !is_root_separator(it.m_path_ptr->m_pathname, root_dir_pos, it.m_pos - 1))
         {
-            --m_pos;
-            m_element = detail::dot_path();
+            --it.m_pos;
+            it.m_element = detail::dot_path();
             return;
         }
     }
 
     // get m_element
-    size_type end_pos = m_path_ptr->m_pathname.find_first_of(separators, m_pos);
+    size_type end_pos = it.m_path_ptr->m_pathname.find_first_of(separators, it.m_pos);
     if (end_pos == string_type::npos)
         end_pos = size;
-    const path::value_type* p = m_path_ptr->m_pathname.c_str();
-    m_element.m_pathname.assign(p + m_pos, p + end_pos);
+    const path::value_type* p = it.m_path_ptr->m_pathname.c_str();
+    it.m_element.m_pathname.assign(p + it.m_pos, p + end_pos);
 }
 
-BOOST_FILESYSTEM_DECL void path::iterator::increment_v4()
+BOOST_FILESYSTEM_DECL void path_algorithms::increment_v4(path_detail::path_iterator& it)
 {
-    const size_type size = m_path_ptr->m_pathname.size();
-    BOOST_ASSERT_MSG(m_pos <= size, "path::iterator increment past end()");
+    const size_type size = it.m_path_ptr->m_pathname.size();
+    BOOST_ASSERT_MSG(it.m_pos <= size, "path::iterator increment past end()");
 
-    if (m_element.m_pathname.empty() && (m_pos + 1) == size && detail::is_directory_separator(m_path_ptr->m_pathname[m_pos]))
+    if (it.m_element.m_pathname.empty() && (it.m_pos + 1) == size && detail::is_directory_separator(it.m_path_ptr->m_pathname[it.m_pos]))
     {
         // The iterator was pointing to the last empty element of the path; set to end.
-        m_pos = size;
+        it.m_pos = size;
         return;
     }
 
     // increment to position past current element; if current element is implicit dot,
     // this will cause m_pos to represent the end iterator
-    m_pos += m_element.m_pathname.size();
+    it.m_pos += it.m_element.m_pathname.size();
 
     // if the end is reached, we are done
-    if (m_pos >= size)
+    if (it.m_pos >= size)
     {
-        BOOST_ASSERT_MSG(m_pos == size, "path::iterator increment after the referenced path was modified");
-        m_element.clear(); // aids debugging
+        BOOST_ASSERT_MSG(it.m_pos == size, "path::iterator increment after the referenced path was modified");
+        it.m_element.clear(); // aids debugging
         return;
     }
 
     // process separator (Windows drive spec is only case not a separator)
-    if (detail::is_directory_separator(m_path_ptr->m_pathname[m_pos]))
+    if (detail::is_directory_separator(it.m_path_ptr->m_pathname[it.m_pos]))
     {
         size_type root_name_size = 0;
-        size_type root_dir_pos = find_root_directory_start(m_path_ptr->m_pathname.c_str(), size, root_name_size);
+        size_type root_dir_pos = find_root_directory_start(it.m_path_ptr->m_pathname.c_str(), size, root_name_size);
 
         // detect root directory and set iterator value to the separator if it is
-        if (m_pos == root_dir_pos && m_element.m_pathname.size() == root_name_size)
+        if (it.m_pos == root_dir_pos && it.m_element.m_pathname.size() == root_name_size)
         {
-            m_element.m_pathname = separator; // generic format; see docs
+            it.m_element.m_pathname = path::separator; // generic format; see docs
             return;
         }
 
         // skip separators until m_pos points to the start of the next element
-        while (m_pos != size && detail::is_directory_separator(m_path_ptr->m_pathname[m_pos]))
+        while (it.m_pos != size && detail::is_directory_separator(it.m_path_ptr->m_pathname[it.m_pos]))
         {
-            ++m_pos;
+            ++it.m_pos;
         }
 
         // detect trailing separator
-        if (m_pos == size &&
-            !is_root_separator(m_path_ptr->m_pathname, root_dir_pos, m_pos - 1))
+        if (it.m_pos == size &&
+            !is_root_separator(it.m_path_ptr->m_pathname, root_dir_pos, it.m_pos - 1))
         {
-            --m_pos;
-            m_element.m_pathname.clear();
+            --it.m_pos;
+            it.m_element.m_pathname.clear();
             return;
         }
     }
 
     // get m_element
-    size_type end_pos = m_path_ptr->m_pathname.find_first_of(separators, m_pos);
+    size_type end_pos = it.m_path_ptr->m_pathname.find_first_of(separators, it.m_pos);
     if (end_pos == string_type::npos)
         end_pos = size;
-    const path::value_type* p = m_path_ptr->m_pathname.c_str();
-    m_element.m_pathname.assign(p + m_pos, p + end_pos);
+    const path::value_type* p = it.m_path_ptr->m_pathname.c_str();
+    it.m_element.m_pathname.assign(p + it.m_pos, p + end_pos);
 }
 
-BOOST_FILESYSTEM_DECL void path::iterator::decrement_v3()
+BOOST_FILESYSTEM_DECL void path_algorithms::decrement_v3(path_detail::path_iterator& it)
 {
-    const size_type size = m_path_ptr->m_pathname.size();
-    BOOST_ASSERT_MSG(m_pos > 0, "path::iterator decrement past begin()");
-    BOOST_ASSERT_MSG(m_pos <= size, "path::iterator decrement after the referenced path was modified");
+    const size_type size = it.m_path_ptr->m_pathname.size();
+    BOOST_ASSERT_MSG(it.m_pos > 0, "path::iterator decrement past begin()");
+    BOOST_ASSERT_MSG(it.m_pos <= size, "path::iterator decrement after the referenced path was modified");
 
     size_type root_name_size = 0;
-    size_type root_dir_pos = find_root_directory_start(m_path_ptr->m_pathname.c_str(), size, root_name_size);
+    size_type root_dir_pos = find_root_directory_start(it.m_path_ptr->m_pathname.c_str(), size, root_name_size);
 
-    if (root_dir_pos < size && m_pos == root_dir_pos)
+    if (root_dir_pos < size && it.m_pos == root_dir_pos)
     {
         // Was pointing at root directory, decrement to root name
     set_to_root_name:
-        m_pos = 0u;
-        const path::value_type* p = m_path_ptr->m_pathname.c_str();
-        m_element.m_pathname.assign(p, p + root_name_size);
+        it.m_pos = 0u;
+        const path::value_type* p = it.m_path_ptr->m_pathname.c_str();
+        it.m_element.m_pathname.assign(p, p + root_name_size);
         return;
     }
 
     // if at end and there was a trailing non-root '/', return "."
-    if (m_pos == size &&
+    if (it.m_pos == size &&
         size > 1 &&
-        detail::is_directory_separator(m_path_ptr->m_pathname[m_pos - 1]) &&
-        !is_root_separator(m_path_ptr->m_pathname, root_dir_pos, m_pos - 1))
+        detail::is_directory_separator(it.m_path_ptr->m_pathname[it.m_pos - 1]) &&
+        !is_root_separator(it.m_path_ptr->m_pathname, root_dir_pos, it.m_pos - 1))
     {
-        --m_pos;
-        m_element = detail::dot_path();
+        --it.m_pos;
+        it.m_element = detail::dot_path();
         return;
     }
 
     // skip separators unless root directory
-    size_type end_pos = m_pos;
+    size_type end_pos = it.m_pos;
     while (end_pos > root_name_size)
     {
         --end_pos;
@@ -1269,12 +1186,12 @@ BOOST_FILESYSTEM_DECL void path::iterator::decrement_v3()
         if (end_pos == root_dir_pos)
         {
             // Decremented to the root directory
-            m_pos = end_pos;
-            m_element.m_pathname = separator; // generic format; see docs
+            it.m_pos = end_pos;
+            it.m_element.m_pathname = path::separator; // generic format; see docs
             return;
         }
 
-        if (!detail::is_directory_separator(m_path_ptr->m_pathname[end_pos]))
+        if (!detail::is_directory_separator(it.m_path_ptr->m_pathname[end_pos]))
         {
             ++end_pos;
             break;
@@ -1284,44 +1201,44 @@ BOOST_FILESYSTEM_DECL void path::iterator::decrement_v3()
     if (end_pos <= root_name_size)
         goto set_to_root_name;
 
-    size_type filename_size = find_filename_size(m_path_ptr->m_pathname, root_name_size, end_pos);
-    m_pos = end_pos - filename_size;
-    const path::value_type* p = m_path_ptr->m_pathname.c_str();
-    m_element.m_pathname.assign(p + m_pos, p + end_pos);
+    size_type filename_size = find_filename_size(it.m_path_ptr->m_pathname, root_name_size, end_pos);
+    it.m_pos = end_pos - filename_size;
+    const path::value_type* p = it.m_path_ptr->m_pathname.c_str();
+    it.m_element.m_pathname.assign(p + it.m_pos, p + end_pos);
 }
 
-BOOST_FILESYSTEM_DECL void path::iterator::decrement_v4()
+BOOST_FILESYSTEM_DECL void path_algorithms::decrement_v4(path_detail::path_iterator& it)
 {
-    const size_type size = m_path_ptr->m_pathname.size();
-    BOOST_ASSERT_MSG(m_pos > 0, "path::iterator decrement past begin()");
-    BOOST_ASSERT_MSG(m_pos <= size, "path::iterator decrement after the referenced path was modified");
+    const size_type size = it.m_path_ptr->m_pathname.size();
+    BOOST_ASSERT_MSG(it.m_pos > 0, "path::iterator decrement past begin()");
+    BOOST_ASSERT_MSG(it.m_pos <= size, "path::iterator decrement after the referenced path was modified");
 
     size_type root_name_size = 0;
-    size_type root_dir_pos = find_root_directory_start(m_path_ptr->m_pathname.c_str(), size, root_name_size);
+    size_type root_dir_pos = find_root_directory_start(it.m_path_ptr->m_pathname.c_str(), size, root_name_size);
 
-    if (root_dir_pos < size && m_pos == root_dir_pos)
+    if (root_dir_pos < size && it.m_pos == root_dir_pos)
     {
         // Was pointing at root directory, decrement to root name
     set_to_root_name:
-        m_pos = 0u;
-        const path::value_type* p = m_path_ptr->m_pathname.c_str();
-        m_element.m_pathname.assign(p, p + root_name_size);
+        it.m_pos = 0u;
+        const path::value_type* p = it.m_path_ptr->m_pathname.c_str();
+        it.m_element.m_pathname.assign(p, p + root_name_size);
         return;
     }
 
     // if at end and there was a trailing '/', return ""
-    if (m_pos == size &&
+    if (it.m_pos == size &&
         size > 1 &&
-        detail::is_directory_separator(m_path_ptr->m_pathname[m_pos - 1]) &&
-        !is_root_separator(m_path_ptr->m_pathname, root_dir_pos, m_pos - 1))
+        detail::is_directory_separator(it.m_path_ptr->m_pathname[it.m_pos - 1]) &&
+        !is_root_separator(it.m_path_ptr->m_pathname, root_dir_pos, it.m_pos - 1))
     {
-        --m_pos;
-        m_element.m_pathname.clear();
+        --it.m_pos;
+        it.m_element.m_pathname.clear();
         return;
     }
 
     // skip separators unless root directory
-    size_type end_pos = m_pos;
+    size_type end_pos = it.m_pos;
     while (end_pos > root_name_size)
     {
         --end_pos;
@@ -1329,12 +1246,12 @@ BOOST_FILESYSTEM_DECL void path::iterator::decrement_v4()
         if (end_pos == root_dir_pos)
         {
             // Decremented to the root directory
-            m_pos = end_pos;
-            m_element.m_pathname = separator; // generic format; see docs
+            it.m_pos = end_pos;
+            it.m_element.m_pathname = path::separator; // generic format; see docs
             return;
         }
 
-        if (!detail::is_directory_separator(m_path_ptr->m_pathname[end_pos]))
+        if (!detail::is_directory_separator(it.m_path_ptr->m_pathname[end_pos]))
         {
             ++end_pos;
             break;
@@ -1344,10 +1261,42 @@ BOOST_FILESYSTEM_DECL void path::iterator::decrement_v4()
     if (end_pos <= root_name_size)
         goto set_to_root_name;
 
-    size_type filename_size = find_filename_size(m_path_ptr->m_pathname, root_name_size, end_pos);
-    m_pos = end_pos - filename_size;
-    const path::value_type* p = m_path_ptr->m_pathname.c_str();
-    m_element.m_pathname.assign(p + m_pos, p + end_pos);
+    size_type filename_size = find_filename_size(it.m_path_ptr->m_pathname, root_name_size, end_pos);
+    it.m_pos = end_pos - filename_size;
+    const path::value_type* p = it.m_path_ptr->m_pathname.c_str();
+    it.m_element.m_pathname.assign(p + it.m_pos, p + end_pos);
+}
+
+} // namespace detail
+
+//  path iterators  ------------------------------------------------------------------//
+
+BOOST_FILESYSTEM_DECL path::iterator path::begin() const
+{
+    iterator itr;
+    itr.m_path_ptr = this;
+
+    size_type element_size;
+    first_element(m_pathname, itr.m_pos, element_size);
+
+    if (element_size > 0)
+    {
+        itr.m_element = m_pathname.substr(itr.m_pos, element_size);
+#ifdef BOOST_WINDOWS_API
+        if (itr.m_element.m_pathname.size() == 1u && itr.m_element.m_pathname[0] == path::preferred_separator)
+            itr.m_element.m_pathname[0] = path::separator;
+#endif
+    }
+
+    return itr;
+}
+
+BOOST_FILESYSTEM_DECL path::iterator path::end() const
+{
+    iterator itr;
+    itr.m_path_ptr = this;
+    itr.m_pos = m_pathname.size();
+    return itr;
 }
 
 } // namespace filesystem