bslalg_rangecompare.h

Go to the documentation of this file.

/// @file bslalg_rangecompare.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bslalg_rangecompare.h                                              -*-C++-*-
#ifndef INCLUDED_BSLALG_RANGECOMPARE
#define INCLUDED_BSLALG_RANGECOMPARE
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
/// @defgroup bslalg_rangecompare bslalg_rangecompare
/// @brief  Provide algorithms to compare iterator-ranges of elements.
/// @addtogroup bsl
/// @{
/// @addtogroup bslalg
/// @{
/// @addtogroup bslalg_rangecompare
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bslalg_rangecompare-purpose"> Purpose</a>
/// * <a href="#bslalg_rangecompare-classes"> Classes </a>
/// * <a href="#bslalg_rangecompare-description"> Description </a>
///   * <a href="#bslalg_rangecompare-usage"> Usage </a>
///     * <a href="#bslalg_rangecompare-example-1-defining-equality-comparison-operators-on-a-container"> Example 1: Defining Equality-Comparison Operators on a Container </a>
///
/// # Purpose {#bslalg_rangecompare-purpose}
/// Provide algorithms to compare iterator-ranges of elements.
///
/// # Classes {#bslalg_rangecompare-classes}
///
/// -  bslalg::RangeCompare: comparison algorithms for iterator ranges
///
/// @see  bslmf_isbitwiseequalitycomparable
///
/// # Description {#bslalg_rangecompare-description}
/// This component provides a utility `struct`,
/// `bslalg::RangeCompare`, that defines two overloaded class methods, `equal`
/// and `lexicographical`, for comparing two ranges, each specified by a pair of
/// input iterators that are compliant with the C++11 standard [24.2.3].  The
/// `equal` method determines whether two specified ranges compare equal.  The
/// `lexicographical` method determines whether the first range compares
/// lexicographically less than, equal to, or greater than the second range.
/// Under certain circumstances, `bslalg::RangeCompare::equal` and
/// `bslalg::RangeCompare::lexicographical` may perform optimized comparisons,
/// as described below.
///
/// `bslalg::RangeCompare::equal` may perform a bit-wise comparison of the two
/// ranges when the following two criteria are met:
/// * The input iterators are convertible to a pointer type.
/// * The trait `bslmf::IsBitwiseEqualityComparable` is declared for
///   the type of the objects in the ranges being compared.
///
/// `bslalg::RangeCompare::lexicographical` may perform a bit-wise comparison of
/// the two ranges when the following criterion is met:
/// * The input iterators are convertible to pointers to a wide or unsigned
///    character type.
///
/// Note that a class having the `bslmf::IsBitwiseEqualityComparable`
/// trait can be described as bit-wise comparable and should meet the following
/// criteria:
/// * The values represented by two objects belonging to the class are the same
///   if and only if each of the data members in the class has the same value
///   in both objects.
/// * The class layout includes no padding.
/// * The class has no virtual members.
///
/// Note that this component is for use primarily by the `bslstl` package.
/// Other clients should use the STL algorithms (in headers `<bsl_algorithm.h>`
/// and `<bsl_memory.h>`).
///
/// ## Usage {#bslalg_rangecompare-usage}
///
///
/// This section illustrates intended use of this component.
///
/// ### Example 1: Defining Equality-Comparison Operators on a Container {#bslalg_rangecompare-example-1-defining-equality-comparison-operators-on-a-container}
///
///
/// In this example we will use the `bslalg::RangeCompare::equal` class method
/// to implement the equality-comparison operators for an iterable container
/// type residing in the `bslstl` package, and highlight the circumstances under
/// which the optimization provided by the class method may be applied.
///
/// Suppose that we have a new iterable container type that will be included in
/// the `bslstl` package, and we wish to define comparison operators for the
/// container.  If the container has an iterator that provides access to the
/// container's elements in a consistent order, and the elements themselves are
/// equality-comparable, we can implement the container's equality-comparison
/// operators by pair-wise comparing each of the elements over the entire range
/// of elements in both containers.  In such cases the container can use the
/// `bslalg::RangeCompare::equal` class method to equal-compare the container's
/// elements, taking advantage of the optimizations the class method provides
/// for bit-wise equality-comparable objects.
///
/// First, we create an elided definition of a container class, `MyContainer`,
/// which provides read-only iterators of the type `MyContainer::ConstIterator`:
/// @code
/// template <class VALUE_TYPE>
/// class MyContainer {
///     // This class implements a container, semantically similar to
///     // 'std::vector', holding objects of the (template parameter) type
///     // 'VALUE_TYPE'.
///
///   private:
///     // DATA
///     // ...
///
///   public:
///     // PUBLIC TYPES
///     typedef const VALUE_TYPE *ConstIterator;
///         // This 'typedef' provides an alias for the type of iterator
///         // providing non-modifiable access to the elements in the
///         // container.
///
///     // CREATORS
///     explicit MyContainer(bslma::Allocator *basicAllocator = 0);
///         // Create an empty 'MyContainer' object having no capacity.
///         // Optionally specify a 'basicAllocator' used to supply memory.  If
///         // 'basicAllocator' is 0, the currently installed default allocator
///         // is used.
///
///     // ...
///
///     // MANIPULATORS
///     // ...
///
///     void push_back(const VALUE_TYPE& value);
///         // Append the specified 'value' at the past-the-end position in
///         // this container, increasing the container's capacity if needed.
///
///     // ...
///
///     // ACCESSORS
///     ConstIterator begin() const;
///         // Return an iterator providing non-modifiable access to the first
///         // element in this container.
///
///     ConstIterator end() const;
///         // Return an iterator providing non-modifiable access to the
///         // past-the-end element in this container.
///
///     std::size_t size() const;
///         // Return the number of elements in this container.
///
///     // ...
/// };
/// @endcode
/// Notice that `ConstIterator` is defined as a pointer type, which is one of
/// the criteria required to enable the optimizations provided by the
/// `bslalg::RangeCompare::equal` class method.
///
/// Then, we declare the equality-comparison operators for `MyContainer`:
/// @code
/// template <class VALUE_TYPE>
/// bool operator==(const MyContainer<VALUE_TYPE>& lhs,
///                 const MyContainer<VALUE_TYPE>& rhs);
///     // Return 'true' if the specified 'lhs' and 'rhs' objects have the same
///     // value, and 'false' otherwise.  Two 'MyContainer' objects have the
///     // same value if they have the same length, and each element in 'lhs'
///     // has the same value as the corresponding element in 'rhs'.
///
/// template <class VALUE_TYPE>
/// bool operator!=(const MyContainer<VALUE_TYPE>& lhs,
///                 const MyContainer<VALUE_TYPE>& rhs);
///     // Return 'true' if the specified 'lhs' and 'rhs' objects do not have
///     // the same value, and 'false' otherwise.  Two 'MyContainer' objects do
///     // not have the same value if they do not have the same length, or if
///     // any element in 'lhs' does not have the same value as the
///     // corresponding element in 'rhs'.
/// @endcode
/// Next, we implement the equality-comparison operators using
/// `bslalg::RangeCompare::equal`:
/// @code
/// template <class VALUE_TYPE>
/// inline
/// bool operator==(const MyContainer<VALUE_TYPE>& lhs,
///                 const MyContainer<VALUE_TYPE>& rhs)
/// {
///     return BloombergLP::bslalg::RangeCompare::equal(lhs.begin(),
///                                                     lhs.end(),
///                                                     lhs.size(),
///                                                     rhs.begin(),
///                                                     rhs.end(),
///                                                     rhs.size());
/// }
///
/// template <class VALUE_TYPE>
/// inline
/// bool operator!=(const MyContainer<VALUE_TYPE>& lhs,
///                 const MyContainer<VALUE_TYPE>& rhs)
/// {
///     return !BloombergLP::bslalg::RangeCompare::equal(lhs.begin(),
///                                                      lhs.end(),
///                                                      lhs.size(),
///                                                      rhs.begin(),
///                                                      rhs.end(),
///                                                      rhs.size());
/// }
/// @endcode
/// Then, we create the elided definition of a value-semantic class, `MyString`,
/// together with its definition of `operator==`:
/// @code
/// class MyString {
///     // This class provides a simple, elided string class that conforms to
///     // the 'bslma::Allocator' model.
///
///   private:
///     // DATA
///     char             *d_start_p;      // storage for the string
///     std::size_t       d_length;       // length of the string
///     bslma::Allocator *d_allocator_p;  // memory allocator (held, not owned)
///
///     // ...
///
///     // FRIENDS
///     friend bool operator==(const MyString&, const MyString&);
///     // ...
///
///   public:
///     // CREATORS
///     explicit MyString(const char       *string,
///                       bslma::Allocator *basicAllocator = 0);
///         // Create a 'MyString' object initialized to the value of the
///         // specified 'string'.  Optionally specify a 'basicAllocator' used
///         // to supply memory.  If 'basicAllocator' is 0, the currently
///         // installed default allocator is used.
///
///     // ...
/// };
///
/// bool operator==(const MyString& lhs, const MyString& rhs)
/// {
///     return lhs.d_length == rhs.d_length
///         && 0 == std::strncmp(lhs.d_start_p, rhs.d_start_p, lhs.d_length);
/// }
/// @endcode
/// Notice that `MyString` is not bit-wise comparable because the address values
/// of the `d_start_p` pointer data members in two `MyString` objects will be
/// different, even if the string values of the two objects are the same.
///
/// Next, we create two `MyContainer<MyString>` objects, and compare them using
/// `operator==`:
/// @code
/// MyContainer<MyString> c1;
/// MyContainer<MyString> c2;
///
/// c1.push_back(MyString("hello"));
/// c1.push_back(MyString("goodbye"));
///
/// c2.push_back(MyString("hello"));
/// c2.push_back(MyString("goodbye"));
///
/// assert(c1 == c2);
/// @endcode
/// Here, the call to the `bslalg::RangeCompare::equal` class method in
/// `operator==` will perform an unoptimized pair-wise comparison of the
/// elements in `c1` and `c2`.
///
/// Then, we create the elided definition of another value-semantic class,
/// `MyPoint`, together with its definition of `operator==`:
/// @code
/// class MyPoint {
///     // This class provides a simple, elided point type that is bit-wise
///     // comparable with other objects of the same type.
///
///   private:
///     // DATA
///     int d_x;  // the x-coordinate of the point
///     int d_y;  // the y-coordinate of the point
///
///     // FRIENDS
///     friend bool operator==(const MyPoint&, const MyPoint&);
///     // ...
///
///   public:
///     // TRAITS
///     BSLMF_NESTED_TRAIT_DECLARATION(MyPoint,
///                           BloombergLP::bslmf::IsBitwiseEqualityComparable);
///
///     // CREATORS
///     MyPoint(int x, int y);
///         // Create a 'MyPoint' object whose x- and y-coordinates have the
///         // specified 'x' and 'y' values, respectively.
///
///     // ...
/// };
///
/// bool operator==(const MyPoint& lhs, const MyPoint& rhs)
/// {
///     return lhs.d_x == rhs.d_x && lhs.d_y == rhs.d_y;
/// }
/// @endcode
/// Notice that the value of a `MyPoint` object derives from the values of all
/// of its data members, and that no padding is required for alignment.
/// Furthermore, `MyPoint` has no virtual methods.  Therefore, `MyPoint` objects
/// are bit-wise comparable, and we can correctly declare the
/// `bslmf::IsBitwiseEqualityComparable` trait for the class, as shown
/// above under the public `TRAITS` section.
///
/// Now, we create two `MyContainer<MyPoint>` objects and compare them using
/// `operator==`:
/// @code
/// MyContainer<MyPoint> c3;
/// MyContainer<MyPoint> c4;
///
/// c3.push_back(MyPoint(1, 2));
/// c3.push_back(MyPoint(3, 4));
///
/// c4.push_back(MyPoint(1, 2));
/// c4.push_back(MyPoint(3, 4));
///
/// assert(c3 == c4);  // potentially optimized
/// @endcode
/// Here, the call to `bslalg::RangeCompare::equal` in `operator==` may take
/// advantage of the fact that `MyPoint` is bit-wise comparable and perform the
/// comparison by directly bit-wise comparing the entire range of elements
/// contained in the `MyContainer<MyPoint>` objects.  This comparison can
/// provide a significant performance boost over the comparison between two
/// `MyContainer<MyPoint>` objects in which the nested
/// `bslmf::IsBitwiseEqualityComparable` trait is not associated with the
/// `MyPoint` class.
///
/// Finally, note that we can instantiate `MyContainer` with `int` or any other
/// primitive type as the `VALUE_TYPE` and still benefit from the optimized
/// comparison operators, because primitive (i.e.: fundamental, enumerated, and
/// pointer) types are inherently bit-wise comparable:
/// @code
/// MyContainer<int> c5;
/// MyContainer<int> c6;
///
/// c5.push_back(1);
/// c5.push_back(2);
/// c5.push_back(3);
///
/// c6.push_back(1);
/// c6.push_back(2);
/// c6.push_back(3);
///
/// assert(c5 == c6);  // potentially optimized
/// @endcode
/// @}
/** @} */
/** @} */
 
