12ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh// Boost string_algo library sequence.hpp header file ---------------------------// 22ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 32ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh// Copyright Pavol Droba 2002-2003. 42ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh// 52ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh// Distributed under the Boost Software License, Version 1.0. 62ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh// (See accompanying file LICENSE_1_0.txt or copy at 72ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh// http://www.boost.org/LICENSE_1_0.txt) 82ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 92ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh// See http://www.boost.org/ for updates, documentation, and revision history. 102ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 112ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh#ifndef BOOST_STRING_DETAIL_SEQUENCE_HPP 122ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh#define BOOST_STRING_DETAIL_SEQUENCE_HPP 132ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 142ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh#include <boost/algorithm/string/config.hpp> 152ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh#include <boost/mpl/bool.hpp> 162ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh#include <boost/mpl/logical.hpp> 172ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh#include <boost/range/begin.hpp> 182ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh#include <boost/range/end.hpp> 192ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 202ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh#include <boost/algorithm/string/sequence_traits.hpp> 212ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 222ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsiehnamespace boost { 232ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh namespace algorithm { 242ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh namespace detail { 252ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 262ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh// insert helpers -------------------------------------------------// 272ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 282ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh template< typename InputT, typename ForwardIteratorT > 292ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh inline void insert( 302ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh InputT& Input, 312ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator At, 322ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh ForwardIteratorT Begin, 332ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh ForwardIteratorT End ) 342ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 352ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh Input.insert( At, Begin, End ); 362ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 372ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 382ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh template< typename InputT, typename InsertT > 392ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh inline void insert( 402ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh InputT& Input, 412ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator At, 422ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh const InsertT& Insert ) 432ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 442ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh ::boost::algorithm::detail::insert( Input, At, ::boost::begin(Insert), ::boost::end(Insert) ); 452ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 462ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 472ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh// erase helper ---------------------------------------------------// 482ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 492ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh // Erase a range in the sequence 502ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh /* 512ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh Returns the iterator pointing just after the erase subrange 522ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh */ 532ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh template< typename InputT > 542ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh inline typename InputT::iterator erase( 552ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh InputT& Input, 562ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator From, 572ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator To ) 582ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 592ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh return Input.erase( From, To ); 602ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 612ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 622ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh// replace helper implementation ----------------------------------// 632ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 642ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh // Optimized version of replace for generic sequence containers 652ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh // Assumption: insert and erase are expensive 662ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh template< bool HasConstTimeOperations > 672ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh struct replace_const_time_helper 682ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 692ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh template< typename InputT, typename ForwardIteratorT > 702ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh void operator()( 712ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh InputT& Input, 722ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator From, 732ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator To, 742ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh ForwardIteratorT Begin, 752ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh ForwardIteratorT End ) 762ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 772ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh // Copy data to the container ( as much as possible ) 782ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh ForwardIteratorT InsertIt=Begin; 792ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator InputIt=From; 802ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh for(; InsertIt!=End && InputIt!=To; InsertIt++, InputIt++ ) 812ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 822ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh *InputIt=*InsertIt; 832ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 842ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 852ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh if ( InsertIt!=End ) 862ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 872ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh // Replace sequence is longer, insert it 882ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh Input.insert( InputIt, InsertIt, End ); 892ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 902ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh else 912ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 922ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh if ( InputIt!=To ) 932ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 942ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh // Replace sequence is shorter, erase the rest 952ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh Input.erase( InputIt, To ); 962ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 972ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 982ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 992ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh }; 1002ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 1012ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh template<> 1022ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh struct replace_const_time_helper< true > 1032ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 1042ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh // Const-time erase and insert methods -> use them 1052ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh template< typename InputT, typename ForwardIteratorT > 1062ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh void operator()( 1072ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh InputT& Input, 1082ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator From, 1092ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator To, 1102ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh ForwardIteratorT Begin, 1112ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh ForwardIteratorT End ) 1122ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 1132ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator At=Input.erase( From, To ); 1142ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh if ( Begin!=End ) 1152ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 1162ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh if(!Input.empty()) 1172ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 1182ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh Input.insert( At, Begin, End ); 1192ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 1202ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh else 1212ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 1222ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh Input.insert( Input.begin(), Begin, End ); 1232ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 1242ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 1252ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 1262ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh }; 1272ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 1282ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh // No native replace method 1292ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh template< bool HasNative > 1302ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh struct replace_native_helper 1312ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 1322ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh template< typename InputT, typename ForwardIteratorT > 1332ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh void operator()( 1342ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh InputT& Input, 1352ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator From, 1362ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator To, 1372ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh ForwardIteratorT Begin, 1382ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh ForwardIteratorT End ) 1392ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 1402ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh replace_const_time_helper< 1412ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh boost::mpl::and_< 1422ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh has_const_time_insert<InputT>, 1432ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh has_const_time_erase<InputT> >::value >()( 1442ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh Input, From, To, Begin, End ); 1452ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 1462ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh }; 1472ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 1482ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh // Container has native replace method 1492ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh template<> 1502ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh struct replace_native_helper< true > 1512ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 1522ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh template< typename InputT, typename ForwardIteratorT > 1532ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh void operator()( 1542ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh InputT& Input, 1552ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator From, 1562ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator To, 1572ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh ForwardIteratorT Begin, 1582ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh ForwardIteratorT End ) 1592ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 1602ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh Input.replace( From, To, Begin, End ); 1612ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 1622ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh }; 1632ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 1642ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh// replace helper -------------------------------------------------// 1652ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 1662ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh template< typename InputT, typename ForwardIteratorT > 1672ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh inline void replace( 1682ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh InputT& Input, 1692ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator From, 1702ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator To, 1712ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh ForwardIteratorT Begin, 1722ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh ForwardIteratorT End ) 1732ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 1742ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh replace_native_helper< has_native_replace<InputT>::value >()( 1752ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh Input, From, To, Begin, End ); 1762ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 1772ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 1782ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh template< typename InputT, typename InsertT > 1792ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh inline void replace( 1802ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh InputT& Input, 1812ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator From, 1822ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh BOOST_STRING_TYPENAME InputT::iterator To, 1832ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh const InsertT& Insert ) 1842ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 1852ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh if(From!=To) 1862ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 1872ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh ::boost::algorithm::detail::replace( Input, From, To, ::boost::begin(Insert), ::boost::end(Insert) ); 1882ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 1892ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh else 1902ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh { 1912ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh ::boost::algorithm::detail::insert( Input, From, ::boost::begin(Insert), ::boost::end(Insert) ); 1922ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 1932ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } 1942ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 1952ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } // namespace detail 1962ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh } // namespace algorithm 1972ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh} // namespace boost 1982ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 1992ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh 2002ca0e41376e99ad53c02fdb5333339ad3dcad19fAndrew Hsieh#endif // BOOST_STRING_DETAIL_SEQUENCE_HPP 201