1 //  Boost string_algo library replace_storage.hpp header file  ---------------------------//
2 
3 //  Copyright Pavol Droba 2002-2003.
4 //
5 // Distributed under the Boost Software License, Version 1.0.
6 //    (See accompanying file LICENSE_1_0.txt or copy at
7 //          http://www.boost.org/LICENSE_1_0.txt)
8 
9 //  See http://www.boost.org/ for updates, documentation, and revision history.
10 
11 #ifndef BOOST_STRING_REPLACE_STORAGE_DETAIL_HPP
12 #define BOOST_STRING_REPLACE_STORAGE_DETAIL_HPP
13 
14 #include <boost/algorithm/string/config.hpp>
15 #include <algorithm>
16 #include <boost/mpl/bool.hpp>
17 #include <boost/algorithm/string/sequence_traits.hpp>
18 #include <boost/algorithm/string/detail/sequence.hpp>
19 
20 namespace boost {
21     namespace algorithm {
22         namespace detail {
23 
24 //  storage handling routines -----------------------------------------------//
25 
26             template< typename StorageT, typename OutputIteratorT >
move_from_storage(StorageT & Storage,OutputIteratorT DestBegin,OutputIteratorT DestEnd)27             inline OutputIteratorT move_from_storage(
28                 StorageT& Storage,
29                 OutputIteratorT DestBegin,
30                 OutputIteratorT DestEnd )
31             {
32                 OutputIteratorT OutputIt=DestBegin;
33 
34                 while( !Storage.empty() && OutputIt!=DestEnd )
35                 {
36                     *OutputIt=Storage.front();
37                     Storage.pop_front();
38                     ++OutputIt;
39                 }
40 
41                 return OutputIt;
42             }
43 
44             template< typename StorageT, typename WhatT >
copy_to_storage(StorageT & Storage,const WhatT & What)45             inline void copy_to_storage(
46                 StorageT& Storage,
47                 const WhatT& What )
48             {
49                 Storage.insert( Storage.end(), ::boost::begin(What), ::boost::end(What) );
50             }
51 
52 
53 //  process segment routine -----------------------------------------------//
54 
55             template< bool HasStableIterators >
56             struct process_segment_helper
57             {
58                 // Optimized version of process_segment for generic sequence
59                 template<
60                     typename StorageT,
61                     typename InputT,
62                     typename ForwardIteratorT >
operator ()boost::algorithm::detail::process_segment_helper63                 ForwardIteratorT operator()(
64                     StorageT& Storage,
65                     InputT& /*Input*/,
66                     ForwardIteratorT InsertIt,
67                     ForwardIteratorT SegmentBegin,
68                     ForwardIteratorT SegmentEnd )
69                 {
70                     // Copy data from the storage until the beginning of the segment
71                     ForwardIteratorT It=::boost::algorithm::detail::move_from_storage( Storage, InsertIt, SegmentBegin );
72 
73                     // 3 cases are possible :
74                     //   a) Storage is empty, It==SegmentBegin
75                     //   b) Storage is empty, It!=SegmentBegin
76                     //   c) Storage is not empty
77 
78                     if( Storage.empty() )
79                     {
80                         if( It==SegmentBegin )
81                         {
82                             // Case a) everything is grand, just return end of segment
83                             return SegmentEnd;
84                         }
85                         else
86                         {
87                             // Case b) move the segment backwards
88                             return std::copy( SegmentBegin, SegmentEnd, It );
89                         }
90                     }
91                     else
92                     {
93                         // Case c) -> shift the segment to the left and keep the overlap in the storage
94                         while( It!=SegmentEnd )
95                         {
96                             // Store value into storage
97                             Storage.push_back( *It );
98                             // Get the top from the storage and put it here
99                             *It=Storage.front();
100                             Storage.pop_front();
101 
102                             // Advance
103                             ++It;
104                         }
105 
106                         return It;
107                     }
108                 }
109             };
110 
111             template<>
112             struct process_segment_helper< true >
113             {
114                 // Optimized version of process_segment for list-like sequence
115                 template<
116                     typename StorageT,
117                     typename InputT,
118                     typename ForwardIteratorT >
operator ()boost::algorithm::detail::process_segment_helper119                 ForwardIteratorT operator()(
120                     StorageT& Storage,
121                     InputT& Input,
122                     ForwardIteratorT InsertIt,
123                     ForwardIteratorT SegmentBegin,
124                     ForwardIteratorT SegmentEnd )
125 
126                 {
127                     // Call replace to do the job
128                     ::boost::algorithm::detail::replace( Input, InsertIt, SegmentBegin, Storage );
129                     // Empty the storage
130                     Storage.clear();
131                     // Iterators were not changed, simply return the end of segment
132                     return SegmentEnd;
133                 }
134             };
135 
136             // Process one segment in the replace_all algorithm
137             template<
138                 typename StorageT,
139                 typename InputT,
140                 typename ForwardIteratorT >
process_segment(StorageT & Storage,InputT & Input,ForwardIteratorT InsertIt,ForwardIteratorT SegmentBegin,ForwardIteratorT SegmentEnd)141             inline ForwardIteratorT process_segment(
142                 StorageT& Storage,
143                 InputT& Input,
144                 ForwardIteratorT InsertIt,
145                 ForwardIteratorT SegmentBegin,
146                 ForwardIteratorT SegmentEnd )
147             {
148                 return
149                     process_segment_helper<
150                         has_stable_iterators<InputT>::value>()(
151                                 Storage, Input, InsertIt, SegmentBegin, SegmentEnd );
152             }
153 
154 
155         } // namespace detail
156     } // namespace algorithm
157 } // namespace boost
158 
159 #endif  // BOOST_STRING_REPLACE_STORAGE_DETAIL_HPP
160