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
25typedef 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
65namespace {
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 ( in, temp ))
72 retVal.push_back ( 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 ( haystack.begin (), haystack.end (), needle.begin (), 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 ( haystack.begin (), haystack.end (), needle.begin (), 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 ( "std::search", 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
129BOOST_AUTO_TEST_CASE( test_main )
130{
131 vec c1 = ReadFromFile ( "search_test_data/0001.corpus" );
132 vec p1b = ReadFromFile ( "search_test_data/0002b.pat" );
133 vec p1e = ReadFromFile ( "search_test_data/0002e.pat" );
134 vec p1n = ReadFromFile ( "search_test_data/0002n.pat" );
135 vec p1f = ReadFromFile ( "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 ( c1, p1b, 0 ); // Find it at position zero
141 std::cout << "---- Middle -----" << std::endl;
142 check_one ( c1, p1f, -2 ); // Don't know answer
143 std::cout << "------ End ------" << std::endl;
144 check_one ( c1, p1e, c1.size() - p1e.size ());
145 std::cout << "--- Not found ---" << std::endl;
146 check_one ( c1, p1n, -1 ); // Not found
147 }
148