bslstl_defaultsearcher.h

Go to the documentation of this file.

/// @file bslstl_defaultsearcher.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bslstl_defaultsearcher.h                                           -*-C++-*-
#ifndef INCLUDED_BSLSTL_DEFAULTSEARCHER
#define INCLUDED_BSLSTL_DEFAULTSEARCHER
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
/// @defgroup bslstl_defaultsearcher bslstl_defaultsearcher
/// @brief  Provide an STL-compliant `default_searcher` class.
/// @addtogroup bsl
/// @{
/// @addtogroup bslstl
/// @{
/// @addtogroup bslstl_defaultsearcher
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bslstl_defaultsearcher-purpose"> Purpose</a>
/// * <a href="#bslstl_defaultsearcher-classes"> Classes </a>
/// * <a href="#bslstl_defaultsearcher-canonical-header"> Canonical Header </a>
/// * <a href="#bslstl_defaultsearcher-description"> Description </a>
///   * <a href="#bslstl_defaultsearcher-algorithm"> Algorithm </a>
///   * <a href="#bslstl_defaultsearcher-iterator-requirements"> Iterator Requirements </a>
///   * <a href="#bslstl_defaultsearcher-comparator-requirements"> Comparator Requirements </a>
///   * <a href="#bslstl_defaultsearcher-optimizations-for-bslstl-defaultsearcher"> Optimizations for bslstl::DefaultSearcher </a>
///   * <a href="#bslstl_defaultsearcher-usage"> Usage </a>
///     * <a href="#bslstl_defaultsearcher-example-1-basic-usage"> Example 1: Basic Usage </a>
///     * <a href="#bslstl_defaultsearcher-example-2-defining-a-comparator"> Example 2: Defining a Comparator </a>
///     * <a href="#bslstl_defaultsearcher-example-3-non-char-searches"> Example 3: Non-char Searches </a>
///
/// # Purpose {#bslstl_defaultsearcher-purpose}
/// Provide an STL-compliant @ref default_searcher  class.
///
/// # Classes {#bslstl_defaultsearcher-classes}
///
/// -  bsl::default_searcher:   class template to search via the "naive" algorithm
/// -  bslstl::DefaultSearcher: class template to search via the "naive" algorithm
///
/// # Canonical Header {#bslstl_defaultsearcher-canonical-header}
/// bsl_functional.h
///
/// @see  bslstl_boyermoorehorspoolsearcher
///
/// # Description {#bslstl_defaultsearcher-description}
/// This component defines two class templates,
/// `bsl::default_searcher` and `bslstl::DefaultSearcher`.  Both are compliant
/// with section `[func.search.default]` of the C++ Standard (C++17 and later).
///
/// `bsl::default_searcher` is strictly limited to the Standard and is provided
/// for clients for whom standard compliance is a priority.
/// `bslstl::DefaultSearcher` provides several additional accessors that are not
/// mentioned in the Standard.
///
/// Except where there is a relevant difference, both are described below as if
/// they were one.
///
/// This class template has two parameters:
///
///  `FORWARD_ITR_NEEDLE`:
///    The iterator type that defines on construction the range of values to be
///    sought (the "needle"), and
/// 
///  `EQUAL`:
///    an optional parameter that defines the class used to compare those
///    values.
///
/// The class also provides a functor-style interface that accepts two iterators
/// that define the range of values to be searched (the "haystack").  Once
/// constructed the searcher object can be re-used to search multiple haystacks
/// (for the same needle).
///
/// The iterators defining the haystack need not be of the same type as those
/// that define the needle.  Moreover, the search method of the searcher can be
/// overloaded for an arbitrary different haystack iterators (subject to
/// {Iterator Requirements}).
///
/// ## Algorithm {#bslstl_defaultsearcher-algorithm}
///
///
/// The `bslstl::DefaultSearcher` class uses the classic, "naive" algorithm.
/// The needle is sought at the beginning of the haystack and, if not found
/// there, the start position in the haystack is incremented.  That is repeated
/// until the needle is found in the haystack or the end of the haystack is
/// encountered.  The time complexity is `O(M * N)`, where `M` is the length of
/// the needle and `N` is the length of the haystack.
///
/// There are more sophisticated algorithms available; however, those typically
/// require creating and retaining metadata derived from the needle and/or
/// haystack.  If the needle is short and the haystack of moderate length, the
/// naive algorithm may be faster than generating that metadata, especially if
/// the search is one-time and the metadata cost cannot be amortized.
///
/// Another advantage of the "default" searcher is that it accepts (relatively
/// simple) *ForwardIterator*s whereas more sophisticated algorithms typically
/// require (more fully-featured) *RandomIterator*s.
///
/// ## Iterator Requirements {#bslstl_defaultsearcher-iterator-requirements}
///
///
/// The two independent iterator types associated with this class -- one
/// defining the needle, the other defining the haystack -- must meet the
/// requirements of *ForwardIterator*.
///
/// Additionally:
/// * These iterators can be constant.
/// * When dereferenced, they must both refer to the same value type.
///
/// Either of the iterator types are allowed to throw exceptions.
///
/// Iterators defining needles are required to remain valid as long as the
/// searcher object might be used.
///
/// ## Comparator Requirements {#bslstl_defaultsearcher-comparator-requirements}
///
///
/// The comparator class must meet the requirements of *BinaryPredicate*:
/// * The class defines an `operator()` method, which, given an
///   *ForwardIterator*, `iterator`, may be invoked as
///   `operator()(*iterator, *iterator)`.
/// * The return value must be contextually convertible to `bool`.
/// * The supplied iterators can be constant.
/// * The class must be copyable.
///
/// The comparator class is allowed to throw exceptions.
///
/// ## Optimizations for bslstl::DefaultSearcher {#bslstl_defaultsearcher-optimizations-for-bslstl-defaultsearcher}
///
///
/// For certain template arguments this implementation improves performance by
/// utilizing low-level operations.  The requirements to do so are:
/// * Both supplied iterators are pointers.
/// * The default equality comparison is allowed to default (to
///   `bsl::equal_to<value_type>`).
/// * The `value_type` is bitwise-equality-comparable.
///
/// Users supplying their own data types are advised to set the
/// `bslmf::IsBitwiseEqualityComparable` trait when applicable so that
/// `bslstl::DefaultSearcher` knows that the last optimization condition listed
/// above is met.  See @ref bslmf_isbitwiseequalitycomparable .
///
/// ## Usage {#bslstl_defaultsearcher-usage}
///
///
/// In this section we show the intended usage of this component.
///
/// ### Example 1: Basic Usage {#bslstl_defaultsearcher-example-1-basic-usage}
///
///
/// The problem of searching a sequence of characters for a particular
/// sub-sequence arises in many applications.  For example, one might need to
/// know if some document contains a particular word of interest.  For example,
/// suppose we would like to know the first occurrence of the word "United" in
/// the Declaration of Independence (of the United States):
///
/// First, we obtain the text of document and word of interest as sequences of
/// `char` values.
/// @code
/// const char document[] =
/// " IN CONGRESS, July 4, 1776.\n"                // 28
/// "\n"                                           //  1
/// " The unanimous Declaration of the thirteen united States of America,\n"
/// //----^----|----^----|----^----|----^----|----  // 44
/// //                                              // --
/// //                                              // 73rd character
/// //
/// "\n"
/// // ...
/// " declare, That these United Colonies are, and of Right ought to be\n"
/// // ...
/// "Honor.";
///
/// const char *word = "United";
/// @endcode
/// Then, we create a `bsl::default_searcher` object (a functor) using the given
/// `word`:
/// @code
/// bsl::default_searcher<const char*> searchForUnited(
///                                                  word,
///                                                  word + bsl::strlen(word));
/// @endcode
/// Notice that no equality comparison functor was specified so
/// `searchForUnited` will use `bsl::equal_to<char>` by default.
///
/// Now, we invoke our functor, specifying the range of the document to be
/// searched:
/// @code
/// bsl::pair<const char *, const char *> result = searchForUnited(
///                                                           document,
///                                                           document
///                                                         + sizeof document);
/// bsl::size_t offset = result.first - document;
///
/// assert(120 == offset);
/// assert(static_cast<bsl::size_t>(result.second - result.first)
///            == bsl::strlen(word));
/// @endcode
/// Finally, we notice that the search correctly ignored the appearance of the
/// word "united" (all lower case) in the second sentence.
///
/// {@ref bslstl_boyermoorehorspoolsearcher |Example 1} shows how the same problem
/// is addressed using `bsl::boyer_moore_horspool_searcher`.
///
/// ### Example 2: Defining a Comparator {#bslstl_defaultsearcher-example-2-defining-a-comparator}
///
///
/// As seen in {Example 1} above, the default equality comparison functor is
/// case sensitive.  If one needs case *in*-sensitive searches, a non-default
/// equality comparison class must be specified.
///
/// First, define (at file scope if using a pre-C++11 compiler) an equality
/// comparison class that provides the required functor interface:
/// @code
/// struct MyCaseInsensitiveCharComparator {
///     bool operator()(const char& a, const char& b) const {
///         return bsl::tolower(a) == bsl::tolower(b);
///     }
/// };
/// @endcode
/// Then, define a new `bsl::default_searcher` type and create a searcher object
/// to search for `word`:
/// @code
/// bsl::default_searcher<const char *,
///                       struct MyCaseInsensitiveCharComparator>
///                                                 searchForUnitedInsensitive(
///                                                 word,
///                                                 word + bsl::strlen(word));
/// @endcode
/// Note that the new searcher object will used a default constructed
/// `MyCaseInsensitiveCharComparator` class.  If an equality comparison object
/// requires state supplied on construction, such an object be explicitly
/// created and supplied as the final constructor argument.
///
/// Now, we invoke our new functor, specifying that the same document searched
/// in {Example 1}:
/// @code
/// bsl::pair<const char *, const char *> resultInsensitive =
///                                                 searchForUnitedInsensitive(
///                                                           document,
///                                                           document
///                                                         + sizeof document);
///
/// bsl::size_t offsetInsensitive = resultInsensitive.first - document;
///
/// assert( 72 == offsetInsensitive);
/// assert(static_cast<bsl::size_t>(resultInsensitive.second
///                               - resultInsensitive.first)
///            == bsl::strlen(word));
/// @endcode
/// Finally, we find the next occurrence of `word` by *reusing* the same
/// searcher object, this time instructing it to begin its search just after the
/// previous occurrence of `word` was found:
/// @code
/// resultInsensitive = searchForUnitedInsensitive(resultInsensitive.second,
///                                                document + sizeof document);
///
/// offsetInsensitive = resultInsensitive.first - document;
///
/// assert(120 == offsetInsensitive);
/// assert(static_cast<bsl::size_t>(resultInsensitive.second
///                               - resultInsensitive.first)
///            == bsl::strlen(word));
/// @endcode
/// {@ref bslstl_boyermoorehorspoolsearcher |Example 2} shows how the same problem
/// is addressed using `bsl::boyer_moore_horspool_searcher`.
///
/// ### Example 3: Non-char Searches {#bslstl_defaultsearcher-example-3-non-char-searches}
///
///
/// The "default" searcher class template is not constrained to searching for
/// `char` values.  Searches can be done on other types (see {Iterator
/// Requirements}).  Moreover the container of the sequence being sought (the
/// "needle") need not the same as the sequence being searched (the "haystack").
///
/// Suppose one has data from an instrument that reports `float` values and that
/// inserts the sequence `{ FLT_MAX, FLT_MIN, FLT_MAX }` as a marker for the
/// start and end of a test run.  We can assume the probably of the instrument
/// reporting this sequence as readings is negligible and that data reported
/// outside of the test runs is random noise.  Here is how we can search for the
/// first test run data in the data sequence.
///
/// First, we create a representation of the sequence that denotes the limit of
/// a test run.
/// @code
/// const float       markerSequence[]     = { FLT_MAX , FLT_MIN , FLT_MAX };
/// const bsl::size_t markerSequenceLength = sizeof  markerSequence
///                                        / sizeof *markerSequence;
/// @endcode
/// Next, we obtain the data to be searched.  (In this example, we will use
/// simulated data.)
/// @code
/// bsl::list<float> data;  // Container provides bidirectional iterators.
/// doTestRun(&data);
/// @endcode
/// Then, we define and create our searcher object:
/// @code
/// bsl::default_searcher<const float *> searchForMarker(markerSequence,
///                                                      markerSequence
///                                                    + markerSequenceLength);
/// @endcode
/// Notice that no equality comparator was specified so `searchForMarker` will
/// use `bsl::equal_to<float>` by default.
///
/// Now, we invoke our searcher on the instrument data.
/// @code
/// typedef bsl::list<float>::const_iterator DataConstItr;
///
/// const bsl::pair<DataConstItr, DataConstItr> notFound(data.cend(),
///                                                      data.cend());
///
/// bsl::pair<DataConstItr, DataConstItr> markerPosition = searchForMarker(
///                                                              data.cbegin(),
///                                                              data.cend());
///
/// assert(notFound != markerPosition);
///
/// DataConstItr startOfTestRun = markerPosition.second;
/// @endcode
/// Finally, we locate the marker of the end of the first test run and pass the
/// location of the first test run data to some other function for processing.
/// @code
/// markerPosition = searchForMarker(markerPosition.second, data.cend());
///
/// assert(notFound != markerPosition);
///
/// DataConstItr endOfTestRun = markerPosition.first;
///
/// processTestRun(startOfTestRun, endOfTestRun);
/// @endcode
///
/// {@ref bslstl_boyermoorehorspoolsearcher |Example 3} shows how the same problem
/// is addressed using `bsl::boyer_moore_horspool_searcher`.  Notice that other
/// example uses `data` from a container that provides random access iterators;
/// whereas here, bidirectional iterators are used (and forward iterators would
/// have sufficed).
/// @}
/** @} */
/** @} */
 
