Compare commits

..
Author SHA1 Message Date
Hartmut Kaiser 6793a2dbc6 Removed part of the Boost files from the SPIRIT_MINIBOOST branch.
[SVN r26365]
2004-11-30 07:20:44 +00:00
Hartmut Kaiser 8e0c30cae2 Removed part of the Boost files from the SPIRIT_MINIBOOST branch.
[SVN r26352]
2004-11-29 15:59:10 +00:00
nobody 069fb87a55 This commit was manufactured by cvs2svn to create branch
'SPIRIT_MINIBOOST'.

[SVN r26343]
2004-11-29 07:29:20 +00:00
Aleksey Gurtovoy 747597c7ef merge RC_1_32_0 fixes
[SVN r26328]
2004-11-28 03:35:12 +00:00
Pavol Droba 72b4390091 regex_finder and regex_fomatter pulled to the boost namespace
[SVN r25877]
2004-10-26 21:41:00 +00:00
Pavol Droba 77ae41a18a Invalid include fixed
[SVN r25672]
2004-10-11 18:30:21 +00:00
Pavol Droba 5d1448f3ac unused parameter warning removal
[SVN r25671]
2004-10-11 18:28:21 +00:00
Aleksey Gurtovoy 0a0facd7c7 c++boost.gif -> boost.png replacement
[SVN r25573]
2004-10-05 15:45:52 +00:00
Joaquín M. López Muñoz 053cc53eea workaround for a problem of GCC 2.95 with local scope using directives
[SVN r25077]
2004-09-14 07:15:51 +00:00
Douglas Gregor 54ac5bebd3 Fix stylesheet link
[SVN r25048]
2004-09-13 15:44:23 +00:00
Pavol Droba 3542f868a0 Problematic std::distance removed
[SVN r25008]
2004-09-10 13:23:32 +00:00
Pavol Droba 4d346d43ad Explicit namespace qualification added to std::distance calls
(hoping to resolve vc7 problem)


[SVN r24953]
2004-09-07 10:30:41 +00:00
Aleksey Gurtovoy 56862b0bcc merge new MPL version from 'mplbook' branch
[SVN r24874]
2004-09-02 15:41:37 +00:00
Pavol Droba 108365abe7 Attempt to fix "Empty sequence after erase problem" reported by vc8.0
[SVN r24835]
2004-08-31 07:43:02 +00:00
Pavol Droba fa09dddc75 More general fix for vc8.0
[SVN r24765]
2004-08-26 16:03:48 +00:00
Pavol Droba 6fb58192d7 Fix fix
[SVN r24678]
2004-08-23 18:52:36 +00:00
Pavol Droba 792b4eae88 Attempt to fix iterator problem detected by VC8.0
[SVN r24677]
2004-08-23 18:46:28 +00:00
Pavol Droba a23ae6316f Licence from authors of previous versions changed to BSL (according to blanket-permission.txt)
[SVN r24479]
2004-08-14 23:02:20 +00:00
Rene Rivera 5063e96367 Work around problems with the CW8 preprocessor by not using BOOST_PP.
[SVN r24326]
2004-08-06 15:50:35 +00:00
Pavol Droba 5221839b71 tabs removed
[SVN r24272]
2004-08-03 17:28:02 +00:00
Pavol Droba ba00033cbf Addtional credits
[SVN r24271]
2004-08-03 17:23:43 +00:00
Pavol Droba 047a42934d Incorrect examples fixed
[SVN r24270]
2004-08-03 17:09:28 +00:00
Pavol Droba 747b4e17cc Small fix to make vacpp happy
[SVN r24245]
2004-08-02 10:32:37 +00:00
Pavol Droba 4c0efd3d1a Small optimization of equal() functions.
[SVN r24185]
2004-07-30 07:46:11 +00:00
Pavol Droba 67f7273ab3 replace_test() function splitted to smaller chuncks.
[SVN r24184]
2004-07-30 07:44:43 +00:00
Rene Rivera ce6a647dd0 Work-around for CW8 problems with static_cast of references to templates.
[SVN r24178]
2004-07-30 04:32:43 +00:00
Hervé Brönnimann 246794db2a Added copyright notices.
[SVN r24171]
2004-07-29 20:27:38 +00:00
Pavol Droba 325fa64dc3 Licence fixed
[SVN r24152]
2004-07-29 07:38:27 +00:00
Rene Rivera 33122fefa7 Fix tabs in file.
[SVN r24039]
2004-07-25 15:09:51 +00:00
Hervé Brönnimann 4b3118ed2b Added BOOST_EXPLICIT_TEMPLATE_TYPE(Value) to fix MSVC (thanks to Joaquin
Munoz)


[SVN r23998]
2004-07-23 17:17:37 +00:00
Hervé Brönnimann 85e0e920bf Removed char* name and dependence on iostream, not appropriate for test
suite (relic of example and debugging).


[SVN r23996]
2004-07-23 16:13:43 +00:00
Joaquín M. López Muñoz 483bc9e231 replaced tuple::get memfun with equivalent global function so as to cover MSVC
[SVN r23956]
2004-07-22 13:43:01 +00:00
Joaquín M. López Muñoz 643c793f3b added a fix for compilers without PTS
[SVN r23955]
2004-07-22 13:39:25 +00:00
Joaquín M. López Muñoz 825468bc42 added an #include for Boost.Ref
[SVN r23954]
2004-07-22 13:37:47 +00:00
Hervé Brönnimann 69339b779c Removed initialization from singular iterator.
[SVN r23910]
2004-07-21 17:23:40 +00:00
Hervé Brönnimann 7a88ef8658 Now includes minmax_test in the test suite.
[SVN r23909]
2004-07-21 17:15:40 +00:00
Hervé Brönnimann 2b2086dd8f Why were these committed in the first place???
[SVN r23908]
2004-07-21 16:48:41 +00:00
Dave Abrahams bfa0f28830 bugfix from Stefan Slapeta <stefan_nospam_@slapeta.com>
[SVN r23887]
2004-07-21 11:18:16 +00:00
Vladimir Prus f16de45e46 Don't copy default-initialized iterator, which might be singlular.
[SVN r23843]
2004-07-20 13:42:31 +00:00
Aleksey Gurtovoy f6752d3ae1 change test-suite names to match library names
[SVN r23820]
2004-07-20 01:41:00 +00:00
Pavol Droba 961e8b399e Applying patches from Daniel James
[SVN r23631]
2004-07-16 14:10:08 +00:00
Pavol Droba 21440d1b17 Appying patch from Danie James
[SVN r23630]
2004-07-16 13:57:40 +00:00
Pavol Droba cc72a93094 tabs removed
[SVN r23618]
2004-07-16 09:08:21 +00:00
Pavol Droba 9fd4119efc Tabs removed
[SVN r23617]
2004-07-16 09:06:39 +00:00
Pavol Droba 00d09671f5 Library name fixed
[SVN r23613]
2004-07-16 07:51:36 +00:00
Pavol Droba 4e55a78e2d Small comment typo removed
[SVN r23609]
2004-07-15 22:24:39 +00:00
Pavol Droba 48e65026d9 Comment fixed
[SVN r23608]
2004-07-15 22:22:25 +00:00
Pavol Droba fb182c2566 Fixing documentation grammar and spelling
[SVN r23606]
2004-07-15 21:48:25 +00:00
Pavol Droba d97ff92ae4 Fixing grammar and typos
[SVN r23605]
2004-07-15 21:47:22 +00:00
Pavol Droba ddd9baba60 Library documentation index added
- Automatic redirection to boost-book generated docs


[SVN r23565]
2004-07-14 23:01:01 +00:00
Pavol Droba 3786aa8b04 string-text library category added
[SVN r23564]
2004-07-14 22:57:55 +00:00
Pavol Droba cc683155c7 Spellchecker applied
[SVN r23562]
2004-07-14 22:24:12 +00:00
Pavol Droba dd8d053685 Some spelling errors fixed.
[SVN r23560]
2004-07-14 22:17:10 +00:00
Pavol Droba 54075a951b Documentation update
[SVN r23559]
2004-07-14 21:46:50 +00:00
Pavol Droba 8cf6df3ad6 documentation update.
added remarks about the exception safety


[SVN r23558]
2004-07-14 21:28:31 +00:00
Pavol Droba caad29f22a Added vacpp workaround for static constants
[SVN r23557]
2004-07-14 21:21:54 +00:00
Pavol Droba 06474a276d Fixed construction to not restrict usage of iterators, that are not
default constructible


[SVN r23497]
2004-07-13 15:14:35 +00:00
Pavol Droba 4185e3fb31 Fixed dangling pointer problem
[SVN r23495]
2004-07-13 15:00:36 +00:00
Pavol Droba 905cbf4a38 find_all char* test case added
[SVN r23494]
2004-07-13 14:59:43 +00:00
Pavol Droba ccce29ecf5 Trying to avoid Intel crash
[SVN r23484]
2004-07-13 14:20:06 +00:00
Pavol Droba 029851b0ce Comments cleanup
[SVN r23447]
2004-07-11 22:07:00 +00:00
Pavol Droba 22b59d1848 Grouping documentation for overloaded functions
[SVN r23385]
2004-07-06 21:28:01 +00:00
Pavol Droba 8242b4ba5a -predicate_facade moved to a separate header
-composition operators for classification predicates moved
 to the same namespace as predicate_facade


[SVN r23382]
2004-07-06 19:52:18 +00:00
Hervé Brönnimann a568d32ba9 Cleanup Jamfile
[SVN r23341]
2004-07-04 22:24:17 +00:00
Hervé Brönnimann 9dcf3e6b76 Cleanup html, dates, grammar, synopsis code. --Herve'
[SVN r23339]
2004-07-04 22:08:29 +00:00
Pavol Droba 113c676eef std::facet requirement added
[SVN r23324]
2004-07-03 10:40:39 +00:00
Pavol Droba b108993f89 std::locale requirement added
[SVN r23323]
2004-07-03 10:32:14 +00:00
Pavol Droba 81044b4233 Metrowerks workaround added
[SVN r23322]
2004-07-03 10:31:01 +00:00
Eric Niebler 71d18481dd move BOOST_USING_STD_MIN and _MAX and BOOST_PREVENT_MACRO_SUBSTITUTION to the config headers, remove boost/minmax.hpp, update coding guidelines
[SVN r23313]
2004-07-02 01:21:32 +00:00
Hervé Brönnimann 16f4b20083 Testing minmax_element only.
[SVN r23310]
2004-07-01 20:52:50 +00:00
Hervé Brönnimann e0d1f0692d Spearated into two files due to the dependence on the tuple library.
Minor changes to minmax.hpp (again tuple). --Herve'


[SVN r23309]
2004-07-01 20:16:38 +00:00
Hervé Brönnimann cf85da14ed Documentation for the minmax library.
Moved from libs/minmax/ to libs/algorithm/minmax
Also changed documentation to reflect use of Boost.tuple
and separation into two header files. --Herve'


