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