/** @addtogroup bsl
 * @{
 */
/** @addtogroup bslalg
 * @{
 */
/** @addtogroup bslalg_rangecompare
 * @{
 */
 
#include <bslscm_version.h>
 
#include <bslmf_integralconstant.h>
#include <bslmf_isbitwiseequalitycomparable.h>
#include <bslmf_isconvertible.h>
#include <bslmf_matchanytype.h>
 
#include <climits>
 
#include <cstddef>
 
#include <cstring>
 
#include <cwchar>
 
 
 
namespace bslalg {
 
                          // ==================
                          // class RangeCompare
                          // ==================
 
/// This utility `struct` provides two static class methods, `equal` and
/// `lexicographical`, for comparing two ranges of values.  `equal` returns
/// `true` if each element in one range has the same value as the
/// corresponding element in the other range, and `false` otherwise.
/// `lexicographical` returns 0 if the two ranges are equal, a positive
/// value if the first range is greater than the second, and a negative
/// value if the second range is greater than the first.  A range is
/// specified by a pair of beginning and ending iterators, with an optional
/// length parameter.  Additionally, an overload is provided for the `equal`
/// class method that allows the end iterator for one range to be omitted.
///
/// `equal` requires that the elements in the ranges can be compared with
/// `operator==`.
///
/// `lexicographical` requires that the elements in the ranges can be
/// compared with `operator<`.
///
/// See @ref bslalg_rangecompare 
struct RangeCompare {
 
