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

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