/** @addtogroup bsl
 * @{
 */
/** @addtogroup bslstl
 * @{
 */
/** @addtogroup bslstl_defaultsearcher
 * @{
 */
 
#include <bslscm_version.h>
 
#include <bslstl_equalto.h>
#include <bslstl_iterator.h>
#include <bslstl_pair.h>
 
#include <bslmf_assert.h>
#include <bslmf_enableif.h>
#include <bslmf_issame.h>
 
#include <bsls_assert.h>
#include <bsls_keyword.h>  // for 'BSLS_KEYWORD_CONSTEXPR'
#include <bsls_libraryfeatures.h>
#include <bsls_performancehint.h>
 
#include <cstring>  // for 'std::memcmp'
#include <utility>  // for 'std::make_pair'
 
 
namespace bslstl {
 
                        // =====================
                        // class DefaultSearcher
                        // =====================
 
/// This class template defines functors that can search for the sequence of
/// `value_type` values defined on construction (i.e., the "needle") in
/// sequences of `value_type` values (i.e., "haystacks") passed to the
/// functor's `operator()`.
///
/// See @ref bslstl_defaultsearcher 
template <class FORWARD_ITR_NEEDLE,
          class EQUAL = bsl::equal_to<
               typename bsl::iterator_traits<FORWARD_ITR_NEEDLE>::value_type> >
class DefaultSearcher {
 
