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.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
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 ( 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, std::ptrdiff_t 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 ( first1: haystack.begin (), last1: haystack.end (), first2: needle.begin (), last2: 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(x: haystack.end(), y: haystack.end());
108 else
109 exp = std::make_pair(x&: exp_start, y: 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 ( first1: haystack.begin (), last1: haystack.end (), first2: needle.begin (), last2: 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 ( prompt: "std::search", diff: 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
135BOOST_AUTO_TEST_CASE( test_main )
136{
137 vec c1 = ReadFromFile ( name: "search_test_data/0001.corpus" );
138 vec p1b = ReadFromFile ( name: "search_test_data/0002b.pat" );
139 vec p1e = ReadFromFile ( name: "search_test_data/0002e.pat" );
140 vec p1n = ReadFromFile ( name: "search_test_data/0002n.pat" );
141 vec p1f = ReadFromFile ( name: "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 ( haystack: c1, needle: p1b, expected: 0 ); // Find it at position zero
147 std::cout << "---- Middle -----" << std::endl;
148 check_one ( haystack: c1, needle: p1f, expected: -2 ); // Don't know answer
149 std::cout << "------ End ------" << std::endl;
150 check_one ( haystack: c1, needle: p1e, expected: static_cast<std::ptrdiff_t>(c1.size() - p1e.size ()));
151 std::cout << "--- Not found ---" << std::endl;
152 check_one ( haystack: c1, needle: p1n, expected: -1 ); // Not found
153 }
154

source code of boost/libs/algorithm/test/search_test3.cpp