    // TYPES
 
    /// `size_type` is an alias for an unsigned value representing the size
    /// of an object or the number of elements in a range.
    typedef std::size_t size_type;
 
    // CLASS METHODS
 
    /// Compare each element in the range beginning at the specified
    /// `start1` position and ending immediately before the specified `end1`
    /// position to the corresponding element in the range of the same
    /// length beginning at the specified `start2` position, as if using
    /// `operator==` element-by-element.  Return `true` if every pair of
    /// corresponding elements compares equal, and `false` otherwise.  
    /// 
    /// \note Note that   this implementation uses `operator==` to perform the
    /// comparisons, or bit-wise comparison if the value type has the
    /// bit-wise equality-comparable trait.
    template <class INPUT_ITER>
    static bool equal(INPUT_ITER start1,
                      INPUT_ITER end1,
                      INPUT_ITER start2);
 
    /// Compare each element in the range beginning at the specified
    /// `start1` position and ending immediately before the specified `end1`
    /// position, to the corresponding element in the range beginning at the
    /// specified `start2` position and ending immediately before the
    /// specified `end2` position, as if by using `operator==`
    /// element-by-element.  Optionally specify the length of each range,
    /// `length1` and `length2`.  Return `true` if the ranges have the same
    /// length and every element in the first range compares equal with the
    /// corresponding element in the second, and `false` otherwise.  
    /// 
    /// \pre The behavior is undefined   unless `length1` is either unspecified or
    /// equals the length of the range `[start1, end1)`, and `length2` is
    /// either unspecified or equals the length of the range `[start2, end2)`.  
    /// 
    /// \note Note that   this implementation uses `operator==`
    /// to perform the comparisons, or bit-wise comparison if the value type
    /// has the bit-wise equality-comparable trait.  Also note that
    /// providing lengths may reduce the runtime cost of this operation.
    template <class INPUT_ITER>
    static bool equal(INPUT_ITER start1,
                      INPUT_ITER end1,
                      INPUT_ITER start2,
                      INPUT_ITER end2);
    template <class INPUT_ITER>
    static bool equal(INPUT_ITER start1, INPUT_ITER end1, size_type length1,
                      INPUT_ITER start2, INPUT_ITER end2, size_type length2);
 