    // PRIVATE TYPES
 
    /// the type of the values that can be obtained by dereferencing a
    /// `FORWARD_ITR_NEEDLE` iterator
    typedef typename bsl::iterator_traits<FORWARD_ITR_NEEDLE>::value_type
                                                               value_type;
 
    typedef typename bsl::iterator_traits<FORWARD_ITR_NEEDLE>::
                                                             iterator_category
                                                              IteratorCategory;
    // DATA
    FORWARD_ITR_NEEDLE d_needleFirst;
    FORWARD_ITR_NEEDLE d_needleLast;
    EQUAL              d_equal;
 
  public:
    // CREATORS
 
    /// Create a `DefaultSearcher` object that can search for the sequence
    /// of `value_type` values found in the specified range
    /// `[needleFirst, needleLast)`.  Optionally supply an `equal` functor for use by `operator()`.  
    /// 
    /// \pre The behavior is undefined   unless
    /// `needleFirst` can be advanced to equal `needleLast`.
    DefaultSearcher(FORWARD_ITR_NEEDLE needleFirst,
                    FORWARD_ITR_NEEDLE needleLast,
                    EQUAL              equal = EQUAL());
 
    /// Create a `DefaultSearcher` object that has the same state as the
    /// specified `original` object.
     DefaultSearcher(const DefaultSearcher& original) = default;
 
