This commit was manufactured by cvs2svn to create tag

'Version_1_34_1'.

[SVN r38286]

include/boost/algorithm/string.hpp

@@ -20,6 +20,7 @@
 #include <boost/algorithm/string/predicate.hpp>
 #include <boost/algorithm/string/find.hpp>
 #include <boost/algorithm/string/split.hpp>
+#include <boost/algorithm/string/join.hpp>
 #include <boost/algorithm/string/replace.hpp>
 #include <boost/algorithm/string/erase.hpp>
 #include <boost/algorithm/string/classification.hpp>

include/boost/algorithm/string/compare.hpp

@@ -1,6 +1,6 @@
 //  Boost string_algo library compare.hpp header file  -------------------------//
 
-//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  Copyright Pavol Droba 2002-2006. Use, modification and
 //  distribution is subject to the Boost Software License, Version
 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
 //  http://www.boost.org/LICENSE_1_0.txt)
@@ -37,7 +37,7 @@ namespace boost {
                 Compare two operands for equality
             */
             template< typename T1, typename T2 >
-                bool operator ()( const T1& Arg1, const T2& Arg2 ) const
+                bool operator()( const T1& Arg1, const T2& Arg2 ) const
             {
                 return Arg1==Arg2;
             }
@@ -62,12 +62,12 @@ namespace boost {
                 Compare two operands. Case is ignored.
             */
             template< typename T1, typename T2 >
-                bool operator ()( const T1& Arg1, const T2& Arg2 ) const
+                bool operator()( const T1& Arg1, const T2& Arg2 ) const
             {
                 #if defined(__BORLANDC__) && (__BORLANDC__ >= 0x560) && (__BORLANDC__ <= 0x564) && !defined(_USE_OLD_RW_STL)
                     return std::toupper(Arg1)==std::toupper(Arg2);
                 #else
-                    return std::toupper(Arg1,m_Loc)==std::toupper(Arg2,m_Loc);
+                    return std::toupper<T1>(Arg1,m_Loc)==std::toupper<T2>(Arg2,m_Loc);
                 #endif
             }
 
@@ -75,11 +75,122 @@ namespace boost {
             std::locale m_Loc;
         };
 
+        //  is_less functor  -----------------------------------------------//
+
+        //! is_less functor
+        /*!
+            Convenient version of standard std::less. Operation is templated, therefore it is 
+            not required to specify the exact types upon the construction
+         */
+        struct is_less
+        {
+            //! Functor operation
+            /*!
+                Compare two operands using > operator
+             */
+            template< typename T1, typename T2 >
+                bool operator()( const T1& Arg1, const T2& Arg2 ) const
+            {
+                return Arg1<Arg2;
+            }
+        };
+
+
+        //! case insensitive version of is_less
+        /*!
+            Case insensitive comparison predicate. Comparison is done using
+            specified locales.
+        */
+        struct is_iless
+        {
+            //! Constructor
+            /*!
+                \param Loc locales used for comparison
+            */
+            is_iless( const std::locale& Loc=std::locale() ) :
+                m_Loc( Loc ) {}
+
+            //! Function operator
+            /*!
+                Compare two operands. Case is ignored.
+            */
+            template< typename T1, typename T2 >
+                bool operator()( const T1& Arg1, const T2& Arg2 ) const
+            {
+                #if defined(__BORLANDC__) && (__BORLANDC__ >= 0x560) && (__BORLANDC__ <= 0x564) && !defined(_USE_OLD_RW_STL)
+                    return std::toupper(Arg1)<std::toupper(Arg2);
+                #else
+                    return std::toupper<T1>(Arg1,m_Loc)<std::toupper<T2>(Arg2,m_Loc);
+                #endif
+            }
+
+        private:
+            std::locale m_Loc;
+        };
+
+        //  is_not_greater functor  -----------------------------------------------//
+
+        //! is_not_greater functor
+        /*!
+            Convenient version of standard std::not_greater_to. Operation is templated, therefore it is 
+            not required to specify the exact types upon the construction
+         */
+        struct is_not_greater
+        {
+            //! Functor operation
+            /*!
+                Compare two operands using > operator
+             */
+            template< typename T1, typename T2 >
+                bool operator()( const T1& Arg1, const T2& Arg2 ) const
+            {
+                return Arg1<=Arg2;
+            }
+        };
+
+
+        //! case insensitive version of is_not_greater
+        /*!
+            Case insensitive comparison predicate. Comparison is done using
+            specified locales.
+        */
+        struct is_not_igreater
+        {
+            //! Constructor
+            /*!
+                \param Loc locales used for comparison
+            */
+            is_not_igreater( const std::locale& Loc=std::locale() ) :
+                m_Loc( Loc ) {}
+
+            //! Function operator
+            /*!
+                Compare two operands. Case is ignored.
+            */
+            template< typename T1, typename T2 >
+                bool operator()( const T1& Arg1, const T2& Arg2 ) const
+            {
+                #if defined(__BORLANDC__) && (__BORLANDC__ >= 0x560) && (__BORLANDC__ <= 0x564) && !defined(_USE_OLD_RW_STL)
+                    return std::toupper(Arg1)<=std::toupper(Arg2);
+                #else
+                    return std::toupper<T1>(Arg1,m_Loc)<=std::toupper<T2>(Arg2,m_Loc);
+                #endif
+            }
+
+        private:
+            std::locale m_Loc;
+        };
+
+
     } // namespace algorithm
 
     // pull names to the boost namespace
     using algorithm::is_equal;
     using algorithm::is_iequal;
+    using algorithm::is_less;
+    using algorithm::is_iless;
+    using algorithm::is_not_greater;
+    using algorithm::is_not_igreater;
 
 } // namespace boost
 

include/boost/algorithm/string/detail/case_conv.hpp

@@ -33,7 +33,7 @@ namespace boost {
                     #if defined(__BORLANDC__) && (__BORLANDC__ >= 0x560) && (__BORLANDC__ <= 0x564) && !defined(_USE_OLD_RW_STL)
                         return std::tolower( Ch);
                     #else
-                        return std::tolower( Ch, m_Loc );
+                        return std::tolower<CharT>( Ch, m_Loc );
                     #endif
                 }
             private:
@@ -53,7 +53,7 @@ namespace boost {
                     #if defined(__BORLANDC__) && (__BORLANDC__ >= 0x560) && (__BORLANDC__ <= 0x564) && !defined(_USE_OLD_RW_STL)
                         return std::toupper( Ch);
                     #else
-                        return std::toupper( Ch, m_Loc );
+                        return std::toupper<CharT>( Ch, m_Loc );
                     #endif
                 }
             private:

include/boost/algorithm/string/detail/classification.hpp

@@ -46,7 +46,7 @@ namespace boost {
                     return std::use_facet< std::ctype<CharT> >(m_Locale).is( m_Type, Ch );
                 }
 