    /// Compare each element in the range beginning at the specified
    /// `start1` position and ending immediately before the specified `end1`
    /// position, to the corresponding element in the range beginning at the
    /// specified `start2` position and ending immediately before the
    /// specified `end2` position.  Optionally specify the length of each
    /// range, `length1` and `length2`.  Return a negative value if the
    /// first range compares lexicographically less than the second range, 0
    /// if they are the same length and compare lexicographically equal, and
    /// a positive value if the first range compares lexicographically greater than the second range.  
    /// 
    /// \pre The behavior is undefined   unless
    /// `length1` is either unspecified or equals the length of the range
    /// `[start1, end1)`, and `length2` is either unspecified or equals the length of the range `[start2, end2)`.  
    /// 
    /// \note Note that   this implementation
    /// uses `std::memcmp` for unsigned character comparisons,
    /// `std::wmemcmp` for wide character comparisons, and `operator<` for
    /// all other types.
    template <class INPUT_ITER>
    static int lexicographical(INPUT_ITER start1,
                               INPUT_ITER end1,
                               INPUT_ITER start2,
                               INPUT_ITER end2);
    template <class INPUT_ITER>
    static int lexicographical(INPUT_ITER start1,
                               INPUT_ITER end1,
                               size_type  length1,
                               INPUT_ITER start2,
                               INPUT_ITER end2,
                               size_type  length2);
};
 
                       // =======================
                       // struct RangeCompare_Imp
                       // =======================
 
/// This utility `struct` provides the implementations for
/// `bslalg::RangeCompare`.  Multiple implementations are provided for each
/// method in `bslalg::RangeCompare`, and the most efficient version is
/// found by disambiguating based on the iterator type, the value type, or
/// the presence of nested traits.
///
/// See @ref bslalg_rangecompare 
struct RangeCompare_Imp {
 
    // CLASS METHODS
 
