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
10 #include <boost/algorithm/searching/boyer_moore.hpp>
11 #include <boost/algorithm/searching/boyer_moore_horspool.hpp>
12 #include <boost/algorithm/searching/knuth_morris_pratt.hpp>
13
14 #define BOOST_TEST_MAIN
15 #include <boost/test/unit_test.hpp>
16
17 #include <ctime> // for clock_t
18 #include <iostream>
19 #include <fstream>
20 #include <iomanip>
21 #include <algorithm>
22 #include <vector>
23 #include <string>
24
25 typedef std::vector<std::string> vec;
26 #define NUM_TRIES 100
27
28 #define runOne(call, refDiff) { \
29 std::clock_t bTime, eTime; \
30 bTime = std::clock (); \
31 for ( i = 0; i < NUM_TRIES; ++i ) { \
32 res = boost::algorithm::call \
33 ( haystack.begin (), haystack.end (), \
34 needle.begin (), needle.end ()); \
35 if ( res != exp ) { \
36 std::cout << "On run # " << i << " expected " \
37 << exp.first - haystack.begin () << " got " \
38 << res.first - haystack.begin () << std::endl; \
39 throw std::runtime_error \
40 ( "Unexpected result from " #call ); \
41 } \
42 } \
43 eTime = std::clock (); \
44 printRes ( #call, eTime - bTime, refDiff ); }
45
46 #define runObject(obj, refDiff) { \
47 std::clock_t bTime, eTime; \
48 bTime = std::clock (); \
49 boost::algorithm::obj <vec::const_iterator> \
50 s_o ( needle.begin (), needle.end ()); \
51 for ( i = 0; i < NUM_TRIES; ++i ) { \
52 res = s_o ( haystack.begin (), haystack.end ()); \
53 if ( res != exp ) { \
54 std::cout << "On run # " << i << " expected " \
55 << exp.first - haystack.begin () << " got " \
56 << res.first - haystack.begin () << std::endl; \
57 throw std::runtime_error \
58 ( "Unexpected result from " #obj " object" ); \
59 } \
60 } \
61 eTime = std::clock (); \
62 printRes ( #obj " object", eTime - bTime, refDiff ); }
63
64
65 namespace {
66
ReadFromFile(const char * name)67 vec ReadFromFile ( const char *name ) {
68 std::ifstream in ( name, std::ios_base::binary | std::ios_base::in );
69 std::string temp;
70 vec retVal;
71 while ( std::getline ( in, temp ))
72 retVal.push_back ( temp );
73
74 return retVal;
75 }
76
printRes(const char * prompt,unsigned long diff,unsigned long stdDiff)77 void printRes ( const char *prompt, unsigned long diff, unsigned long stdDiff ) {
78 std::cout
79 << std::setw(34) << prompt << " "
80 << std::setw(6) << ( 1.0 * diff) / CLOCKS_PER_SEC << " seconds\t"
81 << std::setw(5) << (100.0 * diff) / stdDiff << "% \t"
82 << std::setw(12) << diff;
83 if ( diff > stdDiff )
84 std::cout << " !!";
85 std::cout << std::endl;
86 }
87
check_one(const vec & haystack,const vec & needle,int expected)88 void check_one ( const vec &haystack, const vec &needle, int expected ) {
89 std::size_t i;
90 std::clock_t sTime;
91 unsigned long stdDiff;
92
93 std::pair<vec::const_iterator, vec::const_iterator> res;
94 std::pair<vec::const_iterator, vec::const_iterator> exp; // the expected result
95 vec::const_iterator exp_start;
96
97 if ( expected >= 0 )
98 exp_start = haystack.begin () + expected;
99 else if ( expected == -1 )
100 exp_start = haystack.end (); // we didn't find it1
101 else if ( expected == -2 )
102 exp_start = std::search ( haystack.begin (), haystack.end (), needle.begin (), needle.end ());
103 else
104 throw std::logic_error ( "Expected must be -2, -1, or >= 0" );
105
106 if ( expected == -1 )
107 exp = std::make_pair(haystack.end(), haystack.end());
108 else
109 exp = std::make_pair(exp_start, exp_start + needle.size());
110
111 std::cout << "Pattern is " << needle.size () << " entries long" << std::endl;
112 std::cout << "Corpus is " << haystack.size () << " entries long" << std::endl;
113
114 // First, the std library search
115 sTime = std::clock ();
116 for ( i = 0; i < NUM_TRIES; ++i ) {
117 vec::const_iterator s_res = std::search ( haystack.begin (), haystack.end (), needle.begin (), needle.end ());
118 if ( s_res != exp.first ) {
119 std::cout << "On run # " << i << " expected " << exp.first - haystack.begin () << " got " << s_res - haystack.begin () << std::endl;
120 throw std::runtime_error ( "Unexpected result from std::search" );
121 }
122 }
123 stdDiff = std::clock () - sTime;
124 printRes ( "std::search", stdDiff, stdDiff );
125
126 runOne ( boyer_moore_search, stdDiff );
127 runObject ( boyer_moore, stdDiff );
128 runOne ( boyer_moore_horspool_search, stdDiff );
129 runObject ( boyer_moore_horspool, stdDiff );
130 runOne ( knuth_morris_pratt_search, stdDiff );
131 runObject ( knuth_morris_pratt, stdDiff );
132 }
133 }
134
BOOST_AUTO_TEST_CASE(test_main)135 BOOST_AUTO_TEST_CASE( test_main )
136 {
137 vec c1 = ReadFromFile ( "search_test_data/0001.corpus" );
138 vec p1b = ReadFromFile ( "search_test_data/0002b.pat" );
139 vec p1e = ReadFromFile ( "search_test_data/0002e.pat" );
140 vec p1n = ReadFromFile ( "search_test_data/0002n.pat" );
141 vec p1f = ReadFromFile ( "search_test_data/0002f.pat" );
142
143 std::cout << std::ios::fixed << std::setprecision(4);
144 // std::cout << "Corpus is " << c1.size () << " entries long\n";
145 std::cout << "--- Beginning ---" << std::endl;
146 check_one ( c1, p1b, 0 ); // Find it at position zero
147 std::cout << "---- Middle -----" << std::endl;
148 check_one ( c1, p1f, -2 ); // Don't know answer
149 std::cout << "------ End ------" << std::endl;
150 check_one ( c1, p1e, c1.size() - p1e.size ());
151 std::cout << "--- Not found ---" << std::endl;
152 check_one ( c1, p1n, -1 ); // Not found
153 }
154