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 - haystack.begin () << " got " \ |
38 | << res - 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 - haystack.begin () << " got " \ |
56 | << res - 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 | |
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 ( is&: in, str&: temp )) |
72 | retVal.push_back ( x: temp ); |
73 | |
74 | return retVal; |
75 | } |
76 | |
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 | |
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 | vec::const_iterator res; |
94 | vec::const_iterator exp; // the expected result |
95 | |
96 | if ( expected >= 0 ) |
97 | exp = haystack.begin () + expected; |
98 | else if ( expected == -1 ) |
99 | exp = haystack.end (); // we didn't find it1 |
100 | else if ( expected == -2 ) |
101 | exp = std::search ( first1: haystack.begin (), last1: haystack.end (), first2: needle.begin (), last2: needle.end ()); |
102 | else |
103 | throw std::logic_error ( "Expected must be -2, -1, or >= 0" ); |
104 | |
105 | std::cout << "Pattern is " << needle.size () << " entries long" << std::endl; |
106 | std::cout << "Corpus is " << haystack.size () << " entries long" << std::endl; |
107 | |
108 | // First, the std library search |
109 | sTime = std::clock (); |
110 | for ( i = 0; i < NUM_TRIES; ++i ) { |
111 | res = std::search ( first1: haystack.begin (), last1: haystack.end (), first2: needle.begin (), last2: needle.end ()); |
112 | if ( res != exp ) { |
113 | std::cout << "On run # " << i << " expected " << exp - haystack.begin () << " got " << res - haystack.begin () << std::endl; |
114 | throw std::runtime_error ( "Unexpected result from std::search" ); |
115 | } |
116 | } |
117 | stdDiff = std::clock () - sTime; |
118 | printRes ( prompt: "std::search" , diff: stdDiff, stdDiff ); |
119 | |
120 | runOne ( boyer_moore_search, stdDiff ); |
121 | runObject ( boyer_moore, stdDiff ); |
122 | runOne ( boyer_moore_horspool_search, stdDiff ); |
123 | runObject ( boyer_moore_horspool, stdDiff ); |
124 | runOne ( knuth_morris_pratt_search, stdDiff ); |
125 | runObject ( knuth_morris_pratt, stdDiff ); |
126 | } |
127 | } |
128 | |
129 | BOOST_AUTO_TEST_CASE( test_main ) |
130 | { |
131 | vec c1 = ReadFromFile ( name: "search_test_data/0001.corpus" ); |
132 | vec p1b = ReadFromFile ( name: "search_test_data/0002b.pat" ); |
133 | vec p1e = ReadFromFile ( name: "search_test_data/0002e.pat" ); |
134 | vec p1n = ReadFromFile ( name: "search_test_data/0002n.pat" ); |
135 | vec p1f = ReadFromFile ( name: "search_test_data/0002f.pat" ); |
136 | |
137 | std::cout << std::ios::fixed << std::setprecision(4); |
138 | // std::cout << "Corpus is " << c1.size () << " entries long\n"; |
139 | std::cout << "--- Beginning ---" << std::endl; |
140 | check_one ( haystack: c1, needle: p1b, expected: 0 ); // Find it at position zero |
141 | std::cout << "---- Middle -----" << std::endl; |
142 | check_one ( haystack: c1, needle: p1f, expected: -2 ); // Don't know answer |
143 | std::cout << "------ End ------" << std::endl; |
144 | check_one ( haystack: c1, needle: p1e, expected: c1.size() - p1e.size ()); |
145 | std::cout << "--- Not found ---" << std::endl; |
146 | check_one ( haystack: c1, needle: p1n, expected: -1 ); // Not found |
147 | } |
148 | |