    /// Compare the range beginning at the specified `start1` position and
    /// ending immediately before the specified `end1` position with the
    /// range beginning at the specified `start2` position and ending
    /// immediately before the specified `end2` position, as if using
    /// `operator==` element-by-element.  The unnamed `VALUE_TYPE` argument
    /// is for automatic type deduction, and is ignored.  The fifth argument
    /// is for overloading resolution, and is also ignored.
    template <class VALUE_TYPE>
    static bool equal(const VALUE_TYPE  *start1,
                      const VALUE_TYPE  *end1,
                      const VALUE_TYPE  *start2,
                      const VALUE_TYPE  *end2,
                      const VALUE_TYPE&,
                      bsl::true_type);
    template <class INPUT_ITER, class VALUE_TYPE>
    static bool equal(INPUT_ITER         start1,
                      INPUT_ITER         end1,
                      INPUT_ITER         start2,
                      INPUT_ITER         end2,
                      const VALUE_TYPE&,
                      bsl::false_type);
    template <class INPUT_ITER, class VALUE_TYPE>
    static bool equal(INPUT_ITER         start1,
                      INPUT_ITER         end1,
                      INPUT_ITER         start2,
                      INPUT_ITER         end2,
                      const VALUE_TYPE&);
 
    /// Compare the range beginning at the specified `start1` position and
    /// ending immediately before the specified `end1` position with the
    /// range beginning at the specified `start2` position of the same
    /// length (namely, `end1 - start1`), as if using `operator==`
    /// element-by-element.  The unnamed `VALUE_TYPE` argument is for
    /// automatic type deduction, and is ignored.  The fifth argument is for
    /// overloading resolution, and is also ignored.
    template <class INPUT_ITER, class VALUE_TYPE>
    static bool equal(INPUT_ITER        start1,
                      INPUT_ITER        end1,
                      INPUT_ITER        start2,
                      const VALUE_TYPE&,
                      bsl::true_type);
    template <class INPUT_ITER, class VALUE_TYPE>
    static bool equal(INPUT_ITER        start1,
                      INPUT_ITER        end1,
                      INPUT_ITER        start2,
                      const VALUE_TYPE&,
                      bsl::false_type);
    template <class INPUT_ITER, class VALUE_TYPE>
    static bool equal(INPUT_ITER        start1,
                      INPUT_ITER        end1,
                      INPUT_ITER        start2,
                      const VALUE_TYPE&);
 
    /// Compare the range beginning at the specified `start1` position and
    /// ending immediately before the specified `end1` position with the
    /// range beginning at the specified `start2` position of the same
    /// length (namely, `end1 - start1`), using bit-wise comparison across
    /// the entire ranges.  The last argument is for removing overload
    /// ambiguities, and is not used.  Return `true` if the ranges are
    /// bit-wise equal, and `false` otherwise.
    template <class VALUE_TYPE>
    static bool equalBitwiseEqualityComparable(const VALUE_TYPE  *start1,
                                               const VALUE_TYPE  *end1,
                                               const VALUE_TYPE  *start2,
                                               bsl::true_type);
 
    /// Compare the range beginning at the specified `start1` position and
    /// ending immediately before the specified `end1` position with the
    /// range beginning at the specified `start2` position of the same
    /// length (namely, `end1 - start1`), using `operator==`
    /// element-by-element.  The last argument is for removing overload
    /// ambiguities, and is not used.  Return `true` if each element in the
    /// first range is equal to the corresponding element in the second
    /// range, and `false` otherwise.
    template <class INPUT_ITER>
    static bool equalBitwiseEqualityComparable(INPUT_ITER        start1,
                                               INPUT_ITER        end1,
                                               INPUT_ITER        start2,
                                               bsl::false_type);
 
    /// Compare the range beginning at the specified `start1` position and
    /// ending immediately before the specified `end1` position with the
    /// range beginning at the specified `start2` position and ending
    /// immediately before the specified `end2` position.  The last two
    /// arguments are for removing overload ambiguities and are not used.
    /// Return a negative value if the
    /// first range compares lexicographically less than the second range, 0
    /// if they are the same length and compare lexicographically equal, and
    /// a positive value if the first range compares lexicographically
    /// greater than the second range.
    template <class VALUE_TYPE>
    static int lexicographical(const VALUE_TYPE  *start1,
                               const VALUE_TYPE  *end1,
                               const VALUE_TYPE  *start2,
                               const VALUE_TYPE  *end2,
                               const VALUE_TYPE&,
                               bsl::true_type);
 
    /// Compare each element in the range beginning at the specified
    /// `start1` position and ending immediately before the specified `end1`
    /// position with the corresponding element in the range beginning at
    /// the specified `start2` position and ending immediately before the
    /// specified `end2` position using `operator<`.  The last two arguments
    /// are for removing overload ambiguities and are not used.  Return a
    /// negative value if the first range compares lexicographically less
    /// than the second range, 0 if they are the same length and compare
    /// lexicographically equal, and a positive value if the first range
    /// compares lexicographically greater than the second range.
    template <class INPUT_ITER, class VALUE_TYPE>
    static int lexicographical(INPUT_ITER        start1,
                               INPUT_ITER        end1,
                               INPUT_ITER        start2,
                               INPUT_ITER        end2,
                               const VALUE_TYPE&,
                               bsl::false_type);
 