[SVN r23308]
2004-07-01 20:15:51 +00:00
Hervé Brönnimann ec606bbf14 Change pair<T,T> to tuple<T,T> in return type of minmax()
[SVN r23307]
2004-07-01 19:23:33 +00:00
Hervé Brönnimann 729bb65a2d Removed minmax.hpp from boost (leave Eric Niebler's former file)
and move it to subdir boost/algorithm/
Also incorporate boost::ref into boost/algorithm/minmax.hpp  to avoid
copy constructors when params passed by reference.


[SVN r23305]
2004-07-01 18:38:02 +00:00
Hervé Brönnimann 6df2923b40 Remove these files from the libs/directory, and reenter them later in
the libs/algorithm/ subdir. --Herve'


[SVN r23304]
2004-07-01 18:31:21 +00:00
Pavol Droba 6d7d244051 Attempt to add static link requirement added for cwpro8 and cwpro9.
Should fix the problems on these compilers


[SVN r23291]
2004-06-30 20:13:05 +00:00
Hervé Brönnimann 1e7aec2dee Finally adding the minmax library. Still allowing overlap with header
minmax.hpp from Eric Niebler, which should be resolved soon. --Herve'


[SVN r23225]
2004-06-28 08:36:43 +00:00
Eric Niebler 752c65be35 remove std_min and std_max, update minmax coding guidelines
[SVN r23162]
2004-06-23 04:49:48 +00:00
Vladimir Prus 77303abc55 Added V2 Jamfile
[SVN r23070]
2004-06-10 10:02:02 +00:00
Pavol Droba d92e09176c Constructors, accepting a collection added
[SVN r23040]
2004-06-07 09:53:19 +00:00
Pavol Droba bc420c5acf Jamfile updated to reflect new file naming
[SVN r22752]
2004-05-06 20:46:42 +00:00
Pavol Droba d88e251f39 implementation changed to use boost::function instead of own
virtualizer


[SVN r22658]
2004-04-18 18:36:35 +00:00
Pavol Droba 2b30a1063b Forgotten semicolon added
[SVN r22610]
2004-04-06 13:46:44 +00:00
Pavol Droba 25fb28927e error in "no partial template specialization" code fix
[SVN r22597]
2004-04-04 10:29:31 +00:00
Pavol Droba 52d529be56 test includes changed to increase the coverage of library include problems
[SVN r22582]
2004-04-02 16:56:25 +00:00
Pavol Droba ab8ae73bbd missing includes added
[SVN r22581]
2004-04-02 16:51:55 +00:00
Pavol Droba f4427d6e60 Syntax error fixed
[SVN r22579]
2004-04-01 22:37:29 +00:00
Pavol Droba 9198370df5 removed some warnings
[SVN r22556]
2004-03-26 09:16:00 +00:00
Pavol Droba d9f4e3524d make use of partial template specialization where available.
-> fixed metrowerks


[SVN r22555]
2004-03-26 09:14:17 +00:00
Pavol Droba 6dccaf3fcb out-of-range iterator access fix
[SVN r22493]
2004-03-12 22:49:46 +00:00
Pavol Droba 2152f114f4 Test checkpoints rearranged
[SVN r22484]
2004-03-12 10:11:18 +00:00
Pavol Droba a7a04ccd30 boost::iterator_core_access friend declaration fixed
[SVN r22467]
2004-03-09 22:20:56 +00:00
Pavol Droba b1a851f650 multi-type find_regex test enabled
[SVN r22466]
2004-03-09 18:31:56 +00:00
Pavol Droba d7f2660c0c adding a file needed by regression tool to recognize sublibs
[SVN r22465]
2004-03-09 18:26:14 +00:00
Pavol Droba bdc72f04cd Fixing some regression bugs, not directly linked to the library functionality
- Comeau does not know strdup
- Comeau and intel report "\n" as a printable character (isprint('\n')==true)


[SVN r22464]
2004-03-09 18:25:03 +00:00
Pavol Droba 9d1fb3c9ff fixing the fix
[SVN r22463]
2004-03-09 18:09:45 +00:00
Pavol Droba 678183f831 fixed problem with a iterator running out of range
(reported by gcc3.4 as an invalid condition even though the
iterator has not been dereferenced)


[SVN r22462]
2004-03-09 17:58:59 +00:00
Pavol Droba e0776cd359 <string.h> include added - needed for strdup
[SVN r22458]
2004-03-07 17:29:20 +00:00
Pavol Droba 99f50f9d2b is_any_of - std::set instantiation problem fix
[SVN r22457]
2004-03-07 17:27:06 +00:00
Pavol Droba 1c963dac31 unnecessary semicolons removed
[SVN r22456]
2004-03-07 17:22:58 +00:00
Pavol Droba bae34a3fc0 dependend base class problem fix
[SVN r22455]
2004-03-07 17:19:12 +00:00
Pavol Droba 055be9d55d disabling BOOST_STRING_TYPENAME expansion on borland
?will it help?


[SVN r22454]
2004-03-07 17:17:44 +00:00
Beman Dawes 71ffcff092 fix namespace error when no partial specialization
[SVN r22452]
2004-03-07 14:33:56 +00:00
Beman Dawes fdaa15c290 Remove spurious colons which prevent bjam from seeing all of string_algo when string_algo is explicitly specified as a build target
[SVN r22451]
2004-03-07 14:18:27 +00:00
Pavol Droba c945d5ba7b unnecessary "typename" causing gcc3.4 to fail removed
[SVN r22450]
2004-03-07 14:00:21 +00:00
Pavol Droba 6f22693df6 fixing problems with vacpp.
[SVN r22443]
2004-03-06 09:31:42 +00:00
Pavol Droba 03705cb766 fixing jamfile to work with regression tests
[SVN r22440]
2004-03-05 21:31:22 +00:00
Pavol Droba cb41081ce0 cstddef include added to possibly fix gcc 3.4 builds
[SVN r22439]
2004-03-05 21:28:56 +00:00
Pavol Droba 1deef19d55 String Algorithm Library: initial commit
[SVN r22431]
2004-03-04 22:12:19 +00:00
Eric Niebler 3d9b6badea min and max are always in std namespace
[SVN r22425]
2004-03-02 21:38:40 +00:00
Eric Niebler 5a253182c2 make std_min play nice with the Borland headers
[SVN r22410]
2004-02-29 17:46:07 +00:00
Eric Niebler 874f0deaec remove minmax hack from win32.hpp and fix all places that could be affected by the minmax macros
[SVN r22394]
2004-02-26 18:27:02 +00:00
68 changed files with 5839 additions and 3703 deletions
-116
View File
@@ -1,116 +0,0 @@
// (C) Copyright Jesse Williamson 2009
// 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 <boost/config.hpp>
#include <boost/algorithm/all.hpp>
#include <boost/test/included/test_exec_monitor.hpp>
#include <utility>
#include <iostream>
#include <functional>
// This prettyprinter is useful when debugging:
template <class T>
void show(std::vector<T>& v)
{
for(typename std::vector<T>::const_iterator i = v.begin(); i != v.end(); ++i)
std::cout << *i << '\n';
std::cout << "----------" << std::endl;
}
namespace ba = boost::algorithm;
void test_none()
{
// Note: The literal values here are tested against directly, careful if you change them:
int some_numbers[] = { 1, 5, 0, 18, 1 };
std::vector<int> vi(some_numbers, some_numbers + 5);
int some_letters[] = { 'a', 'q', 'n', 'y', 'n' };
std::vector<char> vc(some_letters, some_letters + 5);
BOOST_CHECK_EQUAL ( true, ba::none_of ( vi, 100 ));
BOOST_CHECK_EQUAL ( true, ba::none_of ( vi.begin(), vi.end (), 100 ));
BOOST_CHECK_EQUAL ( false, ba::none_of ( vi, 1 ));
BOOST_CHECK_EQUAL ( false, ba::none_of ( vi.begin (), vi.end(), 1 ));
BOOST_CHECK_EQUAL ( true, ba::none_of ( vi.end (), vi.end (), 0 ));
// 5 is not in { 0, 18, 1 }, but 1 is
BOOST_CHECK_EQUAL ( true, ba::none_of ( vi.begin () + 2, vi.end(), 5 ));
BOOST_CHECK_EQUAL ( false, ba::none_of ( vi.begin () + 2, vi.end(), 1 ));
// 18 is not in { 1, 5, 0 }, but 5 is
BOOST_CHECK_EQUAL ( true, ba::none_of ( vi.begin (), vi.begin() + 3, 18 ));
BOOST_CHECK_EQUAL ( false, ba::none_of ( vi.begin (), vi.begin() + 3, 5 ));
BOOST_CHECK_EQUAL ( true, ba::none_of ( vc, 'z' ));
BOOST_CHECK_EQUAL ( false, ba::none_of ( vc, 'a' ));
// BOOST_CHECK_EQUAL ( true, ba::none_of ( vc, 'n' )); // Better fail!
}
void test_any ()
{
// Note: The literal values here are tested against directly, careful if you change them:
int some_numbers[] = { 1, 5, 0, 18, 10 };
std::vector<int> vi(some_numbers, some_numbers + 5);
int some_letters[] = { 'a', 'q', 'n', 'y', 'n' };
std::vector<char> vc(some_letters, some_letters + 5);
BOOST_CHECK_EQUAL ( true, ba::any_of ( vi, 1 ));
BOOST_CHECK_EQUAL ( true, ba::any_of ( vi.begin(), vi.end (), 1 ));
BOOST_CHECK_EQUAL ( false, ba::any_of ( vi, 9 ));
BOOST_CHECK_EQUAL ( false, ba::any_of ( vi.begin (), vi.end(), 9 ));
BOOST_CHECK_EQUAL ( true, ba::any_of ( vi, 10 ));
BOOST_CHECK_EQUAL ( false, ba::any_of ( vi, 4 ));
BOOST_CHECK_EQUAL ( false, ba::any_of ( vi.end (), vi.end (), 0 ));
// 5 is not in { 0, 18, 10 }, but 10 is
BOOST_CHECK_EQUAL ( true, ba::any_of ( vi.begin () + 2, vi.end(), 10 ));
BOOST_CHECK_EQUAL ( false, ba::any_of ( vi.begin () + 2, vi.end(), 5 ));
// 18 is not in { 1, 5, 0 }, but 5 is
BOOST_CHECK_EQUAL ( true, ba::any_of ( vi.begin (), vi.begin() + 3, 5 ));
BOOST_CHECK_EQUAL ( false, ba::any_of ( vi.begin (), vi.begin() + 3, 18 ));
BOOST_CHECK_EQUAL ( true, ba::any_of (vc, 'q' ));
BOOST_CHECK_EQUAL ( false, ba::any_of (vc, '!' ));
// BOOST_CHECK_EQUAL ( false, ba::any_of (vc, 'n' )); // Better fail!
}
void test_all ()
{
// Note: The literal values here are tested against directly, careful if you change them:
int some_numbers[] = { 1, 1, 1, 18, 10 };
std::vector<int> vi(some_numbers, some_numbers + 5);
int some_letters[] = { 'a', 'q', 'n', 'y', 'n' };
std::vector<char> vc(some_letters, some_letters + 5);
BOOST_CHECK_EQUAL ( false, ba::all_of ( vi, 1 ));
BOOST_CHECK_EQUAL ( false, ba::all_of ( vi.begin(), vi.end (), 1 ));
BOOST_CHECK_EQUAL ( false, ba::all_of ( vi, 0 ));
BOOST_CHECK_EQUAL ( false, ba::all_of ( vi.begin(), vi.end (), 0 ));
BOOST_CHECK_EQUAL ( true, ba::all_of ( vi.end (), vi.end (), 0));
BOOST_CHECK_EQUAL ( true, ba::all_of ( vi.begin (), vi.begin () + 3, 1));
BOOST_CHECK_EQUAL ( true, ba::all_of ( vc.begin () + 1, vc.begin () + 2, 'q' ));
BOOST_CHECK_EQUAL ( false, ba::all_of(vc, '!' ));
// BOOST_CHECK_EQUAL ( true, ba::all_of(vc, 'n' )); // Better fail!
}
int test_main( int , char* [] )
{
test_none();
test_any();
test_all();
return 0;
}
-80
View File
@@ -1,80 +0,0 @@
/*
Copyright (C) 2008 Jesse Williamson
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 <boost/test/included/test_exec_monitor.hpp>
#include <boost/algorithm/apply.hpp>
#include <list>
#include <vector>
#include <numeric>
#include <iostream>
using namespace std;
using namespace boost::algorithm::sequence;
int make_zero(int x)
{
return 0;
}
string make_z(string x)
{
return "z";
}
int test_main(int, char **)
{
// Basic test:
{
vector<int> v(3);
// Should work on a single element:
BOOST_CHECK(apply(v.begin(), v.begin(), make_zero));
BOOST_CHECK(0 == accumulate(v.begin(), v.end(), 0));
v[0] = 1;
v[1] = 2;
v[2] = 3;
BOOST_CHECK(apply(v.begin(), v.end(), make_zero));
BOOST_CHECK(0 == accumulate(v.begin(), v.end(), 0));
// Use a conditional function (apply_if()), and do not modify the sequence:
v[0] = 10;
v[1] = 2;
v[2] = 10;
BOOST_CHECK(apply_if(v.begin(), v.end(), make_zero, std::bind1st(std::not_equal_to<int>(), 10)));
BOOST_CHECK(20 == accumulate(v.begin(), v.end(), 0) && 0 == v[1] && 3 == v.size());
}
// Basic range test:
{
vector<int> v(128);
generate(v.begin(), v.end(), rand);
BOOST_CHECK(apply(v, make_zero));
BOOST_CHECK(0 == accumulate(v.begin(), v.end(), 0));
}
{
list<string> ls;
const char *s[] = { "hello", "there", "world", "!\n" };
copy(s, s + 4, back_inserter(ls));
apply(ls.begin(), ls.end(), make_z);
BOOST_CHECK(accumulate(ls.begin(), ls.end(), string()) == "zzzz");
}
return 0;
}
-18
View File
@@ -1,18 +0,0 @@
# Boost.All Library test Jamfile
#
# Copyright (C) 2009 Jesse Williamson
#
# 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/clamp:
: [ run clamp_test.cpp
: : : : clamp ]
;
}
-112
View File
@@ -1,112 +0,0 @@
// (C) Copyright Jesse Williamson 2009
// 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 <iostream>
#include <boost/config.hpp>
#include <boost/algorithm/clamp.hpp>
#include <boost/test/included/test_exec_monitor.hpp>
namespace ba = boost::algorithm;
void test_ints()
{
// Inside the range, equal to the endpoints, and outside the endpoints.
BOOST_CHECK_EQUAL ( 3, ba::clamp ( 3, 1, 10 ));
BOOST_CHECK_EQUAL ( 1, ba::clamp ( 1, 1, 10 ));
BOOST_CHECK_EQUAL ( 1, ba::clamp ( 0, 1, 10 ));
BOOST_CHECK_EQUAL ( 10, ba::clamp ( 10, 1, 10 ));
BOOST_CHECK_EQUAL ( 10, ba::clamp ( 11, 1, 10 ));
// Negative numbers
BOOST_CHECK_EQUAL ( -3, ba::clamp ( -3, -10, -1 ));
BOOST_CHECK_EQUAL ( -1, ba::clamp ( -1, -10, -1 ));
BOOST_CHECK_EQUAL ( -1, ba::clamp ( 0, -10, -1 ));
BOOST_CHECK_EQUAL ( -10, ba::clamp ( -10, -10, -1 ));
BOOST_CHECK_EQUAL ( -10, ba::clamp ( -11, -10, -1 ));
// Mixed positive and negative numbers
BOOST_CHECK_EQUAL ( 5, ba::clamp ( 5, -10, 10 ));
BOOST_CHECK_EQUAL ( -10, ba::clamp ( -10, -10, 10 ));
BOOST_CHECK_EQUAL ( -10, ba::clamp ( -15, -10, 10 ));
BOOST_CHECK_EQUAL ( 10, ba::clamp ( 10, -10, 10 ));
BOOST_CHECK_EQUAL ( 10, ba::clamp ( 15, -10, 10 ));
// Unsigned
BOOST_CHECK_EQUAL ( 5U, ba::clamp ( 5U, 1U, 10U ));
BOOST_CHECK_EQUAL ( 1U, ba::clamp ( 1U, 1U, 10U ));
BOOST_CHECK_EQUAL ( 1U, ba::clamp ( 0U, 1U, 10U ));
BOOST_CHECK_EQUAL ( 10U, ba::clamp ( 10U, 1U, 10U ));
BOOST_CHECK_EQUAL ( 10U, ba::clamp ( 15U, 1U, 10U ));
}
void test_floats()
{
// Inside the range, equal to the endpoints, and outside the endpoints.
BOOST_CHECK_EQUAL ( 3.0, ba::clamp ( 3.0, 1.0, 10.0 ));
BOOST_CHECK_EQUAL ( 1.0, ba::clamp ( 1.0, 1.0, 10.0 ));
BOOST_CHECK_EQUAL ( 1.0, ba::clamp ( 0.0, 1.0, 10.0 ));
BOOST_CHECK_EQUAL ( 10.0, ba::clamp ( 10.0, 1.0, 10.0 ));
BOOST_CHECK_EQUAL ( 10.0, ba::clamp ( 11.0, 1.0, 10.0 ));
// Negative numbers
BOOST_CHECK_EQUAL ( -3.f, ba::clamp ( -3.f, -10.f, -1.f ));
BOOST_CHECK_EQUAL ( -1.f, ba::clamp ( -1.f, -10.f, -1.f ));
BOOST_CHECK_EQUAL ( -1.f, ba::clamp ( 0.f, -10.f, -1.f ));
BOOST_CHECK_EQUAL ( -10.f, ba::clamp ( -10.f, -10.f, -1.f ));
BOOST_CHECK_EQUAL ( -10.f, ba::clamp ( -11.f, -10.f, -1.f ));
// Mixed positive and negative numbers
BOOST_CHECK_EQUAL ( 5.f, ba::clamp ( 5.f, -10.f, 10.f ));
BOOST_CHECK_EQUAL ( -10.f, ba::clamp ( -10.f, -10.f, 10.f ));
BOOST_CHECK_EQUAL ( -10.f, ba::clamp ( -15.f, -10.f, 10.f ));
BOOST_CHECK_EQUAL ( 10.f, ba::clamp ( 10.f, -10.f, 10.f ));
BOOST_CHECK_EQUAL ( 10.f, ba::clamp ( 15.f, -10.f, 10.f ));
}
class custom {
public:
custom ( int x ) : v(x) {}
custom ( const custom &rhs ) : v(rhs.v) {}
~custom () {}
custom & operator = ( const custom &rhs ) { v = rhs.v; return *this; }
bool operator < ( const custom &rhs ) const { return v < rhs.v; }
bool operator == ( const custom &rhs ) const { return v == rhs.v; } // need this for the test
std::ostream & print ( std::ostream &os ) const { return os << v; }
private:
int v;
};
std::ostream & operator << ( std::ostream & os, const custom &x ) { return x.print ( os ); }
void test_custom()
{
// Inside the range, equal to the endpoints, and outside the endpoints.
BOOST_CHECK_EQUAL ( custom( 3), ba::clamp ( custom( 3), custom(1), custom(10)));
BOOST_CHECK_EQUAL ( custom( 1), ba::clamp ( custom( 1), custom(1), custom(10)));
BOOST_CHECK_EQUAL ( custom( 1), ba::clamp ( custom( 0), custom(1), custom(10)));
BOOST_CHECK_EQUAL ( custom(10), ba::clamp ( custom(10), custom(1), custom(10)));
BOOST_CHECK_EQUAL ( custom(10), ba::clamp ( custom(11), custom(1), custom(10)));
// Fail!!
// BOOST_CHECK_EQUAL ( custom(1), ba::clamp ( custom(11), custom(1), custom(10)));
}
int test_main( int , char* [] )
{
test_ints ();
test_floats ();
test_custom ();
return 0;
}
-18
View File
@@ -1,18 +0,0 @@
# Boost.CopyIf Library test Jamfile
#
# Copyright (C) 2008 Marshall Clow
#
# 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/copy:
: [ run copy_test.cpp
: : : : copy ]
;
}
-252
View File
@@ -1,252 +0,0 @@
// (C) Copyright Marshall Clow 2008
// 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 <boost/config.hpp>
#include <boost/algorithm/copy.hpp>
#include <boost/test/included/test_exec_monitor.hpp>
#include <utility>
#include <functional>
// #include <boost/algorithm/all.hpp>
// #include <boost/algorithm/select.hpp>
template <int v> bool IsEqual ( int v2 ) { return v2 == v; }
template <int v> bool IsNotEqual ( int v2 ) { return v2 != v; }
template <int v> bool IsGreater ( int v2 ) { return v2 > v; }
template <int v> bool IsLess ( int v2 ) { return v2 < v; }
bool IsEven ( int v2 ) { return ( v2 & 1 ) == 0; }
bool IsOdd ( int v2 ) { return ( v2 & 1 ) != 0; }
namespace bas = boost::algorithm::sequence;
void test_copy_if ()
{
const int vals [] = { 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1 };
const unsigned int valsSize = sizeof ( vals ) / sizeof ( vals [0] );
std::vector<int> cont;
std::vector<int> res;
// Copy all but the last element
std::copy ( vals, vals + valsSize - 1, std::back_inserter(cont));
// Copy_if from constant iterators
res.clear ();
bas::copy_if ( vals, vals + valsSize, std::back_inserter(res), IsEqual<0> );
BOOST_CHECK_EQUAL ( res.size (), 5U );
BOOST_CHECK ( std::find_if ( res.begin (), res.end (), IsNotEqual<0> ) == res.end ());
// Copy them all
res.clear ();
bas::copy_if ( vals, vals + valsSize, std::back_inserter(res), IsLess<100> );
BOOST_CHECK_EQUAL ( valsSize, res.size ());
BOOST_CHECK ( std::equal ( vals, vals + valsSize, res.begin ()));
// Copy none
res.clear ();
bas::copy_if ( vals, vals + valsSize, std::back_inserter(res), IsGreater<100> );
BOOST_CHECK_EQUAL ( 0U, res.size ());
// Copy_if using ranges
res.clear ();
bas::copy_if ( cont, std::back_inserter(res), IsNotEqual<0> );
BOOST_CHECK_EQUAL ( res.size (), 5U );
BOOST_CHECK ( std::find_if ( res.begin (), res.end (), IsEqual<0> ) == res.end ());
// Copy them all
res.clear ();
bas::copy_if ( cont, std::back_inserter(res), IsNotEqual<2> );
BOOST_CHECK_EQUAL ( cont.size (), res.size ());
BOOST_CHECK ( std::equal ( cont.begin (), cont.end (), res.begin ()));
// Copy none
res.clear ();
bas::copy_if ( cont, std::back_inserter(res), IsEqual<2> );
BOOST_CHECK_EQUAL ( 0U, res.size ());
// ---- Backwards tests ----
const int vals2 [] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
const unsigned int vals2Size = sizeof ( vals2 ) / sizeof ( vals2 [0] );
// Copy all but the last element
cont.clear ();
std::copy ( vals2, vals2 + vals2Size - 1, std::back_inserter(cont));
// Copy_if_backward from constant iterators
res.clear ();
bas::copy_backward_if ( vals2, vals2 + vals2Size, std::back_inserter(res), IsEven );
BOOST_CHECK_EQUAL ( res.size (), 5U );
BOOST_CHECK_EQUAL ( res[0], 8 );
BOOST_CHECK_EQUAL ( res[1], 6 );
BOOST_CHECK_EQUAL ( res[2], 4 );
BOOST_CHECK_EQUAL ( res[3], 2 );
BOOST_CHECK_EQUAL ( res[4], 0 );
// Copy them all
res.clear ();
bas::copy_backward_if ( vals2, vals2 + vals2Size, std::back_inserter(res), IsLess<100> );
BOOST_CHECK_EQUAL ( vals2Size, res.size ());
BOOST_CHECK ( std::equal ( vals2, vals2 + vals2Size, res.rbegin ()));
// Copy none
res.clear ();
bas::copy_backward_if ( vals, vals + valsSize, std::back_inserter(res), IsGreater<100> );
BOOST_CHECK_EQUAL ( 0U, res.size ());
// Copy_if_backward using ranges
res.clear ();
bas::copy_backward_if ( cont, std::back_inserter(res), IsEven );
BOOST_CHECK_EQUAL ( res.size (), 5U );
BOOST_CHECK_EQUAL ( res[0], 8 );
BOOST_CHECK_EQUAL ( res[1], 6 );
BOOST_CHECK_EQUAL ( res[2], 4 );
BOOST_CHECK_EQUAL ( res[3], 2 );
BOOST_CHECK_EQUAL ( res[4], 0 );
// Copy them all
res.clear ();
bas::copy_backward_if ( cont, std::back_inserter(res), IsLess<100> );
BOOST_CHECK_EQUAL ( cont.size (), res.size ());
BOOST_CHECK ( std::equal ( cont.rbegin (), cont.rend (), res.begin ()));
// Copy none
res.clear ();
bas::copy_backward_if ( vals, vals + valsSize, std::back_inserter(res), IsGreater<100> );
BOOST_CHECK_EQUAL ( 0U, res.size ());
}
void test_copy_while ()
{
const int vals [] = { 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1 };
const unsigned int valsSize = sizeof ( vals ) / sizeof ( vals [0] );
std::vector<int> cont;
std::vector<int> res;
// Copy all but the last element
std::copy ( vals, vals + valsSize - 1, std::back_inserter(cont));
// Copy_while from constant iterators
res.clear ();
bas::copy_while ( vals, vals + valsSize, std::back_inserter(res), IsEqual<0> );
BOOST_CHECK_EQUAL ( res.size (), 1U );
BOOST_CHECK_EQUAL ( res[0], 0 );
// Copy them all
res.clear ();
bas::copy_while ( vals, vals + valsSize, std::back_inserter(res), IsLess<100> );
BOOST_CHECK_EQUAL ( valsSize, res.size ());
BOOST_CHECK ( std::equal ( vals, vals + valsSize, res.begin ()));
// Copy none
res.clear ();
bas::copy_while ( vals, vals + valsSize, std::back_inserter(res), IsGreater<100> );
BOOST_CHECK_EQUAL ( 0U, res.size ());
// Copy_while using ranges
res.clear ();
bas::copy_while ( cont, std::back_inserter(res), IsNotEqual<1> );
BOOST_CHECK_EQUAL ( res.size (), 1U );
BOOST_CHECK_EQUAL ( res[0], 0 );
// Copy them all
res.clear ();
bas::copy_while ( cont, std::back_inserter(res), IsNotEqual<2> );
BOOST_CHECK_EQUAL ( cont.size (), res.size ());
BOOST_CHECK ( std::equal ( cont.begin (), cont.end (), res.begin ()));
// Copy none
res.clear ();
bas::copy_while ( cont, std::back_inserter(res), IsEqual<2> );
BOOST_CHECK_EQUAL ( 0U, res.size ());
// ---- Backwards tests ----
const int vals2 [] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
const unsigned int vals2Size = sizeof ( vals2 ) / sizeof ( vals2 [0] );
// Copy all but the last element
cont.clear ();
std::copy ( vals2, vals2 + vals2Size - 1, std::back_inserter(cont));
// Copy_if_backward from constant iterators
res.clear ();
bas::copy_backward_while ( vals2, vals2 + vals2Size, std::back_inserter(res), IsGreater<5> );
BOOST_CHECK_EQUAL ( res.size (), 4U );
BOOST_CHECK_EQUAL ( res[0], 9 );
BOOST_CHECK_EQUAL ( res[1], 8 );
BOOST_CHECK_EQUAL ( res[2], 7 );
BOOST_CHECK_EQUAL ( res[3], 6 );
// Copy them all
res.clear ();
bas::copy_backward_while ( vals2, vals2 + vals2Size, std::back_inserter(res), IsLess<100> );
BOOST_CHECK_EQUAL ( vals2Size, res.size ());
BOOST_CHECK ( std::equal ( vals2, vals2 + vals2Size, res.rbegin ()));
// Copy none
res.clear ();
bas::copy_backward_while ( vals, vals + valsSize, std::back_inserter(res), IsGreater<100> );
BOOST_CHECK_EQUAL ( 0U, res.size ());
// Copy_while_backward using ranges
res.clear ();
bas::copy_backward_while ( cont, std::back_inserter(res), IsGreater<5> );
BOOST_CHECK_EQUAL ( res.size (), 3U );
BOOST_CHECK_EQUAL ( res[0], 8 );
BOOST_CHECK_EQUAL ( res[1], 7 );
BOOST_CHECK_EQUAL ( res[2], 6 );
// Copy them all
res.clear ();
bas::copy_backward_while ( cont, std::back_inserter(res), IsLess<100> );
BOOST_CHECK_EQUAL ( cont.size (), res.size ());
BOOST_CHECK ( std::equal ( cont.rbegin (), cont.rend (), res.begin ()));
// Copy none
res.clear ();
bas::copy_backward_while ( vals, vals + valsSize, std::back_inserter(res), IsGreater<100> );
BOOST_CHECK_EQUAL ( 0U, res.size ());
}
void test_copy_n ()
{
const int vals [] = { 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1 };
const unsigned int valsSize = sizeof ( vals ) / sizeof ( vals [0] );
std::vector<int> cont;
std::vector<int> res;
// Copy all but the last element
std::copy ( vals, vals + valsSize - 1, std::back_inserter(cont));
// copy_n from constant iterators
res.clear ();
bas::copy_n ( vals, valsSize, std::back_inserter(res));
BOOST_CHECK_EQUAL ( res.size (), valsSize );
BOOST_CHECK ( std::equal ( vals, vals + valsSize, res.begin ()));
// Copy none
res.clear ();
bas::copy_n ( vals, 0, std::back_inserter(res));
BOOST_CHECK_EQUAL ( 0U, res.size ());
// Copy_while from container
res.clear ();
bas::copy_n ( cont.begin (), cont.size (), std::back_inserter(res) );
BOOST_CHECK_EQUAL ( res.size (), cont.size ());
BOOST_CHECK ( std::equal ( cont.begin (), cont.end (), res.begin ()));
}
int test_main( int , char* [] )
{
test_copy_if ();
test_copy_while ();
test_copy_n ();
return 0;
}
-11
View File
@@ -1,11 +0,0 @@
# Boost.Creasing Library test Jamfile
#
# Copyright (c) 2010 Nuovation System Designs, LLC
# Grant Erickson <gerickson@nuovations.com>
#
# Distributed under 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)
exe creasing_ex : creasing_ex.cpp ;
-69
View File
@@ -1,69 +0,0 @@
// Copyright (c) 2010 Nuovation System Designs, LLC
// Grant Erickson <gerickson@nuovations.com>
//
// Distributed under 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 latest version.
#include <algorithm>
#include <iostream>
#include <boost/algorithm/creasing.hpp>
#include <boost/lambda/lambda.hpp>
/* Preprocessor Defines */
#define elementsof(v) (sizeof (v) / sizeof (v[0]))
#define begin(v) (v)
#define end(v) (v + elementsof (v))
static void
output_sequence_property(bool result, const char * property)
{
std::cout << " "
<< ((result) ? "Is " : "Is not ")
<< property
<< std::endl;
}
template <typename InputIterator>
static void
analyze_sequence(InputIterator first, InputIterator last)
{
bool is_increasing;
bool is_decreasing;
bool is_strictly_increasing;
bool is_strictly_decreasing;
using namespace std;
using namespace boost::lambda;
is_increasing = boost::is_increasing(first, last);
is_decreasing = boost::is_decreasing(first, last);
is_strictly_increasing = boost::is_strictly_increasing(first, last);
is_strictly_decreasing = boost::is_strictly_decreasing(first, last);
cout << "The sequence { ";
for_each(first, last, cout << _1 << ' ');
cout << " }..." << endl;
output_sequence_property(is_increasing, "increasing");
output_sequence_property(is_strictly_increasing, "strictly increasing");
output_sequence_property(is_decreasing, "decreasing");
output_sequence_property(is_strictly_decreasing, "strictly decreasing");
}
int main(void)
{
const int sequence1[] = { 1, 2, 3, 4, 5 };
const int sequence2[] = { 7, 7, 7, 7, 7 };
const float sequence3[] = { 7.618, 4.971, 6.126, 1.727, 6.510 };
analyze_sequence(begin(sequence1), end(sequence1));
analyze_sequence(begin(sequence2), end(sequence2));
analyze_sequence(begin(sequence3), end(sequence3));
return 0;
}
-18
View File
@@ -1,18 +0,0 @@
# Boost.Creasing Library test Jamfile
#
# Copyright (c) 2010 Nuovation System Designs, LLC
# Grant Erickson <gerickson@nuovations.com>
#
# Distributed under 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/creasing:
: [ run creasing_test.cpp
: : : : creasing ]
;
}
-165
View File
@@ -1,165 +0,0 @@
// Copyright (c) 2010 Nuovation System Designs, LLC
// Grant Erickson <gerickson@nuovations.com>
//
// Distributed under 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 latest version.
#include <algorithm>
#include <iostream>
#include <boost/algorithm/creasing.hpp>
#include <boost/lambda/lambda.hpp>
#include <boost/test/unit_test.hpp>
using namespace boost;
/* Preprocessor Defines */
#define elementsof(v) (sizeof (v) / sizeof (v[0]))
#define begin(v) (v)
#define end(v) (v + elementsof (v))
template <typename InputIterator, typename Function>
static bool
test_sequence(InputIterator inBegin,
InputIterator inEnd,
Function inFunction)
{
return (inFunction(inBegin, inEnd));
}
static void
test_creasing(void)
{
const int strictlyIncreasingValues[] = { 1, 2, 3, 4, 5 };
const int strictlyDecreasingValues[] = { 9, 8, 7, 6, 5 };
const int increasingValues[] = { 1, 2, 2, 2, 5 };
const int decreasingValues[] = { 9, 7, 7, 7, 5 };
const int randomValues[] = { 3, 6, 1, 2, 7 };
const int constantValues[] = { 7, 7, 7, 7, 7 };
bool result;
// Test a strictly increasing sequence
result = test_sequence(begin(strictlyIncreasingValues),
end(strictlyIncreasingValues),
is_strictly_increasing<int const *>);
BOOST_CHECK_EQUAL(result, true);
result = test_sequence(begin(strictlyIncreasingValues),
end(strictlyIncreasingValues),
is_increasing<int const *>);
BOOST_CHECK_EQUAL(result, true);
result = test_sequence(begin(strictlyIncreasingValues),
end(strictlyIncreasingValues),
is_strictly_decreasing<int const *>);
BOOST_CHECK_EQUAL(result, false);
result = test_sequence(begin(strictlyIncreasingValues),
end(strictlyIncreasingValues),
is_decreasing<int const *>);
BOOST_CHECK_EQUAL(result, false);
// Test a strictly decreasing sequence
result = test_sequence(begin(strictlyDecreasingValues),
end(strictlyDecreasingValues),
is_strictly_increasing<int const *>);
BOOST_CHECK_EQUAL(result, false);
result = test_sequence(begin(strictlyDecreasingValues),
end(strictlyDecreasingValues),
is_increasing<int const *>);
BOOST_CHECK_EQUAL(result, false);
result = test_sequence(begin(strictlyDecreasingValues),
end(strictlyDecreasingValues),
is_strictly_decreasing<int const *>);
BOOST_CHECK_EQUAL(result, true);
result = test_sequence(begin(strictlyDecreasingValues),
end(strictlyDecreasingValues),
is_decreasing<int const *>);
BOOST_CHECK_EQUAL(result, true);
// Test an increasing sequence
result = test_sequence(begin(increasingValues),
end(increasingValues),
is_strictly_increasing<int const *>);
BOOST_CHECK_EQUAL(result, false);
result = test_sequence(begin(increasingValues),
end(increasingValues),
is_increasing<int const *>);
BOOST_CHECK_EQUAL(result, true);
result = test_sequence(begin(increasingValues),
end(increasingValues),
is_strictly_decreasing<int const *>);
BOOST_CHECK_EQUAL(result, false);
result = test_sequence(begin(increasingValues),
end(increasingValues),
is_decreasing<int const *>);
BOOST_CHECK_EQUAL(result, false);
// Test a decreasing sequence
result = test_sequence(begin(decreasingValues),
end(decreasingValues),
is_strictly_increasing<int const *>);
BOOST_CHECK_EQUAL(result, false);
result = test_sequence(begin(decreasingValues),
end(decreasingValues),
is_increasing<int const *>);
BOOST_CHECK_EQUAL(result, false);
result = test_sequence(begin(decreasingValues),
end(decreasingValues),
is_strictly_decreasing<int const *>);
BOOST_CHECK_EQUAL(result, false);
result = test_sequence(begin(decreasingValues),
end(decreasingValues),
is_decreasing<int const *>);
BOOST_CHECK_EQUAL(result, true);
// Test a random sequence
result = test_sequence(begin(randomValues),
end(randomValues),
is_strictly_increasing<int const *>);
BOOST_CHECK_EQUAL(result, false);
result = test_sequence(begin(randomValues),
end(randomValues),
is_increasing<int const *>);
BOOST_CHECK_EQUAL(result, false);
result = test_sequence(begin(randomValues),
end(randomValues),
is_strictly_decreasing<int const *>);
BOOST_CHECK_EQUAL(result, false);
result = test_sequence(begin(randomValues),
end(randomValues),
is_decreasing<int const *>);
BOOST_CHECK_EQUAL(result, false);
// Test a constant sequence
result = test_sequence(begin(constantValues),
end(constantValues),
is_strictly_increasing<int const *>);
BOOST_CHECK_EQUAL(result, false);
result = test_sequence(begin(constantValues),
end(constantValues),
is_increasing<int const *>);
BOOST_CHECK_EQUAL(result, true);
result = test_sequence(begin(constantValues),
end(constantValues),
is_strictly_decreasing<int const *>);
BOOST_CHECK_EQUAL(result, false);
result = test_sequence(begin(constantValues),
end(constantValues),
is_decreasing<int const *>);
BOOST_CHECK_EQUAL(result, true);
}
int test_main( int, char * [] )
{
test_creasing();
return 0;
}
-1417
View File
File diff suppressed because it is too large Load Diff
-7
View File
@@ -1,7 +0,0 @@
BOOST_ALGORITHM_INC=-I../../../ -I../../../boost/
CXX=c++
all:
$(CXX) -Wall -o example_1 example_1.cpp $(BOOST_ALGORITHM_INC)
-49
View File
@@ -1,49 +0,0 @@
// Boost.Algorithm example
#include <vector>
#include <iostream>
#include <boost/algorithm.hpp>
using namespace boost::algorithm;
using namespace boost::algorithm::sequence;
// Pretty-printer:
template <class T>
void show(std::vector<T>& v);
// Toy function that ignores parameters:
int one_hundred(int&) { return 100; }
int main()
{
int some_numbers[] = { 0, 1, 32, 18, 5 };
std::vector<int> vi(some_numbers, some_numbers + 5);
show(vi);
// none(): See that the values are not all 100:
std::cout << "Are none of the values equal to 100? "
<< ( none(vi, 100) ? "yes" : "no" ) << '\n';
// apply(): Change all the values to 100:
apply(vi, one_hundred);
show(vi);
// all(): See that all of the values are now 100:
std:: cout << "Are any values equal to 100? " <<
( all(vi, 100) ? "yes" : "no" ) << '\n';
}
template <class T>
void show(std::vector<T>& v)
{
for(typename std::vector<T>::const_iterator i = v.begin(); i != v.end(); ++i)
std::cout << *i << '\n';
std::cout << "----------" << std::endl;
}
/// \file example_1.cpp
/// \brief Some examples using the Boost::Algorithm library.
-23
View File
@@ -1,23 +0,0 @@
# Boost.Algorithm Library test Jamfile
#
# Copyright (C) 2002--2004, Herve Bronnimann
#
# Modified 2008, Jesse Williamson
#
# 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/find_if_not:
:
[ run find_if_not.cpp
: : : : find_if_not ]
[ run find_if_not.cpp
: : : : find_if_not ]
;
}
-58
View File
@@ -1,58 +0,0 @@
/* Unit tests for Boost.algorithms.sequence::find_if_not()
*
* Copyright (C) 2008, Jesse Williamson
*
* 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)
*
*/
#include <boost/test/included/test_exec_monitor.hpp>
#include <boost/algorithm/find_if_not.hpp>
#include <list>
#include <vector>
#include <string>
using namespace std;
using namespace boost::algorithm::sequence;
int make_zero(int x)
{
return 0;
}
string make_z(string x)
{
return "z";
}
int test_main(int, char **)
{
// Basic test:
{
vector<int> v(3);
v[0] = 1;
v[1] = 2;
v[2] = 3;
BOOST_CHECK(v[1] == *(find_if_not(v.begin(), v.end(), std::bind2nd(std::equal_to<int>(), 1))));
}
// Range test:
{
vector<int> v(3);
v[0] = 1;
v[1] = 2;
v[2] = 3;
BOOST_CHECK(v[1] == *(find_if_not(v, std::bind2nd(std::equal_to<int>(), 1))));
}
return 0;
}
-274
View File
@@ -1,274 +0,0 @@
/*
Copyright (c) Marshall Clow 2008.
Distributed under 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)
Revision history:
05 May 2008 mtc First version - as part of BoostCon 2008
07 May 2009 mtc Changed names to match n2666
*/
/// \file all.hpp
/// \brief Test ranges against predicates.
/// \author Marshall Clow
#ifndef BOOST_ALGORITHM_ALL_HPP
#define BOOST_ALGORITHM_ALL_HPP
#include <boost/range.hpp> // For boost::begin and boost::end
// I would love to use the all_of, any_of and none_of that are in the C++0x
// standard library if they are available, but I don't know how to do that.
// -- mtc 11-May-2009
// Something like:
// #ifdef <something>
// use std::all_of;
// #else
// template<typename I, typename V>
// bool all_of ( I first, I last, const V &val )
// ... and so on.
// #endif
namespace boost { namespace algorithm {
/// \fn all_of ( I first, I last, const V &val )
/// \brief Returns true if all elements in [first, last) are equal to 'val'
///
/// \param first The start of the input sequence
/// \param last One past the end of the input sequence
/// \param val A value to compare against
///
template<typename I, typename V>
bool all_of ( I first, I last, const V &val )
{
while (first != last) {
if ( *first++ != val )
return false;
}
return true;
}
/// \fn all_of ( Range range, const V &val )
/// \brief Returns true if all elements in the range are equal to 'val'
///
/// \param range The input range
/// \param val A value to compare against
///
template<typename Range, typename V>
bool all_of ( Range range, const V &val )
{
return all_of ( boost::begin ( range ), boost::end ( range ), val );
}
/// \fn all_of_if ( I first, I last, Pred p )
/// \brief Returns true if all elements in [first, last) satisfy the predicate
///
/// \param first The start of the input sequence
/// \param last One past the end of the input sequence
/// \param p A predicate
///
template<typename I, typename Pred>
bool all_of_if ( I first, I last, Pred p )
{
while (first != last) {
if ( !p(*first++))
return false;
}
return true;
}
/// \fn all_of_if ( Range range, Pred p )
/// \brief Returns true if all elements in the range satisfy the predicate
///
/// \param range The input range
/// \param p A predicate to test the elements
///
template<typename Range, typename Pred>
bool all_of_if ( Range range, Pred p )
{
return all_of_if ( boost::begin ( range ), boost::end ( range ), p );
}
/// \fn none_of ( I first, I last, const V &val )
/// \brief Returns true if none of the elements in [first, last) are equal to 'val'
///
/// \param first The start of the input sequence
/// \param last One past the end of the input sequence
/// \param val A value to compare against
///
template<typename I, typename V>
bool none_of ( I first, I last, const V &val )
{
while (first != last) {
if ( *first++ == val )
return false;
}
return true;
}
/// \fn none_of ( Range range, const V &val )
/// \brief Returns true if none of the elements in the range are equal to 'val'
///
/// \param range The input range
/// \param val A value to compare against
///
template<typename Range, typename V>
bool none_of ( Range range, const V & val )
{
return none_of ( boost::begin ( range ), boost::end ( range ), val );
}
/// \fn none_of_if ( I first, I last, Pred p )
/// \brief Returns true if none of the elements in [first, last) satisfy the predicate
///
/// \param first The start of the input sequence
/// \param last One past the end of the input sequence
/// \param p A predicate
///
template<typename I, typename Pred>
bool none_of_if ( I first, I last, Pred p )
{
while (first != last) {
if ( p(*first++))
return false;
}
return true;
}
/// \fn none_of_if ( Range range, Pred p )
/// \brief Returns true if none of the elements in the range satisfy the predicate
///
/// \param range The input range
/// \param p A predicate to test the elements
///
template<typename Range, typename Pred>
bool none_if ( Range range, Pred p )
{
return none_of_if ( boost::begin ( range ), boost::end ( range ), p );
}
/// \fn any_of ( I first, I last, const V &val )
/// \brief Returns true if any of the elements in [first, last) are equal to 'val'
///
/// \param first The start of the input sequence
/// \param last One past the end of the input sequence
/// \param val A value to compare against
///
template<typename I, typename V>
bool any_of ( I first, I last, const V &val )
{
while (first != last) {
if ( *first++ == val )
return true;
}
return false;
}
/// \fn any_of ( Range range, const V &val )
/// \brief Returns true if any of the elements in the range are equal to 'val'
///
/// \param range The input range
/// \param val A value to compare against
///
template<typename Range, typename V>
bool any_of ( Range range, const V &val )
{
return any_of ( boost::begin ( range ), boost::end ( range ), val );
}
/// \fn any_of_if ( I first, I last, Pred p )
/// \brief Returns true if any of the elements in [first, last) satisfy the predicate
///
/// \param first The start of the input sequence
/// \param last One past the end of the input sequence
/// \param p A predicate
///
template<typename I, typename Pred>
bool any_of_if ( I first, I last, Pred p)
{
while (first != last) {
if ( p(*first++))
return true;
}
return false;
}
/// \fn any_of_if ( Range range, Pred p )
/// \brief Returns true if any elements in the range satisfy the predicate
///
/// \param range The input range
/// \param p A predicate to test the elements
///
template<typename Range, typename Pred>
bool any_of_if ( Range range, Pred p )
{
return any_of_if ( boost::begin ( range ), boost::end ( range ), p );
}
/// \fn exists_and_only ( I first, I last, const V &val )
/// \brief Returns true if the value 'val' exists only once in [first, last).
///
/// \param first The start of the input sequence
/// \param last One past the end of the input sequence
/// \param val A value to compare against
///
template<typename I, typename V>
bool exists_and_only ( I first, I last, const V &val )
{
I i = std::find (first, last, val);
if (i == last) return false;
if ( std::find (++i, last, val) != last) return false;
return true;
}
/// \fn exists_and_only ( Range range, const V &val )
/// \brief Returns true if the value 'val' exists only once in the range.
///
/// \param range The input range
/// \param val A value to compare against
///
template<typename Range, typename V>
bool exists_and_only ( Range range, const V &val )
{
return exists_and_only ( boost::begin ( range ), boost::end ( range ), val );
}
/// \fn exists_and_only_if ( I first, I last, Pred p )
/// \brief Returns true if the predicate 'p' is true for exactly one item in [first, last).
///
/// \param first The start of the input sequence
/// \param last One past the end of the input sequence
/// \param p A predicate to test the elements
///
template<typename I, typename Pred>
bool exists_and_only_if ( I first, I last, Pred p )
{
I i = find_if (first, last, p);
if (i == last) return false;
if (find_if(++i, last, p) != last) return false;
return true;
}
/// \fn exists_and_only_if ( Range range, Pred p )
/// \brief Returns true if the predicate 'p' is true for exactly one item in the range.
///
/// \param range The input range
/// \param p A predicate to test the elements
///
template<typename Range, typename Pred>
bool exists_and_only_if ( Range range, Pred p )
{
return exists_and_only_if ( boost::begin ( range ), boost::end ( range ), p );
}
}} // namespace boost and algorithm
#undef ANY_DOING_0X
#endif // BOOST_ALGORITHM_ALL_HPP
-87
View File
@@ -1,87 +0,0 @@
/*
Copyright (C) Jesse Williamson 2008.
Distributed under 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)
*/
#ifndef BOOST_ALGORITHM_APPLY_HPP
#define BOOST_ALGORITHM_APPLY_HPP
/// \file apply.hpp
/// \brief Apply predicates to ranges.
/// \author Jesse Williamson
#include <boost/range.hpp>
namespace boost { namespace algorithm { namespace sequence {
/// \fn apply_if (ForwardIter begin, ForwardIter end, Mutator m, ConditionPredicate c)
/// \brief Applies m to all elements from (begin, end) for which c is true.
///
/// \param begin The start of the sequence to modify
/// \param end One past the end of the input sequence
/// \param m Unary mutator function object
/// \param c Unary condition function object
/// \return The mutator function object
///
template <class ForwardIter, class Mutator, class ConditionPredicate>
Mutator apply_if(ForwardIter begin, ForwardIter end, Mutator m, ConditionPredicate c)
{
for (; begin != end; begin++) {
if (c(*begin))
*begin = m(*begin);
}
return m;
}
/// \fn apply_if (ForwardReadableRange& r, Mutator m, ConditionPredicate c)
/// \brief Applies m to all elements in the range r for which c is true.
///
/// \param r The range to modify
/// \param m Unary mutator function object
/// \param c Unary condition function object
/// \return The mutator function object
///
template <class ForwardReadableRange, class Mutator, class ConditionPredicate>
Mutator apply_if(ForwardReadableRange& R, Mutator m, ConditionPredicate c)
{
return apply_if(boost::begin(R), boost::end(R), m, c);
}
/// \fn apply (ForwardIter begin, ForwardIter end, Mutator m)
/// \brief Applies m to all elements from (begin, end).
///
/// \param begin The start of the sequence to modify
/// \param end One past the end of the input sequence
/// \param m Unary mutator function object
/// \return The mutator function object
///
template <class ForwardIter, class Mutator>
Mutator apply(ForwardIter begin, ForwardIter end, Mutator m)
{
for (; begin != end; begin++)
*begin = m(*begin);
return m;
}
/// \fn apply (ForwardReadableRange& r, Mutator m)
/// \brief Applies m to all elements in the range r
///
/// \param r The range to modify
/// \param m Unary mutator function object
/// \return The mutator function object
///
template <class ForwardReadableRange, class Mutator>
Mutator apply(ForwardReadableRange& R, Mutator m)
{
return apply(boost::begin(R), boost::end(R), m);
}
}}} // namespace boost::algorithm::sequence
#endif // BOOST_ALGORITHM_APPLY_HPP
-44
View File
@@ -1,44 +0,0 @@
/*
Copyright (c) Marshall Clow 2008.
Distributed under 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)
Revision history:
27 June 2009 mtc First version
*/
/// \file clamp.hpp
/// \brief Clamp algorithm
/// \author Marshall Clow
///
/// Suggested by olafvdspek in https://svn.boost.org/trac/boost/ticket/3215
#ifndef BOOST_ALGORITHM_CLAMP_HPP
#define BOOST_ALGORITHM_CLAMP_HPP
namespace boost { namespace algorithm {
/// \fn clamp ( V val, V lo, V hi )
/// \brief Returns the value "val" brought into the range [ lo, hi ]
/// If the value is greater than "hi", return hi. If the value is
/// less than "lo", return lo. Otherwise, return the original value.
///
/// \param val The value to be clamped
/// \param lo The low point of the range to be clamped to
/// \param hi The high point of the range to be clamped to
///
template<typename V>
V clamp ( V val, V lo, V hi )
{
// return val >= hi ? hi : val <= lo ? lo : val;
// Alternately,
// return std::max ( std::min ( val, hi ), lo );
// Rewritten to only use operator <
return val < lo ? lo : hi < val ? hi : val;
}
}}
#endif // BOOST_ALGORITHM_CLAMP_HPP
-311
View File
@@ -1,311 +0,0 @@
/*
Copyright (c) Marshall Clow 2008.
Distributed under 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)
Revision history:
05 May 2008 mtc First version - as part of BoostCon 2008
07 Jul 2008 mtc Added more algorithms proposed by Matt Austern as part of C++Ox
<http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2666.pdf>
*/
#ifndef BOOST_ALGORITHM_SEQUENCE_COPY_HPP
#define BOOST_ALGORITHM_SEQUENCE_COPY_HPP
#include <boost/range.hpp> // For boost::begin and boost::end
#include <iterator> // for std::iterator_traits<>
/// \file copy.hpp
/// \brief STL-type copy()-type algorithms that were left out of the standard.
/// \author Marshall Clow
namespace boost { namespace algorithm { namespace sequence {
/// \fn copy_if ( I first, I last, O res, Pred p )
/// \brief Copies all the elements from [first, last) that satisfy the predicate into 'res'
///
/// \param first The start of the input sequence
/// \param last One past the end of the input sequence
/// \param res An output iterator to copy into
/// \param p A predicate to determine which items to copy
/// \return The (modified) output iterator
///
/// \note Based on a suggested implementation by Bjorne Stoustrop.
///
template<typename I, typename O, typename Pred>
O copy_if ( I first, I last, O res, Pred p)
{
while (first != last)
{
if (p(*first))
*res++ = *first;
++first;
}
return res;
}
/// \fn copy_if ( Range range, O res, Pred p )
/// \brief Copy all the elements from the range that satisfy the predicate into 'res'
///
/// \param range The input range
/// \param res An output iterator to copy into
/// \param p A predicate to determine which items to copy
/// \return The (modified) output iterator
///
template<typename Range, typename O, typename Pred>
O copy_if ( Range range, O res, Pred p )
{
return copy_if ( boost::begin ( range ), boost::end ( range ), res, p );
}
/// \fn reverse_copy_if ( I first, I last, O res, Pred p )
/// \brief Copies all the elements from (last, first] that satisfy the predicate into 'res'
///
/// \param first The start of the input sequence
/// \param last One past the end of the input sequence
/// \param res An output iterator to copy into
/// \param p A predicate to determine which items to copy
/// \return The (modified) output iterator
///
/// \note Based on a suggested implementation by Bjorne Stoustrop.
///
template<typename I, typename O, typename Pred>
O reverse_copy_if ( I first, I last, O res, Pred p)
{
while (first != last)
{
if (p(*--last))
*res++ = *last;
}
return res;
}
/// \fn reverse_copy_if ( Range range, O res, Pred p )
/// \brief Copy all the elements from the range that satisfy the predicate into 'res'
///
/// \param range The input range
/// \param res An output iterator to copy into
/// \param p A predicate to determine which items to copy
/// \return The (modified) output iterator
///
template<typename Range, typename O, typename Pred>
O reverse_copy_if ( Range range, O res, Pred p )
{
return reverse_copy_if ( boost::begin ( range ), boost::end ( range ), res, p );
}
/* -- I'd like a value-based version, too; but I don't know of a good name....
template<typename I,typename O>
O copy_equal ( I first, I last, O res, I::value_type val )
{
while (first != last) {
if (*first == val)
*res++ = *first;
++first;
}
return res;
}
*/
/// \fn copy_while ( I first, I last, O res, Pred p )
/// \brief Copies all the elements from [first, last) up to a point into 'res'.\n
/// Will continue until the input range is exhausted, or the predicate 'p' fails.
///
/// \param first The start of the input sequence
/// \param last One past the end of the input sequence
/// \param res An output iterator to copy into
/// \param p A predicate to determine when to stop copying
/// \return The (modified) output iterator
///
template<typename I, typename O, typename Pred>
std::pair<I,O> copy_while ( I first, I last, O res, Pred p )
{
for (; first != last && p(*first); ++first)
*res++ = *first;
return std::make_pair ( first, res );
}
/// \fn copy_while ( Range range, O res, Pred p )
/// \brief Copies all the elements from the range up to a point into 'res'.\n
/// Will continue until the input range is exhausted, or the predicate 'p' fails.
///
/// \param range The input range
/// \param res An output iterator to copy into
/// \param p A predicate to determine when to stop copying
/// \return The (modified) output iterator
///
template<typename Range, typename O, typename Pred>
std::pair<typename Range::type,O> copy_while ( Range range, O res, Pred p )
{
return copy_while ( boost::begin ( range ), boost::end ( range ), res, p );
}
/// \fn reverse_copy_while ( I first, I last, O res, Pred p )
/// \brief Copies all the elements from (last, first] up to a point into 'res'.\n
/// Will continue until the input range is exhausted, or the predicate 'p' fails.
///
/// \param first The start of the input sequence
/// \param last One past the end of the input sequence
/// \param res An output iterator to copy into
/// \param p A predicate to determine when to stop copying
/// \return The (modified) output iterator
///
template<typename I, typename O, typename Pred>
std::pair<I,O> reverse_copy_while ( I first, I last, O res, Pred p )
{
while ( first != last && p ( *--last ))
*res++ = *last;
return std::make_pair ( last, res );
}
/// \fn reverse_copy_while ( Range range, O res, Pred p )
/// \brief Copies all the elements from the range up to a point into 'res'.\n
/// Will continue until the input range is exhausted, or the predicate 'p' fails.
///
/// \param range The input range
/// \param res An output iterator to copy into
/// \param p A predicate to determine when to stop copying
/// \return The (modified) output iterator
///
template<typename Range, typename O, typename Pred>
std::pair<typename Range::type,O> reverse_copy_while ( Range range, O res, Pred p )
{
return reverse_copy_while ( boost::begin ( range ), boost::end ( range ), res, p );
}
// According to Werner Salomon, the challenge for copy_n is that the algorithm should work correctly
// with an std::istream_iterator. Therefor the input iterator have to increment only N-1 times.
// Marshall sez: Is that really true?
// Long discussion starting
// here <http://www.tech-archive.net/Archive/VC/microsoft.public.vc.stl/2004-05/0112.html>
// Marshall sez: I'm going to increment N times.
//
// Marshall sez: What's the advantage of templatizing on count, rather than using std::size_t?
//
// Jesse says: I've kept the signature that was uncommented to stop Doxygen from complaining. Here's
// the signature that was being discussed:
// template <typename I, typename O>
// O copy_n ( I first, typename std::iterator_traits<I>::difference_type count, O res )
//
// No range-based version here
/// \fn copy_n ( I first, Size count, O res )
/// \brief Copies n elements starting at 'first' into 'res'.
///
/// \param first The start of the input sequence
/// \param count The number of elements to copy
/// \param res An output iterator to copy into
/// \return The (modified) output iterator
///
template <typename I, typename Size, typename O>
O copy_n ( I first, Size count, O res )
{
for ( ; count > 0; ++res, ++first, --count )
*res = *first;
return res;
}
/// \fn uninitialized_copy_n ( I first, Size count, O res )
/// \brief xxx
///
/// \param first The start of the input sequence
/// \param count The number of elements to copy
/// \param res An output iterator to copy into
/// \return The (modified) output iterator
///
template<typename I, typename Size, typename O>
O uninitialized_copy_n ( I first, Size count, O res )
{
typedef typename std::iterator_traits<I>::value_type vt;
for ( ; count > 0; ++res, ++first, --count )
new ( static_cast <void*> ( &*res )) vt (*first);
return res;
}
// Range-based versions of copy and copy_backward.
/// \fn copy ( Range range, O res )
/// \brief Copies elements from the range 'range' into 'res'.
///
/// \param range The input range
/// \param res An output iterator to copy into
/// \return The (modified) output iterator
///
/// \note A range-based version of std::copy
///
template<typename Range, typename O>
O copy ( Range range, O res )
{
return std::copy ( boost::begin ( range ), boost::end ( range ), res );
}
/// \fn copy_backward ( Range range, O res )
/// \brief Copies elements from the range 'range' into 'res'.
///
/// \param range The input range
/// \param res An output iterator to copy into
/// \return The (modified) output iterator
///
/// \note A range-based version of std::copy_backward
///
template<typename Range, typename O>
O copy_backward ( Range range, O res )
{
return std::copy_backward ( boost::begin ( range ), boost::end ( range ), res );
}
/// \fn partition_copy ( I first, I last, O1 out_true, O2 out_false, Pred pred )
/// \brief Copies each element from [first, last) into one of the two output sequences,
/// depending on the result of the predicate
///
/// \param first The start of the input sequence
/// \param last One past the end of the input sequence
/// \param out_true An output iterator to copy into
/// \param out_false An output iterator to copy into
/// \param pred A predicate to determine which output sequence to copy into.
///
///
template <typename I, typename O1, typename O2, typename Pred>
std::pair <O1, O2> partition_copy ( I first, I last, O1 out_true, O2 out_false, Pred pred )
{
while (first != last)
{
if (p(*first))
*out_true++ = *first++;
else
*out_false++ = *first++;
}
return std::make_pair ( out_true, out_false );
}
/// \fn partition_copy ( Range range, O1 out_true, O2 out_false, Pred pred )
/// \brief Copies each element from the range into one of the two output sequences,
/// depending on the result of the predicate
///
/// \param range The input range
/// \param out_true An output iterator to copy into
/// \param out_false An output iterator to copy into
/// \param pred A predicate to determine which output sequence to copy into.
///
/// \note A range-based version of partition_copy.
///
template <typename Range, typename O1, typename O2, typename Pred>
std::pair <O1, O2> partition_copy ( Range range, O1 out_true, O2 out_false, Pred pred )
{
return partition_copy ( boost::begin ( range ), boost::end ( range ), out_true, out_false, pred );
}
}}} // namespace boost & algorithm & sequence
#endif // BOOST_ALGORITHM_SEQUENCE_COPY_HPP
-94
View File
@@ -1,94 +0,0 @@
// Boost creasing.hpp header file -----------------------------------------//
// Copyright (c) 2010 Nuovation System Designs, LLC
// Grant Erickson <gerickson@nuovations.com>
//
// Distributed under 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 latest version.
//
// Description:
// A set of four algorithms for inquiring about the properties of
// sequences, including:
//
// - Increasing
// - Decreasing
// - Strictly Increasing
// - Strictly Decreasing
#ifndef BOOST_ALGORITHM_CREASING_HPP
#define BOOST_ALGORITHM_CREASING_HPP
#include <algorithm>
#include <functional>
#include <iterator>
namespace boost {
namespace detail {
template <typename ForwardIterator, typename BinaryPredicate>
bool
is_creasing(ForwardIterator first, ForwardIterator last,
BinaryPredicate binary_pred)
{
return std::adjacent_find(first,
last,
std::not2(binary_pred)) == last;
}
} // namespace detail
template <typename ForwardIterator>
bool
is_increasing(ForwardIterator first, ForwardIterator last)
{
typedef typename std::iterator_traits<ForwardIterator>::value_type
value_type;
return detail::is_creasing(first,
last,
std::less_equal<value_type>());
}
template <typename ForwardIterator>
bool
is_decreasing(ForwardIterator first, ForwardIterator last)
{
typedef typename std::iterator_traits<ForwardIterator>::value_type
value_type;
return detail::is_creasing(first,
last,
std::greater_equal<value_type>());
}
template <typename ForwardIterator>
bool
is_strictly_increasing(ForwardIterator first, ForwardIterator last)
{
typedef typename std::iterator_traits<ForwardIterator>::value_type
value_type;
return detail::is_creasing(first,
last,
std::less<value_type>());
}
template <typename ForwardIterator>
bool
is_strictly_decreasing(ForwardIterator first, ForwardIterator last)
{
typedef typename std::iterator_traits<ForwardIterator>::value_type
value_type;
return detail::is_creasing(first,
last,
std::greater<value_type>());
}
} // namespace boost
#endif // BOOST_ALGORITHM_CREASING_HPP
-55
View File
@@ -1,55 +0,0 @@
/*
Copyright (C) 2008 Jesse Williamson
Distributed under 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)
*/
#ifndef BOOST_ALGORITHM_SEQUENCE_FIND_IF_NOT_HPP
#define BOOST_ALGORITHM_SEQUENCE_FIND_IF_NOT_HPP
#include <boost/range.hpp>
/// \file find_if_not.hpp
/// \brief Return the first iterator in a range for which a predicate is false.
/// \author Jesse Williamson
namespace boost { namespace algorithm { namespace sequence {
/// \fn InputIterator find_if_not ( InputIterator first, InputIterator last, Predicate pred )
/// \brief Returns the first iterator in the range [first, last] for which pred is false. Returns [last] if
/// no such iterator exists.
///
/// \param first The start of the input sequence.
/// \param last One past the end of the input sequence.
/// \param pred Predicate.
///
template <class InputIterator, class Predicate>
InputIterator find_if_not ( InputIterator first, InputIterator last, Predicate pred )
{
for( ; first != last; ++first )
if(! pred( *first ) )
return first;
return last;
}
/// \fn InputIterator find_if_not ( ForwardReadableRange& R, Predicate pred )
/// \brief Returns the first iterator in the range [R] for which pred is false. Returns [R::end] if
/// no such iterator exists.
///
/// \param R A forward readable Boost range input sequence.
/// \param pred Predicate.
///
template <class ForwardReadableRange, class Predicate>
typename boost::range_iterator<ForwardReadableRange>::type find_if_not( ForwardReadableRange& R, Predicate pred )
{
return find_if_not( boost::begin(R), boost::end(R), pred );
}
}}} // boost::algorithm::sequence
#endif
-47
View File
@@ -1,47 +0,0 @@
/*
Copyright (c) Marshall Clow 2008.
Distributed under 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)
Revision history:
06 May 2008 mtc First version - as part of BoostCon 2008
*/
#ifndef BOOST_ALGORITHM_FOR_EACH_IF_HPP
#define BOOST_ALGORITHM_FOR_EACH_IF_HPP
#include <boost/range.hpp> // For boost::begin and boost::end
/// \file for_each_if.hpp
/// \brief Apply a functor to a range when a predicate is satisfied.
/// \author Marshall Clow
namespace boost { namespace algorithm {
/// \fn for_each_if ( InputIterator first, InputIterator last, Pred p, Func f )
/// \brief Applies the function_object 'f' to each element in [first, last) that satisfies
/// the predicate 'p'.
///
/// \param first The start of the input sequence
/// \param last One past the end of the input sequence
/// \param p A predicate to determine which items to copy
/// \param f A function object that takes a single argument
/// \return the function object 'f'
///
///
template<typename InputIterator, typename Pred, typename Func>
Func for_each_if ( InputIterator first, InputIterator last, Pred p, Func f )
{
while ( first != last )
{
if (p(*first))
f(*first);
++first;
}
return f;
}
}} // namespace boost & algorithm
#endif // BOOST_ALGORITHM_FOR_EACH_IF_HPP
-80
View File
@@ -1,80 +0,0 @@
/*
Copyright (c) Marshall Clow 2008.
Distributed under 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)
Revision history:
19 June 2008 mtc First version -
*/
#ifndef BOOST_ALGORITHM_SEQUENCE_IOTA_HPP
#define BOOST_ALGORITHM_SEQUENCE_IOTA_HPP
// #include <boost/range.hpp> // For boost::begin and boost::end
/// \file iota.hpp
/// \brief Generate and write sequences.
/// \brief Boost implementation of iota, a proposed algorithm for TR2
/// \author Marshall Clow
namespace boost { namespace algorithm { namespace sequence {
/// \fn iota ( I first, I last, V value )
/// \brief Generates a sequence (value, value+1, value+2 .. ) and writes the
/// sequence into [first, last). The sequence is of length std::distance ( first, last )
///
/// \param first The start of the sequence to be output
/// \param last One past the end of the sequence
/// \param value The starting value for the sequence.
///
/// See <http://www.sgi.com/tech/stl/iota.html> for a more complete description.
///
template<typename I, typename V>
void iota ( I first, I last, V value )
{
V temp = value;
while ( first != last )
*first++ = temp++;
}
/*
/// \fn iota ( R range, V value )
/// \brief Generates a sequence (v, v+1, v+2 .. ) and writes the sequence into
/// sequence into [first, last). The sequence is of length std::distance ( first, last )
///
/// \param range The range to write the sequence into
/// \param value The starting value for the sequence.
///
/// See <http://www.sgi.com/tech/stl/iota.html> for a more complete description.
///
template<typename R, typename V>
void iota ( R range, V value )
{
iota ( boost::begin ( range ), boost::end ( range ), value );
}
*/
/// \fn iota ( O res, std::size_t count, V value )
/// \brief Generates a sequence (v, v+1, v+2 .. ) and puts the sequence into [first, last)
/// The sequence is of length 'count'.
///
/// \param res The iterator two write the resulting sequence into
/// \param count The number of items to write.
/// \param value The starting value for the sequence.
///
/// See <http://www.sgi.com/tech/stl/iota.html> for a more complete description.
///
template<typename O, typename V>
void iota ( O res, std::size_t count, V value )
{
V temp = value;
while ( count-- > 0 )
*res++ = temp++;
}
}}} // namespace boost & algorithm & sequence
#endif // BOOST_ALGORITHM_SEQUENCE_IOTA_HPP
-54
View File
@@ -1,54 +0,0 @@
/*
Copyright (c) Marshall Clow 2008.
Distributed under 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)
Implemented by SGI in their STL implementation
This implemnetation is based on interprocess::detail::select1st by Ion Gaztanaga.
Revision history:
06 May 2008 mtc First version - as part of BoostCon 2008
*/
#ifndef BOOST_ALGORITHM_SELECT_HPP
#define BOOST_ALGORITHM_SELECT_HPP
/// \file select.hpp
/// \brief Choose the first or second element of a Pair.
/// \author Marshall Clow
namespace boost { namespace algorithm {
/// \struct select1st
/// \brief Unary function that returns the first element of a std::pair
///
/// \param p The pair.
/// \return p.first
///
///
template <class Pair>
struct select1st : public std::unary_function<Pair, typename Pair::first_type>
{
const typename Pair::first_type& operator()(const Pair& p) const { return p.first; }
typename Pair::first_type& operator()( Pair& p) const { return p.first; }
};
/// \struct select2nd
/// \brief Unary function that returns the first element of a std::pair
///
/// \param p The pair.
/// \return p.first
///
///
template <class Pair>
struct select2nd : public std::unary_function<Pair, typename Pair::second_type>
{
const typename Pair::second_type& operator()(const Pair& p) const { return p.second; }
typename Pair::second_type& operator()( Pair& p) const { return p.second; }
};
}} // namespace boost & algorithm
#endif // BOOST_ALGORITHM_SELECT_HPP
-95
View File
@@ -1,95 +0,0 @@
/*
Copyright (C) 2008 Jesse Williamson
Distributed under 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)
*/
#ifndef BOOST_ALGORITHM_SEQUENCE_TRANSFORM_IF_HPP
#define BOOST_ALGORITHM_SEQUENCE_TRANSFORM_IF_HPP
#include <boost/range.hpp>
/// \file transform_if.hpp
/// \brief Apply operations across ranges when a predicate is true, storing returned values.
/// \author Jesse Williamson
namespace boost { namespace algorithm { namespace sequence {
/// \fn transform_if ( InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op, UnaryPredicate pred )
/// \brief Applies op to all elements in [first, last] for which pred is true, storing each returned value in the range
/// beginning at result.
///
/// \param first The start of the input sequence.
/// \param last One past the end of the input sequence.
/// \param result The start of the output sequence.
/// \param op Unary operation to apply when pred is true.
/// \param pred Unary condition predicate.
///
template <class InputIterator, class OutputIterator, class UnaryFunction, class UnaryPredicate>
OutputIterator transform_if(InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op, UnaryPredicate pred)
{
for( ; first != last; ++first, ++result )
if( pred( *first ) )
*result = op( *first );
return result;
}
/// \fn transform_if ( ForwardReadableRange& R, OutputIterator result, UnaryFunction op, UnaryPredicate pred )
/// \brief Applies op to all elements in [first, last] for which pred is true, storing each returned value in the range
/// beginning at result.
///
/// \param R A forward readable Boost range input sequence.
/// \param result The start of the output sequence.
/// \param op Unary operation to apply when pred is true.
/// \param pred Unary condition predicate.
///
template <class ForwardReadableRange, class OutputIterator, class UnaryFunction, class UnaryPredicate>
OutputIterator transform_if(ForwardReadableRange& R, OutputIterator result, UnaryFunction op, UnaryPredicate pred)
{
return transform_if( boost::begin(R), boost::end(R), result, op, pred );
}
/// \fn transform_if ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction op, BinaryPredicate pred )
/// \brief Applies op to all elements in [first, last] for which pred is true, storing each returned value in the range
/// beginning at result.
///
/// \param first1 The start of the first input sequence.
/// \param last1 One past the end of the first input sequence.
/// \param first2 The start of the second input sequence.
/// \param result The start of the output sequence.
/// \param op Binary operation to apply when pred is true.
/// \param pred Binary condition predicate.
///
template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryFunction, class BinaryPredicate>
OutputIterator transform_if(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction op, BinaryPredicate pred)
{
for ( ; first1 != last1; ++first1, ++first2, ++result )
if ( pred( *first1, *first2 ) )
*result = op( *first1, *first2 );
}
/// \fn transform_if ( ForwardReadableRange& R, InputIterator2 first2, OutputIterator result, BinaryFunction op, BinaryPredicate pred )
/// \brief Applies op to all elements in [first, last] for which pred is true, storing each returned value in the range
/// beginning at result.
///
/// \param R A forward-readable Boost range input sequence.
/// \param first2 The start of the second input sequence.
/// \param result The start of the output sequence.
/// \param op Binary operation to apply when pred is true.
/// \param pred Binary condition predicate.
///
template <class ForwardReadableRange, class InputIterator2, class OutputIterator, class BinaryFunction, class BinaryPredicate>
OutputIterator transform_if(ForwardReadableRange& R, InputIterator2 first2, OutputIterator result, BinaryFunction op, BinaryPredicate pred)
{
return transform_if( boost::begin(R), boost::end(R), first2, result, op, pred );
}
}}} // namespace boost::algorithm::sequence
#endif
+524
View File
@@ -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>
+127
View File
@@ -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>
+14
View File
@@ -0,0 +1,14 @@
# Boost.Minmax Library Example 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)
#
subproject libs/algorithm/minmax/example ;
exe minmax_ex : minmax_ex.cpp ;
exe minmax_timer : minmax_timer.cpp ;
+36
View File
@@ -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()) );
}
+212
View File
@@ -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;
}
+528
View File
@@ -0,0 +1,528 @@
<!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 type</a>s<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/experts/1904/alexandr.htm?topic=experts&topic=experts">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>
+33
View File
@@ -0,0 +1,33 @@
# 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)
#
subproject libs/algorithm/minmax/test ;
# bring in rules for testing
import testing ;
# Make tests run by default.
DEPENDS all : test ;
{
test-suite algorithm/minmax
: [ run
minmax_element_test.cpp
: :
:
: minmax_element
]
[ run
minmax_test.cpp
: :
:
: minmax
]
;
}
@@ -1,6 +1,6 @@
# Boost.All Library test Jamfile
# Boost.Minmax Library test Jamfile
#
# Copyright (C) 2009 Jesse Williamson
# 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
@@ -10,9 +10,8 @@
import testing ;
{
test-suite algorithm/all:
: [ run all_test.cpp
: : : : all ]
;
test-suite algorithm/minmax:
[ run minmax_element_test.cpp ]
;
}
+236
View File
@@ -0,0 +1,236 @@
// (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 <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[] )
{
int n = 100;
if (argc > 1) n = atoi(argv[1]);
test<int>(n);
test<custom>(n);
return 0;
}
+85
View File
@@ -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;
}
+53
View File
@@ -0,0 +1,53 @@
# 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/collection_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/erase.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;\""
;
+199
View File
@@ -0,0 +1,199 @@
<?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">
<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>
+19
View File
@@ -0,0 +1,19 @@
<?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">
<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>
+373
View File
@@ -0,0 +1,373 @@
<?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">
<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/utility/Collection.html">collection</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
<link linkend="string_algo.collection_traits">collection traits</link>. This facility allows to access
the elements inside the string in a uniform iterator-based fashion.
This requirement is actually less stringent than that of collection concept. It implements
an <ulink url="../../libs/algorithm/string/doc/external_concepts.html">external</ulink> collection interface.
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>CollectionT</code> means that the basic collection requirements must hold.
<code>SequenceT</code> designates extended sequence requirements.
</para>
</section>
<section id="string_algo.iterator_range">
<title><code>iterator_range</code> class</title>
<para>
An <classname>iterator_range</classname> is an encapsulation of a pair of iterators that
delimit a sequence (or, a range). This concept is widely used by
sequence manipulating algorithms. Although being so useful, there no direct support
for it in the standard library (The closest thing is that some algorithms return a pair of iterators).
Instead all STL algorithms have two distinct parameters for beginning and end of a range. This design
is natural for implementation of generic algorithms, but it forbids to work with a range as a single value.
</para>
<para>
It is possible to encapsulate a range in <code>std::pair&lt;&gt;</code>, but
<code>std::pair&lt;&gt;</code> is an overly generic encapsulation, so it is not best match for a range.
For instance, it does not enforce that begin and end iterators be of the same type.
</para>
<para>
Naturally the range concept is heavily used also in this library. During the development of
the library, it was discovered, that there is a need for a reasonable encapsulation for it, since
core part of the library deals with substring searching algorithms and any such algorithm
returns a range delimiting the result of the search. <code>std::pair&lt;&gt;</code> was deemed as
unsuitable. Therefore the <code>iterator_range</code> was defined.
</para>
<para>
The intention of the <code>iterator_range</code> class is to manage a range as a single value and provide
a basic interface for common operations. Its interface is similar to that of a collection.
In addition to <code>begin()</code>
and <code>end()</code> accessors, it has member functions for checking whether the range is empty,
or to determine the size of the range. It also has a set of member typedefs that extract
type information from the encapsulated iterators. As such, the interface is compatible with
the <link linkend="string_algo.collection_traits">collection traits</link> requirements so
it is possible to use this class as a parameter to many algorithms in this library.
</para>
<para>
<classname>iterator_range</classname> will be moved to Boost.Range library in the future
releases. The internal version will be deprecated then.
</para>
</section>
<section id="string_algo.collection_traits">
<title>Collection Traits</title>
<para>
Collection traits provide uniform access to different types of
<ulink url="../../libs/utility/Collection.html">collections</ulink> .
This functionality allows to write generic algorithms which work with several
different kinds of collections. For this library it means, that, for instance,
many algorithms work with <code>std::string</code> as well as with <code>char[]</code>.
This facility implements the
<ulink url="../../libs/algorithm/string/doc/external_concepts.html">external</ulink> collection
concept.
</para>
<para>
The following collection types are supported:
<itemizedlist>
<listitem>
Standard containers
</listitem>
<listitem>
Built-in arrays (like int[])
</listitem>
<listitem>
Null terminated strings (this includes char[],wchar_t[],char*, and wchar_t*)
</listitem>
<listitem>
std::pair&lt;iterator,iterator&gt;
</listitem>
</itemizedlist>
</para>
<para>
Collection traits support a subset of the container concept (Std &sect;23.1). This subset
can be described as an input container concept, e.g. a container with immutable content.
Its definition can be found in the header <headername>boost/algorithm/string/collection_traits.hpp</headername>.
</para>
<para>
In the table C denotes a container and c is an object of C.
</para>
<table>
<title>Collection Traits</title>
<tgroup cols="3" align="left">
<thead>
<row>
<entry>Name</entry>
<entry>Standard collection equivalent</entry>
<entry>Description</entry>
</row>Maeterlinck
</thead>
<tbody>
<row>
<entry><classname>value_type_of&lt;C&gt;</classname>::type</entry>
<entry><code>C::value_type</code></entry>
<entry>Type of contained values</entry>
</row>
<row>
<entry><classname>difference_type_of&lt;C&gt;</classname>::type</entry>
<entry><code>C::difference_type</code></entry>
<entry>difference type of the collection</entry>
</row>
<row>
<entry><classname>iterator_of&lt;C&gt;</classname>::type</entry>
<entry><code>C::iterator</code></entry>
<entry>iterator type of the collection</entry>
</row>
<row>
<entry><classname>const_iterator_of&lt;C&gt;</classname>::type</entry>
<entry><code>C::const_iterator</code></entry>
<entry>const_iterator type of the collection</entry>
</row>
<row>
<entry><classname>result_iterator_of&lt;C&gt;</classname>::type</entry>
<entry></entry>
<entry>
result_iterator type of the collection. This type maps to <code>C::iterator</code>
for mutable collection and <code>C::const_iterator</code> for const collection.
</entry>
</row>
<row>
<entry><functionname>begin(c)</functionname></entry>
<entry><code>c.begin()</code></entry>
<entry>
Gets the iterator pointing to the start of the collection.
</entry>
</row>
<row>
<entry><functionname>end(c)</functionname></entry>
<entry><code>c.end()</code></entry>
<entry>
Gets the iterator pointing to the end of the collection.
</entry>
</row>
<row>
<entry><functionname>size(c)</functionname></entry>
<entry><code>c.size()</code></entry>
<entry>
Gets the size of the collection.
</entry>
</row>
<row>
<entry><functionname>empty(c)</functionname></entry>
<entry><code>c.empty()</code></entry>
<entry>
Checks if the collection is empty.
</entry>
</row>
</tbody>
</tgroup>
</table>
<para>
The collection traits are only a temporary part of this library. They will be replaced in the future
releases by Boost.Range library. Use of the internal implementation will be deprecated then.
</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>
+59
View File
@@ -0,0 +1,59 @@
<?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">
<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>
+38
View File
@@ -0,0 +1,38 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><title> Concepts and External Concepts </title><meta http-equiv="Content-Type"content="text/html; charset=iso-8859-1"></head> <body><table ><tr ><td ><img src="../../../../boost.png" width="100%" border="0"></td><td ><h1 >Concepts and External Concepts</h1></td></tr></table><p >Generic programming in C++ is characterized by the use of function and class templates where
the template parameter(s) must satisfy certain requirements.Often these
requirements are so important that we give them a name: we call
such a set of type requirements a <b>concept</b>. We say that a type <i>
conforms to a concept</i> or that it <i>is a model of a concept</i> if it
satisfies all of those requirements. The concept can be specified as a set
of member functions with well-defined semantics
and a set of nested typedefs with well-defined properties.</p><p >Often it much more flexible to provide free-standing functions and typedefs
which provides the exact same semantics (but a different syntax) as
specified
by the concept. This allows generic code to treat different types <i> as if
</i> they fulfilled the concept. In this case we say that the concept has
been <b> externalized </b> or that the new requirements constitutes an <b>external
concept </b>. We say that a type <i> conforms to an external concept </i>
or that it <i> is a model of an external concept </i>. A concept may exist
without a corresponding external concept and conversely.</p><p >Whenever a concept specifies a member function, the corresponding external
concept
must specify a free-standing function of the same name, same return type and
the same argument list except there is an extra first argument which must
be of the type (or a reference to that type) that is to fulfill the external
concept. If the corresonding member function has any cv-qulifiers, the
first argument must have the same cv-qualifiers. Whenever a concept
specifies a nested typedef, the corresponding external concept
specifies a <b>type-generator</b>, that is, a type with a nested typedef
named <code>type</code>. The type-generator has the name as the nested typedef with
<code>_of</code> appended.
The converse relationship of an external concept and its corresponding concept
also holds.</p><p ><b ><i >Example:</i></b></p><p >A type <code>T</code> fulfills the FooConcept if it
has the follwing public members:</p><code> void T::foo( int ) const; <br>
int T::bar(); <br>
typedef <i>implementation defined </i> foo_type;</code><p >The corresponding external concept is the ExternalFooConcept.</p><p >A type <code>T</code> fullfills the ExternalFooConcept if these
free-standing functions and type-generators exists:</p><code>void foo( const T&, int ); <br>
int bar( T& ); <br>
foo_type_of< T >::type;</code> <br> <br><hr size="1" ><h3 >Literature</h3><ul ><li > <a href="http://www.boost.org/more/generic_programming.html#type_generator" target="_self" >Type Generators</a> </li><li > <a href="http://www.boost.org/more/generic_programming.html#concept" target="_self" >Concepts</a> </li><li > <a href="http://www.sgi.com/tech/stl/stl_introduction.html" target="_self" >Concepts and SGI STL</a> </li></ul><hr size="1" ><p >&copy; Thorsten Ottosen 2003-2004 (nesotto_AT_cs.auc.dk).
Permission to copy, use, modify, sell and distribute this software is granted provided this copyright notice appears
in all copies. This software is provided "as is" without express or implied warranty, and with no
claim as to its suitability for any purpose.</p><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br></body></html>
<!-- Copyright Dezide Aps 2003-2004 -->
+47
View File
@@ -0,0 +1,47 @@
<?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">
<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>
+686
View File
@@ -0,0 +1,686 @@
<?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">
<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>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>
</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>
+46
View File
@@ -0,0 +1,46 @@
<?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">
<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>
+45
View File
@@ -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">
<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="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>
+353
View File
@@ -0,0 +1,353 @@
<?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">
<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 <link linkend="string_algo.collection_traits">collection_traits</link>
provides a uniform way of handling different string types.
If there is a need to pass a pair of iterators,
<link linkend="string_algo.iterator_range"><code>iterator_range</code></link>
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 <link linkend="string_algo.iterator_range"><code>iterator_range</code></link>.
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
<link linkend="string_algo.collection_traits">collection_traits</link>.
The following lines transform the result. Notice that
<link linkend="string_algo.iterator_range"><code>iterator_range</code></link> 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 <link linkend="string_algo.iterator_range"><code>iterator_range</code></link>
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_iterator_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_find_iterator It=
make_split_iterator(str1, first_finder("-*-", is_iequal()));
It!=string_find_iterator();
++It)
{
cout &lt;&lt; copy_iterator_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 collection.
</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>
+75
View File
@@ -0,0 +1,75 @@
# Boost string_algo library examples 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.
subproject libs/algorithm/string/example ;
exe conv_example
:
conv_example.cpp
:
<include>$(BOOST_ROOT)
:
;
exe predicate_example
:
predicate_example.cpp
:
<include>$(BOOST_ROOT)
:
;
exe find_example
:
find_example.cpp
:
<include>$(BOOST_ROOT)
:
;
exe replace_example
:
replace_example.cpp
:
<include>$(BOOST_ROOT)
:
;
exe rle_example
:
rle_example.cpp
:
<include>$(BOOST_ROOT)
:
;
exe trim_example
:
trim_example.cpp
:
<include>$(BOOST_ROOT)
:
;
exe regex_example
:
regex_example.cpp
<lib>../../../regex/build/boost_regex
:
<include>$(BOOST_ROOT)
:
;
exe split_example
:
split_example.cpp
:
<include>$(BOOST_ROOT)
:
;
+41
View File
@@ -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;
}
+58
View File
@@ -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;
}
+61
View File
@@ -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;
}
+42
View File
@@ -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;
}
+88
View File
@@ -0,0 +1,88 @@
// 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>
//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;
}
+241
View File
@@ -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;
}
+63
View File
@@ -0,0 +1,63 @@
// 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/iterator_range.hpp>
#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_iterator_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;
}
+47
View File
@@ -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;
}
+9
View File
@@ -0,0 +1,9 @@
<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>
</body>
</html>
+85
View File
@@ -0,0 +1,85 @@
# 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.
subproject libs/algorithm/string/test ;
# bring in rules for testing
import testing ;
# Make tests run by default.
DEPENDS all : test ;
{
test-suite algorithm/string
: [ run
container_test.cpp
: :
:
std::locale-support
std::facet-support
: container
]
[ run
trim_test.cpp
: :
:
std::locale-support
std::facet-support
: trim
]
[ run
conv_test.cpp
: :
:
std::locale-support
std::facet-support
: conv
]
[ run
predicate_test.cpp
: :
:
std::locale-support
std::facet-support
: predicate
]
[ run
find_test.cpp
: :
:
std::locale-support
std::facet-support
: find
]
[ run
split_test.cpp
: :
:
std::locale-support
std::facet-support
: split
]
[ run
replace_test.cpp
: :
:
std::locale-support
std::facet-support
: replace
]
[ run
regex_test.cpp
<lib>../../../regex/build/boost_regex
: :
:
: regex
]
;
}
+63
View File
@@ -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
container_test.cpp
: :
:
: container
]
[ 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
replace_test.cpp
: :
:
: replace
]
[ run
regex_test.cpp
../../../regex/build//boost_regex
: :
:
: regex
]
;
+127
View File
@@ -0,0 +1,127 @@
// 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/collection_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 <utility>
#include <vector>
#include <boost/type_traits.hpp>
// test tools
#include <boost/test/test_tools.hpp>
using namespace std;
using namespace boost;
namespace algo = ::boost::algorithm;
template< typename T >
void argument_cv_test( const T& C, const string& strResult )
{
BOOST_CHECK( equals( make_iterator_range(algo::begin(C),algo::end(C)), strResult ) );
BOOST_CHECK( algo::size(C)==strResult.size() );
BOOST_CHECK( algo::empty(C)==strResult.empty() );
}
template< typename T >
void argument_test( T& C, const string& strResult )
{
BOOST_CHECK( equals( make_iterator_range(algo::begin(C),algo::end(C)), strResult ) );
BOOST_CHECK( algo::size(C)==strResult.size() );
BOOST_CHECK( algo::empty(C)==strResult.empty() );
}
void container_test()
{
BOOST_CHECKPOINT( "type test" );
// types test
BOOST_REQUIRE( (is_same<
algo::result_iterator_of<string>::type,
string::iterator>::value) );
BOOST_REQUIRE( (is_same<
algo::result_iterator_of<const string>::type,
string::const_iterator>::value) );
BOOST_REQUIRE( (is_same<
algo::result_iterator_of<char[4]>::type, char*>::value) );
BOOST_REQUIRE( (is_same<
algo::result_iterator_of<const char[4]>::type,
const char*>::value) );
BOOST_REQUIRE( (is_same<
algo::result_iterator_of<char*>::type, char*>::value) );
BOOST_REQUIRE( (is_same<
algo::result_iterator_of<const char*>::type,
const char*>::value) );
BOOST_REQUIRE( (is_same<
algo::result_iterator_of<
pair<string::iterator, string::iterator> >::type, string::iterator>::value) );
BOOST_REQUIRE( (is_same<
algo::result_iterator_of<
const pair<string::iterator, string::iterator> >::type,
string::iterator>::value) );
BOOST_CHECKPOINT( "non-empty sequence test" );
string str1("abc");
vector<char> vec1( str1.begin(), str1.end() );
pair<string::iterator, string::iterator> pair1=
make_pair( str1.begin(), str1.end() );
char ach1[]="abc";
char *pch1="abc";
// begin/end tests
argument_cv_test( str1, "abc" );
argument_test( str1, "abc" );
argument_cv_test( vec1, "abc" );
argument_test( vec1, "abc" );
argument_cv_test( pair1, "abc" );
argument_test( pair1, "abc" );
argument_cv_test( ach1, "abc" );
argument_test( ach1, "abc" );
argument_cv_test( pch1, "abc" );
argument_test( pch1, "abc" );
BOOST_CHECKPOINT( "empty sequence test" );
string str2;
vector<char> vec2( str2.begin(), str2.end() );
pair<string::iterator, string::iterator> pair2=
make_pair( str2.begin(), str2.end() );
char ach2[]="";
char *pch2=0;
// begin/end tests
argument_cv_test( str2, "" );
argument_test( str2, "" );
argument_cv_test( vec2, "" );
argument_test( vec2, "" );
argument_cv_test( pair2, "" );
argument_test( pair2, "" );
argument_cv_test( ach2, "" );
argument_test( ach2, "" );
argument_cv_test( pch2, "" );
argument_test( pch2, "" );
};
// test main
int test_main( int, char*[] )
{
container_test();
return 0;
}
+95
View File
@@ -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=="" );
free(pch1);
free(pch2);
}
// test main
int test_main( int, char*[] )
{
conv_test();
return 0;
}
+231
View File
@@ -0,0 +1,231 @@
// 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("");
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) );
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=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) );
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) );
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;
}
+126
View File
@@ -0,0 +1,126 @@
// 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" ) );
// 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;
}
+137
View File
@@ -0,0 +1,137 @@
// 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/sequence_traits.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");
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 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();
replace_test();
return 0;
}
+282
View File
@@ -0,0 +1,282 @@
// 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( ireplace_nth, "1AbC3abc2", "aBc" C_ 0 C_ "YYY", string("1YYY3abc2") );
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", string("") C_ 0 C_ string("XXXX"), string("1abc3abc2") );
TEST_ALGO( replace_nth, "", string("") C_ 0 C_ string("XXXX"), string("") );
TEST_ALGO( erase_nth, "1abc3abc2", string("abc") C_ 0, string("13abc2") );
TEST_ALGO( ierase_nth, "1aBc3aBc2", "ABC" C_ 0, string("13aBc2") );
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( 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_ "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, "abc3abc2", 0 C_ string("XXXX"), string("abc3abc2") );
TEST_ALGO( replace_head, "", 4 C_ string("XXXX"), string("") );
TEST_ALGO( erase_head, "abc3abc2", 3, string("3abc2") );
TEST_ALGO( erase_head, "abc3abc2", 0, string("abc3abc2") );
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("abc3YYY") );
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, "abc3abc", 0 C_ string("XXXX"), string("abc3abc") );
TEST_ALGO( replace_tail, "", 4 C_ string("XXXX"), string("") );
TEST_ALGO( erase_tail, "abc3abc", 3, string("abc3") );
TEST_ALGO( erase_tail, "abc3abc", 0, string("abc3abc") );
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;
}
+131
View File
@@ -0,0 +1,131 @@
// 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");
string str3("xx");
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()==2 );
BOOST_CHECK( tokens[0]==string("Xx") );
BOOST_CHECK( tokens[1]==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,
str1,
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(
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;
}
+118
View File
@@ -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;
}
+1
View File
@@ -0,0 +1 @@
The existance of this file tells the regression reporting programs that the directory contains sub-directories which are libraries.
-143
View File
@@ -1,143 +0,0 @@
/*
Copyright (C) 2008 Jesse Williamson
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 <vector>
#include <numeric>
#include <iostream>
#include <algorithm>
#include <functional>
#include <boost/test/included/test_exec_monitor.hpp>
#include <boost/algorithm/iota.hpp>
#include <boost/assign/std/vector.hpp>
#include <boost/algorithm/transform_if.hpp>
using namespace std;
using namespace boost::assign;
using namespace boost::algorithm::sequence;
int make_double(const int& i)
{
return i*2;
}
int mult(const int& i, const int& i2)
{
return i*i2;
}
bool is_even(const int& i)
{
return 0 == i % 2;
}
bool is_odd(const int& i)
{
return !is_even(i);
}
bool both_even(const int& i, const int& i2)
{
return is_even(i) && is_even(i2);
}
int test_main(int, char **)
{
// transform_if(), unary op:
{
// ...on a vector:
vector<int> v(3), v2;
v += 1, 2, 3;
transform_if(v.begin(), v.end(), back_inserter(v2), make_double, is_even);
BOOST_CHECK(4 == accumulate(v2.begin(), v2.end(), 0));
v2.clear();
transform_if(v.begin(), v.end(), back_inserter(v2), make_double, is_odd);
BOOST_CHECK(4 != accumulate(v2.begin(), v2.end(), 0));
BOOST_CHECK(8 == accumulate(v2.begin(), v2.end(), 0));
// ...on an array:
int x[3], y[3];
x[0] = 2;
x[1] = 3;
x[2] = 2;
memset(&y, 0, sizeof(y));
transform_if(x, x + 3, y, make_double, is_even);
BOOST_CHECK(8 == accumulate(y, y + 3, 0));
}
// transform_if() unary op with a range:
{
vector<int> v(3), v2;
v += 1, 2, 3;
transform_if(v, back_inserter(v2), make_double, is_even);
BOOST_CHECK(4 == accumulate(v2.begin(), v2.end(), 0));
}
// transform_if() binary op:
{
// ...on a vector:
vector<int> v(3), v2(3), v3;
v += 1, 2, 3;
v2 += 1, 2, 3;
transform_if(v.begin(), v.end(), v2.begin(), back_inserter(v3), mult, both_even);
BOOST_CHECK(4 == accumulate(v3.begin(), v3.end(), 0));
// ...on an array:
int x[3], y[3], z[3];
x[0] = 2;
x[1] = 3;
x[2] = 2;
y[0] = 1;
y[1] = 3;
y[2] = 4;
memset(&z, 0, sizeof(z));
transform_if(x, x + 3, y, z, mult, both_even);
BOOST_CHECK(8 == accumulate(z, z + 3, 0));
}
// transform_if() binary with a range:
{
vector<int> v(3), v2(3), v3;
v += 1, 2, 3;
v2 += 1, 2, 3;
transform_if(v, v2.begin(), back_inserter(v3), mult, both_even);
BOOST_CHECK(4 == accumulate(v3.begin(), v3.end(), 0));
}
return 0;
}