ceph/src/boost/libs/algorithm/test/search_test4.cpp

   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.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
  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 ( in, temp ))
  60             retVal.push_back ( temp );
  61
  62         return retVal;
  63         }
  64
  65     void check_one ( const vec &haystack, const vec &needle, int 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 ( haystack.begin (), haystack.end (), needle.begin (), 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(haystack.end(), haystack.end());
  82                 else
  83                         exp = std::make_pair(exp_start, 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 ( haystack.begin (), haystack.end (), needle.begin (), 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
 105 BOOST_AUTO_TEST_CASE( test_main )
 106 {
 107     vec c1  = ReadFromFile ( "search_test_data/0001.corpus" );
 108     vec p1b = ReadFromFile ( "search_test_data/0002b.pat" );
 109     vec p1e = ReadFromFile ( "search_test_data/0002e.pat" );
 110     vec p1n = ReadFromFile ( "search_test_data/0002n.pat" );
 111     vec p1f = ReadFromFile ( "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 ( c1, p1b, 0 );       //  Find it at position zero
 117     std::cout << "---- Middle -----" << std::endl;
 118     check_one ( c1, p1f, -2 );      //  Don't know answer
 119     std::cout << "------ End ------" << std::endl;
 120     check_one ( c1, p1e, c1.size() - p1e.size ());
 121     std::cout << "--- Not found ---" << std::endl;
 122     check_one ( c1, p1n, -1 );      //  Not found
 123     }