    /// Compare the range beginning at the specified `start1` position and
    /// ending immediately before the specified `end1` position with the
    /// range beginning at the specified `start2` position and ending
    /// immediately before the specified `end2` position.  The type of the
    /// last argument is considered in determining what optimizations, if
    /// any, can be applied to the comparison.  The last argument is not
    /// used in any other way.  Return a negative value if the
    /// first range compares lexicographically less than the second range, 0
    /// if they are the same length and compare lexicographically equal, and
    /// a positive value if the first range compares lexicographically
    /// greater than the second range.
    template <class INPUT_ITER, class VALUE_TYPE>
    static int lexicographical(INPUT_ITER        start1,
                               INPUT_ITER        end1,
                               INPUT_ITER        start2,
                               INPUT_ITER        end2,
                               const VALUE_TYPE&);
 
    /// Compare the range beginning at the specified `start1` position and
    /// ending immediately before the specified `end1` position with the
    /// range beginning at the specified `start2` position of the same
    /// length (namely, `end1 - start1`), using a bit-wise comparison
    /// across the entire range, if `const char` is unsigned, and using
    /// `operator<` otherwise.  Return a negative value if the
    /// first range compares lexicographically less than the second range, 0
    /// if they are the same length and compare lexicographically equal, and
    /// a positive value if the first range compares lexicographically
    /// greater than the second range.
    static int lexicographical(const char *start1,
                               const char *end1,
                               const char *start2);
 
    /// Compare each element in the range beginning at the specified
    /// `start1` position and ending immediately before the specified `end1`
    /// position with the corresponding element in the range of the same
    /// length beginning at the specified `start2` position.  Return a
    /// negative value if the first range compares lexicographically less
    /// than the second range, 0 if they are the same length and compare
    /// lexicographically equal, and a positive value if the first range
    /// compares lexicographically greater than the second range.
    static int lexicographical(const unsigned char *start1,
                               const unsigned char *end1,
                               const unsigned char *start2);
    static int lexicographical(const wchar_t *start1,
                               const wchar_t *end1,
                               const wchar_t *start2);
    template <class INPUT_ITER>
    static int lexicographical(INPUT_ITER           start1,
                               INPUT_ITER           end1,
                               INPUT_ITER           start2,
                               bslmf::MatchAnyType);
    template <class INPUT_ITER>
    static int lexicographical(INPUT_ITER     start1,
                               INPUT_ITER     end1,
                               INPUT_ITER     start2);
};
 
// ============================================================================
//                  INLINE AND TEMPLATE FUNCTION DEFINITIONS
// ============================================================================
 
                         // -------------------
                         // struct RangeCompare
                         // -------------------
 
// CLASS METHODS
template <class INPUT_ITER>
inline
bool RangeCompare::equal(INPUT_ITER start1,
                         INPUT_ITER end1,
                         INPUT_ITER start2)
{
    if (start1 == end1) {
        return true;                                                  // RETURN
    }
    return RangeCompare_Imp::equal(start1, end1, start2, *start1);
}
 
template <class INPUT_ITER>
inline
bool RangeCompare::equal(INPUT_ITER start1,
                         INPUT_ITER end1,
                         INPUT_ITER start2,
                         INPUT_ITER end2)
{
    if (start1 == end1) {
        return start2 == end2;                                        // RETURN
    }
    return RangeCompare_Imp::equal(start1, end1, start2, end2, *start1);
}
 
template <class INPUT_ITER>
inline
bool RangeCompare::equal(INPUT_ITER start1,
                         INPUT_ITER end1,
                         size_type  length1,
                         INPUT_ITER start2,
                         INPUT_ITER,
                         size_type  length2)
{
    if (length1 != length2) {
        return false;                                                 // RETURN
    }
    if (start1 == end1) {
        return true;                                                  // RETURN
    }
    return RangeCompare_Imp::equal(start1, end1, start2, *start1);
}
 
template <class INPUT_ITER>
int RangeCompare::lexicographical(INPUT_ITER start1,
                                  INPUT_ITER end1,
                                  INPUT_ITER start2,
                                  INPUT_ITER end2)
{
    if (start1 == end1) {
        return start2 != end2 ? -1 : 0;                               // RETURN
    }
    return RangeCompare_Imp::lexicographical(start1,
                                             end1,
                                             start2,
                                             end2,
                                             *start1);
}
 
template <class INPUT_ITER>
int RangeCompare::lexicographical(INPUT_ITER start1,
                                  INPUT_ITER end1,
                                  size_type  length1,
                                  INPUT_ITER start2,
                                  INPUT_ITER end2,
                                  size_type  length2)
{
    const int result = length2 < length1
                       ? - RangeCompare_Imp::lexicographical(start2,
                                                             end2,
                                                             start1)
                       :   RangeCompare_Imp::lexicographical(start1,
                                                             end1,
                                                             start2);
 
    if (result < 0) {
        return -1;                                                    // RETURN
    }
    if (0 < result) {
        return 1;                                                     // RETURN
    }
    if (length1 < length2) {
        return -1;                                                    // RETURN
    }
    if (length2 < length1) {
        return 1;                                                     // RETURN
    }
    return 0;
}
 