    /// Create a `DefaultSeacher` object having the same state as the
    /// specified `original` object.  The `original` object is left in an
    /// unspecified (valid) state.
     DefaultSearcher(DefaultSearcher&& original) = default;
 
    /// Destroy this `DefaultSearcher` object.
     ~DefaultSearcher() = default;
 
    // MANIPULATORS
 
    /// Assign to this object the state of the specified `rhs` object, and
    /// return a non-`const` reference to this object.
     DefaultSearcher& operator=(const DefaultSearcher& rhs) = default;
 
    /// Assign to this object the state of the specified `rhs` had and
    /// return a non-`const` reference to this object.  The `original`
    /// object is left in an unspecified (valid) state.
     DefaultSearcher& operator=(DefaultSearcher&& rhs) = default;
 
    // ACCESSORS
 
    /// Search the specified range `[haystackFirst, haystackLast)` for the
    /// first sequence of `value_type` values specified on construction.
    /// Return the range where those values are found, or the range
    /// `[haystackLast, haystackLast)` if that sequence is not found.  The
    /// search is performed using a "naive" algorithm that has time
    /// complexity of:
    /// @code
    ///   bsl::distance(needleFirst(), needleLast())
    /// * bsl::distance(haystackFirst, haystackLast);
    /// @endcode
    /// Values of the "needle" sequence and the "haystack" sequence are
    /// compared using the equality comparison functor specified on construction.  
    /// 
    /// \pre The behavior is undefined   unless `haystackFirst` can
    /// be advanced to equal `haystackLast` and the iterators used to
    /// construct this object, `needleFirst()` and `needleLast()`, are still valid.  
    /// 
    /// \note Note that   if the "needle" sequence is empty, the range
    /// `[haystackFirst, haystackFirst)` is returned.  Also note that if the
    /// "needle" sequence is longer than the "haystack" sequence -- thus,
    /// impossible for the "needle" to be found in the "haystack" -- the
    /// range `[haystackLast, haystackLast)` is returned.
    template<class FORWARD_ITR_HAYSTACK>
    bsl::pair<FORWARD_ITR_HAYSTACK, FORWARD_ITR_HAYSTACK> operator()(
                                    FORWARD_ITR_HAYSTACK haystackFirst,
                                    FORWARD_ITR_HAYSTACK haystackLast)   const;
 
