string/detail/replace_storage.hpp

0001 //  Boost string_algo library replace_storage.hpp header file  ---------------------------//
0002
0003 //  Copyright Pavol Droba 2002-2003.
0004 //
0005 // Distributed under the Boost Software License, Version 1.0.
0006 //    (See accompanying file LICENSE_1_0.txt or copy at
0007 //          http://www.boost.org/LICENSE_1_0.txt)
0008
0009 //  See http://www.boost.org/ for updates, documentation, and revision history.
0010
0011 #ifndef BOOST_STRING_REPLACE_STORAGE_DETAIL_HPP
0012 #define BOOST_STRING_REPLACE_STORAGE_DETAIL_HPP
0013
0014 #include <boost/algorithm/string/config.hpp>
0015 #include <algorithm>
0016 #include <boost/mpl/bool.hpp>
0017 #include <boost/algorithm/string/sequence_traits.hpp>
0018 #include <boost/algorithm/string/detail/sequence.hpp>
0019
0020 namespace boost {
0021     namespace algorithm {
0022         namespace detail {
0023
0024 //  storage handling routines -----------------------------------------------//
0025
0026             template< typename StorageT, typename OutputIteratorT >
0027             inline OutputIteratorT move_from_storage(
0028                 StorageT& Storage,
0029                 OutputIteratorT DestBegin,
0030                 OutputIteratorT DestEnd )
0031             {
0032                 OutputIteratorT OutputIt=DestBegin;
0033
0034                 while( !Storage.empty() && OutputIt!=DestEnd )
0035                 {
0036                     *OutputIt=Storage.front();
0037                     Storage.pop_front();
0038                     ++OutputIt;
0039                 }
0040
0041                 return OutputIt;
0042             }
0043
0044             template< typename StorageT, typename WhatT >
0045             inline void copy_to_storage(
0046                 StorageT& Storage,
0047                 const WhatT& What )
0048             {
0049                 Storage.insert( Storage.end(), ::boost::begin(What), ::boost::end(What) );
0050             }
0051
0052
0053 //  process segment routine -----------------------------------------------//
0054
0055             template< bool HasStableIterators >
0056             struct process_segment_helper
0057             {
0058                 // Optimized version of process_segment for generic sequence
0059                 template<
0060                     typename StorageT,
0061                     typename InputT,
0062                     typename ForwardIteratorT >
0063                 ForwardIteratorT operator()(
0064                     StorageT& Storage,
0065                     InputT& /*Input*/,
0066                     ForwardIteratorT InsertIt,
0067                     ForwardIteratorT SegmentBegin,
0068                     ForwardIteratorT SegmentEnd )
0069                 {
0070                     // Copy data from the storage until the beginning of the segment
0071                     ForwardIteratorT It=::boost::algorithm::detail::move_from_storage( Storage, InsertIt, SegmentBegin );
0072
0073                     // 3 cases are possible :
0074                     //   a) Storage is empty, It==SegmentBegin
0075                     //   b) Storage is empty, It!=SegmentBegin
0076                     //   c) Storage is not empty
0077
0078                     if( Storage.empty() )
0079                     {
0080                         if( It==SegmentBegin )
0081                         {
0082                             // Case a) everything is grand, just return end of segment
0083                             return SegmentEnd;
0084                         }
0085                         else
0086                         {
0087                             // Case b) move the segment backwards
0088                             return std::copy( SegmentBegin, SegmentEnd, It );
0089                         }
0090                     }
0091                     else
0092                     {
0093                         // Case c) -> shift the segment to the left and keep the overlap in the storage
0094                         while( It!=SegmentEnd )
0095                         {
0096                             // Store value into storage
0097                             Storage.push_back( *It );
0098                             // Get the top from the storage and put it here
0099                             *It=Storage.front();
0100                             Storage.pop_front();
0101
0102                             // Advance
0103                             ++It;
0104                         }
0105
0106                         return It;
0107                     }
0108                 }
0109             };
0110
0111             template<>
0112             struct process_segment_helper< true >
0113             {
0114                 // Optimized version of process_segment for list-like sequence
0115                 template<
0116                     typename StorageT,
0117                     typename InputT,
0118                     typename ForwardIteratorT >
0119                 ForwardIteratorT operator()(
0120                     StorageT& Storage,
0121                     InputT& Input,
0122                     ForwardIteratorT InsertIt,
0123                     ForwardIteratorT SegmentBegin,
0124                     ForwardIteratorT SegmentEnd )
0125
0126                 {
0127                     // Call replace to do the job
0128                     ::boost::algorithm::detail::replace( Input, InsertIt, SegmentBegin, Storage );
0129                     // Empty the storage
0130                     Storage.clear();
0131                     // Iterators were not changed, simply return the end of segment
0132                     return SegmentEnd;
0133                 }
0134             };
0135
0136             // Process one segment in the replace_all algorithm
0137             template<
0138                 typename StorageT,
0139                 typename InputT,
0140                 typename ForwardIteratorT >
0141             inline ForwardIteratorT process_segment(
0142                 StorageT& Storage,
0143                 InputT& Input,
0144                 ForwardIteratorT InsertIt,
0145                 ForwardIteratorT SegmentBegin,
0146                 ForwardIteratorT SegmentEnd )
0147             {
0148                 return
0149                     process_segment_helper<
0150                         has_stable_iterators<InputT>::value>()(
0151                                 Storage, Input, InsertIt, SegmentBegin, SegmentEnd );
0152             }
0153
0154
0155         } // namespace detail
0156     } // namespace algorithm
0157 } // namespace boost
0158
0159 #endif  // BOOST_STRING_REPLACE_STORAGE_DETAIL_HPP