                       // -----------------------
                       // struct RangeCompare_Imp
                       // -----------------------
 
// CLASS METHODS
 
                          // *** equal overloads: ***
 
template <class VALUE_TYPE>
inline
bool RangeCompare_Imp::equal(const VALUE_TYPE  *start1,
                             const VALUE_TYPE  *end1,
                             const VALUE_TYPE  *start2,
                             const VALUE_TYPE  *end2,
                             const VALUE_TYPE&,
                             bsl::true_type)
{
    return RangeCompare::equal(start1,
                               end1,
                               end1 - start1,
                               start2,
                               end2,
                               end2 - start2);
}
 
template <class INPUT_ITER, class VALUE_TYPE>
bool RangeCompare_Imp::equal(INPUT_ITER        start1,
                             INPUT_ITER        end1,
                             INPUT_ITER        start2,
                             INPUT_ITER        end2,
                             const VALUE_TYPE&,
                             bsl::false_type)
{
    for ( ; start1 != end1 && start2 != end2; ++start1, ++start2) {
        if (!(*start1 == *start2)) {
            return false;                                             // RETURN
        }
    }
    return start1 == end1 && start2 == end2;
}
 
template <class INPUT_ITER, class VALUE_TYPE>
bool RangeCompare_Imp::equal(INPUT_ITER        start1,
                             INPUT_ITER        end1,
                             INPUT_ITER        start2,
                             INPUT_ITER        end2,
                             const VALUE_TYPE& value)
{
    typedef typename bsl::is_convertible<INPUT_ITER, const VALUE_TYPE *>::type
                                                      CanUseLengthOptimization;
 
    return equal(start1,
                 end1,
                 start2,
                 end2,
                 value,
                 CanUseLengthOptimization());
}
 
template <class INPUT_ITER, class VALUE_TYPE>
inline
bool RangeCompare_Imp::equal(INPUT_ITER        start1,
                             INPUT_ITER        end1,
                             INPUT_ITER        start2,
                             const VALUE_TYPE&,
                             bsl::true_type)
{
    // Note: We are forced to call a different function to resolve whether
    // 'INPUT_ITER' is convertible to 'const TARGET_TYPE *' or not, otherwise
    // we would be introducing ambiguities (the additional parameter
    // 'CanUseBitwiseCopyOptimization' is necessary to remove further
    // ambiguities on SunPro).
 
    typedef typename bsl::is_convertible<INPUT_ITER, const VALUE_TYPE *>::type
                                              CanUseBitwiseCompareOptimization;
 
    return equalBitwiseEqualityComparable(start1,
                                          end1,
                                          start2,
                                          CanUseBitwiseCompareOptimization());
}
 
template <class INPUT_ITER, class VALUE_TYPE>
bool RangeCompare_Imp::equal(INPUT_ITER        start1,
                             INPUT_ITER        end1,
                             INPUT_ITER        start2,
                             const VALUE_TYPE&,
                             bsl::false_type)
{
    for ( ; start1 != end1; ++start1, ++start2) {
        if (!(*start1 == *start2)) {
            return false;                                             // RETURN
        }
    }
    return true;
}
 
template <class INPUT_ITER, class VALUE_TYPE>
inline
bool RangeCompare_Imp::equal(INPUT_ITER        start1,
                             INPUT_ITER        end1,
                             INPUT_ITER        start2,
                             const VALUE_TYPE& value)
{
    typedef typename
        bslmf::IsBitwiseEqualityComparable<VALUE_TYPE>::type Trait;
    return equal(start1, end1, start2, value, Trait());
}
 