                        // Non-Standard Accessors
 
    /// Return an iterator referring to the first element of the sequence of
    /// `value_type` values that can be sought by this searcher object.
    FORWARD_ITR_NEEDLE needleFirst() const;
 
    /// Return an iterator referring to one past the last element of the
    /// sequence of `value_type` values that can be sought by this searcher
    /// object.
    FORWARD_ITR_NEEDLE needleLast() const;
 
    /// Return the functor used by this searcher object to compare
    /// `value_type` values.
    EQUAL equal() const;
};
 
                        // ===================================
                        // struct DefaultSearcher_CanOptimize
                        // ===================================
 
/// This component-private meta-function `struct` provides a member
/// enumerator `value` that is `true` if all of the specified
/// `FORWARD_ITR_NEEDLE,` `EQUAL,` and `FORWARD_ITR_HAYSTACK` meet the
/// criteria for an optimization of the default searcher, and has the value
/// `false` otherwise.
///
/// See @ref bslstl_defaultsearcher 
template <class FORWARD_ITR_NEEDLE,
          class EQUAL,
          class FORWARD_ITR_HAYSTACK>
struct DefaultSearcher_CanOptimize {
 
    enum {
 
        value = (
 
        bsl::is_pointer<FORWARD_ITR_NEEDLE>::value
    &&  bsl::is_pointer<FORWARD_ITR_HAYSTACK>::value
    &&  bsl::is_same<EQUAL, // 'EQUAL' does 'value_type::operator=='
                     bsl::equal_to<
                           typename
                           bsl::iterator_traits<FORWARD_ITR_NEEDLE>::value_type
                                 >
                    >::value
    &&  bslmf::IsBitwiseEqualityComparable<
                           typename
                           bsl::iterator_traits<FORWARD_ITR_NEEDLE>::value_type
                                          >::value
    &&  bslmf::IsBitwiseEqualityComparable<
                         typename
                         bsl::iterator_traits<FORWARD_ITR_HAYSTACK>::value_type
                                          >::value
        )
    };
};
 
                        // ===============================
                        // struct DefaultSearcher_ImpUtil
                        // ===============================
 
/// This component-private utility `struct` provides two mutually exclusive
/// overloads of the `doSearch` method -- i.e., just one of the two methods
/// is enabled at any time.  Enablement is decided by the
/// `DefaultSearcher_CanOptimize` meta-function.
///
/// See @ref bslstl_defaultsearcher 
struct DefaultSearcher_ImpUtil {
 
    // TYPES
    template <class FORWARD_ITR_NEEDLE,
              class EQUAL,
              class FORWARD_ITR_HAYSTACK>
    static
    typename
    bsl::enable_if< DefaultSearcher_CanOptimize<FORWARD_ITR_NEEDLE,
                                                  EQUAL,
                                                  FORWARD_ITR_HAYSTACK>::value
                  , bsl::pair<FORWARD_ITR_HAYSTACK,
                              FORWARD_ITR_HAYSTACK>
    >::type doSearch(const FORWARD_ITR_HAYSTACK& haystackFirst,
                     const FORWARD_ITR_HAYSTACK& haystackLast,
                     const FORWARD_ITR_NEEDLE&   needleFirst,
                     const FORWARD_ITR_NEEDLE&   needleLast,
                     const EQUAL&                equal);
 