-                #if defined(__BORLANDC__) && (__BORLANDC__ >= 0x560) && (__BORLANDC__ <= 0x564) && !defined(_USE_OLD_RW_STL)
+                #if defined(__BORLANDC__) && (__BORLANDC__ >= 0x560) && (__BORLANDC__ <= 0x582) && !defined(_USE_OLD_RW_STL)
                     template<>
                     bool operator()( char const Ch ) const
                     {

include/boost/algorithm/string/detail/find_format.hpp

@@ -26,20 +26,17 @@ namespace boost {
             template< 
                 typename OutputIteratorT,
                 typename InputT,
-                typename FinderT,
                 typename FormatterT,
                 typename FindResultT >
             inline OutputIteratorT find_format_copy_impl(
                 OutputIteratorT Output,
                 const InputT& Input,
-                FinderT Finder,
                 FormatterT Formatter,
                 const FindResultT& FindResult )
             {       
                 return find_format_copy_impl2( 
                     Output,
                     Input,
-                    Finder,
                     Formatter,
                     FindResult,
                     Formatter(FindResult) );
@@ -48,14 +45,12 @@ namespace boost {
             template< 
                 typename OutputIteratorT,
                 typename InputT,
-                typename FinderT,
                 typename FormatterT,
                 typename FindResultT,
                 typename FormatResultT >
             inline OutputIteratorT find_format_copy_impl2(
                 OutputIteratorT Output,
                 const InputT& Input,
-                FinderT Finder,
                 FormatterT Formatter,
                 const FindResultT& FindResult,
                 const FormatResultT& FormatResult )
@@ -91,18 +86,15 @@ namespace boost {
 
             template< 
                 typename InputT, 
-                typename FinderT,
                 typename FormatterT,
                 typename FindResultT >
             inline InputT find_format_copy_impl(
                 const InputT& Input,
-                FinderT Finder,
                 FormatterT Formatter,
                 const FindResultT& FindResult)
             {
                 return find_format_copy_impl2(
                     Input,
-                    Finder,
                     Formatter,
                     FindResult,
                     Formatter(FindResult) );
@@ -110,13 +102,11 @@ namespace boost {
 
             template< 
                 typename InputT, 
-                typename FinderT,
                 typename FormatterT,
                 typename FindResultT,
                 typename FormatResultT >
             inline InputT find_format_copy_impl2(
                 const InputT& Input,
-                FinderT Finder,
                 FormatterT Formatter,
                 const FindResultT& FindResult,
                 const FormatResultT& FormatResult)
@@ -151,18 +141,15 @@ namespace boost {
         
             template<
                 typename InputT,
-                typename FinderT,
                 typename FormatterT,
                 typename FindResultT >
             inline void find_format_impl( 
                 InputT& Input,
-                FinderT Finder,
                 FormatterT Formatter,
                 const FindResultT& FindResult)
             {
                 find_format_impl2(
                     Input,
-                    Finder,
                     Formatter,
                     FindResult,
                     Formatter(FindResult) );
@@ -170,13 +157,11 @@ namespace boost {
 
             template<
                 typename InputT,
-                typename FinderT,
                 typename FormatterT,
                 typename FindResultT,
                 typename FormatResultT >
             inline void find_format_impl2( 
                 InputT& Input,
-                FinderT,
                 FormatterT Formatter,
                 const FindResultT& FindResult,
                 const FormatResultT& FormatResult)

include/boost/algorithm/string/detail/finder.hpp

@@ -1,6 +1,6 @@
 //  Boost string_algo library finder.hpp header file  ---------------------------//
 
-//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  Copyright Pavol Droba 2002-2006. Use, modification and
 //  distribution is subject to the Boost Software License, Version
 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
 //  http://www.boost.org/LICENSE_1_0.txt)
@@ -90,7 +90,7 @@ namespace boost {
 
 //  find last functor -----------------------------------------------//
 
-            // find the last match a subsequnce in the sequence ( functor )
+            // find the last match a subseqeunce in the sequence ( functor )
             /*
                 Returns a pair <begin,end> marking the subsequence in the sequence.
                 If the find fails, returns <End,End>
@@ -200,7 +200,7 @@ namespace boost {
 
 //  find n-th functor -----------------------------------------------//
 
-            // find the n-th match of a subsequnce in the sequence ( functor )
+            // find the n-th match of a subsequence in the sequence ( functor )
             /*
                 Returns a pair <begin,end> marking the subsequence in the sequence.
                 If the find fails, returns <End,End>
@@ -212,12 +212,15 @@ namespace boost {
                 typedef first_finderF<
                     search_iterator_type,
                     PredicateT> first_finder_type;
+                typedef last_finderF<
+                    search_iterator_type,
+                    PredicateT> last_finder_type;
 
                 // Construction
                 template< typename SearchT >
                 nth_finderF(
                         const SearchT& Search,
-                        unsigned int Nth,
+                        int Nth,
                         PredicateT Comp) :
                     m_Search(begin(Search), end(Search)),
                     m_Nth(Nth),
@@ -225,7 +228,7 @@ namespace boost {
                 nth_finderF(
                         search_iterator_type SearchBegin,
                         search_iterator_type SearchEnd,
-                        unsigned int Nth,
+                        int Nth,
                         PredicateT Comp) :
                     m_Search(SearchBegin, SearchEnd),
                     m_Nth(Nth),
@@ -237,6 +240,26 @@ namespace boost {
                 operator()(
                     ForwardIteratorT Begin,
                     ForwardIteratorT End ) const
+                {
+                    if(m_Nth>=0)
+                    {
+                        return find_forward(Begin, End, m_Nth);
+                    }
+                    else
+                    {
+                        return find_backward(Begin, End, -m_Nth);
+                    }
+
+                }
+
+            private:
+                // Implementation helpers
+                template< typename ForwardIteratorT >
+                iterator_range<ForwardIteratorT>
+                find_forward(
+                    ForwardIteratorT Begin,
+                    ForwardIteratorT End,
+                    unsigned int N) const
                 {
                     typedef ForwardIteratorT input_iterator_type;
                     typedef iterator_range<ForwardIteratorT> result_type;
@@ -245,13 +268,13 @@ namespace boost {
                     if( boost::empty(m_Search) )
                         return result_type( End, End );
 
-                    // Instantiate find funtor
+                    // Instantiate find functor
                     first_finder_type first_finder(
                         m_Search.begin(), m_Search.end(), m_Comp );
 
                     result_type M( Begin, Begin );
 
-                    for( unsigned int n=0; n<=m_Nth; ++n )
+                    for( unsigned int n=0; n<=N; ++n )
                     {
                         // find next match
                         M=first_finder( end(M), End );
@@ -266,14 +289,179 @@ namespace boost {
                     return M;
                 }
 
+                template< typename ForwardIteratorT >
+                iterator_range<ForwardIteratorT>
+                find_backward(
+                    ForwardIteratorT Begin,
+                    ForwardIteratorT End,
+                    unsigned int N) const
+                {
+                    typedef ForwardIteratorT input_iterator_type;
+                    typedef iterator_range<ForwardIteratorT> result_type;
+
+                    // Sanity check
+                    if( boost::empty(m_Search) )
+                        return result_type( End, End );
+
+                    // Instantiate find functor
+                    last_finder_type last_finder(
+                        m_Search.begin(), m_Search.end(), m_Comp );
+
+                    result_type M( End, End );
+
+                    for( unsigned int n=1; n<=N; ++n )
+                    {
+                        // find next match
+                        M=last_finder( Begin, begin(M) );
+
+                        if ( !M )
+                        {
+                            // Subsequence not found, return
+                            return M;
+                        }
+                    }
+
+                    return M;
+                }
+
+
             private:
                 iterator_range<search_iterator_type> m_Search;
-                unsigned int m_Nth;
+                int m_Nth;
                 PredicateT m_Comp;
             };
 
+//  find head/tail implementation helpers ---------------------------//
+
+            template<typename ForwardIteratorT>
+                iterator_range<ForwardIteratorT>
+            find_head_impl(
+                ForwardIteratorT Begin,
+                ForwardIteratorT End,
+                unsigned int N,
+                std::forward_iterator_tag )
+            {
+                typedef ForwardIteratorT input_iterator_type;
+                typedef iterator_range<ForwardIteratorT> result_type;
+
+                input_iterator_type It=Begin;
+                for(
+                    unsigned int Index=0;
+                    Index<N && It!=End; ++Index,++It ) {};
+
+                return result_type( Begin, It );
+            }
+
+            template< typename ForwardIteratorT >
+                iterator_range<ForwardIteratorT>
+            find_head_impl(
+                ForwardIteratorT Begin,
+                ForwardIteratorT End,
+                unsigned int N,
+                std::random_access_iterator_tag )
+            {
+                typedef ForwardIteratorT input_iterator_type;
+                typedef iterator_range<ForwardIteratorT> result_type;
+
+                if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
+                    return result_type( Begin, End );
+
+                return result_type(Begin,Begin+N);
+            }
+
+            // Find head implementation
+            template<typename ForwardIteratorT>
+                iterator_range<ForwardIteratorT>
+            find_head_impl(
+                ForwardIteratorT Begin,
+                ForwardIteratorT End,
+                unsigned int N )
+            {
+                typedef BOOST_STRING_TYPENAME boost::detail::
+                    iterator_traits<ForwardIteratorT>::iterator_category category;
+
+                return find_head_impl( Begin, End, N, category() );
+            }
+
+            template< typename ForwardIteratorT >
+                iterator_range<ForwardIteratorT>
+            find_tail_impl(
+                ForwardIteratorT Begin,
+                ForwardIteratorT End,
+                unsigned int N,
+                std::forward_iterator_tag )
+            {
+                typedef ForwardIteratorT input_iterator_type;
+                typedef iterator_range<ForwardIteratorT> result_type;
+
+                unsigned int Index=0;
+                input_iterator_type It=Begin;
+                input_iterator_type It2=Begin;
+
+                // Advance It2 by N increments
+                for( Index=0; Index<N && It2!=End; ++Index,++It2 ) {};
+
+                // Advance It, It2 to the end
+                for(; It2!=End; ++It,++It2 ) {};
+
+                return result_type( It, It2 );
+            }
+
+            template< typename ForwardIteratorT >
+                iterator_range<ForwardIteratorT>
+            find_tail_impl(
+                ForwardIteratorT Begin,
+                ForwardIteratorT End,
+                unsigned int N,
+                std::bidirectional_iterator_tag )
+            {
+                typedef ForwardIteratorT input_iterator_type;
+                typedef iterator_range<ForwardIteratorT> result_type;
+
+                input_iterator_type It=End;
+                for(
+                    unsigned int Index=0;
+                    Index<N && It!=Begin; ++Index,--It ) {};
+
+                return result_type( It, End );
+            }
+
+            template< typename ForwardIteratorT >
+                iterator_range<ForwardIteratorT>
+            find_tail_impl(
+                ForwardIteratorT Begin,
+                ForwardIteratorT End,
+                unsigned int N,
+                std::random_access_iterator_tag )
+            {
+                typedef ForwardIteratorT input_iterator_type;
+                typedef iterator_range<ForwardIteratorT> result_type;
+
+                if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
+                    return result_type( Begin, End );
+
+                return result_type( End-N, End );
+            }
+
+                        // Operation
+            template< typename ForwardIteratorT >
+            iterator_range<ForwardIteratorT>
+            find_tail_impl(
+                ForwardIteratorT Begin,
+                ForwardIteratorT End,
+                unsigned int N )
+            {
+                typedef BOOST_STRING_TYPENAME boost::detail::
+                    iterator_traits<ForwardIteratorT>::iterator_category category;
+
+                return find_tail_impl( Begin, End, N, category() );
+            }
+
+
+
 //  find head functor -----------------------------------------------//
 
+
             // find a head in the sequence ( functor )
             /*
                 This functor find a head of the specified range. For
@@ -283,7 +471,7 @@ namespace boost {
             struct head_finderF
             {
                 // Construction
-                head_finderF( unsigned int N ) : m_N(N) {}
+                head_finderF( int N ) : m_N(N) {}
 
                 // Operation
                 template< typename ForwardIteratorT >
@@ -292,54 +480,26 @@ namespace boost {
                     ForwardIteratorT Begin,
                     ForwardIteratorT End ) const
                 {
-                    typedef BOOST_STRING_TYPENAME boost::detail::
-                        iterator_traits<ForwardIteratorT>::iterator_category category;
+                    if(m_N>=0)
+                    {
+                        return find_head_impl( Begin, End, m_N );
+                    }
+                    else
+                    {
+                        iterator_range<ForwardIteratorT> Res=
+                            find_tail_impl( Begin, End, -m_N );
 
-                    return findit( Begin, End, category() );
+                        return make_iterator_range(Begin, Res.begin());
+                    }
                 }
 
             private:
-                // Find operation implementation
-                template< typename ForwardIteratorT >
-                    iterator_range<ForwardIteratorT>
-                findit(
-                    ForwardIteratorT Begin,
-                    ForwardIteratorT End,
-                    std::forward_iterator_tag ) const
-                {
-                    typedef ForwardIteratorT input_iterator_type;
-                    typedef iterator_range<ForwardIteratorT> result_type;
-
-                    input_iterator_type It=Begin;
-                    for(
-                        unsigned int Index=0;
-                        Index<m_N && It!=End; ++Index,++It ) {};
-
-                    return result_type( Begin, It );
-                }
-
-                template< typename ForwardIteratorT >
-                    iterator_range<ForwardIteratorT>
-                findit(
-                    ForwardIteratorT Begin,
-                    ForwardIteratorT End,
-                    std::random_access_iterator_tag ) const
-                {
-                    typedef ForwardIteratorT input_iterator_type;
-                    typedef iterator_range<ForwardIteratorT> result_type;
-
-                    if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < m_N ) )
-                        return result_type( Begin, End );
-
-                    return result_type(Begin,Begin+m_N);
-                }
-
-            private:
-                unsigned int m_N;
+                int m_N;
             };
 
 //  find tail functor -----------------------------------------------//
 
+
             // find a tail in the sequence ( functor )
             /*
                 This functor find a tail of the specified range. For
@@ -349,7 +509,7 @@ namespace boost {
             struct tail_finderF
             {
                 // Construction
-                tail_finderF( unsigned int N ) : m_N(N) {}
+                tail_finderF( int N ) : m_N(N) {}
 
                 // Operation
                 template< typename ForwardIteratorT >
@@ -358,74 +518,21 @@ namespace boost {
                     ForwardIteratorT Begin,
                     ForwardIteratorT End ) const
                 {
-                    typedef BOOST_STRING_TYPENAME boost::detail::
-                        iterator_traits<ForwardIteratorT>::iterator_category category;
+                    if(m_N>=0)
+                    {
+                        return find_tail_impl( Begin, End, m_N );
+                    }
+                    else
+                    {
+                        iterator_range<ForwardIteratorT> Res=
+                            find_head_impl( Begin, End, -m_N );
 
-                    return findit( Begin, End, category() );
+                        return make_iterator_range(Res.end(), End);
+                    }
                 }
 
             private:
-                // Find operation implementation
-                template< typename ForwardIteratorT >
-                    iterator_range<ForwardIteratorT>
-                findit(
-                    ForwardIteratorT Begin,
-                    ForwardIteratorT End,
-                    std::forward_iterator_tag ) const
-                {
-                    typedef ForwardIteratorT input_iterator_type;
-                    typedef iterator_range<ForwardIteratorT> result_type;
-
-                    unsigned int Index=0;
-                    input_iterator_type It=Begin;
-                    input_iterator_type It2=Begin;
-
-                    // Advance It2 by N incremets
-                    for( Index=0; Index<m_N && It2!=End; ++Index,++It2 ) {};
-
-                    // Advance It, It2 to the end
-                    for(; It2!=End; ++It,++It2 ) {};
-
-                    return result_type( It, It2 );
-                }
-
-                template< typename ForwardIteratorT >
-                    iterator_range<ForwardIteratorT>
-                findit(
-                    ForwardIteratorT Begin,
-                    ForwardIteratorT End,
-                    std::bidirectional_iterator_tag ) const
-                {
-                    typedef ForwardIteratorT input_iterator_type;
-                    typedef iterator_range<ForwardIteratorT> result_type;
-
-                    input_iterator_type It=End;
-                    for(
-                        unsigned int Index=0;
-                        Index<m_N && It!=Begin; ++Index,--It ) {};
-
-                    return result_type( It, End );
-                }
-
-                template< typename ForwardIteratorT >
-                    iterator_range<ForwardIteratorT>
-                findit(
-                    ForwardIteratorT Begin,
-                    ForwardIteratorT End,
-                    std::random_access_iterator_tag ) const
-                {
-                    typedef ForwardIteratorT input_iterator_type;
-                    typedef iterator_range<ForwardIteratorT> result_type;
-
-                    if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < m_N ) )
-                        return result_type( Begin, End );
-
-                    return result_type( End-m_N, End );
-                }
-
-
-            private:
-                unsigned int m_N;
+                int m_N;
             };
 
 //  find token functor -----------------------------------------------//
@@ -475,7 +582,7 @@ namespace boost {
                         }
                         else
                         {
-                            // Advance by one possition
+                            // Advance by one position
                             ++It2;
                         }
 

include/boost/algorithm/string/erase.hpp

@@ -1,6 +1,6 @@
 //  Boost string_algo library erase.hpp header file  ---------------------------//
 
-//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  Copyright Pavol Droba 2002-2006. Use, modification and
 //  distribution is subject to the Boost Software License, Version
 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
 //  http://www.boost.org/LICENSE_1_0.txt)
@@ -387,6 +387,7 @@ namespace boost {
             \param Input An input string
             \param Search A substring to be searched for
             \param Nth An index of the match to be replaced. The index is 0-based.
+                For negative N, matches are counted from the end of string.
             \return An output iterator pointing just after the last inserted character or
                 a modified copy of the input
 
@@ -400,7 +401,7 @@ namespace boost {
             OutputIteratorT Output,
             const Range1T& Input,
             const Range2T& Search,
-            unsigned int Nth )
+            int Nth )
         {
             return find_format_copy(
                 Output,
@@ -417,7 +418,7 @@ namespace boost {
         inline SequenceT erase_nth_copy( 
             const SequenceT& Input,
             const RangeT& Search,
-            unsigned int Nth )
+            int Nth )
         {
             return find_format_copy( 
                 Input, 
@@ -433,12 +434,13 @@ namespace boost {
             \param Input An input string
             \param Search A substring to be searched for. 
             \param Nth An index of the match to be replaced. The index is 0-based.
+                For negative N, matches are counted from the end of string.
         */
         template<typename SequenceT, typename RangeT>
         inline void erase_nth( 
             SequenceT& Input,
             const RangeT& Search,
-            unsigned int Nth )
+            int Nth )
         {
             find_format( 
                 Input, 
@@ -459,6 +461,7 @@ namespace boost {
             \param Input An input string
             \param Search A substring to be searched for.
             \param Nth An index of the match to be replaced. The index is 0-based.
+                For negative N, matches are counted from the end of string.
             \param Loc A locale used for case insensitive comparison
             \return An output iterator pointing just after the last inserted character or
                 a modified copy of the input
@@ -473,7 +476,7 @@ namespace boost {
             OutputIteratorT Output,
             const Range1T& Input,
             const Range2T& Search,
-            unsigned int Nth,
+            int Nth,
             const std::locale& Loc=std::locale() )
         {
             return find_format_copy(
@@ -491,7 +494,7 @@ namespace boost {
         inline SequenceT ierase_nth_copy( 
             const SequenceT& Input,
             const RangeT& Search,
-            unsigned int Nth,
+            int Nth,
             const std::locale& Loc=std::locale() )
         {
             return find_format_copy( 
@@ -508,13 +511,14 @@ namespace boost {
             \param Input An input string
             \param Search A substring to be searched for. 
             \param Nth An index of the match to be replaced. The index is 0-based.
+                For negative N, matches are counted from the end of string.
             \param Loc A locale used for case insensitive comparison
         */
         template<typename SequenceT, typename RangeT>
         inline void ierase_nth( 
             SequenceT& Input,
             const RangeT& Search,
-            unsigned int Nth,
+            int Nth,
             const std::locale& Loc=std::locale() )
         {
             find_format( 
@@ -675,7 +679,9 @@ namespace boost {
 
             \param Output An output iterator to which the result will be copied
             \param Input An input string
-            \param N Length of the head
+            \param N Length of the head.
+                For N>=0, at most N characters are extracted.
+                For N<0, size(Input)-|N| characters are extracted.
             \return An output iterator pointing just after the last inserted character or
                 a modified copy of the input
 
@@ -687,7 +693,7 @@ namespace boost {
         inline OutputIteratorT erase_head_copy(
             OutputIteratorT Output,
             const RangeT& Input,
-            unsigned int N )
+            int N )
         {
             return find_format_copy(
                 Output,
@@ -703,7 +709,7 @@ namespace boost {
         template<typename SequenceT>
         inline SequenceT erase_head_copy( 
             const SequenceT& Input,
-            unsigned int N )
+            int N )
         {
             return find_format_copy( 
                 Input,
@@ -719,11 +725,13 @@ namespace boost {
 
             \param Input An input string
             \param N Length of the head
+                For N>=0, at most N characters are extracted.
+                For N<0, size(Input)-|N| characters are extracted.
         */
         template<typename SequenceT>
         inline void erase_head( 
             SequenceT& Input,
-            unsigned int N )
+            int N )
         {
             find_format( 
                 Input, 
@@ -743,7 +751,9 @@ namespace boost {
 
             \param Output An output iterator to which the result will be copied
             \param Input An input string
-            \param N Length of the head
+            \param N Length of the head.                 
+                For N>=0, at most N characters are extracted.
+                For N<0, size(Input)-|N| characters are extracted.
             \return An output iterator pointing just after the last inserted character or
                 a modified copy of the input
             
@@ -755,7 +765,7 @@ namespace boost {
         inline OutputIteratorT erase_tail_copy(
             OutputIteratorT Output,
             const RangeT& Input,
-            unsigned int N )
+            int N )
         {
             return find_format_copy(
                 Output,
@@ -771,7 +781,7 @@ namespace boost {
         template<typename SequenceT>
         inline SequenceT erase_tail_copy( 
             const SequenceT& Input,
-            unsigned int N )
+            int N )
         {
             return find_format_copy( 
                 Input,
@@ -787,11 +797,13 @@ namespace boost {
 
             \param Input An input string
             \param N Length of the head
+                For N>=0, at most N characters are extracted.
+                For N<0, size(Input)-|N| characters are extracted.
         */
         template<typename SequenceT>
         inline void erase_tail( 
             SequenceT& Input,
-            unsigned int N )
+            int N )
         {
             find_format( 
                 Input, 

include/boost/algorithm/string/find.hpp

@@ -176,6 +176,7 @@ namespace boost {
             \param Input A string which will be searched.
             \param Search A substring to be searched for.
             \param Nth An index (zero-indexed) of the match to be found.
+                For negative N, the matches are counted from the end of string.
             \return 
                 An \c iterator_range delimiting the match. 
                 Returned iterator is either \c Range1T::iterator or 
@@ -188,7 +189,7 @@ namespace boost {
         find_nth( 
             Range1T& Input, 
             const Range2T& Search,
-            unsigned int Nth)
+            int Nth)
         {
             return nth_finder(Search,Nth)(
                 begin(Input),end(Input));
@@ -196,12 +197,13 @@ namespace boost {
 
         //! Find n-th algorithm ( case insensitive ).
         /*!
-            Search for the n-th (zero-indexed) occurence of the substring in the 
+            Search for the n-th (zero-indexed) occurrence of the substring in the 
             input. Searching is case insensitive.
             
             \param Input A string which will be searched.
             \param Search A substring to be searched for.
-            \param Nth An index (zero-indexed) of the match to be found.
+            \param Nth An index (zero-indexed) of the match to be found. 
+                For negative N, the matches are counted from the end of string.
             \param Loc A locale used for case insensitive comparison
             \return 
                 An \c iterator_range delimiting the match. 
@@ -218,7 +220,7 @@ namespace boost {
         ifind_nth( 
             Range1T& Input, 
             const Range2T& Search,
-            unsigned int Nth,
+            int Nth,
             const std::locale& Loc=std::locale())
         {
             return nth_finder(Search,Nth,is_iequal(Loc))(
@@ -235,6 +237,8 @@ namespace boost {
 
             \param Input An input string
             \param N Length of the head
+                For N>=0, at most N characters are extracted.
+                For N<0, size(Input)-|N| characters are extracted.
             \return 
                 An \c iterator_range delimiting the match. 
                 Returned iterator is either \c Range1T::iterator or 
@@ -248,7 +252,7 @@ namespace boost {
             BOOST_STRING_TYPENAME range_result_iterator<RangeT>::type>
         find_head( 
             RangeT& Input, 
-            unsigned int N)
+            int N)
         {
             return head_finder(N)(
                 begin(Input),end(Input));      
@@ -263,7 +267,9 @@ namespace boost {
             to be the tail.
 
             \param Input An input string
-            \param N Length of the tail
+            \param N Length of the tail. 
+                For N>=0, at most N characters are extracted.
+                For N<0, size(Input)-|N| characters are extracted.
             \return 
                 An \c iterator_range delimiting the match. 
                 Returned iterator is either \c RangeT::iterator or 
@@ -278,7 +284,7 @@ namespace boost {
             BOOST_STRING_TYPENAME range_result_iterator<RangeT>::type>
         find_tail( 
             RangeT& Input, 
-            unsigned int N)
+            int N)
         {
             return tail_finder(N)(
                 begin(Input),end(Input));      

include/boost/algorithm/string/find_format.hpp

@@ -71,7 +71,6 @@ namespace boost {
             return detail::find_format_copy_impl(
                 Output,
                 Input,
-                Finder,
                 Formatter,
                 Finder( begin(Input), end(Input) ) );
         }
@@ -100,7 +99,6 @@ namespace boost {
 
             return detail::find_format_copy_impl(
                 Input,
-                Finder,
                 Formatter,
                 Finder(begin(Input), end(Input)));
         }
@@ -134,7 +132,6 @@ namespace boost {
 
             detail::find_format_impl(
                 Input,
-                Finder,
                 Formatter,
                 Finder(begin(Input), end(Input)));
         }

include/boost/algorithm/string/finder.hpp

@@ -1,6 +1,6 @@
 //  Boost string_algo library finder.hpp header file  ---------------------------//
 
-//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  Copyright Pavol Droba 2002-2006. Use, modification and
 //  distribution is subject to the Boost Software License, Version
 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
 //  http://www.boost.org/LICENSE_1_0.txt)
@@ -132,7 +132,7 @@ namespace boost {
             is_equal>
         nth_finder( 
             const ContainerT& Search, 
-            unsigned int Nth)
+            int Nth)
         {
             return 
                 detail::nth_finderF<
@@ -150,7 +150,7 @@ namespace boost {
             PredicateT>
         nth_finder( 
             const ContainerT& Search, 
-            unsigned int Nth, 
+            int Nth, 
             PredicateT Comp )
         {
             return 
@@ -172,7 +172,7 @@ namespace boost {
             \return An instance of the \c head_finder object
         */
         inline detail::head_finderF
-        head_finder( unsigned int N )
+        head_finder( int N )
         {
             return detail::head_finderF(N);
         }
@@ -189,7 +189,7 @@ namespace boost {
             \return An instance of the \c tail_finder object
         */
         inline detail::tail_finderF
-        tail_finder( unsigned int N )
+        tail_finder( int N )
         {
             return detail::tail_finderF(N);
         }

include/boost/algorithm/string/join.hpp

@@ -0,0 +1,144 @@
+//  Boost string_algo library join.hpp header file  ---------------------------//
+
+//  Copyright Pavol Droba 2002-2006. Use, modification and
+//  distribution is subject to the Boost Software License, Version
+//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+#ifndef BOOST_STRING_JOIN_HPP
+#define BOOST_STRING_JOIN_HPP
+
+#include <boost/algorithm/string/config.hpp>
+#include <boost/algorithm/string/detail/sequence.hpp>
+#include <boost/range/value_type.hpp>
+
+
+/*! \file
+    Defines join algorithm. 
+
+    Join algorithm is a counterpart to split algorithms.
+    It joins strings from a 'list' by adding user defined separator.
+    Additionally there is a version that allows simple filtering
+    by providing a predicate.
+*/
+
+namespace boost {
+    namespace algorithm {
+
+//  join --------------------------------------------------------------//
+
+        //! Join algorithm
+        /*!
+            This algorithm joins all strings in a 'list' into one long string.
+            Segments are concatenated by given separator.
+
+            \param Input A container that holds the input strings. It must be a container-of-containers.
+            \param Separator A string that will separate the joined segments.
+            \return Concatenated string.
+
+            \note This function provides the strong exception-safety guarantee
+        */
+        template< typename SequenceSequenceT, typename Range1T>
+        inline typename range_value<SequenceSequenceT>::type 
+        join(
+            const SequenceSequenceT& Input,
+            Range1T& Separator)
+        {
+            // Define working types
+            typedef typename range_value<SequenceSequenceT>::type ResultT;
+            typedef typename range_const_iterator<SequenceSequenceT>::type InputIteratorT;
+
+            // Parse input
+            InputIteratorT itBegin=begin(Input);
+            InputIteratorT itEnd=end(Input);
+
+            // Construct container to hold the result
+            ResultT Result;
+            
+            // Append first element
+            if(itBegin!=itEnd)
+            {
+                detail::insert(Result, end(Result), *itBegin);
+                ++itBegin;
+            }
+
+            for(;itBegin!=itEnd; ++itBegin)
+            {
+                // Add separator
+                detail::insert(Result, end(Result), Separator);
+                // Add element
+                detail::insert(Result, end(Result), *itBegin);
+            }
+
+            return Result;
+        }
+
+// join_if ----------------------------------------------------------//
+
+        //! Conditional join algorithm
+        /*!
+            This algorithm joins all strings in a 'list' into one long string.
+            Segments are concatenated by given separator. Only segments that
+            satisfy the predicate will be added to the result.
+
+            \param Input A container that holds the input strings. It must be a container-of-containers.
+            \param Separator A string that will separate the joined segments.
+            \param Pred A segment selection predicate
+            \return Concatenated string.
+
+            \note This function provides the strong exception-safety guarantee
+        */
+        template< typename SequenceSequenceT, typename Range1T, typename PredicateT>
+        inline typename range_value<SequenceSequenceT>::type 
+        join_if(
+            const SequenceSequenceT& Input,
+            Range1T& Separator,
+            PredicateT Pred)
+        {
+            // Define working types
+            typedef typename range_value<SequenceSequenceT>::type ResultT;
+            typedef typename range_const_iterator<SequenceSequenceT>::type InputIteratorT;
+
+            // Parse input
+            InputIteratorT itBegin=begin(Input);
+            InputIteratorT itEnd=end(Input);
+
+            // Construct container to hold the result
+            ResultT Result;
+
+            // Roll to the first element that will be added
+            while(itBegin!=itEnd && !Pred(*itBegin)) ++itBegin;
+            // Add this element
+            if(itBegin!=itEnd)
+            {
+                detail::insert(Result, end(Result), *itBegin);
+                ++itBegin;
+            }
+
+            for(;itBegin!=itEnd; ++itBegin)
+            {
+                if(Pred(*itBegin))
+                {
+                    // Add separator
+                    detail::insert(Result, end(Result), Separator);
+                    // Add element
+                    detail::insert(Result, end(Result), *itBegin);
+                }
+            }
+
+            return Result;
+        }
+
+    } // namespace algorithm
+
+    // pull names to the boost namespace
+    using algorithm::join;
+    using algorithm::join_if;
+
+} // namespace boost
+
+
+#endif  // BOOST_STRING_JOIN_HPP
+

include/boost/algorithm/string/predicate.hpp

@@ -307,7 +307,7 @@ namespace boost {
             return equals(Input, Test, is_equal());
         }
 
-        //! 'Equals' predicate ( casa insensitive )
+        //! 'Equals' predicate ( case insensitive )
         /*!
             This predicate holds when the test container is equal to the
             input container i.e. all elements in both containers are same.
@@ -331,6 +331,86 @@ namespace boost {
             return equals(Input, Test, is_iequal(Loc));
         }
 
+// lexicographical_compare predicate -----------------------------//
+
+        //! Lexicographical compare predicate
+        /*!
+             This predicate is an overload of std::lexicographical_compare
+             for range arguments
+
+             It check whether the first argument is lexicographically less
+             then the second one.
+
+             If the optional predicate is specified, it is used for character-wise
+             comparison
+
+             \param Arg1 First argument 
+             \param Arg2 Second argument
+             \param Pred Comparison predicate
+             \return The result of the test
+
+             \note This function provides the strong exception-safety guarantee
+         */
+        template<typename Range1T, typename Range2T, typename PredicateT>
+        inline bool lexicographical_compare(
+            const Range1T& Arg1,
+            const Range2T& Arg2,
+            PredicateT Pred)
+        {
+            return std::lexicographical_compare(
+                begin(Arg1),
+                end(Arg1),
+                begin(Arg2),
+                end(Arg2),
+                Pred);
+        }
+
+        //! Lexicographical compare predicate
+        /*!
+            \overload
+         */
+        template<typename Range1T, typename Range2T>
+            inline bool lexicographical_compare(
+            const Range1T& Arg1,
+            const Range2T& Arg2)
+        {
+            return std::lexicographical_compare(
+                begin(Arg1),
+                end(Arg1),
+                begin(Arg2),
+                end(Arg2),
+                is_less());
+        }
+
+        //! Lexicographical compare predicate (case-insensitive)
+        /*!
+            This predicate is an overload of std::lexicographical_compare
+            for range arguments.
+            It check whether the first argument is lexicographically less
+            then the second one.
+            Elements are compared case insensitively
+
+
+             \param Arg1 First argument 
+             \param Arg2 Second argument
+             \return The result of the test
+
+             \note This function provides the strong exception-safety guarantee
+         */
+        template<typename Range1T, typename Range2T>
+        inline bool ilexicographical_compare(
+            const Range1T& Arg1,
+            const Range2T& Arg2)
+        {
+            return std::lexicographical_compare(
+                begin(Arg1),
+                end(Arg1),
+                begin(Arg2),
+                end(Arg2),
+                is_iless());
+        }
+        
+
 //  all predicate  -----------------------------------------------//
 
         //! 'All' predicate
@@ -374,6 +454,8 @@ namespace boost {
     using algorithm::equals;
     using algorithm::iequals;
     using algorithm::all;
+    using algorithm::lexicographical_compare;
+    using algorithm::ilexicographical_compare;
 
 } // namespace boost
 

include/boost/algorithm/string/regex.hpp

@@ -474,6 +474,147 @@ namespace boost {
                 regex_finder(Rx,Flags) );         
         }
 
+//  join_if ------------------------------------------------------------------//
+
+#ifndef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
+
+        //! Conditional join algorithm
+        /*!
+            This algorithm joins all strings in a 'list' into one long string.
+            Segments are concatenated by given separator. Only segments that
+            match the given regular expression will be added to the result
+
+            This is a specialization of join_if algorithm.
+
+            \param Input A container that holds the input strings. It must be a container-of-containers.
+            \param Separator A string that will separate the joined segments.
+            \param Rx A regular expression
+            \param Flags Regex options
+            \return Concatenated string.
+
+            \note This function provides the strong exception-safety guarantee
+        */
+        template< 
+            typename SequenceSequenceT, 
+            typename Range1T,             
+            typename CharT, 
+            typename RegexTraitsT >
+        inline typename range_value<SequenceSequenceT>::type 
+        join_if(
+            const SequenceSequenceT& Input,
+            Range1T& Separator,
+            const basic_regex<CharT, RegexTraitsT>& Rx,
+            match_flag_type Flags=match_default )
+        {
+            // Define working types
+            typedef typename range_value<SequenceSequenceT>::type ResultT;
+            typedef typename range_const_iterator<SequenceSequenceT>::type InputIteratorT;
+
+            // Parse input
+            InputIteratorT itBegin=begin(Input);
+            InputIteratorT itEnd=end(Input);
+
+            // Construct container to hold the result
+            ResultT Result;
+
+
+            // Roll to the first element that will be added
+            while(
+                itBegin!=itEnd && 
+                !regex_match(begin(*itBegin), end(*itBegin), Rx, Flags)) ++itBegin;
+
+            // Add this element
+            if(itBegin!=itEnd)
+            {
+                detail::insert(Result, end(Result), *itBegin);
+                ++itBegin;
+            }
+
+            for(;itBegin!=itEnd; ++itBegin)
+            {
+                if(regex_match(begin(*itBegin), end(*itBegin), Rx, Flags))
+                {
+                    // Add separator
+                    detail::insert(Result, end(Result), Separator);
+                    // Add element
+                    detail::insert(Result, end(Result), *itBegin);
+                }
+            }
+
+            return Result;
+        }
+
+#else  // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
+
+                //! Conditional join algorithm
+        /*!
+            This algorithm joins all strings in a 'list' into one long string.
+            Segments are concatenated by given separator. Only segments that
+            match the given regular expression will be added to the result
+
+            This is a specialization of join_if algorithm.
+
+            \param Input A container that holds the input strings. It must be a container-of-containers.
+            \param Separator A string that will separate the joined segments.
+            \param Rx A regular expression
+            \param Flags Regex options
+            \return Concatenated string.
+
+            \note This function provides the strong exception-safety guarantee
+        */
+        template< 
+            typename SequenceSequenceT, 
+            typename Range1T,             
+            typename CharT, 
+            typename RegexTraitsT >
+        inline typename range_value<SequenceSequenceT>::type 
+        join_if_regex(
+            const SequenceSequenceT& Input,
+            Range1T& Separator,
+            const basic_regex<CharT, RegexTraitsT>& Rx,
+            match_flag_type Flags=match_default )
+        {
+            // Define working types
+            typedef typename range_value<SequenceSequenceT>::type ResultT;
+            typedef typename range_const_iterator<SequenceSequenceT>::type InputIteratorT;
+
+            // Parse input
+            InputIteratorT itBegin=begin(Input);
+            InputIteratorT itEnd=end(Input);
+
+            // Construct container to hold the result
+            ResultT Result;
+                               
+
+            // Roll to the first element that will be added
+            while(
+                itBegin!=itEnd && 
+                !regex_match(begin(*itBegin), end(*itBegin), Rx, Flags)) ++itBegin;
+
+            // Add this element
+            if(itBegin!=itEnd)
+            {
+                detail::insert(Result, end(Result), *itBegin);
+                ++itBegin;
+            }
+
+            for(;itBegin!=itEnd; ++itBegin)
+            {
+                if(regex_match(begin(*itBegin), end(*itBegin), Rx, Flags))
+                {
+                    // Add separator
+                    detail::insert(Result, end(Result), Separator);
+                    // Add element
+                    detail::insert(Result, end(Result), *itBegin);
+                }
+            }
+
+            return Result;
+        }
+
+
+#endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
+
     } // namespace algorithm
 
     // pull names into the boost namespace
@@ -489,6 +630,14 @@ namespace boost {
     using algorithm::find_all_regex;
     using algorithm::split_regex;
 
+#ifndef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
+    using algorithm::join_if;
+#else  // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
+    using algorithm::join_if_regex;
+#endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
+
+
+
 } // namespace boost
 
 

include/boost/algorithm/string/replace.hpp

@@ -1,6 +1,6 @@
 //  Boost string_algo library replace.hpp header file  ---------------------------//
 
-//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  Copyright Pavol Droba 2002-2006. Use, modification and
 //  distribution is subject to the Boost Software License, Version
 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
 //  http://www.boost.org/LICENSE_1_0.txt)
@@ -428,6 +428,7 @@ namespace boost {
             \param Input An input string
             \param Search A substring to be searched for 
             \param Nth An index of the match to be replaced. The index is 0-based.
+                For negative N, matches are counted from the end of string.
             \param Format A substitute string
             \return An output iterator pointing just after the last inserted character or
                 a modified copy of the input
@@ -443,7 +444,7 @@ namespace boost {
             OutputIteratorT Output,
             const Range1T& Input,
             const Range2T& Search,
-            unsigned int Nth,
+            int Nth,
             const Range3T& Format )
         {
             return find_format_copy(
@@ -461,7 +462,7 @@ namespace boost {
         inline SequenceT replace_nth_copy( 
             const SequenceT& Input,
             const Range1T& Search,
-            unsigned int Nth,
+            int Nth,
             const Range2T& Format )
         {
             return find_format_copy( 
@@ -478,13 +479,14 @@ namespace boost {
             \param Input An input string
             \param Search A substring to be searched for 
             \param Nth An index of the match to be replaced. The index is 0-based.
+                For negative N, matches are counted from the end of string.
             \param Format A substitute string
         */
         template<typename SequenceT, typename Range1T, typename Range2T>
         inline void replace_nth( 
             SequenceT& Input,
             const Range1T& Search,
-            unsigned int Nth,
+            int Nth,
             const Range2T& Format )
         {
             find_format( 
@@ -507,6 +509,7 @@ namespace boost {
             \param Input An input string
             \param Search A substring to be searched for 
             \param Nth An index of the match to be replaced. The index is 0-based.
+                For negative N, matches are counted from the end of string.
             \param Format A substitute string
             \param Loc A locale used for case insensitive comparison
             \return An output iterator pointing just after the last inserted character or
@@ -523,7 +526,7 @@ namespace boost {
             OutputIteratorT Output,
             const Range1T& Input,
             const Range2T& Search,
-            unsigned int Nth,
+            int Nth,
             const Range3T& Format,
             const std::locale& Loc=std::locale() )
         {
@@ -542,7 +545,7 @@ namespace boost {
         inline SequenceT ireplace_nth_copy( 
             const SequenceT& Input,
             const Range1T& Search,
-            unsigned int Nth,
+            int Nth,
             const Range2T& Format,
             const std::locale& Loc=std::locale() )
         {
@@ -561,6 +564,7 @@ namespace boost {
             \param Input An input string
             \param Search A substring to be searched for 
             \param Nth An index of the match to be replaced. The index is 0-based.
+                For negative N, matches are counted from the end of string.
             \param Format A substitute string
             \param Loc A locale used for case insensitive comparison
         */
@@ -568,7 +572,7 @@ namespace boost {
         inline void ireplace_nth( 
             SequenceT& Input,
             const Range1T& Search,
-            unsigned int Nth,
+            int Nth,
             const Range2T& Format,
             const std::locale& Loc=std::locale() )
         {
@@ -745,7 +749,9 @@ namespace boost {
             
             \param Output An output iterator to which the result will be copied
             \param Input An input string
-            \param N Length of the head
+            \param N Length of the head.
+                For N>=0, at most N characters are extracted.
+                For N<0, size(Input)-|N| characters are extracted.
             \param Format A substitute string
             \return An output iterator pointing just after the last inserted character or
                 a modified copy of the input  
@@ -759,7 +765,7 @@ namespace boost {
         inline OutputIteratorT replace_head_copy(
             OutputIteratorT Output,
             const Range1T& Input,
-            unsigned int N,
+            int N,
             const Range2T& Format )
         {
             return find_format_copy(
@@ -776,7 +782,7 @@ namespace boost {
         template<typename SequenceT, typename RangeT>
         inline SequenceT replace_head_copy( 
             const SequenceT& Input,
-            unsigned int N,
+            int N,
             const RangeT& Format )
         {
             return find_format_copy( 
@@ -793,13 +799,15 @@ namespace boost {
             considered to be the head. The input sequence is modified in-place.
 
             \param Input An input string
-            \param N Length of the head
+            \param N Length of the head.
+                For N>=0, at most N characters are extracted.
+                For N<0, size(Input)-|N| characters are extracted.
             \param Format A substitute string
         */
         template<typename SequenceT, typename RangeT>
         inline void replace_head( 
             SequenceT& Input,
-            unsigned int N,
+            int N,
             const RangeT& Format )
         {
             find_format( 
@@ -821,7 +829,9 @@ namespace boost {
 
             \param Output An output iterator to which the result will be copied
             \param Input An input string
-            \param N Length of the tail
+            \param N Length of the tail.
+                For N>=0, at most N characters are extracted.
+                For N<0, size(Input)-|N| characters are extracted.
             \param Format A substitute string
             \return An output iterator pointing just after the last inserted character or
                     a modified copy of the input   
@@ -835,7 +845,7 @@ namespace boost {
         inline OutputIteratorT replace_tail_copy(
             OutputIteratorT Output,
             const Range1T& Input,
-            unsigned int N,
+            int N,
             const Range2T& Format )
         {
             return find_format_copy(
@@ -852,7 +862,7 @@ namespace boost {
         template<typename SequenceT, typename RangeT>
         inline SequenceT replace_tail_copy( 
             const SequenceT& Input,
-            unsigned int N,
+            int N,
             const RangeT& Format )
         {
             return find_format_copy( 
@@ -869,13 +879,15 @@ namespace boost {
             considered to be the tail. The input sequence is modified in-place.
 
             \param Input An input string
-            \param N Length of the tail
+            \param N Length of the tail.
+                For N>=0, at most N characters are extracted.
+                For N<0, size(Input)-|N| characters are extracted.
             \param Format A substitute string
         */
         template<typename SequenceT, typename RangeT>
         inline void replace_tail( 
             SequenceT& Input,
-            unsigned int N,
+            int N,
             const RangeT& Format )
         {
             find_format( 

include/boost/algorithm/string/split.hpp

@@ -1,6 +1,6 @@
-//  Boost string_algo library find.hpp header file  ---------------------------//
+//  Boost string_algo library split.hpp header file  ---------------------------//
 
-//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  Copyright Pavol Droba 2002-2006. Use, modification and
 //  distribution is subject to the Boost Software License, Version
 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
 //  http://www.boost.org/LICENSE_1_0.txt)
@@ -55,7 +55,7 @@ namespace boost {
 
             \note Prior content of the result will be overwritten.
 
-               \note This function provides the strong exception-safety guarantee
+            \note This function provides the strong exception-safety guarantee
         */
         template< typename SequenceSequenceT, typename Range1T, typename Range2T >
         inline SequenceSequenceT& find_all(
@@ -90,7 +90,7 @@ namespace boost {
 
             \note Prior content of the result will be overwritten.
 
-              \note This function provides the strong exception-safety guarantee
+            \note This function provides the strong exception-safety guarantee
         */
         template< typename SequenceSequenceT, typename Range1T, typename Range2T >
         inline SequenceSequenceT& ifind_all(

include/boost/algorithm/string/std/slist_traits.hpp

@@ -12,7 +12,7 @@
 
 #include <boost/algorithm/string/config.hpp>
 #include <boost/algorithm/string/yes_no_type.hpp>
-#include <slist>
+#include BOOST_SLIST_HEADER 
 #include <boost/algorithm/string/sequence_traits.hpp>
 
 namespace boost {

minmax/doc/minmax_benchs.html

@@ -0,0 +1,524 @@
+<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
+<html>
+<head>
+   <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
+   <meta name="GENERATOR" content="Mozilla/4.77 [en] (X11; U; Linux 2.2.19 i686) [Netscape]">
+   <meta name="Author" content="Herve Bronnimann">
+   <meta name="Description" content="Small library to propose minmax_element algorithm.">
+   <title>Boost minmax library</title>
+</head>
+<body text="#000000" bgcolor="#FFFFFF" link="#0000EE" vlink="#551A8B" alink="#FF0000">
+
+<center>
+<h1>
+Minmax_element Performance</h1></center>
+
+<h3>
+<a NAME="Performance"></a><b>About performance</b></h3>
+Of course, there are many factors that affect the performance of an algorithm.
+The number of comparison is only one, but also branch prediction, pipelining,
+locality of reference (affects cache efficiency), etc.  In practice,
+we observe that when the iterator type is a pointer,
+<tt>boost::minmax_element</tt>
+is only a tad slower than
+<tt>std::min_element</tt>, and is even faster
+than
+<tt>boost::first_min_last_max_element</tt>! This is even more true
+for slower iterators (<tt>list&lt;>::iterator</tt> or
+<tt>map&lt;>iterator</tt>
+for instance). The following experiments were conducted on a Pentium III
+500 Mhz running Linux and compiled with g++, version 2.95.2, flags -O3.
+In the tables, we use different distributions: <i>Identical</i> means that
+all the elements are identical, <i>2-valued</i> means that we replace the
+second half of the identical elements by a distinct element, <i>increasing</i>
+means that all the elements are distinct and in increasing order, <i>decrea</i>sing
+is the reverse, and <i>random</i> is produced by random_shuffle.
+<br>
+The program that created these tables is included in the distribution,
+under <a href="../example/minmax_timer.cpp">minmax_timer.cpp</a>
+<br> 
+<center><table BORDER NOSAVE >
+<tr NOSAVE>
+<td NOSAVE><b>vector&lt;int>::iterator</b></td>
+
+<td>Identical</td>
+
+<td>2-valued</td>
+
+<td>Increasing</td>
+
+<td>Decreasing</td>
+
+<td>Random</td>
+</tr>
+
+<tr>
+<td>std::min_element</td>
+
+<td>23.26M/s</td>
+
+<td>23.26M/s</td>
+
+<td>23.15M/s</td>
+
+<td>22.94M/s</td>
+
+<td>22.94M/s</td>
+</tr>
+
+<tr>
+<td>std::max_element</td>
+
+<td>23.26M/s</td>
+
+<td>23.26M/s</td>
+
+<td>23.15M/s</td>
+
+<td>22.94M/s</td>
+
+<td>22.62M/s</td>
+</tr>
+
+<tr>
+<td>boost::first_min_element</td>
+
+<td>23.15M/s</td>
+
+<td>23.04M/s</td>
+
+<td>23.04M/s</td>
+
+<td>22.94M/s</td>
+
+<td>22.83M/s</td>
+</tr>
+
+<tr>
+<td>boost::last_min_element</td>
+
+<td>23.26M/s</td>
+
+<td>23.26M/s</td>
+
+<td>23.26M/s</td>
+
+<td>22.83M/s</td>
+
+<td>16.23M/s</td>
+</tr>
+
+<tr>
+<td>boost::first_max_element</td>
+
+<td>23.15M/s</td>
+
+<td>23.26M/s</td>
+
+<td>23.15M/s</td>
+
+<td>23.04M/s</td>
+
+<td>22.93M/s</td>
+</tr>
+
+<tr>
+<td>boost::last_max_element</td>
+
+<td>23.26M/s</td>
+
+<td>23.15M/s</td>
+
+<td>23.15M/s</td>
+
+<td>22.94M/s</td>
+
+<td>16.18M/s</td>
+</tr>
+
+<tr>
+<td>boost::minmax_element</td>
+
+<td>21.83M/s</td>
+
+<td>21.83M/s</td>
+
+<td>21.83M/s</td>
+
+<td>21.55M/s</td>
+
+<td>17.79M/s</td>
+</tr>
+
+<tr>
+<td>boost::first_min_last_max_element</td>
+
+<td>18.52M/s</td>
+
+<td>18.38M/s</td>
+
+<td>18.38M/s</td>
+
+<td>18.94M/s</td>
+
+<td>16.29M/s</td>
+</tr>
+
+<tr>
+<td>boost::last_min_first_max_element</td>
+
+<td>20.08M/s</td>
+
+<td>20.83M/s</td>
+
+<td>20.75M/s</td>
+
+<td>19.76M/s</td>
+
+<td>15.87M/s</td>
+</tr>
+
+<tr>
+<td>boost::last_min_last_max_element</td>
+
+<td>18.66M/s</td>
+
+<td>19.69M/s</td>
+
+<td>19.69M/s</td>
+
+<td>19.23M/s</td>
+
+<td>15.77M/s</td>
+</tr>
+
+<caption ALIGN=BOTTOM>Number of elements per second for standard vector
+container iterators</caption>
+</table></center>
+
+<center><table BORDER NOSAVE >
+<tr NOSAVE>
+<td NOSAVE><b>list&lt;int>::iterator</b></td>
+
+<td>Identical</td>
+
+<td>2-valued</td>
+
+<td>Increasing</td>
+
+<td>Decreasing</td>
+
+<td>Random</td>
+</tr>
+
+<tr>
+<td>std::min_element</td>
+
+<td>5.8M/s</td>
+
+<td>5.8M/s</td>
+
+<td>5.80M/s</td>
+
+<td>5.73M/s</td>
+
+<td>5.73M/s</td>
+</tr>
+
+<tr>
+<td>std::max_element</td>
+
+<td>5.81M/s</td>
+
+<td>5.81M/s</td>
+
+<td>5.78M/s</td>
+
+<td>5.73M/s</td>
+
+<td>5.75M/s</td>
+</tr>
+
+<tr>
+<td>boost::first_min_element</td>
+
+<td>5.81M/s</td>
+
+<td>5.81M/s</td>
+
+<td>5.79M/s</td>
+
+<td>5.75M/s</td>
+
+<td>5.73M/s</td>
+</tr>
+
+<tr>
+<td>boost::last_min_element</td>
+
+<td>5.81M/s</td>
+
+<td>5.80M/s</td>
+
+<td>5.79M/s</td>
+
+<td>5.73M/s</td>
+
+<td>5.03M/s</td>
+</tr>
+
+<tr>
+<td>boost::first_max_element</td>
+
+<td>5.81M/s</td>
+
+<td>5.80M/s</td>
+
+<td>5.78M/s</td>
+
+<td>5.74M/s</td>
+
+<td>5.73M/s</td>
+</tr>
+
+<tr>
+<td>boost::last_max_element</td>
+
+<td>5.81M/s</td>
+
+<td>5.80M/s</td>
+
+<td>5.79M/s</td>
+
+<td>5.73M/s</td>
+
+<td>5.07M/s</td>
+</tr>
+
+<tr>
+<td>boost::minmax_element</td>
+
+<td>5.68M/s</td>
+
+<td>5.80M/s</td>
+
+<td>5.66M/s</td>
+
+<td>5.74M/s</td>
+
+<td>5.30M/s</td>
+</tr>
+
+<tr>
+<td>boost::first_min_last_max_element</td>
+
+<td>5.79M/s</td>
+
+<td>5.81M/s</td>
+
+<td>5.78M/s</td>
+
+<td>5.73M/s</td>
+
+<td>5.04M/s</td>
+</tr>
+
+<tr>
+<td>boost::last_min_first_max_element</td>
+
+<td>5.69M/s</td>
+
+<td>5.79M/s</td>
+
+<td>5.69M/s</td>
+
+<td>5.73M/s</td>
+
+<td>4.84M/s</td>
+</tr>
+
+<tr>
+<td>boost::last_min_last_max_element</td>
+
+<td>5.61M/s</td>
+
+<td>5.79M/s</td>
+
+<td>5.64M/s</td>
+
+<td>5.74M/s</td>
+
+<td>4.75M/s</td>
+</tr>
+
+<caption ALIGN=BOTTOM>Runtimes for standard list container iterators</caption>
+</table></center>
+
+<center><table BORDER NOSAVE >
+<tr NOSAVE>
+<td NOSAVE><b>multiset&lt;int>::iterator</b></td>
+
+<td>Identical</td>
+
+<td>2-valued</td>
+
+<td>Increasing</td>
+
+<td>Decreasing</td>
+
+<td>Random</td>
+</tr>
+
+<tr>
+<td>std::min_element</td>
+
+<td>4.03M/s</td>
+
+<td>4.04M/s</td>
+
+<td>4.02M/s</td>
+
+<td>4.04M/s</td>
+
+<td>2.97M/s</td>
+</tr>
+
+<tr>
+<td>std::max_element3.007M</td>
+
+<td>4.02M/s</td>
+
+<td>4.02M/s</td>
+
+<td>4.01M/s</td>
+
+<td>4.02M/s</td>
+
+<td>2.96M/s</td>
+</tr>
+
+<tr>
+<td>boost::first_min_element</td>
+
+<td>4.01M/s</td>
+
+<td>4.04M/s</td>
+
+<td>4.03M/s</td>
+
+<td>4.04M/s</td>
+
+<td>3.01M/s</td>
+</tr>
+
+<tr>
+<td>boost::last_min_element</td>
+
+<td>4.03M/s</td>
+
+<td>4.04M/s</td>
+
+<td>4.04M/s</td>
+
+<td>4.04M/s</td>
+
+<td>3.00M/s</td>
+</tr>
+
+<tr>
+<td>boost::first_max_element</td>
+
+<td>4.04M/s</td>
+
+<td>4.04M/s</td>
+
+<td>4.04M/s</td>
+
+<td>4.06M/s</td>
+
+<td>3.01M/s</td>
+</tr>
+
+<tr>
+<td>boost::last_max_element</td>
+
+<td>4.04M/s</td>
+
+<td>4.04M/s</td>
+
+<td>4.03M/s</td>
+
+<td>4.04M/s</td>
+
+<td>3.00M/s</td>
+</tr>
+
+<tr>
+<td>boost::minmax_element</td>
+
+<td>3.98M/s</td>
+
+<td>3.99M/s</td>
+
+<td>3.98M/s</td>
+
+<td>3.99M/s</td>
+
+<td>3.00M/s</td>
+</tr>
+
+<tr>
+<td>boost::first_min_last_max_element</td>
+
+<td>3.99M/s</td>
+
+<td>3.98M/s</td>
+
+<td>3.97M/s</td>
+
+<td>3.99M/s</td>
+
+<td>2.99M/s</td>
+</tr>
+
+<tr>
+<td>boost::last_min_first_max_element</td>
+
+<td>3.97M/s</td>
+
+<td>3.98M/s</td>
+
+<td>3.96M/s</td>
+
+<td>3.98M/s</td>
+
+<td>3.00M/s</td>
+</tr>
+
+<tr>
+<td>boost::last_min_last_max_element</td>
+
+<td>4.00M/s</td>
+
+<td>4.00M/s</td>
+
+<td>4.00M/s</td>
+
+<td>4.02M/s</td>
+
+<td>2.97M/s</td>
+</tr>
+
+<caption ALIGN=BOTTOM>Runtimes for standard set/multiset container iterators</caption>
+</table></center>
+
+<hr SIZE="6">
+<br>Last modified 2004-06-28
+<p><font face="Arial,Helvetica"><font size=-1>&copy; Copyright Herv&eacute;
+Br&ouml;nnimann, Polytechnic University, 2002--2004. 
+Use, modification, and distribution is subject to the Boost Software
+License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">License_1_0.txt</a> or copy at
+<a href="http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)
+</font></font>
+</body>
+</html>

minmax/doc/minmax_synopsis.html

@@ -0,0 +1,127 @@
+<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
+<html>
+<head>
+   <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
+   <meta name="GENERATOR" content="Mozilla/4.77 [en] (X11; U; Linux 2.2.19 i686) [Netscape]">
+   <meta name="Author" content="Herve Bronnimann">
+   <meta name="Description" content="Small library to propose minmax_element algorithm.">
+   <title>Boost minmax library synopsis</title>
+</head>
+<body text="#000000" bgcolor="#FFFFFF" link="#0000EE" vlink="#551A8B" alink="#FF0000">
+
+<center>
+<h1>
+Minmax_element complete synopsis</h1></center>
+
+<h3>
+Synopsis of <tt>&lt;boost/algorithm/minmax.hpp></tt></h3>
+
+<pre>#include &lt;boost/tuple/tuple.hpp>
+
+namespace boost {
+
+  template &lt;class T>
+  tuple&lt;T const&amp;, T const&amp;> >
+  minmax(const T&amp; a, const T&amp; b);
+
+  template &lt;class T, class <a href="http://www.sgi.com/tech/stl/  BinaryPredicate.html">BinaryPredicate</a>>
+  tuple&lt;T const&amp;, T const&amp;> >
+  minmax(const T&amp; a, const T&amp; b, BinaryPredicate comp);
+
+}
+</pre>
+
+<h3>
+Synopsis of <tt>&lt;boost/algorithm/minmax_element.hpp></tt></h3>
+
+<pre>#include &lt;utility> //for std::pair
+
+namespace boost {
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>>
+  std::pair&lt;ForwardIterator,ForwardIterator>
+  minmax_element(ForwardIterator first, ForwardIterator last);
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>>
+  std::pair&lt;ForwardIterator,ForwardIterator>
+  minmax_element(ForwardIterator first, ForwardIterator last,
+                 BinaryPredicate comp);
+
+  // Variants
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>>
+  ForwardIterator first_min_element(ForwardIterator first, ForwardIterator last);
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>>
+  ForwardIterator first_min_element(ForwardIterator first, ForwardIterator last,
+                                    BinaryPredicate comp);
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>>
+  ForwardIterator last_min_element(ForwardIterator first, ForwardIterator last);
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>>
+  ForwardIterator last_min_element(ForwardIterator first, ForwardIterator last,
+                                   BinaryPredicate comp);
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>>
+  ForwardIterator first_max_element(ForwardIterator first, ForwardIterator last);
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>>
+  ForwardIterator first_max_element(ForwardIterator first, ForwardIterator last,
+                                    BinaryPredicate comp);
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>>
+  ForwardIterator last_max_element(ForwardIterator first, ForwardIterator last);
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>>
+  ForwardIterator last_max_element(ForwardIterator first, ForwardIterator last,
+                                   BinaryPredicate comp);
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>>
+  std::pair&lt;ForwardIterator,ForwardIterator>
+  first_min_first_max_element(ForwardIterator first, ForwardIterator last);
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>>
+  std::pair&lt;ForwardIterator,ForwardIterator>
+  first_min_first_max_element(ForwardIterator first, ForwardIterator last,
+                             BinaryPredicate comp);
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>>
+  std::pair&lt;ForwardIterator,ForwardIterator>
+  first_min_last_max_element(ForwardIterator first, ForwardIterator last);
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>>
+  std::pair&lt;ForwardIterator,ForwardIterator>
+  first_min_last_max_element(ForwardIterator first, ForwardIterator last,
+                             BinaryPredicate comp);
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>>
+  std::pair&lt;ForwardIterator,ForwardIterator>
+  last_min_first_max_element(ForwardIterator first, ForwardIterator last);
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>>
+  std::pair&lt;ForwardIterator,ForwardIterator>
+  last_min_first_max_element(ForwardIterator first, ForwardIterator last,
+                             BinaryPredicate comp);
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>>
+  std::pair&lt;ForwardIterator,ForwardIterator>
+  last_min_last_max_element(ForwardIterator first, ForwardIterator last);
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>>
+  std::pair&lt;ForwardIterator,ForwardIterator>
+  last_min_last_max_element(ForwardIterator first, ForwardIterator last,
+                            BinaryPredicate comp);
+
+}</pre>
+
+<hr SIZE="6">
+<br>Last modified 2002-07-01
+<p><font face="Arial,Helvetica"><font size=-1>&copy; Copyright Herv&eacute;
+Br&ouml;nnimann, Polytechnic University, 2002--2004. 
+Use, modification, and distribution is subject to the Boost Software
+License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">License_1_0.txt</a> or copy at
+<a href="http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)
+</font></font>
+</body>
+</html>

minmax/example/minmax_ex.cpp

@@ -0,0 +1,36 @@
+//  (C) Copyright Herve Bronnimann 2004.
+//  Use, modification and distribution are subject to the
+//  Boost Software License, Version 1.0. (See accompanying file
+//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <list>
+#include <algorithm>
+#include <cstdlib>
+#include <cassert>
+#include <iostream>
+
+#include <boost/algorithm/minmax.hpp>
+#include <boost/algorithm/minmax_element.hpp>
+
+int main()
+{
+  using namespace std;
+
+  // Demonstrating minmax()
+  boost::tuple<int const&, int const&> result1 = boost::minmax(1, 0);
+  assert( result1.get<0>() == 0 );
+  assert( result1.get<1>() == 1 );
+
+
+  // Demonstrating minmax_element()
+  list<int> L;
+  typedef list<int>::const_iterator iterator;
+  generate_n(front_inserter(L), 1000, rand);
+  pair< iterator, iterator > result2 = boost::minmax_element(L.begin(), L.end());
+
+  cout << "The smallest element is " << *(result2.first) << endl;
+  cout << "The largest element is  " << *(result2.second) << endl;
+
+  assert( result2.first  == std::min_element(L.begin(), L.end()) );
+  assert( result2.second == std::max_element(L.begin(), L.end()) );
+}

minmax/example/minmax_timer.cpp

@@ -0,0 +1,212 @@
+//  (C) Copyright Herve Bronnimann 2004.
+//  Use, modification and distribution are subject to the
+//  Boost Software License, Version 1.0. (See accompanying file
+//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <utility>
+#include <functional>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <vector>
+#include <list>
+#include <set>
+#include <iostream>
+// What's the proper BOOST_ flag for <iomanip.h> vs <ios>
+#include <iomanip>
+
+#include <boost/timer.hpp>
+#include <boost/algorithm/minmax.hpp>
+
+template <class T1, class T2>
+void tie(std::pair<T1, T2> p, T1& min, T2& max)
+{
+  min = p.first; max = p.second;
+}
+
+template <class Value>
+struct less_count : std::less<Value> {
+  less_count(less_count<Value> const& lc) : _M_counter(lc._M_counter) {}
+  less_count(int& counter) : _M_counter(counter) {}
+  bool operator()(Value const& a, Value const& b) const {
+    ++_M_counter;
+    return std::less<Value>::operator()(a,b);
+  }
+  void reset() {
+    _M_counter = 0;
+  }
+private:
+  int& _M_counter;
+};
+
+inline int opt_min_count(int n) {
+  return (n==0) ? 0 : n-1;
+}
+inline int opt_minmax_count(int n) {
+  if (n < 2) return 0;
+  if (n == 2) return 1;
+  return (n%2 == 0) ? 3*(n/2)-1 : 3*(n/2)+1;
+}
+inline int opt_boost_minmax_count(int n) {
+  if (n < 2) return 0;
+  if (n == 2) return 1;
+  return (n%2 == 0) ? 3*(n/2)-2 : 3*(n/2);
+}
+
+int repeats = 10;
+
+#define TIMER( n, cmd , cmdname ) \
+  t.restart(); \
+  for (int i=0; i<repeats; ++i) { cmd ; } \
+  std::cout << "    " << std::setprecision(4) \
+            << (double)n*repeats/t.elapsed()/1.0E6 \
+            << "M items/sec  " << cmdname << "\n"
+
+#define CTIMER( n, cmd , cmdname, count, opt ) \
+  t.restart(); lc.reset(); \
+  for (int i=0; i<repeats; ++i) { cmd ; } \
+  std::cout << "    " << std::setprecision(4) \
+            << (double)n*repeats/t.elapsed()/1.0E6 \
+            << "M items/sec  " << cmdname \
+            << " ("<< (count)/repeats << " vs " << opt << ")\n"
+
+template <class CIterator>
+void test_minmax_element(CIterator first, CIterator last, int n, char* name)
+{
+  typedef typename std::iterator_traits<CIterator>::value_type vtype;
+  boost::timer t;
+
+  std::cout << "  ON " << name << " WITH OPERATOR<()\n";
+  TIMER( n, std::min_element(first, last),
+    "std::min_element" << name << "");
+  TIMER( n, std::max_element(first, last),
+    "std::max_element" << name << "");
+  TIMER( n, boost::first_min_element(first, last),
+    "boost::first_min_element" << name << "");
+  TIMER( n, boost::last_min_element(first, last),
+    "boost::last_min_element" << name << " ");
+  TIMER( n, boost::first_max_element(first, last),
+    "boost::first_max_element" << name << "");
+  TIMER( n, boost::last_max_element(first, last),
+    "boost::last_max_element" << name << " ");
+  TIMER( n, boost::minmax_element(first, last),
+    "boost::minmax_element" << name << "    ");
+  TIMER( n, boost::first_min_last_max_element(first, last),
+    "boost::first_min_last_max_element" << name << "");
+  TIMER( n, boost::last_min_first_max_element(first, last),
+    "boost::last_min_first_max_element" << name << "");
+  TIMER( n, boost::last_min_last_max_element(first, last),
+    "boost::last_min_last_max_element" << name << " ");
+
+  #define pred std::bind2nd( std::greater<vtype>(), vtype(10) )
+  TIMER( n, boost::min_element_if(first, last, pred),
+    "boost::min_element_if" << name << "");
+  TIMER( n, boost::max_element_if(first, last, pred),
+    "boost::max_element_if" << name << "");
+  TIMER( n, std::min_element(boost::make_filter_iterator(first, last, pred),
+                             boost::make_filter_iterator(last, last, pred)),
+    "std::min_element_with_filter_iterator" << name << "");
+  TIMER( n, std::max_element(boost::make_filter_iterator(first, last, pred),
+                             boost::make_filter_iterator(last, last, pred)),
+    "std::max_element_if_with_filter_iterator" << name << "");
+  #undef pred
+
+  int counter = 0;
+  less_count<vtype> lc(counter);
+  std::cout << "  ON " << name << " WITH LESS<> AND COUNTING COMPARISONS\n";
+  CTIMER( n, std::min_element(first, last, lc),
+    "std::min_element" << name << "        ",
+    counter, opt_min_count(n) );
+  CTIMER( n, std::max_element(first, last, lc),
+    "std::max_element" << name << "        ",
+    counter, opt_min_count(n) );
+  CTIMER( n, boost::first_min_element(first, last, lc),
+    "boost::first_min_element" << name << "",
+    counter, opt_min_count(n) );
+  CTIMER( n, boost::last_min_element(first, last, lc),
+    "boost::last_max_element" << name << " ",
+    counter, opt_min_count(n) );
+  CTIMER( n, boost::first_max_element(first, last, lc),
+    "boost::first_min_element" << name << "",
+    counter, opt_min_count(n) );
+  CTIMER( n, boost::last_max_element(first, last, lc),
+    "boost::last_max_element" << name << " ",
+    counter, opt_min_count(n) );
+  CTIMER( n, boost::minmax_element(first, last, lc),
+    "boost::minmax_element" << name << "   ",
+    counter, opt_minmax_count(n) );
+  CTIMER( n, boost::first_min_last_max_element(first, last, lc),
+    "boost::first_min_last_max_element" << name << "",
+    counter, opt_boost_minmax_count(n) );
+  CTIMER( n, boost::last_min_first_max_element(first, last, lc),
+    "boost::last_min_first_max_element" << name << "",
+    counter, opt_boost_minmax_count(n) );
+  CTIMER( n, boost::last_min_last_max_element(first, last, lc),
+    "boost::last_min_last_max_element" << name << " ",
+    counter, opt_minmax_count(n) );
+}
+
+template <class Container, class Iterator, class Value>
+void test_container(Iterator first, Iterator last, int n, char* name)
+{
+  Container c(first, last);
+  typename Container::iterator fit(c.begin()), lit(c.end());
+  test_minmax_element(fit, lit, n, name);
+}
+
+template <class Iterator>
+void test_range(Iterator first, Iterator last, int n)
+{
+  typedef typename std::iterator_traits<Iterator>::value_type Value;
+  // Test various containers with these values
+  test_container< std::vector<Value>, Iterator, Value >(first, last, n, "<vector>");
+#ifndef ONLY_VECTOR
+  test_container< std::list<Value>,   Iterator, Value >(first, last, n, "<list>  ");
+  test_container< std::multiset<Value>,    Iterator, Value >(first, last, n, "<set>   ");
+#endif
+}
+
+template <class Value>
+void test(int n)
+{
+  // Populate test vector with identical values
+  std::cout << "IDENTICAL VALUES...   \n";
+  std::vector<Value> test_vector(n, Value(1));
+  typename std::vector<Value>::iterator first( test_vector.begin() );
+  typename std::vector<Value>::iterator last( test_vector.end() );
+  test_range(first, last, n);
+
+  // Populate test vector with two values
+  std::cout << "TWO DISTINCT VALUES...\n";
+  typename std::vector<Value>::iterator middle( first + n/2 );
+  std::fill(middle, last, Value(2));
+  test_range(first, last, n);
+
+  // Populate test vector with increasing values
+  std::cout << "INCREASING VALUES...  \n";
+  std::fill(first, last, Value(1));
+  std::accumulate(first, last, Value(0));
+  test_range(first, last, n);
+
+  // Populate test vector with decreasing values
+  std::cout << "DECREASING VALUES...  \n";
+  std::reverse(first, last);
+  test_range(first, last, n);
+
+  // Populate test vector with random values
+  std::cout << "RANDOM VALUES...      \n";
+  std::random_shuffle(first, last);
+  test_range(first, last, n);
+}
+
+int
+main(char argc, char** argv)
+{
+  int n = 100;
+  if (argc > 1) n = atoi(argv[1]);
+  if (argc > 2) repeats = atoi(argv[2]);
+
+  test<int>(n);
+
+  return 0;
+}

minmax/index.html

@@ -0,0 +1,527 @@
+<!DOCTYPE html public "-//w3c//dtd html 4.0 transitional//en">
+<HTML>
+<HEAD>
+   <LINK REL="stylesheet" TYPE="text/css" HREF="../../../boost.css">
+   <META http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
+   <META name="GENERATOR" content="Mozilla/4.77 [en] (X11; U; Linux 2.2.19 i686) [Netscape]">
+   <META name="Author" content="Herve Bronnimann">
+   <META name="Description" content="Small library to propose minmax_element algorithm.">
+   <title>Boost Minmax library</title>
+</HEAD>
+<body text="#000000" bgcolor="#FFFFFF" link="#0000EE" vlink="#551A8B" alink="#FF0000">
+
+<h2><img src="../../../boost.png" WIDTH="276" HEIGHT="86">Header &lt;<A
+HREF="../../../boost/algorithm/minmax.hpp">boost/algorithm/minmax.hpp</A>&gt; </H2>
+
+<quote>
+<b>
+<a href="#minmax_element">Motivation</a><br>
+<a href="#synopsis">Synopsis</a><br>
+<a href="#description">Function templates description</a><br>
+<a href="#definition">Definition</a><br>
+<a href="#reqs">Requirements on types</a><br>
+<a href="#precond">Preconditions</a><br>
+<a href="#postcond">Postconditions</a><br>
+<a href="#complexity">Complexity</a><br>
+<a href="#example">Example</a><br>
+<a href="#notes">Notes</a><br>
+<a href="#rationale">Rationale</a><br>
+<a href="#perf">Note about performance</a><br>
+<a href="#acks">Acknowledgements</a>
+</b>
+</quote>
+
+
+<a name="minmax_element">
+<h3>
+Motivation</h3>
+
+<p>The minmax library is composed of two headers, <a
+href="../../../boost/algorithm/minmax.hpp">&lt;boost/algorithm/minmax.hpp></a>
+and <a
+href="../../../boost/algorithm/minmax_element.hpp">&lt;boost/algorithm/minmax_element.hpp></a>.
+(See <a href="#two_headers">rationale</a>.)
+The problem solved by this library is that simultaneous min and max
+computation requires
+only one comparison, but using <tt>std::min</tt> and <tt>std::max</tt>
+forces two comparisons. Worse, to compute the minimum and
+maximum elements of a range of <tt>n</tt> elements requires only
+<tt>3n/2+1</tt> comparisons, instead of the <tt>2n</tt> (in two passes)
+forced by <tt>std::min_element</tt> and <tt>std::max_element</tt>.
+I always thought it is a waste to have to call two functions to compute the
+extent of a range, performing two passes over the input, when one should
+be enough. The present library solves both problems.</p>
+
+<p>The first file implements the function templates
+<tt>minmax</tt>
+as straightforward extensions of the C++
+standard. As it returns a pair of <tt>const&amp;</tt>, we must use the <a
+href=:../../../../tuple/index.html>Boost.tuple</a> library to construct such
+pairs. (Please note: the intent is not to fix the known defaults of
+<tt>std::min</tt>
+and <tt>std::max</tt>, but to add one more algorithms that combines both; see the
+<a href="#no-fix">rationale</a>.)</p>
+
+<p>The second file implements the function templates
+<tt>minmax_element</tt>. In a
+second part, it also proposes variants that can usually not be computed by
+the minmax algorithm, and which are more flexible in case some elements are equal.
+Those variants could have been also provided with policy-based design,
+but I ruled against that (see <a href="#no-policy">rationale</a>).
+</p>
+
+<p>If you are interested about
+<a href="doc/minmax_benchs.html">performance</a>,
+you will see that <tt>minmax_element</tt> is just slightly less efficient
+than a single <tt>min_element</tt> or <tt>max_element</tt>, and thus
+twice as efficient as two separate calls to <tt>min_element</tt> and
+<tt>max_element</tt>. From a
+theoretical standpoint,
+all the <tt>minmax_element</tt> functions perform at most
+<tt>3n/2+1</tt>
+comparisons and exactly n increments of the
+<tt>ForwardIterator</tt>.</p>
+</a>
+
+<a name="synopsis">
+<h3>
+Synopsis of <tt>&lt;boost/algorithm/minmax.hpp></tt></h3>
+
+<pre>#include &lt;boost/tuple/tuple.hpp>
+
+namespace boost {
+
+  template &lt;class T>
+  tuple&lt;T const&amp;, T const&amp;> >
+  minmax(const T&amp; a, const T&amp; b);
+
+  template &lt;class T, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>>
+  tuple&lt;T const&amp;, T const&amp;> >
+  minmax(const T&amp; a, const T&amp; b, BinaryPredicate comp);
+
+}
+</pre>
+
+<h3>
+Synopsis of <tt>&lt;boost/algorithm/minmax_element.hpp></tt></h3>
+
+<pre>#include &lt;utility> // for std::pair
+
+namespace boost {
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>>
+  std::pair&lt;ForwardIterator,ForwardIterator>
+  minmax_element(ForwardIterator first, ForwardIterator last);
+
+  template &lt;class <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>>
+  std::pair&lt;ForwardIterator,ForwardIterator>
+  minmax_element(ForwardIterator first, ForwardIterator last,
+                 BinaryPredicate comp);
+
+}
+</pre>
+
+In addition, there are a bunch of extensions which specify
+which element(s) you want to pick in case of equal elements. They are:
+<ul>
+<li><tt>first_min_element</tt> and <tt>last_min_element</tt></li>
+<li><tt>first_max_element</tt> and <tt>last_max_element</tt></li>
+<li><tt>first_min_first_max_element</tt>,
+<tt>first_min_last_max_element</tt>,
+<tt>last_min_first_max_element</tt>, and
+<tt>last_min_last_max_element</tt></li>
+</ul>
+I won't bore you with the complete synopsis, they have exactly the same
+declaration as their corresponding <tt>_element</tt> function. Still,
+you can find the complete synopsis <a href="doc/minmax_synopsis.html">here</a>.
+</a>
+
+<a name="description">
+<h3>
+Function templates description</h3>
+The <tt>minmax</tt> algorithm returns a pair <tt>p</tt> containing either
+<i>(a,b)</i>
+or <i>(b,a)</i>, such that <tt>p.first&lt;p.second</tt> in the first version,
+or <tt>comp(p.first,p.second)</tt> in the second version. If the elements
+are equivalent, the pair <i>(a,b) </i>is returned. <a href="#Note1">[1]</a>
+<p>The <tt>minmax_element </tt>is semantically equivalent to <tt>first_min_first_max_element</tt>.
+<p><tt>First_min_element</tt> and <tt>first_max_element</tt> find the smallest
+and largest elements in the range <tt>[first, last)</tt>. If there are
+several instance of these elements, the first one is returned. They are
+identical to
+<tt>std::min_element</tt> and <tt>std::max_element</tt>and
+are only included in this library for symmetry.
+<p><tt>Last_min_element</tt> and <tt>last_max_element</tt> find the smallest
+and largest elements in the range <tt>[first, last)</tt>. They are almost
+identical to
+<tt>std::min_element</tt> and <tt>std::max_element</tt>, except
+that they return the last instance of the largest element (and not the
+first, as <tt>first_min_element</tt> and <tt>last_max_element</tt> would).
+<p>The family of algorithms comprising <tt>first_min_first_max_element</tt>,
+<tt>first_min_first_max_element</tt>,
+<tt>first_min_first_max_element</tt>,
+and <tt>first_min_first_max_element</tt> can be described generically as
+follows (using <i><tt>which</tt></i> and
+<i><tt>what</tt></i> for <tt>first</tt>
+or <tt>last</tt>): <tt><i>which</i>_min_<i>what</i>_max_element</tt> finds
+the (first or last, according to <i><tt>which</tt></i>) smallest element
+and the (first or last, according to <i><tt>what</tt></i>) largest element
+in the range
+<tt>[first, last)</tt>. The first version is semantically
+equivalent to:
+<pre><tt>  std::make_pair(boost::<i>which</i>_min_element(first,last),
+                 boost::<i>what</i>_max_element(first,last))</tt>,</pre>
+and the second version to:
+<pre><tt>  std::make_pair(boost::<i>which</i>_min_element(first,last,comp),
+                 boost::<i>what</i>_max_element(first,last,comp))</tt>.</pre>
+
+<p><br><b><i>Note</i></b>: the <tt>first_min_last_max_element</tt> can also be described
+as finding the first and last elements in the range if it were stably sorted.
+</a>
+
+<a name="definition">
+<h3>
+Definition</h3>
+Defined in <a href="../../../boost/algorithm/minmax.hpp">minmax.hpp</a>
+and
+in <a href="../../../boost/algorithm/minmax_element.hpp">minmax_element.hpp</a>.
+</a>
+
+<a name="reqs">
+<h3>
+Requirements on types</h3>
+For minmax, <tt>T</tt> must be a model of <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThan
+Comparable</a>.
+<p>For all the other function templates, versions with two template parameters:
+<ul>
+<li>
+<tt>ForwardIterator</tt> is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">Forward
+Iterator</a>.</li>
+
+<li>
+<tt>ForwardIterator</tt>'s value type is <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThan
+Comparable</a>.</li>
+</ul>
+For the versions with three template parameters:
+<ul>
+<li>
+<tt>ForwardIterator</tt> is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">Forward
+Iterator</a>.</li>
+
+<li>
+<tt>BinaryPredicate</tt> is a model of <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">Binary
+Predicate</a>.</li>
+
+<li>
+<tt>ForwardIterator</tt>'s value type is convertible to <tt>BinaryPredicate</tt>'s
+first argument type and second argument type.</li>
+</ul>
+</a>
+
+<a name="precond">
+<h3>
+Preconditions</h3>
+
+<ul>
+<li>
+<tt>[first, last)</tt> is a valid range.</li>
+</ul>
+</a>
+
+<a name="postcond">
+<h3>
+Postconditions</h3>
+In addition to the semantic description above. for <tt>minmax_element</tt>
+and all the <tt><i>which</i>_min_<i>what</i>_max_element</tt>
+variants, the return value is
+<tt>last</tt> or <tt>std::make_pair(last,last)</tt>
+if and only if <tt>[first, last)</tt> is an empty range. Otherwise, the
+return value or both members of the resulting pair are iterators in the
+range
+<tt>[first, last)</tt>.
+</a>
+
+<a name="complexity">
+<h3>
+<a NAME="Complexity"></a>Complexity</h3>
+Minmax performs a single comparison and is otherwise of constant complexity.
+The use of <tt>boost::tuple&lt;T const&amp;></tt> prevents copy
+constructors in case the arguments are passed by reference.
+<p>The complexity of all the other algorithms is linear. They all perform
+exactly n increment operations, and zero comparisons if <tt>[first,last)</tt>
+is empty, otherwise :
+<ul>
+<li>
+all the <tt>min_element</tt> and <tt>max_element</tt> variants perform
+exactly<tt>(n-1)</tt> comparisons,</li>
+
+<li>
+<tt>minmax_element</tt> , <tt>first_min_first_max_element</tt>, and <tt>last_min_last_max_element</tt>
+perform at most <tt>3(n/2)-1</tt> comparisons if <tt>n</tt> is even and
+non-zero, and at most <tt>3(n/2)+1</tt> if <tt>n</tt> is odd,
+<a href="#Note2">[2]</a></li>
+
+<li>
+<tt>first_min_last_max_element</tt>, and <tt>last_min_first_max_element</tt>
+perform exactly <tt>3n/2-2</tt> comparisons if n is even and non-zero,
+and at most <tt>3(n/2)</tt> if <tt>n</tt> is odd,
+<a href="#Note1">[3]</a></li>
+</ul>
+where <tt>n</tt> is the number of elements in <tt>[first,last)</tt>.
+</a>
+
+<a name="example">
+<h3>
+Example</h3>
+This example is included in the distribution in the examples section of
+the library under
+<a href="example/minmax_ex.cpp">minmax_ex.cpp</a>.
+
+<pre>int main()
+{
+  using namespace std;
+  boost::tuple&lt;int const&amp;, int const&amp;> result1 = boost::minmax(1, 0);
+
+  assert( result1.get<0>() == 0 );
+  assert( result1.get<1>() == 1 );
+
+  <a href="http://www.sgi.com/tech/stl/List.html">list</a>&lt;int> L;
+  <a href="http://www.sgi.com/tech/stl/generate_n.html">generate_n</a>(<a href="http://www.sgi.com/tech/stl/front_insert_iterator.html">front_inserter</a>(L), 1000, rand);
+
+  typedef list&lt;int>::const_iterator iterator;
+  pair&lt; iterator, iterator > result2 = boost::minmax_element(L.begin(), L.end());
+  cout &lt;&lt; "The smallest element is " &lt;&lt; *(result2.first) &lt;&lt; endl;
+  cout &lt;&lt; "The largest element is  " &lt;&lt; *(result2.second) &lt;&lt; endl;
+
+  assert( result2.first  == std::min_element(L.begin(), L.end());
+  assert( result2.second == std::max_element(L.begin(), L.end());
+}</pre>
+</a>
+
+<a name="notes">
+<h3>
+Notes</h3>
+<a NAME="Note1"></a><a href="#Note1">[1]</a> We do not support
+idioms such as <tt><a href="../../tuple/doc/tuple_users_guide.html#tiers">tie</a>(a,b)=minmax(a,b)</tt>
+to order two elements <tt>a</tt>, <tt>b</tt>, although this would have
+the desired effect if we returned a reference instead of a constant
+reference. The reason is that two unnecessary assignments are
+performed if a and b are in order. It is better to stick to <tt>if (b&lt;a)
+swap(a,b)</tt> to achieve that effect.
+<p><a NAME="Note2"></a><a href="#Note2">[2]</a> These algorithms always
+perform at least <tt>3n/2-2</tt> comparisons, which is a lower bound on
+the number of comparisons in any case (Cormen, Leiserson, Rivest: "Introduction
+to Algorithms", section 9.1, Exercise 9.1-). The algorithms essentially compare
+the elements in pairs, performing 1 comparison for the first two elements,
+then 3 comparisons for each remaining pair of elements (one to order the
+elements and one for updating each the minimum and and the maximum). When
+the number of elements is odd, the last one needs to be compared to the
+current minimum and also to the current maximum. In addition, for <tt>minmax</tt>,
+in cases where equality of the two members in the pair could occur, and
+the update stores the second, we save the first to check at the end if
+the update should have stored the first (in case of equality). It's hard
+to predict if the last comparison is performed or not, hence the at most
+in both cases.
+<p><a NAME="Note3"></a><a href="#Note3">[3]</a> These algorithms always
+perform at least <tt>3n/2-2</tt> comparisons, which is a lower bound on
+the number of comparisons in any case. The method is the same as in note
+<a href="#Note2">[2]</a>
+above, and like above, when the number of elements is odd, the last one
+needs to be compared to the current minimum and also to the current maximum.
+We can avoid the latter comparison if the former is successful, hence the
+<i>at
+most</i> instead of <i>exactly</i> in the odd case.
+</a>
+
+<a name="rationale">
+<h3>
+<b>Rationale:</b></h3>
+
+<a name="two_headers">
+<h4><b>Why not a single header <tt>&amp;boost/algorithm/minmax.hpp></tt>?</b></h4>
+<p>This was the design originally proposed and approved in the formal
+review. As the need for Boost.tuple became clear (due to the limitations
+of <tt>std::pair</tt>), it became also annoying to require another
+library for <tt>minmax_element</tt> which does not need it. Hence the
+separation into two header files.</p>
+
+<a name="no-fix">
+<h4><b>Your minmax suffers from the same problems as std::min and
+std::max.</b></h4>
+<p>I am aware of the problems with std::min and
+std::max, and all the debate that has been going on (please consult
+<a href="http://www.cuj.com/documents/s=7996/cujcexp1904alexandr/alexandr.htm">Alexandrescu's paper</a> and the links therein). But I don't see the purpose of this
+library as fixing something that is part of the C++ standard. I humbly
+think it's beyond the scope of this library. Rather, I am
+following the way of the standard in simply providing one more function
+of the same family. If someone else wants to fix std::min, their fix
+would probably apply to boost::minmax as well.</p>
+</a>
+
+<h4><b>Why no <tt>min/max_element_if</tt>?</b></h4>
+<p>In a first version of the library, I proposed <tt>_if</tt> versions of
+all the algorithms (well, not all, because that would be too much).
+However, there is simply no reason to do so, and all the versions I had
+were just as fast implemented using the excellent
+<tt>&lt;boost/iterator_adaptors.hpp></tt> library. Namely, a call to
+<tt>min_element_if(first, last, pred)</tt> would be just as well
+implemented by:
+<pre>
+     // equivalent to min_element_if(first, last, pred)
+     min_element(boost::make_filter_iterator(first, last, pred),
+                 boost::make_filter_iterator(last, last, pred));
+</pre>
+Arguably, the <tt>min_element_if</tt> version is somewhat shorter, but
+the overhead of iterator adaptors is not large, and they get rid of a
+lot of code (think of all the combinations between first/last and
+doubling them with _if variants!).</p>
+
+<h4><b>Discussion: about std::max_element</b></h4>
+<p>This rationale is somewhat historical, but explains why there are all
+these <tt>first/last_min/max_element</tt> functions.</p>
+<p>The C++ standard mandates that <tt>std::min_element</tt> and <tt>std::max_element</tt>
+return the first instance of the smallest and largest elements (as opposed
+to, say, the last). This arbitrary choice has some consistency: In the
+case of v of type vector&lt;int>, for instance, it is true that <tt>std::min_element(v.begin(),v.end(),std::less&lt;int>())
+== std::max_element(v.begin(),v.end(),std::greater&lt;int>())</tt>.
+<p>There is of course nothing wrong with this: it's simply a matter of
+choice. Yet another way to specify min_element and max_element is to define
+them as the first and the last elements if the range was stably sorted.
+(The <i>stable</i> sort is necessary to disambiguate between iterators
+that have the same value.) In that case, min should return the first instance
+and max should return the last. Then, both functions are related by
+<tt>reverse_iterator(std::first_min_element(v.begin(),v.end(),std::less&lt;int>()))
+==
+std::last_max_element(v.rbegin(),v.rend(),std::greater&lt;int>())</tt>.
+This definition is subtly different from the previous one.</p>
+<p>The definition problem surfaces when one tries to design a minmax_element,
+using the procedure proposed in (Cormen, Leiserson, Rivest: "Introduction
+to Algorithms", section 9.1). It <i>should</i> be possible to derive an
+algorithm using only <tt>3n/2</tt> comparisons if <tt>[first,last) </tt>has
+<tt>n</tt>
+elements, but if one tries to write a function called <tt>first_min_first_max_element()</tt>
+which returns both <tt>std::min_element</tt> and <tt>std::max_element</tt>
+in a pair, the trivial implementation does not work. The problem, rather
+subtly, is about equal elements: I had to think for a while to find a
+way to perform only three
+comparisons per pair and return the first min and first max elements.
+For a long time, it seemed any
+attempts at doing so would consume four comparisons per pair in the worst
+case. This implementation achieves three.</p>
+<p>It is not possible (or even desirable) to change the meaning of
+<tt>max_element</tt>,
+but it is still beneficial to provide a function called <tt>minmax_element</tt>,
+which returns a pair of <tt>min_element</tt> and <tt>max_element</tt>.
+Although it is easy enough to call <tt>min_element</tt> and <tt>max_element</tt>,
+this performs
+<tt>2(n-1)</tt> comparisons, and necessitates <b>two</b>
+passes over the input. In contrast,
+<tt>minmax_element</tt> will perform
+the fewer comparisons and perform a <b>single</b> pass over the input.
+The savings can be significant when the iterator type is not a raw pointer,
+or even is just a model of the InputIterator concept (although in that
+case the interface would have to be
+changed, as the return type could not be copied, so one could e.g.
+return a value).</p>
+<p>In order to benefit from all the variants of the algorithm, I propose
+to introduce both <tt>first_min_element</tt> and <tt>last_min_element</tt>,
+and their counterparts <tt>first_max_element</tt> and <tt>last_max_element</tt>.
+Then I also propose all the variants algorithms: <tt>first_min_last_max_element</tt>
+and <tt>last_min_first_max_element</tt>, which perform only at most <tt>3n/2</tt>
+comparisons, and only a single pass on the input. In fact, it can be proven
+that computing minmax requires at least <tt>3(n/2)-2</tt> comparisons in
+any instance of the problem (Cormen, Leiserson, Rivest, 2nd edition, section
+9.1). The implementation I give does not perform unnecessary comparisons
+(whose result could have been computed by transitivity from previous
+comparisons).</p>
+<p>It appears that <tt>first_min_last_max_element</tt> may be just a tad
+slower than
+<tt>first_min_element</tt> alone, still much less than <tt>first_min_element</tt>
+and
+<tt>last_max_element</tt> called separately.  <a href="#Performance">[2]</a>
+
+<h4><b>Why algorithms and not accumulators?</b></h4>
+<p>The minmax algorithms are useful in computing the extent of a range.
+In computer graphics, we need a bounding box of a set of objects.
+In that case the need for a single pass is even more stringent
+as all three directions must be done at once. Food for thoughts: there
+is matter for a nice generic programming library with stackable <tt>update_min</tt>
+and <tt>update_max</tt> function objects which store a reference to the
+<tt>min_result</tt>and
+<tt>max_result</tt> variables, in conjunction with the <tt>for_each</tt>
+algorithm).</p>
+<p>I believe many standard sequential algorithms could be reformulated
+with accumulators (and many others, such as in statistics, expectation /
+variance / etc.). It seems that there is room for another library, but I
+do not see it competing with minmax, rather extending several algorithms
+(including minmax) to the accumulator framework. However, I felt it is
+beyond the scope of this library to provide such accumulators.</p>
+
+<a NAME="no-policy">
+<h4><b>This first/last is a perfect application for a policy-based
+design.</b></h4>
+<p>True, and I could have gone that way, with the default policy for
+<tt>min_element</tt> and <tt>max_element</tt> to pick the first
+occurence of the result. This would have thinned the number of
+combinations of the minmax_element variants. But it would also have
+meant to change the interface of <tt>boost::minmax_element</tt>.
+One of the goals of the <tt>minmax_element</tt> algorithm is its
+eventual addition to the C++ standard, in connection with
+<tt>std::min_element</tt> and <tt>std::max_element</tt>
+(and I feel that it would be quite natural
+given the shortness of the implementation, and the not quite trivial
+detail which is needed to get it right). So changing the interface by
+adding policies would have meant unfortunately to depart from the
+standard and created an obstacle towards that goal. Besides, the code
+remains rather readable and simple without policies. So I am quite happy
+to keep it like this.
+</p></a>
+</a>
+
+<a name="perf">
+<a href="doc/minmax_benchs.html"><h3><b>About performance</b></h3></a>
+</a>
+
+<a name="acks">
+<h3>
+Acknowledgements</h3>
+My students in CS903 (Polytechnic Univ., <a href="http://photon.poly.edu/~hbr/cs903/">http://photon.poly.edu/~hbr/cs903/</a>)
+who had <tt>minmax_element</tt> as an assignment helped clarify the issues,
+and also come up with the optimum number of comparisons for <tt>first_min_last_max_element</tt>.
+The identification of the issue surrounding <tt>max_element</tt> is solely
+my own.
+<p>One <tt>minmax_element</tt> implementation, which performs <tt>3(n/2)+O(log
+n)</tt> comparisons on the average when the elements are <tt>random_shuffle</tt>d,
+was suggested by my student Marc Glisse. The current one, which performs
+<tt>3(n/2)+1</tt>
+comparisons in the worst case, was suggested by John Iacono.<p>
+<p>Finally, Matthew Wilson and Jeremy Siek contributed pre-review
+comments, while Gennadiy Rozental, John Maddock, Craig Henderson, Gary
+Powell participated in the review of the library, managed by Thomas
+Witt. In particular, Gennadiy suggested a factorization of the code;
+while I haven't followed it all the way, his suggestions do make the
+code more readable and still work with older compilers. 
+Late after the review, as I finally scrounged to add the library for a
+release, Eric Niebler noted the bad behavior of <tt>std::pair</tt> for
+<tt>minmax</tt> and suggested to use Boost.tuple instead. 
+All my thanks for the excellent advice and reviews from all.
+<h3>
+See also</h3>
+<tt><a href="http://www.sgi.com/tech/stl/min.html">min</a></tt>, <tt><a href="http://www.sgi.com/tech/stl/max.html">max</a></tt>,
+<tt><a href="http://www.sgi.com/tech/stl/min_element.html">min_element</a></tt>,
+<tt><a href="http://www.sgi.com/tech/stl/max_element.html">max_element</a></tt>,
+<tt><a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThan
+Comparable</a></tt>,
+<tt><a href="http://www.sgi.com/tech/stl/sort.html">sort</a></tt>,
+<tt><a href="http://www.sgi.com/tech/stl/nth_element.html">nth_element</a></tt>
+.
+<hr SIZE="6">
+<br>Last modified 2004-07-01
+<p><font face="Arial,Helvetica"><font size=-1>&copy; Copyright Herv&eacute;
+Br&ouml;nnimann, Polytechnic University, 2002--2004. 
+Use, modification, and distribution is subject to the Boost Software
+License, Version 1.0. (See accompanying file <a href="../../../LICENSE_1_0.txt">License_1_0.txt</a> or copy at
+<a href="http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)
+</font></font>
+</body>
+</html>

minmax/test/Jamfile.v2

@@ -0,0 +1,20 @@
+#  Boost.Minmax Library test Jamfile
+#
+#  Copyright (C) 2002--2004, Herve Bronnimann
+#
+# Use, modification, and distribution is subject to the Boost Software
+# License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+# http://www.boost.org/LICENSE_1_0.txt)
+#
+
+import testing ;
+
+{
+  test-suite algorithm/minmax:
+   : [ run minmax_element_test.cpp
+       : : : : minmax_element ]
+     [ run minmax_test.cpp
+       : : : : minmax ]      
+   ;
+}
+

minmax/test/minmax_element_test.cpp

@@ -0,0 +1,241 @@
+//  (C) Copyright Herve Bronnimann 2004.
+//  Use, modification and distribution are subject to the
+//  Boost Software License, Version 1.0. (See accompanying file
+//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <utility>
+#include <functional>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <vector>
+#include <list>
+#include <set>
+#include <cstdlib>
+
+#include <boost/config.hpp> /* prevents some nasty warns in MSVC */
+#include <boost/algorithm/minmax_element.hpp>
+#include <boost/test/included/test_exec_monitor.hpp>
+#include <boost/iterator/reverse_iterator.hpp>
+
+class custom {
+  int m_x;
+  friend bool operator<(custom const& x, custom const& y);
+public:
+  explicit custom(int x = 0) : m_x(x) {}
+  custom(custom const& y) : m_x(y.m_x) {}
+  custom operator+(custom const& y) const { return custom(m_x+y.m_x); }
+  custom& operator+=(custom const& y) { m_x += y.m_x; return *this; }
+};
+
+bool operator< (custom const& x, custom const& y)
+{
+  return x.m_x < y.m_x;
+}
+
+BOOST_BROKEN_COMPILER_TYPE_TRAITS_SPECIALIZATION(custom)
+
+namespace std {
+
+template <>
+struct iterator_traits<int*> {
+  typedef random_access_iterator_tag  iterator_category;
+  typedef int                          value_type;
+  typedef ptrdiff_t                    difference_type;
+  typedef value_type*                  pointer;
+  typedef value_type&                  reference;
+};
+
+template <>
+struct iterator_traits<custom*> {
+  typedef random_access_iterator_tag  iterator_category;
+  typedef custom                       value_type;
+  typedef ptrdiff_t                    difference_type;
+  typedef value_type*                  pointer;
+  typedef value_type&                  reference;
+};
+
+}
+
+template <class T1, class T2, class T3, class T4>
+void tie(std::pair<T1, T2> p, T3& first, T4& second)
+{
+  first = T3(p.first); second = T4(p.second);
+}
+
+template <class Value>
+struct less_count : std::less<Value> {
+    typedef std::less<Value> Base;
+  less_count(less_count<Value> const& lc) : m_counter(lc.m_counter) {}
+  less_count(int& counter) : m_counter(counter) {}
+  bool operator()(Value const& a, Value const& b) const {
+    ++m_counter;
+    return Base::operator()(a,b);
+  }
+  void reset() {
+    m_counter = 0;
+  }
+private:
+  int& m_counter;
+};
+
+inline int opt_min_count(int n) {
+  return (n==0) ? 0 : n-1;
+}
+inline int opt_minmax_count(int n) {
+  if (n < 2) return 0;
+  if (n == 2) return 2;
+  return (n%2 == 0) ? 3*(n/2)-1 : 3*(n/2)+1;
+}
+inline int opt_boost_minmax_count(int n) {
+  if (n < 2) return 0;
+  if (n == 2) return 1;
+  return (n%2 == 0) ? 3*(n/2)-2 : 3*(n/2);
+}
+
+#define CHECK_EQUAL_ITERATORS( left, right, first ) \
+BOOST_CHECK_EQUAL( std::distance( first, left ), std::distance( first, right ) )
+
+template <class CIterator>
+void test_minmax(CIterator first, CIterator last, int n)
+{
+  using namespace boost;
+
+  typedef typename std::iterator_traits<CIterator>::value_type Value;
+  typedef boost::reverse_iterator<CIterator> RCIterator;
+  // assume that CIterator is BidirectionalIter
+  CIterator min, max;
+  RCIterator rfirst(last), rlast(first), rmin, rmax;
+  int counter = 0;
+  less_count<Value> lc(counter);
+
+  // standard extensions
+  // first version, operator<
+  tie( boost::minmax_element(first, last), min, max );
+
+  CHECK_EQUAL_ITERATORS( min, std::min_element(first, last), first );
+  CHECK_EQUAL_ITERATORS( max, std::max_element(first, last), first );
+  
+  // second version, comp function object (keeps a counter!)
+  lc.reset();
+  tie( boost::minmax_element(first, last, lc), min, max );
+  BOOST_CHECK( counter <= opt_minmax_count(n) );
+  CHECK_EQUAL_ITERATORS( min, std::min_element(first, last, lc), first );
+  CHECK_EQUAL_ITERATORS( max, std::max_element(first, last, lc), first );
+
+  // boost extensions
+  // first version, operator<
+  CHECK_EQUAL_ITERATORS( boost::first_min_element(first, last), std::min_element(first, last), first );
+  rmin = RCIterator(boost::last_min_element(first, last));
+  rmin = (rmin == rfirst) ? rlast : --rmin;
+  CHECK_EQUAL_ITERATORS( rmin, std::min_element(rfirst, rlast), rfirst );
+  CHECK_EQUAL_ITERATORS( boost::first_max_element(first, last), std::max_element(first, last), first );
+  rmax = RCIterator(boost::last_max_element(first, last));
+  rmax = (rmax == rfirst) ? rlast : --rmax;
+  CHECK_EQUAL_ITERATORS( rmax, std::max_element(rfirst, rlast), rfirst );
+  tie( boost::first_min_last_max_element(first, last), min, max );
+  CHECK_EQUAL_ITERATORS( min, boost::first_min_element(first, last), first );
+  CHECK_EQUAL_ITERATORS( max, boost::last_max_element(first, last), first );
+  tie( boost::last_min_first_max_element(first, last), min, max );
+  CHECK_EQUAL_ITERATORS( min, boost::last_min_element(first, last), first );
+  CHECK_EQUAL_ITERATORS( max, boost::first_max_element(first, last), first );
+  tie( boost::last_min_last_max_element(first, last), min, max );
+  CHECK_EQUAL_ITERATORS( min, boost::last_min_element(first, last), first );
+  CHECK_EQUAL_ITERATORS( max, boost::last_max_element(first, last), first );
+
+  // second version, comp function object (keeps a counter!)
+  lc.reset();
+  min = boost::first_min_element(first, last, lc);
+  BOOST_CHECK( counter <= opt_min_count(n) );
+  CHECK_EQUAL_ITERATORS( min, std::min_element(first, last, lc), first );
+  lc.reset();
+  rmin = RCIterator(boost::last_min_element(first, last, lc));
+  rmin = (rmin == rfirst) ? rlast : --rmin;
+  BOOST_CHECK( counter <= opt_min_count(n) );
+  CHECK_EQUAL_ITERATORS( rmin, std::min_element(rfirst, rlast, lc), rfirst );
+  lc.reset();
+  max =  boost::first_max_element(first, last, lc);
+  BOOST_CHECK( counter <= opt_min_count(n) );
+  CHECK_EQUAL_ITERATORS( max, std::max_element(first, last, lc), first );
+  lc.reset();
+  rmax = RCIterator(boost::last_max_element(first, last, lc));
+  rmax = (rmax == rfirst) ? rlast : --rmax;
+  BOOST_CHECK( counter <= opt_min_count(n) );
+  CHECK_EQUAL_ITERATORS( rmax, std::max_element(rfirst, rlast, lc), rfirst );
+  lc.reset();
+  tie( boost::first_min_last_max_element(first, last, lc), min, max );
+  BOOST_CHECK( counter <= opt_boost_minmax_count(n) );
+  CHECK_EQUAL_ITERATORS( min, boost::first_min_element(first, last, lc), first );
+  CHECK_EQUAL_ITERATORS( max, boost::last_max_element(first, last, lc), first );
+  lc.reset();
+  tie( boost::last_min_first_max_element(first, last, lc), min, max );
+  BOOST_CHECK( counter <= opt_boost_minmax_count(n) );
+  BOOST_CHECK( min == boost::last_min_element(first, last, lc) );
+  CHECK_EQUAL_ITERATORS( max, boost::first_max_element(first, last, lc), first );
+  lc.reset();
+  tie( boost::last_min_last_max_element(first, last, lc), min, max );
+  BOOST_CHECK( counter <= opt_minmax_count(n) );
+  CHECK_EQUAL_ITERATORS( min, boost::last_min_element(first, last, lc), first );
+  CHECK_EQUAL_ITERATORS( max, boost::last_max_element(first, last, lc), first );
+}
+
+template <class Container, class Iterator, class Value>
+void test_container(Iterator first, Iterator last, int n,
+                    Container* dummy = 0
+                    BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Value) )
+{
+  Container c(first, last);
+  test_minmax(c.begin(), c.end(), n);
+}
+
+template <class Iterator>
+void test_range(Iterator first, Iterator last, int n)
+{
+  typedef typename std::iterator_traits<Iterator>::value_type Value;
+  // Test various containers with these values
+  test_container< std::vector<Value>, Iterator, Value >(first, last, n);
+  test_container< std::list<Value>,   Iterator, Value >(first, last, n);
+  test_container< std::set<Value>,    Iterator, Value >(first, last, n);
+}
+
+template <class Value>
+void test(int n BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Value))
+{
+  // Populate test vector with identical values
+  std::vector<Value> test_vector(n, Value(1));
+  typename std::vector<Value>::iterator first( test_vector.begin() );
+  typename std::vector<Value>::iterator last( test_vector.end() );
+  test_range(first, last, n);
+
+  // Populate test vector with two values
+  typename std::vector<Value>::iterator middle( first + n/2 );
+  std::fill(middle, last, Value(2));
+  test_range(first, last, n);
+
+  // Populate test vector with increasing values
+  std::accumulate(first, last, Value(0));
+  test_range(first, last, n);
+
+  // Populate test vector with decreasing values
+  std::reverse(first, last);
+  test_range(first, last, n);
+
+  // Populate test vector with random values
+  std::random_shuffle(first, last);
+  test_range(first, last, n);
+}
+
+int test_main( int argc, char* argv[] )
+{
+#ifndef BOOST_NO_STDC_NAMESPACE
+  using std::atoi;
+#endif
+
+  int n = 100;
+  if (argc > 1) n = atoi(argv[1]);
+
+  test<int>(n);
+  test<custom>(n);
+
+  return 0;
+}

minmax/test/minmax_test.cpp

@@ -0,0 +1,85 @@
+//  (C) Copyright Herve Bronnimann 2004.
+//  Use, modification and distribution are subject to the
+//  Boost Software License, Version 1.0. (See accompanying file
+//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <utility>
+#include <functional>
+
+#include <boost/config.hpp>
+#include <boost/algorithm/minmax.hpp>
+#include <boost/test/included/test_exec_monitor.hpp>
+
+class custom {
+  int m_x;
+  friend std::ostream& operator<<(std::ostream& str, custom const& x);
+public:
+  explicit custom(int x = 0) : m_x(x) {}
+  custom(custom const& y) : m_x(y.m_x) {}
+  bool operator==(custom const& y) const { return m_x == y.m_x; }
+  bool operator<(custom const& y) const { return m_x < y.m_x; }
+  custom operator+(custom const& y) const { return custom(m_x+y.m_x); }
+  custom& operator+=(custom const& y) { m_x += y.m_x; return *this; }
+};
+
+std::ostream&
+operator<<(std::ostream& str, custom const& x)
+{
+  return  str << x.m_x;
+}
+
+template <class Value>
+struct less_count : std::less<Value> {
+  typedef std::less<Value> Base;
+  less_count(less_count<Value> const& lc) : m_counter(lc.m_counter) {}
+  less_count(int& counter) : m_counter(counter) {}
+  bool operator()(Value const& a, Value const& b) const {
+    ++m_counter;
+    return Base::operator()(a,b);
+  }
+  void reset() {
+    m_counter = 0;
+  }
+private:
+  int& m_counter;
+};
+
+using namespace boost;
+
+template <class Value>
+void test(BOOST_EXPLICIT_TEMPLATE_TYPE(Value))
+{
+  Value zero(0), one(1);
+  int counter = 0;
+  less_count<Value> lc(counter);
+
+  // Test functionality
+  tuple<Value const&, Value const&> result1 = minmax(zero, one);
+  BOOST_CHECK_EQUAL( get<0>(result1), zero );
+  BOOST_CHECK_EQUAL( get<1>(result1), one );
+
+  tuple<Value const&, Value const&> result2 = minmax(one, zero);
+  BOOST_CHECK_EQUAL( get<0>(result2), zero );
+  BOOST_CHECK_EQUAL( get<1>(result2), one );
+  
+  // Test functionality and number of comparisons
+  lc.reset();
+  tuple<Value const&, Value const&> result3 = minmax(zero, one, lc );
+  BOOST_CHECK_EQUAL( get<0>(result3), zero );
+  BOOST_CHECK_EQUAL( get<1>(result3), one );
+  BOOST_CHECK_EQUAL( counter, 1 );
+
+  lc.reset();
+  tuple<Value const&, Value const&> result4 = minmax(one, zero, lc );
+  BOOST_CHECK_EQUAL( get<0>(result4), zero );
+  BOOST_CHECK_EQUAL( get<1>(result4), one );
+  BOOST_CHECK_EQUAL( counter, 1);
+}
+
+int test_main( int , char* [] )
+{
+  test<int>(); // ("builtin");
+  test<custom>(); // ("custom ");
+
+  return 0;
+}

string/doc/Jamfile.v2

@@ -0,0 +1,54 @@
+#  Boost string_algo library documentation Jamfile  ---------------------------------
+#
+#  Copyright Pavol Droba 2002-2003. Use, modification and
+#  distribution is subject to the Boost Software License, Version
+#  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+#  http://www.boost.org/LICENSE_1_0.txt)
+#
+#  See http://www.boost.org for updates, documentation, and revision history.
+
+import toolset ;
+toolset.using doxygen ;
+
+boostbook string_algo : string_algo.xml ;
+
+doxygen autodoc
+    :   
+    [ glob ../../../../boost/algorithm/string.hpp ]
+    [ glob ../../../../boost/algorithm/string_regex.hpp ]
+
+    [ glob ../../../../boost/algorithm/string/classification.hpp ]
+    [ glob ../../../../boost/algorithm/string/iterator_range.hpp ]       
+    [ glob ../../../../boost/algorithm/string/sequence_traits.hpp ]
+    [ glob ../../../../boost/algorithm/string/std_containers_traits.hpp ]
+    [ glob ../../../../boost/algorithm/string/concept.hpp ]
+    [ glob ../../../../boost/algorithm/string/compare.hpp ]
+    [ glob ../../../../boost/algorithm/string/constants.hpp ]
+    [ glob ../../../../boost/algorithm/string/case_conv.hpp ]
+    [ glob ../../../../boost/algorithm/string/find.hpp ]
+    [ glob ../../../../boost/algorithm/string/finder.hpp ]
+    [ glob ../../../../boost/algorithm/string/find_iterator.hpp ]
+    [ glob ../../../../boost/algorithm/string/trim.hpp ]
+    [ glob ../../../../boost/algorithm/string/predicate.hpp ]
+    [ glob ../../../../boost/algorithm/string/split.hpp ]
+    [ glob ../../../../boost/algorithm/string/iter_find.hpp ]
+    [ glob ../../../../boost/algorithm/string/erase.hpp ]
+    [ glob ../../../../boost/algorithm/string/join.hpp ]
+    [ glob ../../../../boost/algorithm/string/replace.hpp ]
+    [ glob ../../../../boost/algorithm/string/find_format.hpp ]
+    [ glob ../../../../boost/algorithm/string/formatter.hpp ]
+    [ glob ../../../../boost/algorithm/string/regex.hpp ]
+    [ glob ../../../../boost/algorithm/string/regex_find_format.hpp ]
+    :
+    <doxygen:param>HIDE_UNDOC_MEMBERS=YES
+    <doxygen:param>EXTRACT_PRIVATE=NO
+    <doxygen:param>ENABLE_PREPROCESSING=YES
+    <doxygen:param>MACRO_EXPANSION=YES
+    <doxygen:param>EXPAND_ONLY_PREDEF=YES
+    <doxygen:param>SEARCH_INCLUDES=YES
+    <doxygen:param>PREDEFINED="BOOST_STRING_TYPENAME=typename \"BOOST_STATIC_CONSTANT(type,var)=static const type var;\""
+    ;
+        
+
+
+

string/doc/concept.xml

@@ -0,0 +1,206 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN"
+"http://www.boost.org/tools/boostbook/dtd/boostbook.dtd">
+
+<!-- Copyright (c) 2002-2006 Pavol Droba.
+     Subject to the Boost Software License, Version 1.0. 
+     (See accompanying file LICENSE-1.0 or  http://www.boost.org/LICENSE-1.0)
+-->
+
+
+<section id="string_algo.concept" last-revision="$Date$">
+    <title>Concepts</title>
+
+    <using-namespace name="boost"/>
+    <using-namespace name="boost::algorithm"/>
+
+    <section>   
+        <title>Definitions</title>
+        
+        <table>
+            <title>Notation</title>
+            <tgroup cols="2" align="left">
+                <tbody>
+                    <row>
+                        <entry><code>F</code></entry>
+                        <entry>A type that is a model of Finder</entry>
+                    </row>
+                    <row>
+                        <entry><code>Fmt</code></entry>
+                        <entry>A type that is a model of Formatter</entry>
+                    </row>
+                    <row>
+                        <entry><code>Iter</code></entry>
+                        <entry>
+                            Iterator Type
+                        </entry>
+                    </row>
+                    <row>
+                        <entry><code>f</code></entry>
+                        <entry>Object of type <code>F</code></entry>
+                    </row>
+                    <row>
+                        <entry><code>fmt</code></entry>
+                        <entry>Object of type <code>Fmt</code></entry>
+                    </row>
+                    <row>
+                        <entry><code>i,j</code></entry>
+                        <entry>Objects of type <code>Iter</code></entry>
+                    </row>
+                    </tbody>
+            </tgroup>
+        </table>
+    </section>
+
+    <section id="string_algo.finder_concept">
+        <title>Finder Concept</title>
+
+        <para>
+            Finder is a functor which searches for an arbitrary part of a container. 
+            The result of the search is given as an <classname>iterator_range</classname> 
+            delimiting the selected part.
+        </para>
+
+        <table>             
+            <title>Valid Expressions</title>
+            <tgroup cols="3" align="left">
+                <thead>
+                    <row>   
+                        <entry>Expression</entry>
+                        <entry>Return Type</entry>
+                        <entry>Effects</entry>
+                    </row>
+                </thead>
+                <tbody>
+                    <row>
+                        <entry><code>f(i,j)</code></entry>
+                        <entry>Convertible to <code>iterator_range&lt;Iter&gt;</code></entry>
+                        <entry>Perform the search on the interval [i,j) and returns the result of the search</entry>
+                    </row>
+                </tbody>
+            </tgroup>
+        </table>
+
+        <para>
+            Various algorithms need to perform a search in a container and a Finder is a generalization of such
+            search operations that allows algorithms to abstract from searching. For instance, generic replace
+            algorithms can replace any part of the input, and the Finder is used to select the desired one.
+        </para>
+        <para>
+            Note, that it is only required that the finder works with a particular iterator type. However,
+            a Finder operation can be defined as a template, allowing the Finder to work with any iterator.
+        </para>
+        <para>
+            <emphasis role="bold">Examples</emphasis>
+        </para>
+        <para> 
+            <itemizedlist>
+                <listitem>
+                    Finder implemented as a class. This Finder always returns the whole input as a match. <code>operator()</code>
+                    is templated, so that the finder can be used on any iterator type.
+                    
+                    <programlisting>
+struct simple_finder
+{
+    template&lt;typename ForwardIteratorT&gt;
+    boost::iterator_range&lt;ForwardIterator&gt; operator()(
+        ForwardIteratorT Begin,
+        ForwardIteratorT End )
+    {
+        return boost::make_range( Begin, End );
+    }
+};
+        </programlisting>
+                </listitem>
+                <listitem>
+                    Function Finder. Finder can be any function object. That is, any ordinary function with the
+                    required signature can be used as well. However, such a function can be used only for
+                    a specific iterator type. 
+                    
+                    <programlisting>
+boost::iterator_range&lt;std::string&gt; simple_finder(
+    std::string::const_iterator Begin,
+    std::string::const_iterator End )
+{
+    return boost::make_range( Begin, End );
+}
+        </programlisting>
+                </listitem>
+            </itemizedlist>
+        </para> 
+    </section>
+    <section id="string_algo.formatter_concept">
+        <title>Formatter concept</title>
+
+        <para>
+            Formatters are used by <link linkend="string_algo.replace">replace algorithms</link>.
+            They are used in close combination with finders.
+            A formatter is a functor, which takes a result from a Finder operation and transforms it in a specific way. 
+            The operation of the formatter can use additional information provided by a specific finder,
+            for example <functionname>regex_formatter()</functionname> uses the match information from
+            <functionname>regex_finder()</functionname> to format the result of formatter operation.
+        </para>
+    
+        <table>
+            <title>Valid Expressions</title>
+            <tgroup cols="3" align="left">
+                <thead>
+                    <row>   
+                        <entry>Expression</entry>
+                        <entry>Return Type</entry>
+                        <entry>Effects</entry>
+                    </row>
+                </thead>
+                <tbody>
+                   <row>
+                        <entry><code>fmt(f(i,j))</code></entry>
+                        <entry>A container type, accessible using container traits</entry>
+                        <entry>Formats the result of the finder operation</entry>
+                    </row>
+                </tbody>
+            </tgroup>
+        </table>
+
+        <para>
+            Similarly to finders, formatters generalize format operations. When a finder is used to 
+            select a part of the input, formatter takes this selection and performs some formating
+            on it. Algorithms can abstract from formating using a formatter.
+        </para>
+        <para>
+            <emphasis role="bold">Examples</emphasis>
+        </para>
+        <para> 
+            <itemizedlist>
+                <listitem>
+                    Formatter implemented as a class. This Formatter does not perform any formating and 
+                    returns the match, repackaged. <code>operator()</code>
+                    is templated, so that the Formatter can be used on any Finder type.
+                    
+                    <programlisting>
+struct simple_formatter
+{
+    template&lt;typename FindResultT&gt;
+    std::string operator()( const FindResultT&amp; Match )
+    {
+        std::string Temp( Match.begin(), Match.end() );
+        return Temp;
+    }
+};
+                </programlisting>
+                </listitem>
+                <listitem>
+                    Function Formatter. Similarly to Finder, Formatter can be any function object. 
+                    However, as a function, it can be used only with a specific Finder type. 
+                  
+                    <programlisting>
+std::string simple_formatter( boost::iterator_range&lt;std::string::const_iterator&gt;&amp; Match )
+{
+    std::string Temp( Match.begin(), Match.end() );
+    return Temp;
+}
+                    </programlisting>
+                </listitem>
+            </itemizedlist>
+        </para> 
+     </section>
+</section>

string/doc/credits.xml

@@ -0,0 +1,26 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN"
+"http://www.boost.org/tools/boostbook/dtd/boostbook.dtd">
+
+<!-- Copyright (c) 2002-2006 Pavol Droba.
+     Subject to the Boost Software License, Version 1.0. 
+     (See accompanying file LICENSE-1.0 or  http://www.boost.org/LICENSE-1.0)
+-->
+
+
+<section id="string_algo.credits" last-revision="$Date$">
+    <title>Credits</title>
+    <section id="string_algo.ack">
+        <title>Acknowledgments</title>
+        <para>
+            The author would like to thank everybody who gave suggestions and comments. Especially valuable
+            were the contributions of Thorsten Ottosen, Jeff Garland and the other boost members who participated
+            in the review process, namely David Abrahams, Daniel Frey, Beman Dawes, John Maddock, David B.Held, Pavel Vozenilek
+            and many other.
+        </para>
+        <para>
+            Additional thanks go to Stefan Slapeta and Toon Knapen, who have been very resourceful in solving various
+            portability issues.
+        </para>
+    </section>
+</section>

string/doc/design.xml

@@ -0,0 +1,222 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN"
+"http://www.boost.org/tools/boostbook/dtd/boostbook.dtd">
+
+<!-- Copyright (c) 2002-2006 Pavol Droba.
+     Subject to the Boost Software License, Version 1.0. 
+     (See accompanying file LICENSE-1.0 or  http://www.boost.org/LICENSE-1.0)
+-->
+
+<section id="string_algo.design" last-revision="$Date$">
+    <title>Design Topics</title>
+
+    <using-namespace name="boost"/>
+    <using-namespace name="boost::algorithm"/>
+
+    <section id="string_algo.string">
+        <title>String Representation</title>
+
+        <para>
+            As the name suggest, this library works mainly with strings. However, in the context of this library,
+            a string is not restricted to any particular implementation (like <code>std::basic_string</code>),
+            rather it is a concept. This allows the algorithms in this library to be reused for any string type,
+            that satisfies the given requirements.
+        </para>
+        <para>
+            <emphasis role="bold">Definition:</emphasis> A string is a 
+            <ulink url="../../libs/range/doc/range.html">range</ulink> of characters accessible in sequential
+            ordered fashion. Character is any value type with "cheap" copying and assignment.                
+        </para>
+        <para>
+            First requirement of string-type is that it must accessible using 
+            <ulink url="../../libs/range/index.html">Boost.Range</ulink>. This facility allows to access
+            the elements inside the string in a uniform iterator-based fashion. 
+            This is sufficient for our library
+        </para>
+        <para>            
+            Second requirement defines the way in which the characters are stored in the string. Algorithms in 
+            this library work with an assumption that copying a character is cheaper then allocating extra 
+            storage to cache results. This is a natural assumption for common character types. Algorithms will 
+            work even if this requirement is not satisfied, however at the cost of performance degradation.
+        <para>
+        </para>
+            In addition some algorithms have additional requirements on the string-type. Particularly, it is required
+            that an algorithm can create a new string of the given type. In this case, it is required that
+            the type satisfies the sequence (Std &sect;23.1.1) requirements.
+        </para>
+        <para>
+            In the reference and also in the code, requirement on the string type is designated by the name of
+            template argument. <code>RangeT</code> means that the basic range requirements must hold.
+            <code>SequenceT</code> designates extended sequence requirements.
+        </para>
+    </section>
+    
+    <section id="string_algo.sequence_traits">
+        <title>Sequence Traits</title>
+
+        <para>
+            The major difference between <code>std::list</code> and <code>std::vector</code> is not in the interfaces
+            they provide, but rather in the inner details of the class and the way how it performs 
+            various operations. The problem is that it is not possible to infer this difference from the 
+            definitions of classes without some special mechanism.
+            However, some algorithms can run significantly faster with the knowledge of the properties
+            of a particular container.
+        </para>
+        <para>
+            Sequence traits allow one to specify additional properties of a sequence container (see Std.&sect;32.2).
+            These properties are then used by algorithms to select optimized handling for some operations.
+            The sequence traits are declared in the header 
+            <headername>boost/algorithm/string/sequence_traits.hpp</headername>.
+        </para>
+
+        <para>
+            In the table C denotes a container and c is an object of C.
+        </para>
+        <table>
+            <title>Sequence Traits</title>
+            <tgroup cols="2" align="left">
+                <thead>
+                    <row>   
+                        <entry>Trait</entry>
+                        <entry>Description</entry>
+                    </row>
+                </thead>
+                <tbody>
+                    <row>
+                        <entry><classname>has_native_replace&lt;C&gt;</classname>::value</entry>
+                        <entry>Specifies that the sequence has std::string like replace method</entry>
+                    </row>
+                    <row>
+                        <entry><classname>has_stable_iterators&lt;C&gt;</classname>::value</entry>
+                        <entry>
+                            Specifies that the sequence has stable iterators. It means,
+                            that operations like <code>insert</code>/<code>erase</code>/<code>replace</code> 
+                            do not invalidate iterators.
+                        </entry>
+                    </row>
+                    <row>
+                        <entry><classname>has_const_time_insert&lt;C&gt;</classname>::value</entry>
+                        <entry>
+                            Specifies that the insert method of the sequence has 
+                            constant time complexity.
+                        </entry>
+                    </row>
+                    <row>
+                        <entry><classname>has_const_time_erase&lt;C&gt;</classname>::value</entry>
+                        <entry>
+                            Specifies that the erase method of the sequence has constant time complexity
+                        </entry>
+                    </row>
+                    </tbody>
+            </tgroup>
+        </table>
+        
+        <para>
+            Current implementation contains specializations for std::list&lt;T&gt; and
+            std::basic_string&lt;T&gt; from the standard library and SGI's std::rope&lt;T&gt; and std::slist&lt;T&gt;.
+        </para>
+    </section>
+    <section id="string_algo.find">
+        <title>Find Algorithms</title>
+
+        <para>
+            Find algorithms have similar functionality to <code>std::search()</code> algorithm. They provide a different 
+            interface which is more suitable for common string operations. 
+            Instead of returning just the start of matching subsequence they return a range which is necessary 
+            when the length of the matching subsequence is not known beforehand. 
+            This feature also allows a partitioning of  the input sequence into three 
+            parts: a prefix, a substring and a suffix. 
+        </para>
+        <para>
+            Another difference is an addition of various searching methods besides find_first, including find_regex. 
+        </para>
+        <para>
+            It the library, find algorithms are implemented in terms of 
+            <link linkend="string_algo.finder_concept">Finders</link>. Finders are used also by other facilities 
+            (replace,split).
+            For convenience, there are also function wrappers for these finders to simplify find operations.
+        </para>
+        <para>
+            Currently the library contains only naive implementation of find algorithms with complexity 
+            O(n * m) where n is the size of the input sequence and m is the size of the search sequence. 
+            There are algorithms with complexity O(n), but for smaller sequence a constant overhead is 
+            rather big. For small m &lt;&lt; n (m by magnitude smaller than n) the current implementation 
+            provides acceptable efficiency. 
+            Even the C++ standard defines the required complexity for search algorithm as O(n * m). 
+            It is possible that a future version of library will also contain algorithms with linear 
+            complexity as an option
+        </para>
+    </section>
+    <section id="string_algo.replace">
+        <title>Replace Algorithms</title>
+
+        <para>
+            The implementation of replace algorithms follows the layered structure of the library. The 
+            lower layer implements generic substitution of a range in the input sequence. 
+            This layer takes a <link linkend="string_algo.finder_concept">Finder</link> object and a 
+            <link linkend="string_algo.formatter_concept">Formatter</link> object as an input. These two 
+            functors define what to replace and what to replace it with. The upper layer functions 
+            are just wrapping calls to the lower layer. Finders are shared with the find and split facility. 
+        </para>
+        <para>
+            As usual, the implementation of the lower layer is designed to work with a generic sequence while
+            taking advantage of specific features if possible 
+            (by using <link linkend="string_algo.sequence_traits">Sequence traits</link>)
+        </para>         
+    </section>
+    <section id="string_algo.split">
+        <title>Find Iterators &amp; Split Algorithms</title>
+
+        <para>
+            Find iterators are a logical extension of the <link linkend="string_algo.find">find facility</link>.
+            Instead of searching for one match, the whole input can be iteratively searched for multiple matches.
+            The result of the search is then used to partition the input. It depends on the algorithms which parts 
+            are returned as the result. They can be the matching parts (<classname>find_iterator</classname>) of the parts in
+            between (<classname>split_iterator</classname>). 
+        </para>
+        <para>
+            In addition the split algorithms like <functionname>find_all()</functionname> and <functionname>split()</functionname>
+            can simplify the common operations. They use a find iterator to search the whole input and copy the 
+            matches they found into the supplied container.
+        </para>
+    </section>
+    <section id="string_algo.exception">
+        <title>Exception Safety</title>
+
+        <para>
+            The library requires that all operations on types used as template
+            or function arguments provide the <emphasis>basic exception-safety guarantee</emphasis>. 
+            In turn, all functions and algorithms in this library, except where stated
+            otherwise, will provide the <emphasis>basic exception-safety guarantee</emphasis>.
+            In other words:
+            The library maintains its invariants and does not leak resources in
+            the face of exceptions.  Some library operations give stronger
+            guarantees, which are documented on an individual basis.
+        </para>
+        
+        <para>
+            Some functions can provide the <emphasis>strong exception-safety guarantee</emphasis>.
+            That means that following statements are true:    
+            <itemizedlist>
+                <listitem>
+                    If an exception is thrown, there are no effects other than those
+                    of the function 
+                </listitem>
+                <listitem>
+                    If an exception is thrown other than by the function, there are no effects
+                </listitem>
+            </itemizedlist>
+            This guarantee can be provided under the condition that the operations 
+            on the types used for arguments for these functions either
+            provide the strong exception guarantee or do not alter the global state .
+         </para>
+        <para>
+            In the reference, under the term <emphasis>strong exception-safety guarantee</emphasis>, we mean the
+            guarantee as defined above.            
+        </para>
+        <para>
+            For more information about the exception safety topics, follow this 
+            <ulink url="../../more/generic_exception_safety.html">link</ulink>
+        </para>        
+    </section>
+</section>

string/doc/environment.xml

@@ -0,0 +1,66 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN"
+"http://www.boost.org/tools/boostbook/dtd/boostbook.dtd">
+
+
+<!-- Copyright (c) 2002-2006 Pavol Droba.
+     Subject to the Boost Software License, Version 1.0. 
+     (See accompanying file LICENSE-1.0 or  http://www.boost.org/LICENSE-1.0)
+-->
+
+<section id="string_algo.env" last-revision="$Date$">
+    <title>Environment</title>
+    <section>
+        <title>Build</title>
+        <para>
+            The whole library is provided in headers. Regex variants of some algorithms, 
+            however, are dependent on the <libraryname>Boost.Regex</libraryname> library. All such algorithms are
+            separated in <headername>boost/algorithm/string_regex.hpp</headername>. 
+            If this header is used, the application must be linked with the <libraryname>Boost.Regex</libraryname> 
+            library. 
+        </para>
+    </section>
+
+    <section>
+        <title>Examples</title>
+        <para>
+            Examples showing the basic usage of the library can be found in the libs/algorithm/string/example
+            directory. There is a separate file for the each part of the library. Please follow the boost
+            build guidelines to build examples using the bjam. To successfully build regex examples 
+            the <libraryname>Boost.Regex</libraryname> library is required. 
+        </para>
+    </section>
+
+    <section>
+        <title>Tests</title>
+        <para>
+            A full set of test cases for the library is located in the libs/algorithm/string/test directory. 
+            The test cases can be executed using the boost build system. For the tests of regular 
+            expression variants of algorithms, the <libraryname>Boost.Regex</libraryname> library is required. 
+        </para>
+    </section>
+
+    <section>
+        <title>Portability</title>
+        <para>
+            The library has been successfully compiled and tested with the following compilers:
+            
+            <itemizedlist>
+                <listitem>Microsoft Visual C++ 7.0</listitem>
+                <listitem>Microsoft Visual C++ 7.1</listitem>
+                <listitem>GCC 3.2</listitem>
+                <listitem>GCC 3.3.1</listitem>
+            </itemizedlist>
+
+            See <ulink url="http://boost.sourceforge.net/regression-logs/">Boost regression tables</ulink>
+            for additional info for a particular compiler.
+        </para>
+        <para>
+            There are known limitation on platforms not supporting partial template specialization. 
+            Library depends on correctly implemented <code>std::iterator_traits</code> class. 
+            If a standard library provided with compiler is broken, the String Algorithm Library 
+            cannot function properly. Usually it implies that primitive pointer iterators are not 
+            working with the library functions. 
+        </para>
+    </section>
+</section>

string/doc/intro.xml

@@ -0,0 +1,53 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN"
+"http://www.boost.org/tools/boostbook/dtd/boostbook.dtd">
+
+<!-- Copyright (c) 2002-2006 Pavol Droba.
+     Subject to the Boost Software License, Version 1.0. 
+     (See accompanying file LICENSE-1.0 or  http://www.boost.org/LICENSE-1.0)
+-->
+
+<section id="string_algo.intro" last-revision="$Date$">
+    <title>Introduction</title>
+
+    <para>
+        The String Algorithm Library provides a generic implementation of
+        string-related algorithms which are missing in STL. It is an extension
+        to the algorithms library of STL and it includes trimming, case conversion, 
+        predicates and find/replace functions. All of them come in different variants 
+        so it is easier to choose the best fit for a particular need.
+    </para>
+    <para>
+        The implementation is not restricted to work with a particular container 
+        (like <code>std::basic_string</code>), rather it is as generic as
+        possible. This generalization is not compromising the performance since
+        algorithms are using container specific features when it means a performance
+        gain.
+    </para>
+    <para>
+        <emphasis role="bold">
+            Important note: In this documentation we use term <emphasis>string</emphasis> to 
+            designate a sequence of <emphasis>characters</emphasis> stored in an arbitrary container.
+            A <emphasis>string</emphasis> is not restricted to <code>std::basic_string</code> and 
+            <emphasis>character</emphasis> does not have to be <code>char</code> or <code>wchar_t</code>,
+            although these are most common candidates.
+        </emphasis>
+        Consult the <link linkend="string_algo.design">design chapter</link> to see precise specification of
+        supported string types.
+    </para>
+    <para>      
+        The library interface functions and classes are defined in namespace <code>boost::algorithm</code>, and
+        they are lifted into namespace <code>boost</code> via using declaration.
+    </para>
+    <para>
+        The documentation is divided into several sections. For a quick start read the 
+        <link linkend="string_algo.usage">Usage</link> section followed by 
+        <link linkend="string_algo.quickref">Quick Reference</link>. 
+        <link linkend="string_algo.design">The Design Topics</link>,
+        <link linkend="string_algo.concept">Concepts</link> and <link linkend="string_algo.rationale">Rationale</link>
+        provide some explanation about the library design and structure an explain how it should be used.
+        See the <link linkend="string_algo.reference">Reference</link> for the complete list of provided utilities
+        and algorithms. Functions and classes in the reference are organized by the headers in which they are defined.
+        The reference contains links to the detailed description for every entity in the library.
+    </para>
+</section>

string/doc/quickref.xml

@@ -0,0 +1,744 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN"
+"http://www.boost.org/tools/boostbook/dtd/boostbook.dtd">
+
+<!-- Copyright (c) 2002-2006 Pavol Droba.
+     Subject to the Boost Software License, Version 1.0. 
+     (See accompanying file LICENSE-1.0 or  http://www.boost.org/LICENSE-1.0)
+-->
+
+<section id="string_algo.quickref" last-revision="$Date$">
+    <title>Quick Reference</title>
+
+    <using-namespace name="boost"/>
+    <using-namespace name="boost::algorithm"/>
+
+    <section>   
+        <title>Algorithms</title>
+        
+        <table>
+            <title>Case Conversion</title>
+            <tgroup cols="3" align="left">
+                <thead>
+                    <row>
+                        <entry>Algorithm name</entry>
+                        <entry>Description</entry>
+                        <entry>Functions</entry>
+                    </row>
+                </thead>
+                <tbody>
+                    <row>
+                        <entry><code>to_upper</code></entry>
+                        <entry>Convert a string to upper case</entry>
+                        <entry>
+                            <functionname>to_upper_copy()</functionname>
+                            <sbr/>
+                            <functionname>to_upper()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry><code>to_lower</code></entry>
+                        <entry>Convert a string to lower case</entry>
+                        <entry>
+                            <functionname>to_lower_copy()</functionname>
+                            <sbr/>
+                            <functionname>to_lower()</functionname>
+                        </entry>
+                    </row>
+                </tbody>
+            </tgroup>
+        </table>
+        <table>
+            <title>Trimming</title>
+            <tgroup cols="3" align="left">
+                <thead>
+                    <row>
+                        <entry>Algorithm name</entry>
+                        <entry>Description</entry>
+                        <entry>Functions</entry>
+                    </row>
+                </thead>
+                <tbody>
+                    <row>
+                        <entry><code>trim_left</code></entry>
+                        <entry>Remove leading spaces from a string</entry>
+                        <entry>
+                            <functionname>trim_left_copy_if()</functionname>
+                            <sbr/>
+                            <functionname>trim_left_if()</functionname>
+                            <sbr/>
+                            <functionname>trim_left_copy()</functionname>
+                            <sbr/>
+                            <functionname>trim_left()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry><code>trim_right</code></entry>
+                        <entry>Remove trailing spaces from a string</entry>
+                        <entry>
+                            <functionname>trim_right_copy_if()</functionname>
+                            <sbr/>
+                            <functionname>trim_right_if()</functionname>
+                            <sbr/>
+                            <functionname>trim_right_copy()</functionname>
+                            <sbr/>
+                            <functionname>trim_right()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry><code>trim</code></entry>
+                        <entry>Remove leading and trailing spaces from a string</entry>
+                        <entry>
+                            <functionname>trim_copy_if()</functionname>
+                            <sbr/>
+                            <functionname>trim_if()</functionname>
+                            <sbr/>
+                            <functionname>trim_copy()</functionname>
+                            <sbr/>
+                            <functionname>trim()</functionname>
+                        </entry>
+                    </row>
+ 
+                </tbody>
+            </tgroup>
+        </table>
+        <table>
+            <title>Predicates</title>
+            <tgroup cols="3" align="left">
+                <thead>
+                    <row>
+                        <entry>Algorithm name</entry>
+                        <entry>Description</entry>
+                        <entry>Functions</entry>
+                    </row>
+                </thead>
+                <tbody>
+                    <row>
+                        <entry><code>starts_with</code></entry>
+                        <entry>Check if a string is a prefix of the other one</entry>
+                        <entry>
+                            <functionname>starts_with()</functionname>
+                            <sbr/>
+                            <functionname>istarts_with()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry><code>ends_with</code></entry>
+                        <entry>Check if a string is a suffix of the other one</entry>
+                        <entry>
+                            <functionname>ends_with()</functionname>
+                            <sbr/>
+                            <functionname>iends_with()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry><code>contains</code></entry>
+                        <entry>Check if a string is contained of the other one</entry>
+                        <entry>
+                            <functionname>contains()</functionname>
+                            <sbr/>
+                            <functionname>icontains()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry><code>equals</code></entry>
+                        <entry>Check if two strings are equal</entry>
+                        <entry>
+                            <functionname>equals()</functionname>
+                            <sbr/>
+                            <functionname>iequals()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry><code>lexicographical_compare</code></entry>
+                        <entry>Check if a string is lexicographically less then another one</entry>
+                        <entry>
+                            <functionname>lexicographical_compare()</functionname>
+                            <sbr/>
+                            <functionname>ilexicographical_compare()</functionname>
+                        </entry>
+                    </row>
+
+                    <row>
+                        <entry><code>all</code></entry>
+                        <entry>Check if all elements of a string satisfy the given predicate</entry>
+                        <entry>
+                            <functionname>all()</functionname>
+                        </entry>
+                    </row>
+                </tbody>
+            </tgroup>
+        </table>
+        <table>
+            <title>Find algorithms</title>
+            <tgroup cols="3" align="left">
+                <thead>
+                    <row>
+                        <entry>Algorithm name</entry>
+                        <entry>Description</entry>
+                        <entry>Functions</entry>
+                    </row>
+                </thead>
+                <tbody>
+                    <row>
+                        <entry>find_first</entry>
+                        <entry>Find the first occurrence of a string in the input</entry>
+                        <entry>
+                            <functionname>find_first()</functionname>
+                            <sbr/>
+                            <functionname>ifind_first()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>find_last</entry>
+                        <entry>Find the last occurrence of a string in the input</entry>
+                        <entry>
+                            <functionname>find_last()</functionname>
+                            <sbr/>
+                            <functionname>ifind_last()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>find_nth</entry>
+                        <entry>Find the nth (zero-indexed) occurrence of a string in the input</entry>
+                        <entry>
+                            <functionname>find_nth()</functionname>
+                            <sbr/>
+                            <functionname>ifind_nth()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>find_head</entry>
+                        <entry>Retrieve the head of a string</entry>
+                        <entry>
+                            <functionname>find_head()</functionname>
+                        </entry>
+                    </row>                  
+                    <row>
+                        <entry>find_tail</entry>
+                        <entry>Retrieve the tail of a string</entry>
+                        <entry>
+                            <functionname>find_tail()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>find_token</entry>
+                        <entry>Find first matching token in the string</entry>
+                        <entry>
+                            <functionname>find_token()</functionname>
+                        </entry>
+                    </row>                      
+                    <row>
+                        <entry>find_regex</entry>
+                        <entry>Use the regular expression to search the string</entry>
+                        <entry>
+                            <functionname>find_regex()</functionname>
+                        </entry>
+                    </row>                      
+                    <row>
+                        <entry>find</entry>
+                        <entry>Generic find algorithm</entry>
+                        <entry>
+                            <functionname>find()</functionname>
+                        </entry>
+                    </row>                      
+                </tbody>
+            </tgroup>
+        </table>
+        <table>
+            <title>Erase/Replace</title>
+            <tgroup cols="3" align="left">
+                <thead>
+                    <row>
+                        <entry>Algorithm name</entry>
+                        <entry>Description</entry>
+                        <entry>Functions</entry>
+                    </row>
+                </thead>
+                <tbody>
+                    <row>
+                        <entry>replace/erase_first</entry>
+                        <entry>Replace/Erase the first occurrence of a string in the input</entry>
+                        <entry>
+                            <functionname>replace_first()</functionname>
+                            <sbr/>
+                            <functionname>replace_first_copy()</functionname>
+                            <sbr/>
+                            <functionname>ireplace_first()</functionname>
+                            <sbr/>
+                            <functionname>ireplace_first_copy()</functionname>
+                            <sbr/>                      
+                            <functionname>erase_first()</functionname>
+                            <sbr/>
+                            <functionname>erase_first_copy()</functionname>
+                            <sbr/>
+                            <functionname>ierase_first()</functionname>
+                            <sbr/>
+                            <functionname>ierase_first_copy()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>replace/erase_last</entry>
+                        <entry>Replace/Erase the last occurrence of a string in the input</entry>
+                        <entry>
+                            <functionname>replace_last()</functionname>
+                            <sbr/>
+                            <functionname>replace_last_copy()</functionname>
+                            <sbr/>
+                            <functionname>ireplace_last()</functionname>
+                            <sbr/>
+                            <functionname>ireplace_last_copy()</functionname>
+                            <sbr/>                      
+                            <functionname>erase_last()</functionname>
+                            <sbr/>
+                            <functionname>erase_last_copy()</functionname>
+                            <sbr/>
+                            <functionname>ierase_last()</functionname>
+                            <sbr/>
+                            <functionname>ierase_last_copy()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>replace/erase_nth</entry>
+                        <entry>Replace/Erase the nth (zero-indexed) occurrence of a string in the input</entry>
+                        <entry>
+                            <functionname>replace_nth()</functionname>
+                            <sbr/>
+                            <functionname>replace_nth_copy()</functionname>
+                            <sbr/>
+                            <functionname>ireplace_nth()</functionname>
+                            <sbr/>
+                            <functionname>ireplace_nth_copy()</functionname>
+                            <sbr/>                      
+                            <functionname>erase_nth()</functionname>
+                            <sbr/>
+                            <functionname>erase_nth_copy()</functionname>
+                            <sbr/>
+                            <functionname>ierase_nth()</functionname>
+                            <sbr/>
+                            <functionname>ierase_nth_copy()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>replace/erase_all</entry>
+                        <entry>Replace/Erase the all occurrences of a string in the input</entry>
+                        <entry>
+                            <functionname>replace_all()</functionname>
+                            <sbr/>
+                            <functionname>replace_all_copy()</functionname>
+                            <sbr/>
+                            <functionname>ireplace_all()</functionname>
+                            <sbr/>
+                            <functionname>ireplace_all_copy()</functionname>
+                            <sbr/>                      
+                            <functionname>erase_all()</functionname>
+                            <sbr/>
+                            <functionname>erase_all_copy()</functionname>
+                            <sbr/>
+                            <functionname>ierase_all()</functionname>
+                            <sbr/>
+                            <functionname>ierase_all_copy()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>replace/erase_head</entry>
+                        <entry>Replace/Erase the head of the input</entry>
+                        <entry>
+                            <functionname>replace_head()</functionname>
+                            <sbr/>
+                            <functionname>replace_head_copy()</functionname>
+                            <sbr/>
+                            <functionname>erase_head()</functionname>
+                            <sbr/>
+                            <functionname>erase_head_copy()</functionname>
+                            <sbr/>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>replace/erase_tail</entry>
+                        <entry>Replace/Erase the tail of the input</entry>
+                        <entry>
+                            <functionname>replace_tail()</functionname>
+                            <sbr/>
+                            <functionname>replace_tail_copy()</functionname>
+                            <sbr/>
+                            <functionname>erase_tail()</functionname>
+                            <sbr/>
+                            <functionname>erase_tail_copy()</functionname>
+                            <sbr/>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>replace/erase_regex</entry>
+                        <entry>Replace/Erase a substring matching the given regular expression</entry>
+                        <entry>
+                            <functionname>replace_regex()</functionname>
+                            <sbr/>
+                            <functionname>replace_regex_copy()</functionname>
+                            <sbr/>
+                            <functionname>erase_regex()</functionname>
+                            <sbr/>
+                            <functionname>erase_regex_copy()</functionname>
+                            <sbr/>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>replace/erase_regex_all</entry>
+                        <entry>Replace/Erase all substrings matching the given regular expression</entry>
+                        <entry>
+                            <functionname>replace_all_regex()</functionname>
+                            <sbr/>
+                            <functionname>replace_all_regex_copy()</functionname>
+                            <sbr/>
+                            <functionname>erase_all_regex()</functionname>
+                            <sbr/>
+                            <functionname>erase_all_regex_copy()</functionname>
+                            <sbr/>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>find_format</entry>
+                        <entry>Generic replace algorithm</entry>
+                        <entry>
+                            <functionname>find_format()</functionname>
+                            <sbr/>
+                            <functionname>find_format_copy()</functionname>
+                            <sbr/>
+                            <functionname>find_format_all()</functionname>
+                            <sbr/>
+                            <functionname>find_format_all_copy()()</functionname>
+                        </entry>
+                    </row>
+                </tbody>
+            </tgroup>
+        </table>
+        <table>
+            <title>Split</title>
+            <tgroup cols="3" align="left">
+                <thead>
+                    <row>
+                        <entry>Algorithm name</entry>
+                        <entry>Description</entry>
+                        <entry>Functions</entry>
+                    </row>
+                </thead>
+                <tbody>
+                    <row>
+                        <entry>find_all</entry>
+                        <entry>Find/Extract all matching substrings in the input</entry>
+                        <entry>
+                            <functionname>find_all()</functionname>
+                            <sbr/>
+                            <functionname>ifind_all()</functionname>
+                            <sbr/>
+                            <functionname>find_all_regex()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>split</entry>
+                        <entry>Split input into parts</entry>
+                        <entry>
+                            <functionname>split()</functionname>
+                            <sbr/>
+                            <functionname>split_regex()</functionname>
+                        </entry>
+					</row>
+					<row>
+						<entry>iter_find</entry>
+						<entry>Iteratively apply the finder to the input to find all matching substrings</entry>
+						<entry>
+							<functionname>iter_find()</functionname>
+						</entry>
+					</row>
+					<row>
+						<entry>iter_split</entry>
+						<entry>Use the finder to find matching substrings in the input and use them as separators to split the input into parts</entry>
+						<entry>
+							<functionname>iter_split()</functionname>
+						</entry>
+					</row>
+                </tbody>
+            </tgroup>
+        </table>
+        <table>
+            <title>Join</title>
+            <tgroup cols="3" align="left">
+                <thead>
+                    <row>
+                        <entry>Algorithm name</entry>
+                        <entry>Description</entry>
+                        <entry>Functions</entry>
+                    </row>
+                </thead>
+                <tbody>
+                    <row>
+                        <entry>join</entry>
+                        <entry>Join all elements in a container into a single string</entry>
+                        <entry>
+                            <functionname>join</functionname>
+                        </entry>
+                    </row>
+                        <row>
+                        <entry>join_if</entry>
+                        <entry>Join all elements in a container that satisfies the condition into a single string</entry>
+                        <entry>
+                            <functionname>join_if()</functionname>
+                        </entry>
+                   </row>
+                </tbody>
+            </tgroup>
+        </table>
+    </section>
+    <section>
+        <title>Finders and Formatters</title>
+        
+        <table>
+            <title>Finders</title>
+            <tgroup cols="3" align="left">
+                <thead>
+                    <row>
+                        <entry>Finder</entry>
+                        <entry>Description</entry>
+                        <entry>Generators</entry>
+                    </row>
+                </thead>
+                <tbody>
+                    <row>
+                        <entry>first_finder</entry>
+                        <entry>Search for the first match of the string in an input</entry>
+                        <entry>
+                            <functionname>first_finder()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>last_finder</entry>
+                        <entry>Search for the last match of the string in an input</entry>
+                        <entry>
+                            <functionname>last_finder()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>nth_finder</entry>
+                        <entry>Search for the nth (zero-indexed) match of the string in an input</entry>
+                        <entry>
+                            <functionname>nth_finder()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>head_finder</entry>
+                        <entry>Retrieve the head of an input</entry>
+                        <entry>
+                            <functionname>head_finder()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>tail_finder</entry>
+                        <entry>Retrieve the tail of an input</entry>
+                        <entry>
+                            <functionname>tail_finder()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>token_finder</entry>
+                        <entry>Search for a matching token in an input</entry>
+                        <entry>
+                            <functionname>token_finder()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>range_finder</entry>
+                        <entry>Do no search, always returns the given range</entry>
+                        <entry>
+                            <functionname>range_finder()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>regex_finder</entry>
+                        <entry>Search for a substring matching the given regex</entry>
+                        <entry>
+                            <functionname>regex_finder()</functionname>
+                        </entry>
+                    </row>
+                </tbody>
+            </tgroup>
+        </table>
+
+        <table>
+            <title>Formatters</title>
+            <tgroup cols="3" align="left">
+                <thead>
+                    <row>
+                        <entry>Formatter</entry>
+                        <entry>Description</entry>
+                        <entry>Generators</entry>
+                    </row>
+                </thead>
+                <tbody>
+                    <row>
+                        <entry>const_formatter</entry>
+                        <entry>Constant formatter. Always return the specified string</entry>
+                        <entry>
+                            <functionname>const_formatter()</functionname>
+                        </entry>                                                
+                    </row>
+                    <row>
+                        <entry>identity_formatter</entry>
+                        <entry>Identity formatter. Return unmodified input input</entry>
+                        <entry>
+                            <functionname>identity_formatter()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>empty_formatter</entry>
+                        <entry>Null formatter. Always return an empty string</entry>
+                        <entry>
+                            <functionname>empty_formatter()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>regex_formatter</entry>
+                        <entry>Regex formatter. Format regex match using the specification in the format string</entry>
+                        <entry>
+                            <functionname>regex_formatter()</functionname>
+                        </entry>
+                    </row>
+                </tbody>
+            </tgroup>
+        </table>
+    </section>
+    <section>
+        <title>Iterators</title>
+        
+        <table>
+            <title>Find Iterators</title>
+            <tgroup cols="3" align="left">
+                <thead>
+                    <row>
+                        <entry>Iterator name</entry>
+                        <entry>Description</entry>
+                        <entry>Iterator class</entry>
+                    </row>
+                </thead>
+                <tbody>
+                    <row>
+                        <entry>find_iterator</entry>
+                        <entry>Iterates through matching substrings in the input</entry>
+                        <entry>
+                            <classname>find_iterator</classname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>split_iterator</entry>
+                        <entry>Iterates through gaps between matching substrings in the input</entry>
+                        <entry>
+                            <classname>split_iterator</classname>
+                        </entry>
+                    </row>              
+                </tbody>
+            </tgroup>
+        </table>
+    </section>
+    
+    <section>
+        <title>Classification</title>
+        
+        <table>
+            <title>Predicates</title>
+            <tgroup cols="3" align="left">
+                <thead>
+                    <row>
+                        <entry>Predicate name</entry>
+                        <entry>Description</entry>
+                        <entry>Generator</entry>
+                    </row>
+                </thead>
+                <tbody>
+                    <row>
+                        <entry>is_classified</entry>
+                        <entry>Generic <code>ctype</code> mask based classification</entry>
+                        <entry>
+                            <functionname>is_classified()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>is_space</entry>
+                        <entry>Recognize spaces</entry>
+                        <entry>
+                            <functionname>is_space()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>is_alnum</entry>
+                        <entry>Recognize alphanumeric characters</entry>
+                        <entry>
+                            <functionname>is_alnum()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>is_alpha</entry>
+                        <entry>Recognize letters</entry>
+                        <entry>
+                            <functionname>is_alpha()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>is_cntrl</entry>
+                        <entry>Recognize control characters</entry>
+                        <entry>
+                            <functionname>is_cntrl()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>is_digit</entry>
+                        <entry>Recognize decimal digits</entry>
+                        <entry>
+                            <functionname>is_digit()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>is_graph</entry>
+                        <entry>Recognize graphical characters</entry>
+                        <entry>
+                            <functionname>is_graph()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>is_lower</entry>
+                        <entry>Recognize lower case characters</entry>
+                        <entry>
+                            <functionname>is_lower()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>is_print</entry>
+                        <entry>Recognize printable characters</entry>
+                        <entry>
+                            <functionname>is_print()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>is_punct</entry>
+                        <entry>Recognize punctuation characters</entry>
+                        <entry>
+                            <functionname>is_punct()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>is_upper</entry>
+                        <entry>Recognize uppercase characters</entry>
+                        <entry>
+                            <functionname>is_upper()</functionname>
+                        </entry>
+                    </row>
+                    <row>
+                        <entry>is_xdigit</entry>
+                        <entry>Recognize hexadecimal digits</entry>
+                        <entry>
+                            <functionname>is_xdigit()</functionname>
+                        </entry>
+                    </row>
+                </tbody>
+            </tgroup>
+        </table>
+    </section>
+</section>

string/doc/rationale.xml

@@ -0,0 +1,53 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN"
+"http://www.boost.org/tools/boostbook/dtd/boostbook.dtd">
+
+<!-- Copyright (c) 2002-2006 Pavol Droba.
+     Subject to the Boost Software License, Version 1.0. 
+     (See accompanying file LICENSE-1.0 or  http://www.boost.org/LICENSE-1.0)
+-->
+
+
+<section id="string_algo.rationale" last-revision="$Date$">
+    <title>Rationale</title>
+
+    <using-namespace name="boost"/>
+    <using-namespace name="boost::algorithm"/>
+    
+   <section it="string_algo.locale">
+        <title>Locales</title>
+
+        <para>
+            Locales have a very close relation to string processing. They contain information about
+            the character sets and are used, for example, to change the case of characters and 
+            to classify the characters. 
+        </para>
+        <para>
+            C++ allows to work with multiple different instances of locales at once. If an algorithm
+            manipulates some data in a way that requires the usage of locales, there must be a way
+            to specify them. However, one instance of locales is sufficient for most of the applications,
+            and for a user it could be very tedious to specify which locales to use at every place 
+            where it is needed. 
+        </para> 
+        <para>
+            Fortunately, the C++ standard allows to specify the <emphasis>global</emphasis> locales (using static member
+            function <code>std:locale::global()</code>). When instantiating an
+            <code>std::locale</code> class without explicit information, the instance will 
+            be initialized with the <emphasis>global</emphasis> locale. This implies, that if an algorithm needs a locale,
+            it should have an <code>std::locale</code> parameter defaulting to  <code>std::locale()</code>.
+            If a user needs to specify locales explicitly, she can do so. Otherwise the <emphasis>global</emphasis>
+            locales are used.
+        </para>
+    </section>
+    <section id="string_algo.regex">
+        <title>Regular Expressions</title>
+
+        <para>
+            Regular expressions are an essential part of text processing. For this reason, the library 
+            also provides regex variants of some algorithms. The library does not attempt to replace
+            <libraryname>Boost.Regex</libraryname>; it merely wraps its functionality in a new interface.
+            As a part of this library, regex algorithms integrate smoothly with other components, which 
+            brings additional value.
+        </para>
+    </section>
+</section>

string/doc/release_notes.xml

@@ -0,0 +1,45 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN"
+"http://www.boost.org/tools/boostbook/dtd/boostbook.dtd">
+
+<!-- Copyright (c) 2002-2006 Pavol Droba.
+     Subject to the Boost Software License, Version 1.0. 
+     (See accompanying file LICENSE-1.0 or  http://www.boost.org/LICENSE-1.0)
+-->
+
+<section id="string_algo.release_notes" last-revision="$Date$">
+
+    <using-namespace name="boost"/>
+    <using-namespace name="boost::algorithm"/>
+
+    <title>Release Notes</title>
+
+    <itemizedlist>
+        <listitem>
+            <para><emphasis role="bold">1.32</emphasis></para>
+            <para>Initial release in Boost</para>
+        </listitem>
+        <listitem>
+            <para><emphasis role="bold">1.33</emphasis></para>
+            <para>Internal version of collection traits removed, library adapted to Boost.Range</para>
+        </listitem>
+        <listitem>
+            <para><emphasis role="bold">1.34</emphasis></para>
+            <itemizedlist>
+                <listitem>
+                    <functionname>lexicographical_compare()</functionname>
+                </listitem>
+                <listitem>
+                    <functionname>join()</functionname> and <functionname>join_if()</functionname> 
+                </listitem>
+                <listitem>
+                    New comparison predicates <code>is_less</code>, <code>is_not_greater</code>
+                </listitem>
+                <listitem>
+                     Negative indexes support (like Perl) in various algorihtms
+                     (<code>*_head/tail</code>, <code>*_nth</code>).
+                </listitem>                                      
+            </itemizedlist>
+        </listitem>
+    </itemizedlist>
+</section>

string/doc/string_algo.xml

@@ -0,0 +1,52 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN"
+"http://www.boost.org/tools/boostbook/dtd/boostbook.dtd">
+
+<!-- Copyright (c) 2002-2006 Pavol Droba.
+     Subject to the Boost Software License, Version 1.0. 
+     (See accompanying file LICENSE-1.0 or  http://www.boost.org/LICENSE-1.0)
+-->
+
+<library name="String Algorithms" dirname="algorithm/string" xmlns:xi="http://www.w3.org/2001/XInclude" 
+    id="string_algo" last-revision="$Date$">
+    <libraryinfo>
+        <author>
+            <firstname>Pavol</firstname>
+            <surname>Droba</surname>
+        </author>
+
+        <copyright>
+            <year>2002</year>
+            <year>2003</year>
+            <year>2004</year>
+            <holder>Pavol Droba</holder>
+        </copyright>
+
+        <legalnotice>
+            <para>Use, modification and distribution is subject to the Boost
+                Software License, Version 1.0. (See accompanying file
+                <filename>LICENSE_1_0.txt</filename> or copy at <ulink
+                    url="http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</ulink>)
+            </para>
+        </legalnotice>
+
+        <librarypurpose>
+            A set of generic string-related algorithms and utilities
+        </librarypurpose> 
+        <librarycategory name="category:algoritms"/>
+        <librarycategory name="category:string-text"/>
+    </libraryinfo>
+
+    <title>Boost String Algorithms Library</title>  
+    <xi:include href="intro.xml"/>
+    <xi:include href="release_notes.xml"/>
+    <xi:include href="usage.xml"/>
+    <xi:include href="quickref.xml"/>
+    <xi:include href="design.xml"/>
+    <xi:include href="concept.xml"/>
+    <xi:include href="autodoc.boostbook"/>
+    <xi:include href="rationale.xml"/>
+    <xi:include href="environment.xml"/>
+    <xi:include href="credits.xml"/>
+</library>
+

string/doc/usage.xml

@@ -0,0 +1,359 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN"
+"http://www.boost.org/tools/boostbook/dtd/boostbook.dtd">
+
+<!-- Copyright (c) 2002-2006 Pavol Droba.
+     Subject to the Boost Software License, Version 1.0. 
+     (See accompanying file LICENSE-1.0 or  http://www.boost.org/LICENSE-1.0)
+-->
+
+<section id="string_algo.usage" last-revision="$Date$">
+    <title>Usage</title>
+
+    <using-namespace name="boost"/>
+    <using-namespace name="boost::algorithm"/>
+
+
+    <section>
+        <title>First Example</title>
+        
+        <para>
+            Using the algorithms is straightforward. Let us have a look at the first example:
+        </para>
+        <programlisting>
+    #include &lt;boost/algorithm/string.hpp&gt;
+    using namespace std;
+    using namespace boost;
+    
+    // ...
+
+    string str1(" hello world! ");
+    to_upper(str1);  // str1 == " HELLO WORLD! "
+    trim(str1);      // str1 == "HELLO WORLD!"
+
+    string str2=
+       to_lower_copy(
+          ireplace_first_copy(
+             str1,"hello","goodbye")); // str2 == "goodbye world!"
+        </programlisting>
+        <para>
+            This example converts str1 to upper case and trims spaces from the start and the end
+            of the string. str2 is then created as a copy of str1 with "hello" replaced with "goodbye".
+            This example demonstrates several important concepts used in the library:
+        </para>
+        <itemizedlist>
+            <listitem>
+                <para><emphasis role="bold">Container parameters:</emphasis>
+                    Unlike in the STL algorithms, parameters are not specified only in the form
+                    of iterators. The STL convention allows for great flexibility,
+                    but it has several limitations. It is not possible to <emphasis>stack</emphasis> algorithms together, 
+                    because a container is passed in two parameters. Therefore it is not possible to use 
+                    a return value from another algorithm. It is considerably easier to write
+                    <code>to_lower(str1)</code>, than <code>to_lower(str1.begin(), str1.end())</code>.
+                </para>
+                <para>
+                    The magic of <ulink url="../../libs/range/index.html">Boost.Range</ulink> 
+                    provides a uniform way of handling different string types. 
+                    If there is a need to pass a pair of iterators, 
+                    <ulink url="../../libs/range/doc/utility_class.html"><code>boost::iterator_range</code></ulink>
+                    can be used to package iterators into a structure with a compatible interface.
+                </para>
+            </listitem>
+            <listitem>
+                <para><emphasis role="bold">Copy vs. Mutable:</emphasis>
+                    Many algorithms in the library are performing a transformation of the input. 
+                    The transformation can be done in-place, mutating the input sequence, or a copy 
+                    of the transformed input can be created, leaving the input intact. None of 
+                    these possibilities is superior to the other one and both have different 
+                    advantages and disadvantages. For this reason, both are provided with the library. 
+                </para>
+            </listitem>
+            <listitem>
+                <para><emphasis role="bold">Algorithm stacking:</emphasis>
+                    Copy versions return a transformed input as a result, thus allow a simple chaining of
+                    transformations within one expression (i.e. one can write <code>trim_copy(to_upper_copy(s))</code>). 
+                    Mutable versions have <code>void</code> return, to avoid misuse.
+                </para>
+            </listitem>
+            <listitem>
+                <para><emphasis role="bold">Naming:</emphasis>
+                    Naming follows the conventions from the Standard C++ Library. If there is a 
+                    copy and a mutable version of the same algorithm, the mutable version has no suffix 
+                    and the copy version has the suffix <emphasis>_copy</emphasis>. 
+                    Some algorithms have the prefix <emphasis>i</emphasis> 
+                    (e.g. <functionname>ifind_first()</functionname>).
+                    This prefix identifies that the algorithm works in a case-insensitive manner.
+                </para>
+            </listitem>
+        </itemizedlist>
+        <para>
+            To use the library, include the <headername>boost/algorithm/string.hpp</headername> header. 
+            If the regex related functions are needed, include the 
+            <headername>boost/algorithm/string_regex.hpp</headername> header.
+        </para>
+    </section>
+    <section>
+        <title>Case conversion</title>
+        
+        <para>
+            STL has a nice way of converting character case. Unfortunately, it works only
+            for a single character and we want to convert a string, 
+        </para>
+        <programlisting>
+    string str1("HeLlO WoRld!");
+    to_upper(str1); // str1=="HELLO WORLD!"
+        </programlisting>
+        <para>
+            <functionname>to_upper()</functionname> and <functionname>to_lower()</functionname> convert the case of 
+            characters in a string using a specified locale.
+        </para>
+        <para>
+            For more information see the reference for <headername>boost/algorithm/string/case_conv.hpp</headername>.
+        </para>
+    </section>
+    <section>
+        <title>Predicates and Classification</title>
+        <para>
+            A part of the library deals with string related predicates. Consider this example:
+        </para>
+        <programlisting>
+    bool is_executable( string&amp; filename )
+    {
+        return 
+            iends_with(filename, ".exe") ||
+            iends_with(filename, ".com");
+    }
+
+    // ...
+    string str1("command.com");
+    cout 
+        &lt;&lt; str1
+        &lt;&lt; is_executable("command.com")? "is": "is not" 
+        &lt;&lt; "an executable" 
+        &lt;&lt; endl; // prints "command.com is an executable"
+    
+    //..
+    char text1[]="hello world!";
+    cout 
+        &lt;&lt; text1 
+        &lt;&lt; all( text1, is_lower() )? "is": "is not"
+        &lt;&lt; " written in the lower case" 
+        &lt;&lt; endl; // prints "hello world! is written in the lower case"
+        </programlisting>
+        <para>
+            The predicates determine whether if a substring is contained in the input string
+            under various conditions. The conditions are: a string starts with the substring, 
+            ends with the substring, 
+            simply contains the substring or if both strings are equal. See the reference for 
+            <headername>boost/algorithm/string/predicate.hpp</headername> for more details. 
+        </para>
+        <para>  
+            In addition the algorithm <functionname>all()</functionname> checks
+            all elements of a container to satisfy a condition specified by a predicate. 
+            This predicate can be any unary predicate, but the library provides a bunch of 
+            useful string-related predicates and combinators ready for use.
+            These are located in the <headername>boost/algorithm/string/classification.hpp</headername> header.
+            Classification predicates can be combined using logical combinators to form
+            a more complex expressions. For example: <code>is_from_range('a','z') || is_digit()</code>
+        </para>
+    </section>
+    <section>
+        <title>Trimming</title>
+        
+        <para>
+            When parsing the input from a user, strings usually have unwanted leading or trailing 
+            characters. To get rid of them, we need trim functions:
+        </para>
+        <programlisting>
+    string str1="     hello world!     ";
+    string str2=trim_left_copy(str1);   // str2 == "hello world!     "
+    string str3=trim_right_copy(str2);  // str3 == "     hello world!"
+    trim(str1);                         // str1 == "hello world!"
+
+    string phone="00423333444";
+    // remove leading 0 from the phone number
+    trim_left_if(phone,is_any_of("0")); // phone == "423333444"
+        </programlisting>
+        <para>
+            It is possible to trim the spaces on the right, on the left or on both sides of a string.
+            And for those cases when there is a need to remove something else than blank space, there
+            are <emphasis>_if</emphasis> variants. Using these, a user can specify a functor which will 
+            select the <emphasis>space</emphasis> to be removed. It is possible to use classification 
+            predicates like <functionname>is_digit()</functionname> mentioned in the previous paragraph.
+            See the reference for the <headername>boost/algorithm/string/trim.hpp</headername>.
+        </para>
+    </section>
+    <section>
+        <title>Find algorithms</title>
+        
+        <para>
+            The library contains a set of find algorithms. Here is an example:
+        </para>
+        <programlisting>
+    char text[]="hello dolly!";
+    iterator_range&lt;char*&gt; result=find_last(text,"ll");
+
+    transform( result.begin(), result.end(), result.begin(), bind2nd(plus&lt;char&gt;(), 1) );
+    // text = "hello dommy!"            
+
+    to_upper(result); // text == "hello doMMy!"
+
+    // iterator_range is convertible to bool
+    if(find_first(text, "dolly"))
+    {
+        cout &lt;&lt; "Dolly is there" &lt;&lt; endl;
+    }
+        </programlisting>
+        <para>
+            We have used <functionname>find_last()</functionname> to search the <code>text</code> for "ll".
+            The result is given in the <ulink url="../../libs/range/doc/utility_class.html"><code>boost::iterator_range</code></ulink>. 
+            This range delimits the
+            part of the input which satisfies the find criteria. In our example it is the last occurrence of "ll".
+            
+            As we can see, input of the <functionname>find_last()</functionname> algorithm can be also 
+            char[] because this type is supported by 
+            <ulink url="../../libs/range/index.html">Boost.Range</ulink>.
+
+            The following lines transform the result. Notice that 
+            <ulink url="../../libs/range/doc/utility_class.html"><code>boost::iterator_range</code></ulink> has familiar 
+            <code>begin()</code> and <code>end()</code> methods, so it can be used like any other STL container.
+            Also it is convertible to bool therefore it is easy to use find algorithms for a simple containment checking.
+        </para>
+        <para>
+            Find algorithms are located in <headername>boost/algorithm/string/find.hpp</headername>.
+        </para>
+    </section>
+    <section>
+        <title>Replace Algorithms</title>
+        <para>
+            Find algorithms can be used for searching for a specific part of string. Replace goes one step
+            further. After a matching part is found, it is substituted with something else. The substitution is computed
+            from the original, using some transformation. 
+        </para>
+        <programlisting>
+    string str1="Hello  Dolly,   Hello World!"
+    replace_first(str1, "Dolly", "Jane");      // str1 == "Hello  Jane,   Hello World!"
+    replace_last(str1, "Hello", "Goodbye");    // str1 == "Hello  Jane,   Goodbye World!"
+    erase_all(str1, " ");                      // str1 == "HelloJane,GoodbyeWorld!"
+    erase_head(str1, 6);                       // str1 == "Jane,GoodbyeWorld!"
+        </programlisting>
+        <para>
+            For the complete list of replace and erase functions see the 
+            <link linkend="string_algo.reference">reference</link>.
+            There is a lot of predefined function for common usage, however, the library allows you to 
+            define a custom <code>replace()</code> that suits a specific need. There is a generic <functionname>find_format()</functionname> 
+            function which takes two parameters.
+            The first one is a <link linkend="string_algo.finder_concept">Finder</link> object, the second one is 
+            a <link linkend="string_algo.formatter_concept">Formatter</link> object. 
+            The Finder object is a functor which performs the searching for the replacement part. The Formatter object
+            takes the result of the Finder (usually a reference to the found substring) and creates a 
+            substitute for it. Replace algorithm puts these two together and makes the desired substitution. 
+        </para>
+        <para>
+            Check <headername>boost/algorithm/string/replace.hpp</headername>, <headername>boost/algorithm/string/erase.hpp</headername> and
+            <headername>boost/algorithm/string/find_format.hpp</headername> for reference.
+        </para>
+    </section>
+    <section>
+        <title>Find Iterator</title>
+
+        <para>
+            An extension to find algorithms it the Find Iterator. Instead of searching for just a one part of a string, 
+            the find iterator allows us to iterate over the substrings matching the specified criteria.
+            This facility is using the <link linkend="string_algo.finder_concept">Finder</link> to incrementally
+            search the string. 
+            Dereferencing a find iterator yields an <ulink url="../../libs/range/doc/utility_class.html"><code>boost::iterator_range</code></ulink> 
+            object, that delimits the current match.
+        </para>
+        <para>
+            There are two iterators provided <classname>find_iterator</classname> and 
+            <classname>split_iterator</classname>. The former iterates over substrings that are found using the specified
+            Finder. The latter iterates over the gaps between these substrings.
+        </para>
+        <programlisting>
+    string str1("abc-*-ABC-*-aBc");
+    // Find all 'abc' substrings (ignoring the case)
+    // Create a find_iterator
+    typedef find_iterator&lt;string::iterator&gt; string_find_iterator;
+    for(string_find_iterator It=
+            make_find_iterator(str1, first_finder("abc", is_iequal()));
+        It!=string_find_iterator();
+        ++It)
+    {
+        cout &lt;&lt; copy_range&lt;std::string&gt;(*It) &lt;&lt; endl;
+    }
+
+    // Output will be:
+    // abc
+    // ABC
+    // aBC
+    
+    typedef split_iterator&lt;string::iterator&gt; string_split_iterator;
+    for(string_split_iterator It=
+        make_split_iterator(str1, first_finder("-*-", is_iequal()));
+        It!=string_split_iterator();
+        ++It)
+    {
+        cout &lt;&lt; copy_range&lt;std::string&gt;(*It) &lt;&lt; endl;
+    }
+
+    // Output will be:
+    // abc
+    // ABC
+    // aBC
+        </programlisting>
+        <para>
+            Note that the find iterators have only one template parameter. It is the base iterator type.
+            The Finder is specified at runtime. This allows us to typedef a find iterator for
+            common string types and reuse it. Additionally make_*_iterator functions help
+            to construct a find iterator for a particular range.
+        </para>
+        <para>
+            See the reference in <headername>boost/algorithm/string/find_iterator.hpp</headername>.
+        </para>
+    </section>
+    <section>
+        <title>Split</title>
+
+        <para>
+            Split algorithms are an extension to the find iterator for one common usage scenario.
+            These algorithms use a find iterator and store all matches into the provided
+            container. This container must be able to hold copies (e.g. <code>std::string</code>) or 
+            references (e.g. <code>iterator_range</code>) of the extracted substrings.
+        </para>
+        <para>
+            Two algorithms are provided. <functionname>find_all()</functionname> finds all copies
+            of a string in the input. <functionname>split()</functionname> splits the input into parts.
+        </para>
+
+        <programlisting>
+    string str1("hello abc-*-ABC-*-aBc goodbye");
+
+    typedef vector&lt; iterator_range&lt;string::iterator&gt; &gt; find_vector_type;
+    
+    find_vector_type FindVec; // #1: Search for separators
+    ifind_all( FindVec, str1, "abc" ); // FindVec == { [abc],[ABC],[aBc] }
+
+    typedef vector&lt; string &gt; split_vector_type;
+    
+    split_vector_type SplitVec; // #2: Search for tokens
+    split( SplitVec, str1, is_any_of("-*") ); // SplitVec == { "hello abc","ABC","aBc goodbye" }
+        </programlisting>
+        <para>
+            <code>[hello]</code> designates an <code>iterator_range</code> delimiting this substring.                       
+        </para>
+        <para>
+            First example show how to construct a container to hold references to all extracted
+            substrings. Algorithm <functionname>ifind_all()</functionname> puts into FindVec references
+            to all substrings that are in case-insensitive manner equal to "abc".
+        </para>
+        <para>
+            Second example uses <functionname>split()</functionname> to split string str1 into parts
+            separated by characters '-' or '*'. These parts are then put into the SplitVec.
+            It is possible to specify if adjacent separators are concatenated or not.
+        </para>
+        <para>
+            More information can be found in the reference: <headername>boost/algorithm/string/split.hpp</headername>.
+        </para>
+   </section>
+</section>

string/example/conv_example.cpp

@@ -0,0 +1,41 @@
+//  Boost string_algo library example file  ---------------------------------//
+
+//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  distribution is subject to the Boost Software License, Version
+//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+#include <string>
+#include <vector>
+#include <iostream>
+#include <iterator>
+#include <boost/algorithm/string/case_conv.hpp>
+
+using namespace std;
+using namespace boost;
+
+int main()
+{  
+    cout << "* Case Conversion Example *" << endl << endl;
+
+    string str1("AbCdEfG");
+    vector<char> vec1( str1.begin(), str1.end() );
+    
+    // Convert vector of chars to lower case
+    cout << "lower-cased copy of vec1: ";
+    to_lower_copy( ostream_iterator<char>(cout), vec1 );
+    cout << endl;
+
+    // Conver string str1 to upper case ( copy the input )
+    cout << "upper-cased copy of str1: " << to_upper_copy( str1 ) << endl;
+
+    // Inplace conversion
+    to_lower( str1 );
+    cout << "lower-cased str1: " << str1 << endl;
+
+    cout << endl;
+
+    return 0;
+}

string/example/find_example.cpp

@@ -0,0 +1,58 @@
+//  Boost string_algo library example file  ---------------------------------//
+
+//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  distribution is subject to the Boost Software License, Version
+//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+#include <string>
+#include <iostream>
+#include <algorithm>
+#include <functional>
+#include <boost/algorithm/string/case_conv.hpp>
+#include <boost/algorithm/string/find.hpp>
+
+using namespace std;
+using namespace boost;
+
+int main()
+{  
+    cout << "* Find Example *" << endl << endl;
+
+    string str1("abc___cde___efg");
+    string str2("abc");
+
+    // find "cde" substring
+    iterator_range<string::iterator> range=find_first( str1, string("cde") );
+
+    // convert a substring to upper case 
+    // note that iterator range can be directly passed to the algorithm
+    to_upper( range );
+
+    cout << "str1 with upper-cased part matching cde: " << str1 << endl;
+
+    // get a head of the string
+    iterator_range<string::iterator> head=find_head( str1, 3 );
+    cout << "head(3) of the str1: " << string( head.begin(), head.end() ) << endl;
+
+    // get the tail
+    head=find_tail( str2, 5 );
+    cout << "tail(5) of the str2: " << string( head.begin(), head.end() ) << endl;
+
+    // char processing
+    char text[]="hello dolly!";
+    iterator_range<char*> crange=find_last(text,"ll");
+
+    // transform the range ( add 1 )
+    transform( crange.begin(), crange.end(), crange.begin(), bind2nd( plus<char>(), 1 ) );
+    // uppercase the range
+    to_upper( crange );
+
+    cout << text << endl;
+
+    cout << endl;
+
+    return 0;
+}

string/example/predicate_example.cpp

@@ -0,0 +1,61 @@
+//  Boost string_algo library example file  ---------------------------------//
+
+//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  distribution is subject to the Boost Software License, Version
+//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+#include <string>
+#include <iostream>
+#include <functional>
+#include <boost/algorithm/string/predicate.hpp>
+#include <boost/algorithm/string/classification.hpp>
+#include <boost/bind.hpp>
+
+
+using namespace std;
+using namespace boost;
+
+int main()
+{
+    cout << "* Predicate Example *" << endl << endl;
+
+    string str1("123xxx321");
+    string str2("abc");
+
+    // Check if str1 starts with '123'
+    cout << "str1 starts with \"123\": " << 
+        (starts_with( str1, string("123") )?"true":"false") << endl; 
+    
+    // Check if str1 ends with '123'
+    cout << "str1 ends with \"123\": " << 
+        (ends_with( str1, string("123") )?"true":"false") << endl; 
+
+    // Check if str1 containes 'xxx'
+    cout << "str1 contains \"xxx\": " << 
+        (contains( str1, string("xxx") )?"true":"false") << endl; 
+
+
+    // Check if str2 equals to 'abc'
+    cout << "str2 equals \"abc\": " << 
+        (equals( str2, string("abc") )?"true":"false") << endl; 
+
+
+    // Classification functors and all predicate
+    if ( all(";.,", is_punct() ) )
+    {
+        cout << "\";.,\" are all punctuation characters" << endl;  
+    }
+
+    // Classification predicates can be combined 
+    if ( all("abcxxx", is_any_of("xabc") && !is_space() ) )
+    {
+        cout << "true" << endl;
+    }
+
+    cout << endl;
+
+    return 0;
+}   

string/example/regex_example.cpp

@@ -0,0 +1,42 @@
+//  Boost string_algo library example file  ---------------------------------//
+
+//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  distribution is subject to the Boost Software License, Version
+//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+#include <string>
+#include <iostream>
+#include <iterator>
+#include <boost/regex.hpp>
+#include <boost/algorithm/string/regex.hpp>
+
+using namespace std;
+using namespace boost;
+
+int main()
+{  
+    cout << "* Regex Example *" << endl << endl;
+
+    string str1("abc__(456)__123__(123)__cde");
+
+    // Replace all substrings matching (digit+) 
+    cout << 
+        "replace all (digit+) in str1 with #digit+# :" <<
+        replace_all_regex_copy( str1, regex("\\(([0-9]+)\\)"), string("#$1#") ) << endl;
+    
+    // Erase all substrings matching (digit+) 
+    cout << 
+        "remove all sequences of letters from str1 :" <<
+        erase_all_regex_copy( str1, regex("[[:alpha:]]+") ) << endl;
+
+    // in-place regex transformation
+    replace_all_regex( str1, regex("_(\\([^\\)]*\\))_"), string("-$1-") );
+    cout << "transformad str1: " << str1 << endl;
+
+    cout << endl;
+
+    return 0;
+}

string/example/replace_example.cpp

@@ -0,0 +1,89 @@
+//  Boost string_algo library example file  ---------------------------------//
+
+//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  distribution is subject to the Boost Software License, Version
+//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+#include <string>
+#include <iostream>
+#include <iterator>
+//#include <boost/algorithm/string/replace.hpp>
+//#include <boost/algorithm/string/erase.hpp>
+//#include <boost/algorithm/string/case_conv.hpp>
+#include <boost/algorithm/string.hpp>
+
+//Following two includes contain second-layer function.
+//They are already included by first-layer header
+
+//#include <boost/algorithm/string/replace2.hpp>
+//#include <boost/algorithm/string/find2.hpp>
+
+using namespace std;
+using namespace boost;
+
+// uppercase formatter
+/*
+    Convert an input to upper case. 
+    Note, that this formatter can be used only on std::string inputs.
+*/
+inline string upcase_formatter( 
+    const iterator_range<string::const_iterator>& Replace )
+{
+    string Temp(Replace.begin(), Replace.end());
+    to_upper(Temp);
+    return Temp;
+}
+
+int main()
+{  
+    cout << "* Replace Example *" << endl << endl;
+
+    string str1("abc___cde___efg");
+
+    // Erase 6-9th characters from the string
+    cout << "str1 without 6th to 9th character:" <<
+        erase_range_copy( str1, make_iterator_range(str1.begin()+6, str1.begin()+9) ) << endl;
+
+    // Replace 6-9th character with '+++'
+    cout << "str1 with 6th to 9th character replaced with '+++': " << 
+        replace_range_copy( 
+            str1, make_iterator_range(str1.begin()+6, str1.begin()+9), "+++" ) << endl;
+
+    cout << "str1 with 'cde' replaced with 'XYZ': ";
+    
+    // Replace first 'cde' with 'XYZ'. Modify the input
+    replace_first_copy( ostream_iterator<char>(cout), str1, "cde", "XYZ" );
+    cout << endl;
+    
+    // Replace all '___'
+    cout << "str1 with all '___' replaced with '---': " << 
+        replace_all_copy( str1, "___", "---" ) << endl;
+
+    // Erase all '___'
+    cout << "str1 without all '___': " << 
+        erase_all_copy( str1, "___" ) << endl;
+
+    // replace third and 5th occurrence of _ in str1
+    // note that nth argument is 0-based
+    replace_nth( str1, "_", 4, "+" );
+    replace_nth( str1, "_", 2, "+" );
+
+    cout << "str1 with third and 5th occurrence of _ replace: " << str1 << endl;
+
+    // Custom formatter examples
+    string str2("abC-xxxx-AbC-xxxx-abc");
+
+    // Find string 'abc' ignoring the case and convert it to upper case
+    cout << "Upcase all 'abc'(s) in the str2: " <<
+        find_format_all_copy( 
+            str2,
+            first_finder("abc", is_iequal()), 
+            upcase_formatter );
+    
+    cout << endl;
+
+    return 0;
+}

string/example/rle_example.cpp

@@ -0,0 +1,241 @@
+//  Boost string_algo library example file  ---------------------------------//
+
+//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  distribution is subject to the Boost Software License, Version
+//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+/*
+    RLE compression using replace framework. Goal is to compress a sequence of
+    repeating characters into 3 bytes ( repeat mark, character and repetition count ).
+    For simplification, it works only on numeric-value sequences.
+*/
+
+#include <string>
+#include <iostream>
+#include <limits>
+#include <boost/detail/iterator.hpp>
+#include <boost/algorithm/string/find_format.hpp>
+#include <boost/algorithm/string/finder.hpp>
+
+using namespace std;
+using namespace boost;
+
+// replace mark specification, specialize for a specific element type
+template< typename T > T repeat_mark() { return (std::numeric_limits<T>::max)(); };
+
+// Compression  -----------------------------------------------------------------------
+
+
+// compress finder -rle
+/*
+    Find a sequence which can be compressed. It has to be at least 3-character long
+    sequence of repetitive characters 
+*/
+struct find_compressF 
+{
+    // Construction
+    find_compressF() {}
+
+    // Operation
+    template<typename ForwardIteratorT>
+    iterator_range<ForwardIteratorT> operator()( 
+        ForwardIteratorT Begin, 
+        ForwardIteratorT End ) const
+    {
+        typedef ForwardIteratorT input_iterator_type;
+        typedef typename boost::detail::iterator_traits<input_iterator_type>::value_type value_type;
+        typedef iterator_range<input_iterator_type> result_type;
+
+        // begin of the matching segment
+        input_iterator_type MStart=End;
+        // Repetition counter
+        value_type Cnt=0;
+
+        // Search for a sequence of repetitive characters
+        for(input_iterator_type It=Begin; It!=End;)
+        {
+            input_iterator_type It2=It++;
+
+            if ( It==End || Cnt>=(std::numeric_limits<value_type>::max)() )
+            {
+                return result_type( MStart, It );
+            }
+
+            if ( *It==*It2 )
+            {
+                if ( MStart==End )
+                {
+                    // Mark the start
+                    MStart=It2;
+                }
+
+                // Increate repetition counter
+                Cnt++;
+            }
+            else
+            {
+                if ( MStart!=End )
+                {
+                    if ( Cnt>2 )
+                        return result_type( MStart, It );
+                    else
+                    {
+                        MStart=End;
+                        Cnt=0;
+                    }
+                }
+            }
+        }
+
+        return result_type( End, End );
+    }
+};
+
+// rle compress format
+/*
+    Transform a sequence into repeat mark, character and count 
+*/
+template<typename SeqT>
+struct format_compressF
+{
+private:
+    typedef SeqT result_type;
+    typedef typename SeqT::value_type value_type;
+
+public:
+    // Construction
+    format_compressF() {};
+
+    // Operation
+    template< typename ReplaceT >
+    result_type operator()( const ReplaceT& Replace ) const
+    {
+        SeqT r;
+        r.push_back( repeat_mark<value_type>() );
+        r.push_back( *(Replace.begin()) );
+        r.push_back( value_type( Replace.size() ) );
+        
+        return r;
+    }
+};
+
+// Decompression  -----------------------------------------------------------------------
+
+
+// find decompress-rle functor
+/*
+    find a repetition block
+*/
+struct find_decompressF
+{
+    // Construction
+    find_decompressF() {}
+
+    // Operation
+    template<typename ForwardIteratorT>
+    iterator_range<ForwardIteratorT> operator()( 
+        ForwardIteratorT Begin, 
+        ForwardIteratorT End ) const
+    {
+        typedef ForwardIteratorT input_iterator_type;
+        typedef typename boost::detail::iterator_traits<input_iterator_type>::value_type value_type;
+        typedef iterator_range<input_iterator_type> result_type;
+
+        for(input_iterator_type It=Begin; It!=End; It++)
+        {
+            if( *It==repeat_mark<value_type>() )
+            {
+                // Repeat mark found, extract body
+                input_iterator_type It2=It++; 
+                
+                if ( It==End ) break;
+                    It++; 
+                if ( It==End ) break;
+                    It++;
+                
+                return result_type( It2, It );
+            }
+        }
+
+        return result_type( End, End );
+    }
+};
+
+// rle decompress format
+/*
+    transform a repetition block into a sequence of characters
+*/
+template< typename SeqT >
+struct format_decompressF
+{
+private:
+    typedef SeqT result_type;
+    typedef typename SeqT::value_type value_type;
+
+public:
+    // Construction
+    format_decompressF() {};
+
+    // Operation
+    template< typename ReplaceT >
+    result_type operator()( const ReplaceT& Replace ) const
+    {
+        // extract info
+        typename ReplaceT::const_iterator It=Replace.begin();
+
+        value_type Value=*(++It);
+        value_type Repeat=*(++It);
+        
+        SeqT r;
+        for( value_type Index=0; Index<Repeat; Index++ ) r.push_back( Value );
+
+        return r;
+    }
+};
+
+
+int main()
+{
+    cout << "* RLE Compression Example *" << endl << endl;
+
+    string original("123_AA_*ZZZZZZZZZZZZZZ*34");
+
+    // copy compression
+    string compress=find_format_all_copy( 
+        original, 
+        find_compressF(), 
+        format_compressF<string>() );
+
+    cout << "Compressed string: " << compress << endl;
+
+    // Copy decompression
+    string decompress=find_format_all_copy( 
+        compress, 
+        find_decompressF(), 
+        format_decompressF<string>() );
+
+    cout << "Decompressed string: " << decompress << endl;
+
+    // in-place compression
+    find_format_all( 
+        original, 
+        find_compressF(), 
+        format_compressF<string>() );
+    
+    cout << "Compressed string: " << original << endl;
+
+    // in-place decompression
+    find_format_all( 
+        original, 
+        find_decompressF(), 
+        format_decompressF<string>() );
+
+    cout << "Decompressed string: " << original << endl;
+
+    cout << endl;
+
+    return 0;
+}

string/example/split_example.cpp

@@ -0,0 +1,62 @@
+//  Boost string_algo library example file  ---------------------------------//
+
+//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  distribution is subject to the Boost Software License, Version
+//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+#include <string>
+#include <vector>
+#include <iostream>
+#include <iterator>
+#include <functional>
+#include <boost/algorithm/string/classification.hpp>
+#include <boost/algorithm/string/split.hpp>
+#include <boost/algorithm/string/find_iterator.hpp>
+
+using namespace std;
+using namespace boost;
+
+int main()
+{  
+    cout << "* Split Example *" << endl << endl;
+
+    string str1("abc-*-ABC-*-aBc");
+
+    cout << "Before: " << str1 << endl;
+
+    // Find all 'abc' substrings (ignoring the case)
+    // Create a find_iterator
+    typedef find_iterator<string::iterator> string_find_iterator;
+    for(string_find_iterator It=
+            make_find_iterator(str1, first_finder("abc", is_iequal()));
+        It!=string_find_iterator();
+        ++It)
+    {
+        cout << copy_range<std::string>(*It) << endl;
+        // shift all chars in the match by one
+        transform( 
+            It->begin(), It->end(), 
+            It->begin(), 
+            bind2nd( plus<char>(), 1 ) );
+    }
+
+    // Print the string now
+    cout << "After: " << str1 << endl;
+    
+    // Split the string into tokens ( use '-' and '*' as delimiters )
+    // We need copies of the input only, and adjacent tokens are compressed
+    vector<std::string> ResultCopy;
+    split(ResultCopy, str1, is_any_of("-*"), token_compress_on);
+
+    for(unsigned int nIndex=0; nIndex<ResultCopy.size(); nIndex++)
+    {
+        cout << nIndex << ":" << ResultCopy[nIndex] << endl;
+    };
+
+    cout << endl;
+
+    return 0;
+}

string/example/trim_example.cpp

@@ -0,0 +1,47 @@
+//  Boost string_algo library example file  ---------------------------------//
+
+//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  distribution is subject to the Boost Software License, Version
+//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+#include <string>
+#include <iostream>
+#include <boost/algorithm/string/trim.hpp>
+#include <boost/algorithm/string/classification.hpp>
+
+using namespace std;
+using namespace boost;
+
+int main()
+{
+    cout << "* Trim Example *" << endl << endl;
+
+    string str1("     1x x x x1     ");
+    string str2("<>trim<>");
+    string str3("123abs343");
+
+    // Simple left trim
+    cout << "trim_left copy of str1: " << "\"" << trim_left_copy( str1 ) << "\"" << endl;
+
+    // Inplace right trim
+    trim_right( str1 );
+    cout << "trim_right on str1: " << "\"" << str1 << "\"" << endl;
+
+    // Parametric trim. 'Space' is defined using is_any_of predicate
+    cout 
+        << "trimmed copy of str4 ( space='<>' ): " 
+        << "\""<< trim_copy_if( str2, is_any_of("<>") ) << "\"" << endl;
+    
+
+    // Parametric trim. 'Space' is defined using is_digit predicate
+    cout 
+        << "trimmed copy of str5 ( space=digit ): " 
+        << "\"" << trim_copy_if( str3, is_digit() ) << "\"" << endl;
+
+    cout << endl;
+
+    return 0;
+}

string/index.html

@@ -0,0 +1,20 @@
+
+<!-- Copyright (c) 2002-2006 Pavol Droba.
+     Subject to the Boost Software License, Version 1.0. 
+     (See accompanying file LICENSE-1.0 or  http://www.boost.org/LICENSE-1.0)
+-->
+
+<html>
+<head>
+<meta http-equiv="refresh" content="0; URL=../../../doc/html/string_algo.html">
+</head>
+<body>
+Automatic redirection failed, please go to
+<a href="../../../doc/html/string_algo.html">../../doc/html/string_algo.html</a> 
+&nbsp;<hr>
+<p><EFBFBD> Copyright Beman Dawes, 2001</p>
+<p>Distributed under the Boost Software License, Version 1.0. (See accompanying 
+file <a href="../../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or copy 
+at <a href="http://www.boost.org/LICENSE_1_0.txt">www.boost.org/LICENSE_1_0.txt</a>)</p>
+</body>
+</html>

string/test/Jamfile.v2

@@ -0,0 +1,63 @@
+#  Boost string_algo library test suite Jamfile  ----------------------------
+#
+#  Copyright Pavol Droba 2002-2003. Use, modification and
+#  distribution is subject to the Boost Software License, Version
+#  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+#  http://www.boost.org/LICENSE_1_0.txt)
+#
+#  See http://www.boost.org for updates, documentation, and revision history.
+
+import testing ;
+
+test-suite algorithm/string
+    : [ run 
+            trim_test.cpp
+          : :
+            :
+            : trim
+        ]
+      [ run 
+            conv_test.cpp
+          : :
+            :
+            : conv
+        ]
+      [ run 
+            predicate_test.cpp
+          : :
+            :
+            : predicate
+        ]
+      [ run 
+            find_test.cpp
+          : :
+            :
+            : find
+        ]
+      [ run
+            split_test.cpp
+          : :
+            :
+            : split
+        ]
+      [ run
+            join_test.cpp
+          : :
+            :
+            : join
+        ]
+      [ run 
+            replace_test.cpp
+          : :
+            :
+            : replace
+        ]
+      [ run 
+            regex_test.cpp
+            ../../../regex/build//boost_regex
+          : :
+            :   
+            : regex
+        ]
+    ;
+

string/test/conv_test.cpp

@@ -0,0 +1,95 @@
+//  Boost string_algo library conv_test.cpp file  ---------------------------//
+
+//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  distribution is subject to the Boost Software License, Version
+//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+#include <boost/algorithm/string/case_conv.hpp>
+
+// Include unit test framework
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <string>
+#include <iostream>
+#include <algorithm>
+#include <boost/test/test_tools.hpp>
+
+using namespace std;
+using namespace boost;
+
+void conv_test()
+{
+    string str1("AbCdEfG 123 xxxYYYzZzZ");
+    string str2("AbCdEfG 123 xxxYYYzZzZ");
+    string str3("");
+    const char pch[]="AbCdEfG 123 xxxYYYzZzZ";    
+    unsigned int pchlen=sizeof(pch);
+
+    char* pch1=new char[pchlen];
+    std::copy(pch, pch+pchlen, pch1);
+    char* pch2=new char[pchlen];
+    std::copy(pch, pch+pchlen, pch2);
+
+    // *** iterator tests *** //
+
+    string strout;
+    to_lower_copy( back_inserter(strout), str1 );
+    BOOST_CHECK( strout=="abcdefg 123 xxxyyyzzzz" );
+    strout.clear();
+    to_upper_copy( back_inserter(strout), str1 );
+    BOOST_CHECK( strout=="ABCDEFG 123 XXXYYYZZZZ" );
+
+    strout.clear();
+    to_lower_copy( back_inserter(strout), "AbCdEfG 123 xxxYYYzZzZ" );
+    BOOST_CHECK( strout=="abcdefg 123 xxxyyyzzzz" );
+    strout.clear();
+    to_upper_copy( back_inserter(strout), "AbCdEfG 123 xxxYYYzZzZ" );
+    BOOST_CHECK( strout=="ABCDEFG 123 XXXYYYZZZZ" );
+
+    strout.clear();
+    to_lower_copy( back_inserter(strout), pch1 );
+    BOOST_CHECK( strout=="abcdefg 123 xxxyyyzzzz" );
+    strout.clear();
+    to_upper_copy( back_inserter(strout), pch1 );
+    BOOST_CHECK( strout=="ABCDEFG 123 XXXYYYZZZZ" );
+
+    // *** value passing tests *** //
+
+    BOOST_CHECK( to_lower_copy( str1 )=="abcdefg 123 xxxyyyzzzz" );
+    BOOST_CHECK( to_upper_copy( str1 )=="ABCDEFG 123 XXXYYYZZZZ" );
+
+    BOOST_CHECK( to_lower_copy( str3 )=="" );
+    BOOST_CHECK( to_upper_copy( str3 )=="" );
+
+    // *** inplace tests *** //
+
+    to_lower( str1 );
+    BOOST_CHECK( str1=="abcdefg 123 xxxyyyzzzz" );
+    to_upper( str2 );
+    BOOST_CHECK( str2=="ABCDEFG 123 XXXYYYZZZZ" );
+
+    // c-string modification
+    to_lower( pch1 );
+    BOOST_CHECK( string(pch1)=="abcdefg 123 xxxyyyzzzz" );
+    to_upper( pch2 );
+    BOOST_CHECK( string(pch2)=="ABCDEFG 123 XXXYYYZZZZ" );
+
+    to_lower( str3 );
+    BOOST_CHECK( str3=="" );
+    to_upper( str3 );
+    BOOST_CHECK( str3=="" );
+
+    delete[] pch1;
+    delete[] pch2;
+}
+
+// test main 
+int test_main( int, char*[] )
+{
+    conv_test();
+    
+    return 0;
+}

string/test/find_test.cpp

@@ -0,0 +1,259 @@
+//  Boost string_algo library substr_test.cpp file  ------------------//
+
+//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  distribution is subject to the Boost Software License, Version
+//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+#include <boost/algorithm/string/find.hpp>
+#include <boost/algorithm/string/classification.hpp>
+
+// Include unit test framework
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <string>
+#include <vector>
+#include <iostream>
+#include <iterator>
+#include <sstream>
+#include <boost/test/test_tools.hpp>
+
+using namespace std;
+using namespace boost;
+
+void find_test()
+{
+    string str1("123abcxXxabcXxXabc321");
+    string str2("abc");
+    string str3("");
+    const char* pch1="123abcxxxabcXXXabc321";
+    vector<int> vec1( str1.begin(), str1.end() );
+
+    // find results ------------------------------------------------------------//
+    iterator_range<string::iterator> nc_result;
+    iterator_range<string::const_iterator> cv_result;
+    
+    iterator_range<vector<int>::iterator> nc_vresult;
+    iterator_range<vector<int>::const_iterator> cv_vresult;
+
+    iterator_range<const char*> ch_result;
+
+    // basic tests ------------------------------------------------------------//
+
+
+    // find_first
+    BOOST_CHECKPOINT( "find_first" );
+
+    nc_result=find_first( str1, string("abc") );
+    BOOST_CHECK( 
+        ( (nc_result.begin()-str1.begin()) == 3) &&
+        ( (nc_result.end()-str1.begin()) == 6) );
+
+    cv_result=find_first( const_cast<const string&>(str1), str2 );
+    BOOST_CHECK( 
+        ( (cv_result.begin()-str1.begin()) == 3) &&
+        ( (cv_result.end()-str1.begin()) == 6) );
+
+    cv_result=ifind_first( const_cast<const string&>(str1), "xXX" );
+    BOOST_CHECK( 
+        ( (cv_result.begin()-str1.begin()) == 6) &&
+        ( (cv_result.end()-str1.begin()) == 9) );
+
+    ch_result=find_first( pch1, "abc" );
+    BOOST_CHECK(( (ch_result.begin() - pch1 ) == 3) && ( (ch_result.end() - pch1 ) == 6 ) );
+
+    // find_last
+    BOOST_CHECKPOINT( "find_last" );
+    
+    nc_result=find_last( str1, string("abc") );
+    BOOST_CHECK( 
+        ( (nc_result.begin()-str1.begin()) == 15) &&
+        ( (nc_result.end()-str1.begin()) == 18) );
+
+    cv_result=find_last( const_cast<const string&>(str1), str2 );
+    BOOST_CHECK( 
+        ( (cv_result.begin()-str1.begin()) == 15) &&
+        ( (cv_result.end()-str1.begin()) == 18) );
+
+    cv_result=ifind_last( const_cast<const string&>(str1), "XXx" );
+    BOOST_CHECK( 
+        ( (cv_result.begin()-str1.begin()) == 12) &&
+        ( (cv_result.end()-str1.begin()) == 15) );
+
+    ch_result=find_last( pch1, "abc" );
+    BOOST_CHECK(( (ch_result.begin() - pch1 ) == 15) && ( (ch_result.end() - pch1 ) == 18 ) );
+
+    // find_nth
+    BOOST_CHECKPOINT( "find_nth" );
+
+    nc_result=find_nth( str1, string("abc"), 1 );
+    BOOST_CHECK( 
+        ( (nc_result.begin()-str1.begin()) == 9) &&
+        ( (nc_result.end()-str1.begin()) == 12) );
+
+    nc_result=find_nth( str1, string("abc"), -1 );
+    BOOST_CHECK( 
+        ( (nc_result.begin()-str1.begin()) == 15) &&
+        ( (nc_result.end()-str1.begin()) == 18) );
+
+
+    cv_result=find_nth( const_cast<const string&>(str1), str2, 1 );
+    BOOST_CHECK( 
+        ( (cv_result.begin()-str1.begin()) == 9) &&
+        ( (cv_result.end()-str1.begin()) == 12) );
+
+    cv_result=find_nth( const_cast<const string&>(str1), str2, -1 );
+    BOOST_CHECK( 
+        ( (cv_result.begin()-str1.begin()) == 15) &&
+        ( (cv_result.end()-str1.begin()) == 18) );
+        
+    cv_result=ifind_nth( const_cast<const string&>(str1), "xxx", 1 );
+    BOOST_CHECK( 
+        ( (cv_result.begin()-str1.begin()) == 12) &&
+        ( (cv_result.end()-str1.begin()) == 15) );
+
+    cv_result=ifind_nth( const_cast<const string&>(str1), "xxx", 1 );
+    BOOST_CHECK( 
+        ( (cv_result.begin()-str1.begin()) == 12) &&
+        ( (cv_result.end()-str1.begin()) == 15) );
+
+
+    ch_result=find_nth( pch1, "abc", 1 );
+    BOOST_CHECK(( (ch_result.begin() - pch1 ) == 9) && ( (ch_result.end() - pch1 ) == 12 ) );
+
+    // find_head
+    BOOST_CHECKPOINT( "find_head" );
+
+    nc_result=find_head( str1, 6 );
+    BOOST_CHECK( 
+        ( (nc_result.begin()-str1.begin()) == 0) &&
+        ( (nc_result.end()-str1.begin()) == 6) );
+
+    nc_result=find_head( str1, -6 );
+    BOOST_CHECK( 
+        ( (nc_result.begin()-str1.begin()) == 0) &&
+        ( (str1.end()-nc_result.end()) == 6 ) );
+
+    cv_result=find_head( const_cast<const string&>(str1), 6 );
+    BOOST_CHECK( 
+        ( (cv_result.begin()-str1.begin()) == 0) &&
+        ( (cv_result.end()-str1.begin()) == 6) );
+
+    ch_result=find_head( pch1, 6 );
+    BOOST_CHECK( ( (ch_result.begin() - pch1 ) == 0 ) && ( (ch_result.end() - pch1 ) == 6 ) );
+
+    // find_tail
+    BOOST_CHECKPOINT( "find_tail" );
+
+    nc_result=find_tail( str1, 6 );
+    BOOST_CHECK( 
+        ( (nc_result.begin()-str1.begin()) == 15) &&
+        ( (nc_result.end()-str1.begin()) == 21) );
+
+    nc_result=find_tail( str1, -6 );
+    BOOST_CHECK( 
+        ( (nc_result.begin()-str1.begin()) == 6) &&
+        ( (nc_result.end()-str1.begin()) == 21) );
+
+
+    cv_result=find_tail( const_cast<const string&>(str1), 6 );
+    BOOST_CHECK( 
+        ( (cv_result.begin()-str1.begin()) == 15) &&
+        ( (cv_result.end()-str1.begin()) == 21) );
+
+    ch_result=find_tail( pch1, 6 );
+    BOOST_CHECK( ( (ch_result.begin() - pch1 ) == 15 ) && ( (ch_result.end() - pch1 ) == 21 ) );
+
+    // find_token
+    BOOST_CHECKPOINT( "find_token" );
+
+    nc_result=find_token( str1, is_any_of("abc"), token_compress_on );
+    BOOST_CHECK( 
+        ( (nc_result.begin()-str1.begin()) == 3) &&
+        ( (nc_result.end()-str1.begin()) == 6) );
+
+    cv_result=find_token( const_cast<const string&>(str1), is_any_of("abc"), token_compress_on );
+    BOOST_CHECK( 
+        ( (cv_result.begin()-str1.begin()) == 3) &&
+        ( (cv_result.end()-str1.begin()) == 6) );
+
+    nc_result=find_token( str1, is_any_of("abc"), token_compress_off );
+    BOOST_CHECK( 
+        ( (nc_result.begin()-str1.begin()) == 3) &&
+        ( (nc_result.end()-str1.begin()) == 4) );
+
+    cv_result=find_token( const_cast<const string&>(str1), is_any_of("abc"), token_compress_off );
+    BOOST_CHECK( 
+        ( (cv_result.begin()-str1.begin()) == 3) &&
+        ( (cv_result.end()-str1.begin()) == 4) );
+
+    ch_result=find_token( pch1, is_any_of("abc"), token_compress_off );
+    BOOST_CHECK( ( (ch_result.begin() - pch1 ) == 3 ) && ( (ch_result.end() - pch1 ) == 4 ) );
+
+    // generic find
+    BOOST_CHECKPOINT( "generic find" );
+
+    nc_result=find(str1, first_finder(string("abc")));
+    BOOST_CHECK( 
+        ( (nc_result.begin()-str1.begin()) == 3) &&
+        ( (nc_result.end()-str1.begin()) == 6) );
+
+    cv_result=find(const_cast<const string&>(str1), first_finder(str2) );
+    BOOST_CHECK( 
+        ( (cv_result.begin()-str1.begin()) == 3) &&
+        ( (cv_result.end()-str1.begin()) == 6) );
+
+    // multi-type comparison test 
+    BOOST_CHECKPOINT( "multi-type" );
+
+    nc_vresult=find_first( vec1, string("abc") );
+    BOOST_CHECK( 
+        ( (nc_result.begin()-str1.begin()) == 3) &&
+        ( (nc_result.end()-str1.begin()) == 6) );
+
+    cv_vresult=find_first( const_cast<const vector<int>&>(vec1), str2 );
+    BOOST_CHECK( 
+        ( (cv_result.begin()-str1.begin()) == 3) &&
+        ( (cv_result.end()-str1.begin()) == 6) );
+
+    // overflow test
+    BOOST_CHECKPOINT( "overflow" );
+    
+    nc_result=find_first( str2, string("abcd") );
+    BOOST_CHECK( nc_result.begin()==nc_result.end() );
+    cv_result=find_first( const_cast<const string&>(str2), string("abcd") );
+    BOOST_CHECK( cv_result.begin()==cv_result.end() );
+
+    cv_result=find_head( const_cast<const string&>(str2), 4 );
+    BOOST_CHECK( string( cv_result.begin(), cv_result.end() )== string("abc") );
+    cv_result=find_tail( const_cast<const string&>(str2), 4 );
+    BOOST_CHECK( string( cv_result.begin(), cv_result.end() )== string("abc") );
+
+    // Empty string test
+    BOOST_CHECKPOINT( "empty" );
+    
+    nc_result=find_first( str3, string("abcd") );
+    BOOST_CHECK( nc_result.begin()==nc_result.end() );
+    nc_result=find_first( str1, string("") );
+    BOOST_CHECK( nc_result.begin()==nc_result.end() );
+
+    cv_result=find_first( const_cast<const string&>(str3), string("abcd") );
+    BOOST_CHECK( cv_result.begin()==cv_result.end() );
+    cv_result=find_first( const_cast<const string&>(str1), string("") );
+    BOOST_CHECK( cv_result.begin()==cv_result.end() ); 
+
+    // iterator_range specific tests
+    ostringstream osstr;
+    osstr << find_first( str1, "abc" );
+    BOOST_CHECK( osstr.str()=="abc" );
+}
+
+// test main 
+int test_main( int, char*[] )
+{
+    find_test();
+    
+    return 0;
+}

string/test/join_test.cpp

@@ -0,0 +1,79 @@
+//  Boost string_algo library iterator_test.cpp file  ---------------------------//
+
+//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  distribution is subject to the Boost Software License, Version
+//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+#include <boost/algorithm/string/join.hpp>
+#include <boost/algorithm/string/classification.hpp>
+// equals predicate is used for result comparison
+#include <boost/algorithm/string/predicate.hpp>
+
+// Include unit test framework
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <string>
+#include <vector>
+#include <iostream>
+
+#include <boost/test/test_tools.hpp>
+
+
+using namespace std;
+using namespace boost;
+
+bool is_not_empty(const std::string& str)
+{
+    return !str.empty();
+}
+
+void join_test()
+{
+    // Prepare inputs
+    vector<string> tokens1;
+    tokens1.push_back("xx");
+    tokens1.push_back("abc");
+    tokens1.push_back("xx");
+
+    vector<string> tokens2;
+    tokens2.push_back("");
+    tokens2.push_back("xx");
+    tokens2.push_back("abc");
+    tokens2.push_back("");
+    tokens2.push_back("abc");
+    tokens2.push_back("xx");
+    tokens2.push_back("");
+
+    vector<string> tokens3;
+    tokens3.push_back("");
+    tokens3.push_back("");
+    tokens3.push_back("");
+
+    vector<string> empty_tokens;
+
+    vector<vector<int> > vtokens;
+    for(unsigned int n=0; n<tokens2.size(); ++n)
+    {
+        vtokens.push_back(vector<int>(tokens2[n].begin(), tokens2[n].end()));
+    }
+
+    BOOST_CHECK( equals(join(tokens1, "-"), "xx-abc-xx") );
+    BOOST_CHECK( equals(join(tokens2, "-"), "-xx-abc--abc-xx-") );
+    BOOST_CHECK( equals(join(vtokens, "-"), "-xx-abc--abc-xx-") );
+    BOOST_CHECK( equals(join(empty_tokens, "-"), "") );
+
+    BOOST_CHECK( equals(join_if(tokens2, "-", is_not_empty), "xx-abc-abc-xx") );
+    BOOST_CHECK( equals(join_if(empty_tokens, "-", is_not_empty), "") );
+    BOOST_CHECK( equals(join_if(tokens3, "-", is_not_empty), "") );
+}
+
+// test main 
+int test_main( int, char*[] )
+{
+    join_test();
+    
+    return 0;
+}

string/test/predicate_test.cpp

@@ -0,0 +1,135 @@
+//  Boost string_algo library predicate_test.cpp file  ------------------//
+
+//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  distribution is subject to the Boost Software License, Version
+//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+#include <boost/algorithm/string/predicate.hpp>
+#include <boost/algorithm/string/classification.hpp>
+
+// Include unit test framework
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <string>
+#include <vector>
+#include <iostream>
+#include <functional>
+#include <boost/test/test_tools.hpp>
+
+using namespace std;
+using namespace boost;
+
+void predicate_test()
+{
+    string str1("123xxx321");
+    string str1_prefix("123");
+    string str2("abc");
+    string str3("");
+    string str4("abc");
+    vector<int> vec1( str1.begin(), str1.end() );
+
+    // Basic tests
+    BOOST_CHECK( starts_with( str1, string("123") ) );
+    BOOST_CHECK( !starts_with( str1, string("1234") ) );
+
+    BOOST_CHECK( istarts_with( "aBCxxx", "abc" ) );
+    BOOST_CHECK( !istarts_with( "aBCxxx", "abcd" ) );
+
+    BOOST_CHECK( ends_with( str1, string("321") ) );
+    BOOST_CHECK( !ends_with( str1, string("123") ) );
+
+    BOOST_CHECK( iends_with( "aBCxXx", "XXX" ) );
+    BOOST_CHECK( !iends_with( "aBCxxX", "xXXX" ) );
+
+    BOOST_CHECK( contains( str1, string("xxx") ) );
+    BOOST_CHECK( !contains( str1, string("yyy") ) );
+
+    BOOST_CHECK( icontains( "123XxX321", "xxx" ) );
+    BOOST_CHECK( !icontains( "123xXx321", "yyy" ) );
+
+    BOOST_CHECK( equals( str2, string("abc") ) );
+    BOOST_CHECK( !equals( str1, string("yyy") ) );
+
+    BOOST_CHECK( iequals( "AbC", "abc" ) );
+    BOOST_CHECK( !iequals( "aBc", "yyy" ) );
+
+    BOOST_CHECK( lexicographical_compare("abc", "abd") );
+    BOOST_CHECK( !lexicographical_compare("abc", "abc") );
+    BOOST_CHECK( lexicographical_compare("abc", "abd", is_less()) );
+
+    BOOST_CHECK( !ilexicographical_compare("aBD", "AbC") );
+    BOOST_CHECK( ilexicographical_compare("aBc", "AbD") );
+    BOOST_CHECK( lexicographical_compare("abC", "aBd", is_iless()) );
+
+    // multi-type comparison test
+    BOOST_CHECK( starts_with( vec1, string("123") ) );
+    BOOST_CHECK( ends_with( vec1, string("321") ) );
+    BOOST_CHECK( contains( vec1, string("xxx") ) );
+    BOOST_CHECK( equals( vec1, str1 ) );
+
+    // overflow test
+    BOOST_CHECK( !starts_with( str2, string("abcd") ) );
+    BOOST_CHECK( !ends_with( str2, string("abcd") ) );
+    BOOST_CHECK( !contains( str2, string("abcd") ) );
+    BOOST_CHECK( !equals( str2, string("abcd") ) );
+
+    // equal test
+    BOOST_CHECK( starts_with( str2, string("abc") ) );
+    BOOST_CHECK( ends_with( str2, string("abc") ) );
+    BOOST_CHECK( contains( str2, string("abc") ) );
+    BOOST_CHECK( equals( str2, string("abc") ) );
+
+    //! Empty string test
+    BOOST_CHECK( starts_with( str2, string("") ) );
+    BOOST_CHECK( ends_with( str2, string("") ) );
+    BOOST_CHECK( contains( str2, string("") ) );
+    BOOST_CHECK( equals( str3, string("") ) );
+
+    //! Container compatibility test
+    BOOST_CHECK( starts_with( "123xxx321", "123" ) );
+    BOOST_CHECK( ends_with( "123xxx321", "321" ) );
+    BOOST_CHECK( contains( "123xxx321", "xxx" ) );
+    BOOST_CHECK( equals( "123xxx321", "123xxx321" ) );
+
+}
+
+#define TEST_CLASS( Pred, YesInput, NoInput )\
+{\
+    BOOST_CHECK( all( string(YesInput), Pred ) );\
+    BOOST_CHECK( !all( string(NoInput), Pred ) );\
+}
+
+void classification_test()
+{
+    TEST_CLASS( is_space(), "\n\r\t ", "..." );
+    TEST_CLASS( is_alnum(), "ab129ABc", "_ab129ABc" );
+    TEST_CLASS( is_alpha(), "abc", "abc1" );
+    TEST_CLASS( is_cntrl(), "\n\t\r", "..." );
+    TEST_CLASS( is_digit(), "1234567890", "abc" );
+    TEST_CLASS( is_graph(), "123abc.,", "  \t" );
+    TEST_CLASS( is_lower(), "abc", "Aasdf" );
+    TEST_CLASS( is_print(), "abs", "\003\004asdf" );
+    TEST_CLASS( is_punct(), ".,;\"", "abc" );
+    TEST_CLASS( is_upper(), "ABC", "aBc" );
+    TEST_CLASS( is_xdigit(), "ABC123", "XFD" );
+    TEST_CLASS( is_any_of( string("abc") ), "aaabbcc", "aaxb" );
+    TEST_CLASS( is_any_of( "abc" ), "aaabbcc", "aaxb" );
+    TEST_CLASS( is_from_range( 'a', 'c' ), "aaabbcc", "aaxb" );
+
+    TEST_CLASS( !is_classified(std::ctype_base::space), "...", "..\n\r\t " );
+    TEST_CLASS( ( !is_any_of("abc") && is_from_range('a','e') ) || is_space(), "d e", "abcde" );
+}
+
+#undef TEST_CLASS
+
+// test main 
+int test_main( int, char*[] )
+{
+    predicate_test();
+    classification_test();
+    
+    return 0;
+}

string/test/regex_test.cpp

@@ -0,0 +1,159 @@
+//  Boost string_algo library substr_test.cpp file  ------------------//
+
+//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  distribution is subject to the Boost Software License, Version
+//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+#include <boost/algorithm/string/regex.hpp>
+#include <boost/algorithm/string/join.hpp>
+#include <boost/algorithm/string/sequence_traits.hpp>
+// equals predicate is used for result comparison
+#include <boost/algorithm/string/predicate.hpp>
+
+
+// Include unit test framework
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <string>
+#include <vector>
+#include <iostream>
+#include <boost/regex.hpp>
+#include <boost/test/test_tools.hpp>
+
+using namespace std;
+using namespace boost;
+
+static void find_test()
+{
+    string str1("123a1cxxxa23cXXXa456c321");
+    const char* pch1="123a1cxxxa23cXXXa456c321";
+    regex rx("a[0-9]+c");
+    vector<int> vec1( str1.begin(), str1.end() );
+    vector<string> tokens;
+
+    // find results
+    iterator_range<string::iterator> nc_result;
+    iterator_range<string::const_iterator> cv_result;
+    
+    iterator_range<vector<int>::iterator> nc_vresult;
+    iterator_range<vector<int>::const_iterator> cv_vresult;
+
+    iterator_range<const char*> ch_result;
+
+    // basic tests
+    nc_result=find_regex( str1, rx );
+    BOOST_CHECK( 
+        ( (nc_result.begin()-str1.begin()) == 3) &&
+        ( (nc_result.end()-str1.begin()) == 6) );
+
+    cv_result=find_regex( str1, rx );
+    BOOST_CHECK( 
+        ( (cv_result.begin()-str1.begin()) == 3) &&
+        ( (cv_result.end()-str1.begin()) == 6) );
+
+    ch_result=find_regex( pch1, rx );
+    BOOST_CHECK(( (ch_result.begin() - pch1 ) == 3) && ( (ch_result.end() - pch1 ) == 6 ) );
+
+    // multi-type comparison test
+    nc_vresult=find_regex( vec1, rx );
+    BOOST_CHECK( 
+        ( (nc_result.begin()-str1.begin()) == 3) &&
+        ( (nc_result.end()-str1.begin()) == 6) );
+
+    cv_vresult=find_regex( vec1, rx );
+    BOOST_CHECK( 
+        ( (cv_result.begin()-str1.begin()) == 3) &&
+        ( (cv_result.end()-str1.begin()) == 6) );
+
+    // find_all_regex test
+    find_all_regex( tokens, str1, rx );
+
+    BOOST_REQUIRE( tokens.size()==3 );
+    BOOST_CHECK( tokens[0]==string("a1c") );
+    BOOST_CHECK( tokens[1]==string("a23c") );
+    BOOST_CHECK( tokens[2]==string("a456c") );
+
+    // split_regex test
+    split_regex(    tokens, str1, rx );
+
+    BOOST_REQUIRE( tokens.size()==4 );
+    BOOST_CHECK( tokens[0]==string("123") );
+    BOOST_CHECK( tokens[1]==string("xxx") );
+    BOOST_CHECK( tokens[2]==string("XXX") );
+    BOOST_CHECK( tokens[3]==string("321") );
+
+}
+
+static void join_test()
+{
+    // Prepare inputs
+    vector<string> tokens1;
+    tokens1.push_back("xx");
+    tokens1.push_back("abc");
+    tokens1.push_back("xx");
+
+#ifndef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
+    BOOST_CHECK( equals(join_if(tokens1, "-", regex("x+")), "xx-xx") );
+    BOOST_CHECK( equals(join_if(tokens1, "-", regex("[abc]+")), "abc") );
+#else 
+    BOOST_CHECK( equals(join_if_regex(tokens1, "-", regex("x+")), "xx-xx") );
+    BOOST_CHECK( equals(join_if_regex(tokens1, "-", regex("[abc]+")), "abc") );
+#endif 
+}
+
+static void replace_test()
+{
+    string str1("123a1cxxxa23cXXXa456c321");
+    regex rx1("a([0-9]+)c");
+    regex rx2("([xX]+)");
+    regex rx3("_[^_]*_");
+    string fmt1("_A$1C_");
+    string fmt2("_xXx_");
+    vector<int> vec1( str1.begin(), str1.end() );
+
+    // inmutable tests
+    
+    // basic tests
+    BOOST_CHECK( replace_regex_copy( str1, rx1, fmt1 )==string("123_A1C_xxxa23cXXXa456c321") );
+    BOOST_CHECK( replace_all_regex_copy( str1, rx1, fmt1 )==string("123_A1C_xxx_A23C_XXX_A456C_321") );
+    BOOST_CHECK( erase_regex_copy( str1, rx1 )==string("123xxxa23cXXXa456c321") );
+    BOOST_CHECK( erase_all_regex_copy( str1, rx1 )==string(string("123xxxXXX321")) );
+
+    // output iterator variants test
+    string strout;
+    replace_regex_copy( back_inserter(strout), str1, rx1, fmt1 );
+    BOOST_CHECK( strout==string("123_A1C_xxxa23cXXXa456c321") );
+    strout.clear();
+    replace_all_regex_copy( back_inserter(strout), str1, rx1, fmt1 );
+    BOOST_CHECK( strout==string("123_A1C_xxx_A23C_XXX_A456C_321") );
+    strout.clear();
+    erase_regex_copy( back_inserter(strout), str1, rx1 );
+    BOOST_CHECK( strout==string("123xxxa23cXXXa456c321") );
+    strout.clear();
+    erase_all_regex_copy( back_inserter(strout), str1, rx1 );
+    BOOST_CHECK( strout==string("123xxxXXX321") );
+    strout.clear();
+
+    // in-place test
+    replace_regex( str1, rx1, fmt2 );
+    BOOST_CHECK( str1==string("123_xXx_xxxa23cXXXa456c321") );
+
+    replace_all_regex( str1, rx2, fmt1 );
+    BOOST_CHECK( str1==string("123__AxXxC___AxxxC_a23c_AXXXC_a456c321") );
+    erase_regex( str1, rx3 );
+    BOOST_CHECK( str1==string("123AxXxC___AxxxC_a23c_AXXXC_a456c321") );
+    erase_all_regex( str1, rx3 );
+    BOOST_CHECK( str1==string("123AxXxCa23ca456c321") );
+}
+
+int test_main( int, char*[] )
+{
+    find_test();
+    join_test();
+    replace_test();
+
+    return 0;
+}

string/test/replace_test.cpp

@@ -0,0 +1,301 @@
+//  Boost string_algo library substr_test.cpp file  ------------------//
+
+//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  distribution is subject to the Boost Software License, Version
+//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+#include <boost/algorithm/string/replace.hpp>
+#include <boost/algorithm/string/erase.hpp>
+#include <boost/algorithm/string/std/list_traits.hpp>
+#include <boost/algorithm/string/std/string_traits.hpp>
+
+// Include unit test framework
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <string>
+#include <vector>
+#include <list>
+#include <iostream>
+
+// equals predicate is used for result comparison
+#include <boost/algorithm/string/predicate.hpp>
+
+#include <boost/test/test_tools.hpp>
+
+using namespace std;
+using namespace boost;
+
+void sequence_traits_test()
+{
+    // basic_string traits
+    BOOST_CHECK( boost::algorithm::has_native_replace<string>::value );
+    BOOST_CHECK( !boost::algorithm::has_stable_iterators<string>::value );
+    BOOST_CHECK( !boost::algorithm::has_const_time_insert<string>::value );    
+    BOOST_CHECK( !boost::algorithm::has_const_time_erase<string>::value ); 
+
+    // vector traits
+    BOOST_CHECK( !boost::algorithm::has_native_replace< vector<char> >::value );
+    BOOST_CHECK( !boost::algorithm::has_stable_iterators< vector<char> >::value );
+    BOOST_CHECK( !boost::algorithm::has_const_time_insert< vector<char> >::value );    
+    BOOST_CHECK( !boost::algorithm::has_const_time_erase< vector<char> >::value ); 
+
+    // list traits
+    BOOST_CHECK( !boost::algorithm::has_native_replace< list<char> >::value );
+    BOOST_CHECK( boost::algorithm::has_stable_iterators< list<char> >::value );
+    BOOST_CHECK( boost::algorithm::has_const_time_insert< list<char> >::value );   
+    BOOST_CHECK( boost::algorithm::has_const_time_erase< list<char> >::value );    
+}
+
+// Combine tests for all variants of the algorithm
+#define C_ ,
+#define TEST_ALGO( Algo, Input, Params, Output ) \
+{\
+    BOOST_CHECKPOINT( #Algo " - Copy" );\
+\
+    string str1(Input);\
+\
+    /* Copy test */ \
+    BOOST_CHECK( Algo##_copy( str1, Params )==Output );\
+\
+    BOOST_CHECKPOINT( #Algo " - Iterator" );\
+    /* Iterator test */\
+    string strout;\
+    Algo##_copy( back_inserter(strout), str1, Params );\
+    BOOST_CHECK( strout==Output ); \
+\
+    /* In-place test */\
+    vector<char> vec1( str1.begin(), str1.end() );\
+    list<char> list1( str1.begin(), str1.end() );\
+\
+    BOOST_CHECKPOINT( #Algo " - Inplace(string)" );\
+    Algo( str1, Params ); \
+    BOOST_CHECK( equals( str1, Output ) ); \
+\
+    BOOST_CHECKPOINT( #Algo " - Inplace(vector)" );\
+    Algo( vec1, Params ); \
+    BOOST_CHECK( equals( vec1, Output ) );\
+\
+    BOOST_CHECKPOINT( #Algo " - Inplace(list)" );\
+    Algo( list1, Params ); \
+    BOOST_CHECK( equals( list1, Output ) );\
+}
+
+void replace_first_test()
+{
+    // replace first
+    TEST_ALGO( replace_first, "1abc3abc2", string("abc") C_ string("YYY"), string("1YYY3abc2") );
+    TEST_ALGO( ireplace_first, "1AbC3abc2", "aBc" C_ "YYY", string("1YYY3abc2") );
+    TEST_ALGO( replace_first, "1abc3abc2", string("abc") C_ string("Z"), string("1Z3abc2") );
+    TEST_ALGO( replace_first, "1abc3abc2", string("abc") C_ string("XXXX"), string("1XXXX3abc2") );
+    TEST_ALGO( replace_first, "1abc3abc2", string("") C_ string("XXXX"), string("1abc3abc2") );
+    TEST_ALGO( replace_first, "1abc3abc2", "" C_ "XXXX", string("1abc3abc2") );
+    TEST_ALGO( replace_first, "", string("") C_ string("XXXX"), string("") );
+    TEST_ALGO( erase_first, "1abc3abc2", string("abc"), string("13abc2") );
+    TEST_ALGO( ierase_first, "1aBc3abc2", "abC", "13abc2" );
+    TEST_ALGO( erase_first, "1abc3abc2", "abc", "13abc2" );
+    TEST_ALGO( erase_first, "1abc3abc2", string(""), string("1abc3abc2") );
+    TEST_ALGO( erase_first, "", string("abc"), string("") );
+}
+
+void replace_last_test()
+{
+    // replace last
+    TEST_ALGO( replace_last, "1abc3abc2", string("abc") C_ string("YYY"), string("1abc3YYY2") );
+    TEST_ALGO( ireplace_last, "1abc3AbC2", "aBc" C_ "YYY", string("1abc3YYY2") );
+    TEST_ALGO( replace_last, "1abc3abc2", string("abc") C_ string("Z"), string("1abc3Z2") );
+    TEST_ALGO( replace_last, "1abc3abc2", string("abc") C_ string("XXXX"), string("1abc3XXXX2") );
+    TEST_ALGO( replace_last, "1abc3abc2", "abc" C_ "XXXX", string("1abc3XXXX2") );
+    TEST_ALGO( replace_last, "", string("") C_ string("XXXX"), string("") );
+    TEST_ALGO( erase_last, "1abc3abc2", string("abc"), string("1abc32") );
+    TEST_ALGO( ierase_last, "1aBc3aBc2", "ABC", string("1aBc32") );
+    TEST_ALGO( erase_last, "1abc3abc2", "abc", string("1abc32") );
+    TEST_ALGO( erase_last, "1abc3abc2", string(""), string("1abc3abc2") );
+    TEST_ALGO( erase_last, "", string("abc"), string("") );
+}
+
+void replace_all_test()
+{
+    // replace all
+    TEST_ALGO( replace_all, "1abc3abc2", string("abc") C_ string("YYY"), string("1YYY3YYY2") );
+    TEST_ALGO( ireplace_all, "1aBc3AbC2", "abC" C_ "YYY", string("1YYY3YYY2") );
+    TEST_ALGO( replace_all, "1abc3abc2", string("abc") C_ string("Z"), string("1Z3Z2") );
+    TEST_ALGO( replace_all, "1abc3abc2", string("abc") C_ string("XXXX"), string("1XXXX3XXXX2") );
+    TEST_ALGO( replace_all, "1abc3abc2", "abc" C_ "XXXX", string("1XXXX3XXXX2") );
+    TEST_ALGO( replace_all, "", string("") C_ string("XXXX"), string("") );
+    TEST_ALGO( erase_all, "1abc3abc2", string("abc"), string("132") );
+    TEST_ALGO( ierase_all, "1aBc3aBc2", "aBC", string("132") );
+    TEST_ALGO( erase_all, "1abc3abc2", "abc", string("132") );
+    TEST_ALGO( erase_all, "1abc3abc2", string(""), string("1abc3abc2") );
+    TEST_ALGO( erase_all, "", string("abc"), string("") );
+}
+
+void replace_nth_test()
+{
+    // replace nth
+    TEST_ALGO( replace_nth, "1abc3abc2", string("abc") C_ 0 C_ string("YYY"), string("1YYY3abc2") );
+    TEST_ALGO( replace_nth, "1abc3abc2", string("abc") C_ -1 C_ string("YYY"), string("1abc3YYY2") );
+    TEST_ALGO( ireplace_nth, "1AbC3abc2", "aBc" C_ 0 C_ "YYY", string("1YYY3abc2") );
+    TEST_ALGO( ireplace_nth, "1AbC3abc2", "aBc" C_ -1 C_ "YYY", string("1AbC3YYY2") );
+    TEST_ALGO( replace_nth, "1abc3abc2", string("abc") C_ 0 C_ string("Z"), string("1Z3abc2") );
+    TEST_ALGO( replace_nth, "1abc3abc2", string("abc") C_ 0 C_ string("XXXX"), string("1XXXX3abc2") );
+    TEST_ALGO( replace_nth, "1abc3abc2", "abc" C_ 0 C_ "XXXX", string("1XXXX3abc2") );
+    TEST_ALGO( replace_nth, "1abc3abc2", "abc" C_ 3 C_ "XXXX", string("1abc3abc2") );
+    TEST_ALGO( replace_nth, "1abc3abc2", "abc" C_ -3 C_ "XXXX", string("1abc3abc2") );
+    TEST_ALGO( replace_nth, "1abc3abc2", string("") C_ 0 C_ string("XXXX"), string("1abc3abc2") );
+    TEST_ALGO( replace_nth, "", string("") C_ 0 C_ string("XXXX"), string("") );
+    TEST_ALGO( replace_nth, "", string("") C_ -1 C_ string("XXXX"), string("") );
+    TEST_ALGO( erase_nth, "1abc3abc2", string("abc") C_ 0, string("13abc2") );
+    TEST_ALGO( erase_nth, "1abc3abc2", string("abc") C_ -1, string("1abc32") );
+    TEST_ALGO( erase_nth, "1abc3abc2", string("abc") C_ -3, string("1abc3abc2") );
+    TEST_ALGO( ierase_nth, "1aBc3aBc2", "ABC" C_ 0, string("13aBc2") );
+    TEST_ALGO( ierase_nth, "1aBc3aBc2", "ABC" C_ -1, string("1aBc32") );
+    TEST_ALGO( ierase_nth, "1aBc3aBc2", "ABC" C_ -3, string("1aBc3aBc2") );
+    TEST_ALGO( erase_nth, "1abc3abc2", "abc" C_ 0, string("13abc2") );
+    TEST_ALGO( erase_nth, "1abc3abc2", string("") C_ 0, string("1abc3abc2") );
+    TEST_ALGO( erase_nth, "", string("abc") C_ 0, string("") );
+    TEST_ALGO( erase_nth, "", string("abc") C_ -1, string("") );
+    TEST_ALGO( replace_nth, "1abc3abc2", string("abc") C_ 1 C_ string("YYY"), string("1abc3YYY2") );
+    TEST_ALGO( replace_nth, "1abc3abc2", string("abc") C_ 2 C_ string("YYY"), string("1abc3abc2") );
+}
+
+void replace_head_test()
+{
+    // replace head
+    TEST_ALGO( replace_head, "abc3abc2", 3 C_ string("YYY"), string("YYY3abc2") );
+    TEST_ALGO( replace_head, "abc3abc2", -3 C_ string("YYY"), string("YYYbc2") );
+    TEST_ALGO( replace_head, "abc3abc2", 3 C_ "YYY", string("YYY3abc2") );
+    TEST_ALGO( replace_head, "abc", 3 C_ string("Z"), string("Z") );
+    TEST_ALGO( replace_head, "abc", 6 C_ string("XXXX"), string("XXXX") );
+    TEST_ALGO( replace_head, "abc", -6 C_ string("XXXX"), string("abc") );
+    TEST_ALGO( replace_head, "abc3abc2", 0 C_ string("XXXX"), string("abc3abc2") );
+    TEST_ALGO( replace_head, "", 4 C_ string("XXXX"), string("") );
+    TEST_ALGO( replace_head, "", -4 C_ string("XXXX"), string("") );
+    TEST_ALGO( erase_head, "abc3abc2", 3, string("3abc2") );
+    TEST_ALGO( erase_head, "abc3abc2", -3, string("bc2") );
+    TEST_ALGO( erase_head, "abc3abc2", 0, string("abc3abc2") );
+    TEST_ALGO( erase_head, "", 4, string("") );
+    TEST_ALGO( erase_head, "", -4, string("") );
+}
+
+void replace_tail_test()
+{
+    // replace tail
+    TEST_ALGO( replace_tail, "abc3abc", 3 C_ string("YYY"), string("abc3YYY") );
+    TEST_ALGO( replace_tail, "abc3abc", -3 C_ "YYY", string("abcYYY") );
+    TEST_ALGO( replace_tail, "abc", 3 C_ string("Z"), string("Z") );
+    TEST_ALGO( replace_tail, "abc", 6 C_ string("XXXX"), string("XXXX") );
+    TEST_ALGO( replace_tail, "abc", -6 C_ string("XXXX"), string("abc") );
+    TEST_ALGO( replace_tail, "abc3abc", 0 C_ string("XXXX"), string("abc3abc") );
+    TEST_ALGO( replace_tail, "", 4 C_ string("XXXX"), string("") );
+    TEST_ALGO( replace_tail, "", -4 C_ string("XXXX"), string("") );
+    TEST_ALGO( erase_tail, "abc3abc", 3, string("abc3") );
+    TEST_ALGO( erase_tail, "abc3abc", -3, string("abc") );
+    TEST_ALGO( erase_tail, "abc3abc", 0, string("abc3abc") );
+    TEST_ALGO( erase_tail, "", 4, string("") );
+    TEST_ALGO( erase_tail, "", -4, string("") );
+}
+
+void replace_range_test()
+{
+    // replace_range
+    {
+        BOOST_CHECKPOINT( "replace_range" );
+
+        string str1("1abc3abc2");
+        BOOST_CHECK( 
+            replace_range_copy( 
+                str1, 
+                make_iterator_range(str1.begin()+1, str1.begin()+4),
+                string("XXX") )==string("1XXX3abc2") );
+
+        string strout;
+        replace_range_copy( 
+                back_inserter( strout ),
+                str1, 
+                make_iterator_range(str1.begin()+1, str1.begin()+4),
+                string("XXX") );
+        BOOST_CHECK( strout==string("1XXX3abc2") );
+
+        replace_range( 
+                str1, 
+                make_iterator_range(str1.begin()+1, str1.begin()+4),
+                string("XXX") );
+        BOOST_CHECK( str1==string("1XXX3abc2") );
+    }
+    // erase_range
+    {
+        BOOST_CHECKPOINT( "erase_range" );
+
+        string str1("1abc3abc2");
+        BOOST_CHECK( 
+        erase_range_copy( 
+                str1, 
+                make_iterator_range(str1.begin()+1, str1.begin()+4))==string("13abc2") );
+
+        string strout;
+        erase_range_copy( 
+                back_inserter( strout ),
+                str1, 
+                make_iterator_range(str1.begin()+1, str1.begin()+4));
+        BOOST_CHECK( strout==string("13abc2") );
+
+        erase_range( 
+                str1, 
+                make_iterator_range(str1.begin()+1, str1.begin()+4));
+        BOOST_CHECK( str1==string("13abc2") );
+    }
+}
+
+void collection_comp_test()
+{
+    // container traits compatibility tests
+    {
+        string strout;
+        replace_first_copy( back_inserter(strout), "1abc3abc2", "abc", "YYY" );
+        BOOST_CHECK( strout==string("1YYY3abc2") ); 
+    }
+    {
+        string strout;
+        replace_last_copy( back_inserter(strout), "1abc3abc2", "abc", "YYY" );
+        BOOST_CHECK( strout==string("1abc3YYY2") ); 
+    }   
+    {
+        string strout;
+        replace_all_copy( back_inserter(strout), "1abc3abc2", "abc", "YYY" );
+        BOOST_CHECK( strout==string("1YYY3YYY2") ); 
+    }   
+    {
+        string strout;
+        replace_nth_copy( back_inserter(strout), "1abc3abc2", "abc", 1, "YYY" );
+        BOOST_CHECK( strout==string("1abc3YYY2") ); 
+    }   
+    {
+        string strout;
+        replace_head_copy( back_inserter(strout), "abc3abc2", 3 , "YYY" );
+        BOOST_CHECK( strout==string("YYY3abc2") ); 
+    }   
+    {
+        string strout;
+        replace_tail_copy( back_inserter(strout), "abc3abc", 3 , "YYY" );
+        BOOST_CHECK( strout==string("abc3YYY") ); 
+    }   
+}
+
+// test main 
+int test_main( int, char*[] )
+{
+    sequence_traits_test(); 
+    replace_first_test();
+    replace_last_test();
+    replace_all_test();
+    replace_nth_test();
+    replace_head_test();
+    replace_tail_test();
+    replace_range_test();
+    collection_comp_test();
+
+    return 0;
+}

string/test/split_test.cpp

@@ -0,0 +1,133 @@
+//  Boost string_algo library iterator_test.cpp file  ---------------------------//
+
+//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  distribution is subject to the Boost Software License, Version
+//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+#include <boost/algorithm/string/split.hpp>
+#include <boost/algorithm/string/classification.hpp>
+// equals predicate is used for result comparison
+#include <boost/algorithm/string/predicate.hpp>
+
+// Include unit test framework
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <string>
+#include <vector>
+#include <iostream>
+
+#include <boost/test/test_tools.hpp>
+
+
+using namespace std;
+using namespace boost;
+
+template< typename T1, typename T2 >
+void deep_compare( const T1& X, const T2& Y )
+{
+    BOOST_REQUIRE( X.size() == Y.size() );
+    for( unsigned int nIndex=0; nIndex<X.size(); ++nIndex )
+    {
+        BOOST_CHECK( equals( X[nIndex], Y[nIndex] ) );
+    }
+}
+
+void iterator_test()
+{
+    string str1("xx-abc--xx-abb");
+    string str2("Xx-abc--xX-abb-xx");
+    string str3("xx");
+    const char* pch1="xx-abc--xx-abb";
+    vector<string> tokens;
+    vector< vector<int> > vtokens;
+
+    // find_all tests
+    find_all(
+        tokens,
+        pch1,
+        "xx" );
+
+    BOOST_REQUIRE( tokens.size()==2 );
+    BOOST_CHECK( tokens[0]==string("xx") );
+    BOOST_CHECK( tokens[1]==string("xx") );
+
+    ifind_all(
+        tokens,
+        str2,
+        "xx" );
+
+    BOOST_REQUIRE( tokens.size()==3 );
+    BOOST_CHECK( tokens[0]==string("Xx") );
+    BOOST_CHECK( tokens[1]==string("xX") );
+    BOOST_CHECK( tokens[2]==string("xx") );
+
+    find_all(
+        tokens,
+        str1,
+        "xx" );
+
+    BOOST_REQUIRE( tokens.size()==2 );
+    BOOST_CHECK( tokens[0]==string("xx") );
+    BOOST_CHECK( tokens[1]==string("xx") );
+
+    find_all(
+        vtokens,
+        str1,
+        string("xx") );
+    deep_compare( tokens, vtokens );
+
+    // split tests
+    split(
+        tokens,
+        str2,
+        is_any_of("xX"),
+        token_compress_on );
+
+    BOOST_REQUIRE( tokens.size()==4 );
+    BOOST_CHECK( tokens[0]==string("") );
+    BOOST_CHECK( tokens[1]==string("-abc--") );
+    BOOST_CHECK( tokens[2]==string("-abb-") );
+    BOOST_CHECK( tokens[3]==string("") );
+
+    split(
+        tokens,
+        pch1,
+        is_any_of("x"),
+        token_compress_on );
+
+    BOOST_REQUIRE( tokens.size()==3 );
+    BOOST_CHECK( tokens[0]==string("") );
+    BOOST_CHECK( tokens[1]==string("-abc--") );
+    BOOST_CHECK( tokens[2]==string("-abb") );
+
+    split(
+        vtokens,
+        str1,
+        is_any_of("x"),
+        token_compress_on );
+    deep_compare( tokens, vtokens );
+
+    split(
+        tokens,
+        str1,
+        is_punct(),
+        token_compress_off );
+
+    BOOST_REQUIRE( tokens.size()==5 );
+    BOOST_CHECK( tokens[0]==string("xx") );
+    BOOST_CHECK( tokens[1]==string("abc") );
+    BOOST_CHECK( tokens[2]==string("") );
+    BOOST_CHECK( tokens[3]==string("xx") );
+    BOOST_CHECK( tokens[4]==string("abb") );
+}
+
+// test main 
+int test_main( int, char*[] )
+{
+    iterator_test();
+    
+    return 0;
+}

string/test/trim_test.cpp

@@ -0,0 +1,118 @@
+//  Boost string_algo library trim_test.cpp file  ---------------------------//
+
+//  Copyright Pavol Droba 2002-2003. Use, modification and
+//  distribution is subject to the Boost Software License, Version
+//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+#include <boost/algorithm/string/trim.hpp>
+
+// Include unit test framework
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <string>
+#include <iostream>
+#include <boost/test/test_tools.hpp>
+
+using namespace std;
+using namespace boost;
+
+void trim_test()
+{
+    string str1("     1x x x x1     ");
+    string str2("     2x x x x2     ");
+    string str3("    ");
+
+    // *** value passing tests *** //
+
+    // general string test
+    BOOST_CHECK( trim_left_copy( str1 )=="1x x x x1     " ) ;
+    BOOST_CHECK( trim_right_copy( str1 )=="     1x x x x1" ) ;
+    BOOST_CHECK( trim_copy( str1 )=="1x x x x1" ) ;
+
+    // spaces-only string test
+    BOOST_CHECK( trim_left_copy( str3 )=="" );
+    BOOST_CHECK( trim_right_copy( str3 )=="" );
+    BOOST_CHECK( trim_copy( str3 )=="" );
+
+    // empty string check 
+    BOOST_CHECK( trim_left_copy( string("") )=="" );
+    BOOST_CHECK( trim_right_copy( string("") )=="" );
+    BOOST_CHECK( trim_copy( string("") )=="" );
+
+    // iterator tests
+    string str;
+    trim_left_copy_if( std::back_inserter(str), str1, is_space() );
+    BOOST_CHECK( str=="1x x x x1     " );
+
+    str.clear();
+    trim_right_copy_if( std::back_inserter(str), str1, is_space() );
+    BOOST_CHECK( str=="     1x x x x1" );
+
+    str.clear();
+    trim_copy_if( std::back_inserter(str), str1, is_space() );
+    BOOST_CHECK( str=="1x x x x1" );
+
+    str.clear();
+    trim_left_copy_if( 
+        std::back_inserter(str), 
+        "     1x x x x1     ", 
+        is_space() );
+    BOOST_CHECK( str=="1x x x x1     " );
+
+    str.clear();
+    trim_right_copy_if( 
+        std::back_inserter(str), 
+        "     1x x x x1     ", 
+        is_space() );
+    BOOST_CHECK( str=="     1x x x x1" );
+
+    str.clear();
+    trim_copy_if( 
+        std::back_inserter(str), 
+        "     1x x x x1     ", 
+        is_space() );
+    BOOST_CHECK( str=="1x x x x1" );
+    // *** inplace tests *** //
+
+    // general string test
+    trim_left( str1 );
+    BOOST_CHECK( str1=="1x x x x1     " );
+    trim_right( str1 );
+    BOOST_CHECK( str1=="1x x x x1" );
+    trim( str2 );
+    BOOST_CHECK( str2=="2x x x x2" );
+    
+    // spaces-only string test
+    str3 = "    "; trim_left( str3 );
+    BOOST_CHECK( str3=="" );
+    str3 = "    "; trim_right( str3 );
+    BOOST_CHECK( str3=="" );
+    str3 = "    "; trim( str3 );
+    BOOST_CHECK( str3=="" );
+
+    // empty string check 
+    str3 = ""; trim_left( str3 );
+    BOOST_CHECK( str3=="" );
+    str3 = ""; trim_right( str3 );
+    BOOST_CHECK( str3=="" );
+    str3 = ""; trim( str3 );
+    BOOST_CHECK( str3=="" );
+
+    // *** non-standard predicate tests *** //
+    BOOST_CHECK( 
+        trim_copy_if( 
+            string("123abc456"), 
+            is_classified(std::ctype_base::digit) )=="abc" );
+    BOOST_CHECK( trim_copy_if( string("<>abc<>"), is_any_of( "<<>>" ) )=="abc" );
+}
+
+// test main 
+int test_main( int, char*[] )
+{
+    trim_test();
+    
+    return 0;
+}

sublibs

@@ -0,0 +1 @@
+The existance of this file tells the regression reporting programs that the directory contains sub-directories which are libraries.