             // *** equalBitwiseEqualityComparable overloads: ***
 
template <class VALUE_TYPE>
inline
bool RangeCompare_Imp::equalBitwiseEqualityComparable(
                                                     const VALUE_TYPE  *start1,
                                                     const VALUE_TYPE  *end1,
                                                     const VALUE_TYPE  *start2,
                                                     bsl::true_type)
{
    std::size_t numBytes = reinterpret_cast<const char *>(end1)
                         - reinterpret_cast<const char *>(start1);
 
    return 0 == std::memcmp(reinterpret_cast<const void *>(start1),
                            reinterpret_cast<const void *>(start2),
                            numBytes);
}
 
template <class INPUT_ITER>
inline
bool RangeCompare_Imp::equalBitwiseEqualityComparable(INPUT_ITER        start1,
                                                      INPUT_ITER        end1,
                                                      INPUT_ITER        start2,
                                                      bsl::false_type)
{
    // We can't be as optimized as above.
 
    return equal(start1, end1, start2, *start1, bsl::false_type());
}
 
                     // *** lexicographical overloads: ***
 
template <class VALUE_TYPE>
inline
int RangeCompare_Imp::lexicographical(const VALUE_TYPE  *start1,
                                      const VALUE_TYPE  *end1,
                                      const VALUE_TYPE  *start2,
                                      const VALUE_TYPE  *end2,
                                      const VALUE_TYPE&,
                                      bsl::true_type)
{
    // In this case, we can compute the length directly, and avoid the overhead
    // of the two comparisons in the loop condition (one is enough).
 
    return RangeCompare::lexicographical(start1,
                                         end1,
                                         end1 - start1,
                                         start2,
                                         end2,
                                         end2 - start2);
}
 
template <class INPUT_ITER, class VALUE_TYPE>
int RangeCompare_Imp::lexicographical(INPUT_ITER        start1,
                                      INPUT_ITER        end1,
                                      INPUT_ITER        start2,
                                      INPUT_ITER        end2,
                                      const VALUE_TYPE&,
                                      const bsl::false_type)
{
    for ( ; start1 != end1 && start2 != end2; ++start1, ++start2) {
        if (*start1 < *start2) {
            return -1;                                                // RETURN
        }
        else if (*start2 < *start1) {
            return 1;                                                 // RETURN
        }
    }
    if (start1 != end1) {
        return 1;                                                     // RETURN
    }
    if (start2 != end2) {
        return -1;                                                    // RETURN
    }
    return 0;
}
 
template <class INPUT_ITER, class VALUE_TYPE>
inline
int RangeCompare_Imp::lexicographical(INPUT_ITER        start1,
                                      INPUT_ITER        end1,
                                      INPUT_ITER        start2,
                                      INPUT_ITER        end2,
                                      const VALUE_TYPE& value)
{
    typedef typename bsl::is_convertible<INPUT_ITER, const VALUE_TYPE *>::type
                                                      CanUseLengthOptimization;
 
    return lexicographical(start1, end1, start2, end2, value,
                           CanUseLengthOptimization());
}
 
inline
int RangeCompare_Imp::lexicographical(const unsigned char *start1,
                                      const unsigned char *end1,
                                      const unsigned char *start2)
{
    return std::memcmp(start1, start2, end1 - start1);
}
 
inline
int RangeCompare_Imp::lexicographical(const char *start1,
                                      const char *end1,
                                      const char *start2)
{
#if CHAR_MAX == SCHAR_MAX
    return std::memcmp(start1, start2, (end1 - start1));
#else
    return lexicographical<const char *>(start1, end1, start2, 0);
#endif
}
 
inline
int RangeCompare_Imp::lexicographical(const wchar_t *start1,
                                      const wchar_t *end1,
                                      const wchar_t *start2)
{
    return std::wmemcmp(start1, start2, end1 - start1);
}
 
template <class INPUT_ITER>
int RangeCompare_Imp::lexicographical(INPUT_ITER start1,
                                      INPUT_ITER end1,
                                      INPUT_ITER start2,
                                      bslmf::MatchAnyType)
{
    for ( ; start1 != end1; ++start1, ++start2) {
        if (*start1 < *start2) {
            return -1;                                                // RETURN
        }
        else if (*start2 < *start1) {
            return 1;                                                 // RETURN
        }
    }
    return 0;
}
 
template <class INPUT_ITER>
inline
int RangeCompare_Imp::lexicographical(INPUT_ITER start1,
                                      INPUT_ITER end1,
                                      INPUT_ITER start2)
{
    if (start1 != end1) {
        return lexicographical(start1, end1, start2, *start1);        // RETURN
    }
    return 0;
}
 
}  // close package namespace
 
#ifndef BDE_OPENSOURCE_PUBLICATION  // BACKWARD_COMPATIBILITY
// ============================================================================
//                           BACKWARD COMPATIBILITY
// ============================================================================
 
/// This alias is defined for backward compatibility.
typedef bslalg::RangeCompare bslalg_RangeCompare;
#endif  // BDE_OPENSOURCE_PUBLICATION -- BACKWARD_COMPATIBILITY
 
 
 
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2013 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 ----------------------------------
 
/** @} */
/** @} */
/** @} */