    /// Search the specified "haystack" sequence of `value_type` values,
    /// `[haystackFirst, hastackLast)`, for the specified "needle" sequence
    /// of `value_type` values, `[needleFirst, needleLast)` where the
    /// `value_type` values are compared using the specified `equal`
    /// functor.  Return the range where the sought sequence of values are
    /// found, or the range `[haystackLast, haystackLast)` if that sequence
    /// is not found.  The search is performed using a "naive" algorithm
    /// that has time complexity of:
    /// @code
    ///   bsl::distance(needleFirst(), needleLast())
    /// * bsl::distance(haystackFirst, haystackLast);
    /// @endcode
    /// Values of the "needle" sequence and the "haystack" sequences are
    /// compared using the equality comparison functor specified on
    /// construction except, possibly, if the `DefaultSearcher_CanOptimize`
    /// metafunction indicates that the template parameters are eligible for
    /// optimization.  The optimized overload is enabled when needle and
    /// haystack can be validly compared using `std::memcmp`, a
    /// low-level function that is often highly optimized for its platform. 
    /// 
    /// \pre The behavior is undefined   unless `haystackFirst` can be advanced to equal `haystackLast`.  
    /// 
    /// \note Note that   if the "needle" sequence is empty,
    /// the range `[haystackFirst, haystackFirst)` is returned.  Also note
    /// that if the "needle" sequence is longer than the "haystack" sequence
    /// -- thus, impossible for the "needle" to be found in the "haystack"
    /// -- the range `[haystackLast, haystackLast)` is returned.
    template <class FORWARD_ITR_NEEDLE,
              class EQUAL,
              class FORWARD_ITR_HAYSTACK>
    static
    typename
    bsl::enable_if<!DefaultSearcher_CanOptimize<FORWARD_ITR_NEEDLE,
                                                  EQUAL,
                                                  FORWARD_ITR_HAYSTACK>::value
                  , bsl::pair<FORWARD_ITR_HAYSTACK,
                              FORWARD_ITR_HAYSTACK>
    >::type doSearch(const FORWARD_ITR_HAYSTACK& haystackFirst,
                     const FORWARD_ITR_HAYSTACK& haystackLast,
                     const FORWARD_ITR_NEEDLE&   needleFirst,
                     const FORWARD_ITR_NEEDLE&   needleLast,
                     const EQUAL&                equal);
};
 
}  // close package namespace
 
 
#ifndef BSLS_LIBRARYFEATURES_HAS_CPP17_SEARCH_FUNCTORS
namespace bsl {
                        // ======================
                        // class default_searcher
                        // ======================
 
// This class template defines functors that can search for the sequence of
// `value_type` values defined on construction in sequences of `value_type`
// values passed to the functor's `operator()`.
template<class ForwardIterator1,
         class BinaryPredicate = equal_to<
            typename bsl::iterator_traits<ForwardIterator1>::value_type> >
class default_searcher {
 
    //DATA
    BloombergLP::bslstl::DefaultSearcher<ForwardIterator1,
                                         BinaryPredicate> d_imp;
 
  public:
    // CREATORS
 
    /// Create a @ref default_searcher  object that can search for the sequence
    /// of `value_type` values found in the specified range
    /// `[pat_first, pat_last)`.  Optionally supply a `pred` functor for use
    /// by `operator()`.  See {Comparator Requirements}.  
    /// 
    /// \pre The behavior is undefined   unless @ref pat_first  can be advanced to equal @ref pat_last .
    BSLS_KEYWORD_CONSTEXPR
    default_searcher(ForwardIterator1 pat_first,
                     ForwardIterator1 pat_last,
                     BinaryPredicate  pred = BinaryPredicate());
 
    /// Create a @ref default_searcher  object having same state as the
    /// specified `original` object.
     default_searcher(const default_searcher& original) = default;
 
    /// Create a @ref default_searcher  object having same state as the
    /// specified `original` object. by moving (in constant time) the state
    /// of `original` to the new searcher.  The `original` object is left in
    /// an unspecified (valid) state.
     default_searcher(BloombergLP::bslmf::MovableRef<default_searcher>
                                                        original) = default;
 
    /// Destroy this @ref default_searcher  object.
     ~default_searcher() = default;
 
    // MANIPULATORS
 
    /// Assign to this object the state of the specified `rhs` object, and
    /// return a non-`const` reference to this searcher.
     default_searcher& operator=(const default_searcher& rhs) = default;
 
    /// Assign to this object the state of the specified `rhs` object and
    /// return a non-`const` reference to this searcher.
     default_searcher& operator=(
                            BloombergLP::bslmf::MovableRef<default_searcher>
                                                             rhs) = default;
 
    // ACCESSORS
 
    /// Search the specified range `[first, last)` for the first sequence of
    /// `value_type` values specified on construction.  Return the range
    /// where those values are found, or the range `[last, last)` if that
    /// sequence is not found.  The search is performed using a "naive"
    /// algorithm that has time complexity of:
    /// @code
    ///    bsl::distance(pat_first, pat_last) * bsl::distance(first, last);
    /// @endcode
    /// Values of the two sequences are compared using the equality
    /// comparison functor specified on construction.  
    /// 
    /// \pre The behavior is undefined   unless `first` can be advanced to equal `last` and the
    /// iterators used to construct this object are still valid.  
    /// 
    /// \note Note that   if the sought sequence is empty, the range `[first, first)` is
    /// returned.  Also note that if the sequence sought is longer than the
    /// sequence searched -- thus the sought sequence cannot be found -- the
    /// range `[last, last)` is returned.
    template<class ForwardIterator2>
    BSLS_KEYWORD_CONSTEXPR
    pair<ForwardIterator2, ForwardIterator2> operator()(
                                                  ForwardIterator2 first,
                                                  ForwardIterator2 last) const;
};
 
}  // close namespace bsl
#endif // BSLS_LIBRARYFEATURES_HAS_CPP17_SEARCH_FUNCTORS
 
