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 - haystack.begin () << " got " \ |
34 | << res - 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 - haystack.begin () << " got " \ |
47 | << res - haystack.begin () << std::endl; \ |
48 | throw std::runtime_error \ |
49 | ( "Unexpected result from " #obj " object" ); \ |
50 | } \ |
51 | } |
52 | |
53 | namespace { |
54 | |
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 ( is&: in, str&: temp )) |
60 | retVal.push_back ( x: temp ); |
61 | |
62 | return retVal; |
63 | } |
64 | |
65 | void check_one ( const vec &haystack, const vec &needle, int expected ) { |
66 | |
67 | vec::const_iterator res; |
68 | vec::const_iterator exp; // the expected result |
69 | |
70 | if ( expected >= 0 ) |
71 | exp = haystack.begin () + expected; |
72 | else if ( expected == -1 ) |
73 | exp = haystack.end (); // we didn't find it1 |
74 | else if ( expected == -2 ) |
75 | exp = std::search ( first1: haystack.begin (), last1: haystack.end (), first2: needle.begin (), last2: needle.end ()); |
76 | else |
77 | throw std::logic_error ( "Expected must be -2, -1, or >= 0" ); |
78 | |
79 | std::cout << "Pattern is " << needle.size () << " entries long" << std::endl; |
80 | std::cout << "Corpus is " << haystack.size () << " entries long" << std::endl; |
81 | |
82 | // First, the std library search |
83 | res = std::search ( first1: haystack.begin (), last1: haystack.end (), first2: needle.begin (), last2: needle.end ()); |
84 | if ( res != exp ) { |
85 | std::cout << "Expected " << exp - haystack.begin () << " got " << res - haystack.begin () << std::endl; |
86 | throw std::runtime_error ( "Unexpected result from std::search" ); |
87 | } |
88 | |
89 | runOne ( boyer_moore_search, stdDiff ); |
90 | runObject ( boyer_moore, stdDiff ); |
91 | runOne ( boyer_moore_horspool_search, stdDiff ); |
92 | runObject ( boyer_moore_horspool, stdDiff ); |
93 | runOne ( knuth_morris_pratt_search, stdDiff ); |
94 | runObject ( knuth_morris_pratt, stdDiff ); |
95 | } |
96 | |
97 | } |
98 | |
99 | BOOST_AUTO_TEST_CASE( test_main ) |
100 | { |
101 | vec c1 = ReadFromFile ( name: "search_test_data/0001.corpus" ); |
102 | vec p1b = ReadFromFile ( name: "search_test_data/0002b.pat" ); |
103 | vec p1e = ReadFromFile ( name: "search_test_data/0002e.pat" ); |
104 | vec p1n = ReadFromFile ( name: "search_test_data/0002n.pat" ); |
105 | vec p1f = ReadFromFile ( name: "search_test_data/0002f.pat" ); |
106 | |
107 | std::cout << std::ios::fixed << std::setprecision(4); |
108 | // std::cout << "Corpus is " << c1.size () << " entries long\n"; |
109 | std::cout << "--- Beginning ---" << std::endl; |
110 | check_one ( haystack: c1, needle: p1b, expected: 0 ); // Find it at position zero |
111 | std::cout << "---- Middle -----" << std::endl; |
112 | check_one ( haystack: c1, needle: p1f, expected: -2 ); // Don't know answer |
113 | std::cout << "------ End ------" << std::endl; |
114 | check_one ( haystack: c1, needle: p1e, expected: c1.size() - p1e.size ()); |
115 | std::cout << "--- Not found ---" << std::endl; |
116 | check_one ( haystack: c1, needle: p1n, expected: -1 ); // Not found |
117 | } |
118 | |