1 /*
2 Copyright (c) Marshall Clow 2010-2012.
3
4 Distributed under the Boost Software License, Version 1.0. (See accompanying
5 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6
7 For more information, see http://www.boost.org
8
9 Testing the range-based interfaces
10 */
11
12 #include <boost/algorithm/searching/boyer_moore.hpp>
13 #include <boost/algorithm/searching/boyer_moore_horspool.hpp>
14 #include <boost/algorithm/searching/knuth_morris_pratt.hpp>
15
16 #define BOOST_TEST_MAIN
17 #include <boost/test/unit_test.hpp>
18
19 #include <iostream>
20 #include <fstream>
21 #include <iomanip>
22 #include <algorithm>
23 #include <vector>
24 #include <string>
25
26 typedef std::vector<std::string> vec;
27 #define NUM_TRIES 100
28
29 #define runOne(call, refDiff) { \
30 res = boost::algorithm::call ( haystack, needle ); \
31 if ( res != exp ) { \
32 std::cout << "Expected " \
33 << exp.first - haystack.begin () << " got " \
34 << res.first - haystack.begin () << std::endl; \
35 throw std::runtime_error \
36 ( "Unexpected result from " #call ); \
37 } \
38 }
39
40 #define runObject(obj, refDiff) { \
41 boost::algorithm::obj <vec::const_iterator> s_o = \
42 boost::algorithm::make_##obj ( needle ); \
43 res = s_o ( haystack ); \
44 if ( res != exp ) { \
45 std::cout << "Expected " \
46 << exp.first - haystack.begin () << " got " \
47 << res.first - haystack.begin () << std::endl; \
48 throw std::runtime_error \
49 ( "Unexpected result from " #obj " object" ); \
50 } \
51 }
52
53 namespace {
54
ReadFromFile(const char * name)55 vec ReadFromFile ( const char *name ) {
56 std::ifstream in ( name, std::ios_base::binary | std::ios_base::in );
57 std::string temp;
58 vec retVal;
59 while ( std::getline ( in, temp ))
60 retVal.push_back ( temp );
61
62 return retVal;
63 }
64
check_one(const vec & haystack,const vec & needle,int expected)65 void check_one ( const vec &haystack, const vec &needle, int expected ) {
66
67 std::pair<vec::const_iterator, vec::const_iterator> res;
68 std::pair<vec::const_iterator, vec::const_iterator> exp; // the expected result
69 vec::const_iterator exp_start;
70
71 if ( expected >= 0 )
72 exp_start = haystack.begin () + expected;
73 else if ( expected == -1 )
74 exp_start = haystack.end (); // we didn't find it1
75 else if ( expected == -2 )
76 exp_start = std::search ( haystack.begin (), haystack.end (), needle.begin (), needle.end ());
77 else
78 throw std::logic_error ( "Expected must be -2, -1, or >= 0" );
79
80 if ( expected == -1 )
81 exp = std::make_pair(haystack.end(), haystack.end());
82 else
83 exp = std::make_pair(exp_start, exp_start + needle.size());
84
85 std::cout << "Pattern is " << needle.size () << " entries long" << std::endl;
86 std::cout << "Corpus is " << haystack.size () << " entries long" << std::endl;
87
88 // First, the std library search
89 vec::const_iterator s_res = std::search ( haystack.begin (), haystack.end (), needle.begin (), needle.end ());
90 if ( s_res != exp.first ) {
91 std::cout << "Expected " << exp.first - haystack.begin () << " got " << s_res - haystack.begin () << std::endl;
92 throw std::runtime_error ( "Unexpected result from std::search" );
93 }
94
95 runOne ( boyer_moore_search, stdDiff );
96 runObject ( boyer_moore, stdDiff );
97 runOne ( boyer_moore_horspool_search, stdDiff );
98 runObject ( boyer_moore_horspool, stdDiff );
99 runOne ( knuth_morris_pratt_search, stdDiff );
100 runObject ( knuth_morris_pratt, stdDiff );
101 }
102
103 }
104
BOOST_AUTO_TEST_CASE(test_main)105 BOOST_AUTO_TEST_CASE( test_main )
106 {
107 vec c1 = ReadFromFile ( "search_test_data/0001.corpus" );
108 vec p1b = ReadFromFile ( "search_test_data/0002b.pat" );
109 vec p1e = ReadFromFile ( "search_test_data/0002e.pat" );
110 vec p1n = ReadFromFile ( "search_test_data/0002n.pat" );
111 vec p1f = ReadFromFile ( "search_test_data/0002f.pat" );
112
113 std::cout << std::ios::fixed << std::setprecision(4);
114 // std::cout << "Corpus is " << c1.size () << " entries long\n";
115 std::cout << "--- Beginning ---" << std::endl;
116 check_one ( c1, p1b, 0 ); // Find it at position zero
117 std::cout << "---- Middle -----" << std::endl;
118 check_one ( c1, p1f, -2 ); // Don't know answer
119 std::cout << "------ End ------" << std::endl;
120 check_one ( c1, p1e, c1.size() - p1e.size ());
121 std::cout << "--- Not found ---" << std::endl;
122 check_one ( c1, p1n, -1 ); // Not found
123 }
124