// ----------------------------------------------------------------------------
//                          INLINE DEFINITIONS
// ----------------------------------------------------------------------------
 
 
namespace bslstl {
 
                        // ---------------------
                        // class DefaultSearcher
                        // ---------------------
 
//CREATORS
template  <class FORWARD_ITR_NEEDLE,
           class EQUAL>
inline
DefaultSearcher<FORWARD_ITR_NEEDLE,
                EQUAL>::
DefaultSearcher(FORWARD_ITR_NEEDLE needleFirst,
                FORWARD_ITR_NEEDLE needleLast,
                EQUAL              equal)
: d_needleFirst(needleFirst)
, d_needleLast( needleLast)
, d_equal(equal)
{
    BSLS_ASSERT(0 <= bsl::distance(needleFirst, needleLast));
}
 
// ACCESSORS
template <class FORWARD_ITR_NEEDLE,
          class EQUAL>
template <class FORWARD_ITR_HAYSTACK>
inline
bsl::pair<FORWARD_ITR_HAYSTACK, FORWARD_ITR_HAYSTACK>
DefaultSearcher<FORWARD_ITR_NEEDLE, EQUAL>::operator()(
                                       FORWARD_ITR_HAYSTACK haystackFirst,
                                       FORWARD_ITR_HAYSTACK haystackLast) const
{
    BSLMF_ASSERT((bsl::is_same<
               typename bsl::iterator_traits<FORWARD_ITR_NEEDLE  >::value_type,
               typename bsl::iterator_traits<FORWARD_ITR_HAYSTACK>::value_type
                             >::value));
 
    return BloombergLP::bslstl::
           DefaultSearcher_ImpUtil::doSearch<FORWARD_ITR_NEEDLE,
                                             EQUAL,
                                             FORWARD_ITR_HAYSTACK>(
                                                                 haystackFirst,
                                                                 haystackLast,
                                                                 d_needleFirst,
                                                                 d_needleLast,
                                                                 d_equal);
 
}
 
template <class FORWARD_ITR_NEEDLE, class EQUAL>
inline
FORWARD_ITR_NEEDLE DefaultSearcher<FORWARD_ITR_NEEDLE, EQUAL>::needleFirst()
                                                                          const
{
    return d_needleFirst;
}
 
template <class FORWARD_ITR_NEEDLE, class EQUAL>
inline
FORWARD_ITR_NEEDLE DefaultSearcher<FORWARD_ITR_NEEDLE, EQUAL>::needleLast()
                                                                          const
{
    return d_needleLast;
}
 
template <class FORWARD_ITR_NEEDLE, class EQUAL>
inline
EQUAL DefaultSearcher<FORWARD_ITR_NEEDLE, EQUAL>::equal() const
{
    return d_equal;
}
 
                        // -----------------------------
                        // class DefaultSearcher_ImpUtil
                        // -----------------------------
 
// CLASS METHODS
template <class FORWARD_ITR_NEEDLE, class EQUAL, class FORWARD_ITR_HAYSTACK>
inline
typename
bsl::enable_if<
    ! DefaultSearcher_CanOptimize<FORWARD_ITR_NEEDLE,
                                  EQUAL,
                                  FORWARD_ITR_HAYSTACK>::value
    , bsl::pair<FORWARD_ITR_HAYSTACK, FORWARD_ITR_HAYSTACK>
>::type DefaultSearcher_ImpUtil::doSearch(
                                     const FORWARD_ITR_HAYSTACK& haystackFirst,
                                     const FORWARD_ITR_HAYSTACK& haystackLast,
                                     const FORWARD_ITR_NEEDLE&   needleFirst,
                                     const FORWARD_ITR_NEEDLE&   needleLast,
                                     const EQUAL&                equal)
{
    BSLS_ASSERT(0 <= bsl::distance(haystackFirst, haystackLast));
 
    for (FORWARD_ITR_HAYSTACK itrHaystackOuter  = haystackFirst;
                              itrHaystackOuter != haystackLast;
                            ++itrHaystackOuter) {
 
        FORWARD_ITR_HAYSTACK itrHaystackInner = itrHaystackOuter;
 
        for (FORWARD_ITR_NEEDLE itrNeedle = needleFirst;
                              /* tests below */ ;
                              ++itrNeedle, ++itrHaystackInner) {
 
            if (needleLast == itrNeedle) {         // Needle match in haystack!
                return std::make_pair(itrHaystackOuter,
                                      itrHaystackInner);              // RETURN
            }
 
            if (haystackLast == itrHaystackInner) {     // Hit end of haystack.
                return std::make_pair(haystackLast,
                                      haystackLast);                  // RETURN
            }
 
            if (equal(*itrHaystackInner, *itrNeedle)) {
                continue;  // Needle match still possible.
            } else {
                break;     // Move starting point in haystack and try again.
            }
        }
    }
 
    // Ran out of haystack without match.
 
    return std::make_pair(haystackLast, haystackLast);
}
 
template <class FORWARD_ITR_NEEDLE, class EQUAL, class FORWARD_ITR_HAYSTACK>
inline
typename
bsl::enable_if<
      DefaultSearcher_CanOptimize<FORWARD_ITR_NEEDLE,
                                  EQUAL,
                                  FORWARD_ITR_HAYSTACK>::value
    , bsl::pair<FORWARD_ITR_HAYSTACK, FORWARD_ITR_HAYSTACK>
>::type DefaultSearcher_ImpUtil::doSearch(
                                     const FORWARD_ITR_HAYSTACK& haystackFirst,
                                     const FORWARD_ITR_HAYSTACK& haystackLast,
                                     const FORWARD_ITR_NEEDLE&   needleFirst,
                                     const FORWARD_ITR_NEEDLE&   needleLast,
                                     const EQUAL&                )
{
    ///Implementation Note
    ///-------------------
    // This specialization is used only when the 'EQUAL' template parameter
    // was specified as 'bsl::equal_to<value_type>', the default value.  We
    // ignore that argument and perform its "moral equivalent" for the various
    // ranges using 'std::memcmp'.
 
    typedef typename bsl::iterator_traits<FORWARD_ITR_HAYSTACK>::
                                                               difference_type
                                                            HaystackDifference;
 
    typedef typename bsl::iterator_traits<FORWARD_ITR_NEEDLE>::difference_type
                                                              NeedleDifference;
 
    const   NeedleDifference   needleLength =   needleLast -   needleFirst;
    const HaystackDifference haystackLength = haystackLast - haystackFirst;
 
    BSLS_ASSERT(0 <=   needleLength);
    BSLS_ASSERT(0 <= haystackLength);
 
    if (haystackLength < needleLength) {                       // Cannot match.
        return std::make_pair(haystackLast, haystackLast);            // RETURN
    }
 
    if (0 == needleLength || 0 == haystackLength) {
        return std::make_pair(haystackFirst, haystackFirst);          // RETURN
    }
 
    for (FORWARD_ITR_HAYSTACK itr = haystackFirst;
                              itr < haystackLast - needleLength + 1; ++itr) {
 
            FORWARD_ITR_HAYSTACK itrInner          = itr;
            FORWARD_ITR_NEEDLE   needleItrInner    = needleFirst;
            NeedleDifference     needleLengthInner = needleLength;
 
            if (BSLS_PERFORMANCEHINT_PREDICT_UNLIKELY(*itr == *needleFirst)) {
                if (1 == needleLength) {
                    return std::make_pair(itr, itr + needleLength);   // RETURN
                }
                           ++itrInner;
                     ++needleItrInner;
                  --needleLengthInner;
            } else {
                continue; // Avoided 'memcmp' call
            }
 
            if (0 == std::memcmp(         itrInner,
                                    needleItrInner,
                                 needleLengthInner)) {
                return std::make_pair(itr, itr + needleLength);       // RETURN
            }
    }
 
    // Ran out of haystack without match.
    return std::make_pair(haystackLast, haystackLast);
}
 
}  // close package namespace
 
 
#ifndef BSLS_LIBRARYFEATURES_HAS_CPP17_SEARCH_FUNCTORS
namespace bsl {
                        // ----------------------
                        // class default_searcher
                        // ----------------------
 
// CREATORS
template <class ForwardIterator1,
          class BinaryPredicate>
inline
BSLS_KEYWORD_CONSTEXPR
default_searcher<ForwardIterator1,
                 BinaryPredicate>::default_searcher(ForwardIterator1 pat_first,
                                                    ForwardIterator1 pat_last,
                                                    BinaryPredicate  pred)
: d_imp(pat_first, pat_last, pred)
{
}
 
        // ACCESSORS
template <class ForwardIterator1,
          class BinaryPredicate>
template <class ForwardIterator2>
inline
BSLS_KEYWORD_CONSTEXPR
pair<ForwardIterator2,
     ForwardIterator2> default_searcher<ForwardIterator1,
                                        BinaryPredicate>::operator()(
                                                   ForwardIterator2 first,
                                                   ForwardIterator2 last) const
{
    return d_imp(first, last);
}
 
}  // close namespace bsl
#endif // BSLS_LIBRARYFEATURES_HAS_CPP17_SEARCH_FUNCTORS
 
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2019 Bloomberg Finance L.P.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// ----------------------------- END-OF-FILE ----------------------------------
 
/** @} */
/** @} */
/** @} */