concept_check/test/stl_concept_covering.cpp

// (C) Copyright Jeremy Siek 2000-2002.
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#include <algorithm>
#include <numeric>
#include <boost/config.hpp>
#include <boost/concept_check.hpp>
#include <boost/concept_archetype.hpp>

/*

 This file uses the archetype classes to find out which concepts
 actually *cover* the STL algorithms true requirements. The
 archetypes/concepts chosen do not necessarily match the C++ standard
 or the SGI STL documentation, but instead were chosen based on the
 minimal concepts that current STL implementations require, which in
 many cases is less stringent than the standard. In some places there
 was significant differences in the implementations' requirements and
 in those places macros were used to select different requirements,
 the purpose being to document what the requirements of various
 implementations are.  It is an open issue as to whether the C++
 standard should be changed to reflect these weaker requirements.

*/

/**
 * Input iterator - explanation from Peter Dimov:
 *
 * Requirements say that *it is convertible to the value_type, and it is, in
 * our case. The problem however is that op== is a template and the first
 * argument fails deduction. std::find is specified in terms of the exact
 * expression `*it == value`, so if it doesn't compile (and it doesn't),
 * `find(it, it, value)` won't compile either.
 *
 * To address this, the no_proxy variant of the input iterator is used
 * instead.
 */

#define BOOST_CONCEPT_CHECK_COMPATIBLE_INPUT_ITERATOR_ARCHETYPE input_iterator_archetype_no_proxy

boost::detail::dummy_constructor dummy_cons;

// This is a special concept needed for std::swap_ranges.
// It is mutually convertible, and also SGIAssignable
template <class T>
class mutually_convertible_archetype
{
private:
  mutually_convertible_archetype() { }
public:
  mutually_convertible_archetype(const mutually_convertible_archetype&) { }
  mutually_convertible_archetype&
  operator=(const mutually_convertible_archetype&)
    { return *this; }
  mutually_convertible_archetype(boost::detail::dummy_constructor) { }

  template <class U>
  mutually_convertible_archetype&
  operator=(const mutually_convertible_archetype<U>&)
    { return *this; }

};


// for std::accumulate
namespace accum
{
  typedef boost::sgi_assignable_archetype<> Ret;
  struct T {
    T(const Ret&) { }
    T(boost::detail::dummy_constructor x) { }
  };
  typedef boost::null_archetype<> Tin;
  Ret operator+(const T&, const Tin&) {
    return Ret(dummy_cons);
  }
}

// for std::shuffle
namespace shuffle
{
  struct URBG {
    typedef unsigned int result_type;
    result_type BOOST_CONSTEXPR static min() { return 0; }
    result_type BOOST_CONSTEXPR static max() { return 1; }
    result_type operator()() { return 1; }
  };
}

// for std::inner_product
namespace inner_prod
{
  typedef boost::sgi_assignable_archetype<> RetAdd;
  typedef boost::sgi_assignable_archetype<> RetMult;
  struct T {
    T(const RetAdd&) { }
    T(boost::detail::dummy_constructor x) { }
  };
  typedef boost::null_archetype<int> Tin1;
  typedef boost::null_archetype<char> Tin2;
}

namespace boost { // so Koenig lookup will find

  inner_prod::RetMult
  operator*(const inner_prod::Tin1&, const inner_prod::Tin2&) {
    return inner_prod::RetMult(dummy_cons);
  }
  inner_prod::RetAdd
  operator+(const inner_prod::T&,
            const inner_prod::RetMult&) {
    return inner_prod::RetAdd(dummy_cons);
  }
}


// for std::partial_sum and adj_diff
namespace part_sum
{
  class T {
  public:
    typedef boost::sgi_assignable_archetype<> Ret;
    T(const Ret&) { }
    T(boost::detail::dummy_constructor x) { }
  private:
    T() { }
  };
  T::Ret operator+(const T&, const T&) {
    return T::Ret(dummy_cons);
  }
  T::Ret operator-(const T&, const T&) {
    return T::Ret(dummy_cons);
  }
}

// for std::power

namespace power_stuff {
  struct monoid_archetype {
    monoid_archetype(boost::detail::dummy_constructor x) { }
  };

  boost::multipliable_archetype<monoid_archetype>
  identity_element
  (std::multiplies< boost::multipliable_archetype<monoid_archetype> >)
  {
    return boost::multipliable_archetype<monoid_archetype>(dummy_cons);
  }
}

struct tag1 { };
struct tag2 { };


int
main()
{
  using namespace boost;

  //===========================================================================
  // Non-mutating Algorithms
  {
    input_iterator_archetype< null_archetype<> > in;
    unary_function_archetype< null_archetype<> , null_archetype<> >
      f(dummy_cons);
    std::for_each(in, in, f);
  }
  // gcc bug
  {
    typedef equality_comparable2_first_archetype<> Left;
    BOOST_CONCEPT_CHECK_COMPATIBLE_INPUT_ITERATOR_ARCHETYPE< Left > in;
    equality_comparable2_second_archetype<> value(dummy_cons);
    in = std::find(in, in, value);
  }
  {
    typedef null_archetype<> T;
    input_iterator_archetype<T> in;
    unary_predicate_archetype<T> pred(dummy_cons);
    in = std::find_if(in, in, pred);
  }
  {
    forward_iterator_archetype< equality_comparable_archetype<> > fo;
    fo = std::adjacent_find(fo, fo);
  }
  {
    forward_iterator_archetype<
      convertible_to_archetype< null_archetype<>  > > fo;
    binary_predicate_archetype<null_archetype<> , null_archetype<> >
      pred(dummy_cons);
    fo = std::adjacent_find(fo, fo, pred);
  }
  // gcc bug
  {
    typedef equal_op_first_archetype<> Left;
    BOOST_CONCEPT_CHECK_COMPATIBLE_INPUT_ITERATOR_ARCHETYPE<Left> in;
    typedef equal_op_second_archetype<> Right;
    forward_iterator_archetype<Right> fo;
    in = std::find_first_of(in, in, fo, fo);
  }
  {
    typedef equal_op_first_archetype<> Left;
    typedef BOOST_CONCEPT_CHECK_COMPATIBLE_INPUT_ITERATOR_ARCHETYPE<Left> InIter;
    InIter in;
    function_requires< InputIterator<InIter> >();
    equal_op_second_archetype<> value(dummy_cons);
    std::iterator_traits<InIter>::difference_type
      n = std::count(in, in, value);
    ignore_unused_variable_warning(n);
  }
  {
    typedef input_iterator_archetype< null_archetype<> > InIter;
    InIter in;
    unary_predicate_archetype<null_archetype<> > pred(dummy_cons);
    std::iterator_traits<InIter>::difference_type
      n = std::count_if(in, in, pred);
    ignore_unused_variable_warning(n);
  }
  // gcc bug
  {
    typedef equal_op_first_archetype<> Left;
    typedef BOOST_CONCEPT_CHECK_COMPATIBLE_INPUT_ITERATOR_ARCHETYPE<Left> InIter1;
    InIter1 in1;
    typedef equal_op_second_archetype<> Right;
    typedef BOOST_CONCEPT_CHECK_COMPATIBLE_INPUT_ITERATOR_ARCHETYPE<Right> InIter2;
    InIter2 in2;
    std::pair<InIter1, InIter2> p = std::mismatch(in1, in1, in2);
    ignore_unused_variable_warning(p);
  }
  {
    typedef input_iterator_archetype<null_archetype<> > InIter;
    InIter in1, in2;
    binary_predicate_archetype<null_archetype<> , null_archetype<> >
      pred(dummy_cons);
    std::pair<InIter, InIter> p = std::mismatch(in1, in1, in2, pred);
    ignore_unused_variable_warning(p);
  }
  // gcc bug
  {
    typedef equality_comparable2_first_archetype<> Left;
    BOOST_CONCEPT_CHECK_COMPATIBLE_INPUT_ITERATOR_ARCHETYPE<Left> in1;
    typedef equality_comparable2_second_archetype<> Right;
    BOOST_CONCEPT_CHECK_COMPATIBLE_INPUT_ITERATOR_ARCHETYPE<Right> in2;
    bool b = std::equal(in1, in1, in2);
    ignore_unused_variable_warning(b);
  }
  {
    input_iterator_archetype< null_archetype<> >
      in1, in2;
    binary_predicate_archetype<null_archetype<> , null_archetype<> >
      pred(dummy_cons);
    bool b = std::equal(in1, in1, in2, pred);
    ignore_unused_variable_warning(b);
  }
  {
    typedef equality_comparable2_first_archetype<> Left;
    forward_iterator_archetype<Left> fo1;
    typedef equality_comparable2_second_archetype<> Right;
    forward_iterator_archetype<Right> fo2;
    fo1 = std::search(fo1, fo1, fo2, fo2);
  }
  {
    typedef equality_comparable2_first_archetype<
      convertible_to_archetype<null_archetype<> > > Left;
    forward_iterator_archetype<Left> fo1;
    typedef equality_comparable2_second_archetype<
      convertible_to_archetype<null_archetype<> > > Right;
    forward_iterator_archetype<Right> fo2;
    binary_predicate_archetype<null_archetype<> , null_archetype<> >
      pred(dummy_cons);
    fo1 = std::search(fo1, fo1, fo2, fo2, pred);
  }
  {
    typedef equality_comparable2_first_archetype<> Left;
    forward_iterator_archetype<Left> fo;
    equality_comparable2_second_archetype<> value(dummy_cons);
    int n = 1;
    fo = std::search_n(fo, fo, n, value);
  }
  {
    forward_iterator_archetype<
      convertible_to_archetype<null_archetype<> > > fo;
    convertible_to_archetype<null_archetype<> > value(dummy_cons);
    binary_predicate_archetype<null_archetype<> , null_archetype<> >
      pred(dummy_cons);
    int n = 1;
    fo = std::search_n(fo, fo, n, value, pred);
  }
  {
    typedef equality_comparable2_first_archetype<> Left;
    forward_iterator_archetype<Left> fo1;
    typedef equality_comparable2_second_archetype<null_archetype<> > Right;
    forward_iterator_archetype<Right> fo2;
    fo1 = std::find_end(fo1, fo1, fo2, fo2);
  }
  {
    // equality comparable required because find_end() calls search
    typedef equality_comparable2_first_archetype<
      convertible_to_archetype<null_archetype<> > > Left;
    forward_iterator_archetype<Left> fo1;
    typedef equality_comparable2_second_archetype<
      convertible_to_archetype<null_archetype<> > > Right;
    forward_iterator_archetype<Right> fo2;
    binary_predicate_archetype<null_archetype<> , null_archetype<> >
      pred(dummy_cons);
    fo1 = std::find_end(fo1, fo1, fo2, fo2, pred);
  }

  //===========================================================================
  // Mutating Algorithms

  {
    typedef null_archetype<> T;
    input_iterator_archetype<T> in;
    output_iterator_archetype<T> out(dummy_cons);
    out = std::copy(in, in, out);
  }
  {
    typedef assignable_archetype<> OutT;
    typedef convertible_to_archetype<OutT> InT;
    bidirectional_iterator_archetype<InT> bid_in;
    mutable_bidirectional_iterator_archetype<OutT> bid_out;
    bid_out = std::copy_backward(bid_in, bid_in, bid_out);
  }
  {
    sgi_assignable_archetype<> a(dummy_cons), b(dummy_cons);
    std::swap(a, b);
  }
  {
    typedef sgi_assignable_archetype<> T;
    mutable_forward_iterator_archetype<T> a, b;
    std::iter_swap(a, b);
  }
#if 0
  {
    // fails on gcc 7.3 and clang 6.0
    typedef mutually_convertible_archetype<int> Tin;
    typedef mutually_convertible_archetype<char> Tout;
    mutable_forward_iterator_archetype<Tin> fi1;
    mutable_forward_iterator_archetype<Tout> fi2;
    fi2 = std::swap_ranges(fi1, fi1, fi2);
  }
#endif
  {
    typedef null_archetype<int> Tin;
    typedef null_archetype<char> Tout;
    input_iterator_archetype<Tin> in;
    output_iterator_archetype<Tout> out(dummy_cons);
    unary_function_archetype<null_archetype<> ,
      convertible_to_archetype<Tout> > op(dummy_cons);
    out = std::transform(in, in, out, op);
  }
  {
    typedef null_archetype<int> Tin1;
    typedef null_archetype<char> Tin2;
    typedef null_archetype<double> Tout;
    input_iterator_archetype<Tin1> in1;
    input_iterator_archetype<Tin2> in2;
    output_iterator_archetype<Tout> out(dummy_cons);
    binary_function_archetype<Tin1, Tin2,
      convertible_to_archetype<Tout> > op(dummy_cons);
    out = std::transform(in1, in1, in2, out, op);
  }
  {
    typedef equality_comparable2_first_archetype<
      assignable_archetype<> > FT;
    mutable_forward_iterator_archetype<FT> fi;
    equality_comparable2_second_archetype<
      convertible_to_archetype<FT> > value(dummy_cons);
    std::replace(fi, fi, value, value);
  }
  {
    typedef null_archetype<> PredArg;
    typedef assignable_archetype<
      convertible_to_archetype<PredArg> > FT;
    mutable_forward_iterator_archetype<FT> fi;
    unary_predicate_archetype<PredArg> pred(dummy_cons);
    convertible_to_archetype<FT> value(dummy_cons);
    std::replace_if(fi, fi, pred, value);
  }
#if (!defined(BOOST_MSVC) || BOOST_WORKAROUND(BOOST_MSVC, > 1900)) && !defined(BOOST_EMBTC)
  // fails on MSVC 2015 and earlier
  {
    // Issue, the use of ?: inside replace_copy() complicates things
    typedef equal_op_first_archetype<> Tin;
    typedef null_archetype<> Tout;
    typedef equal_op_second_archetype< convertible_to_archetype<Tout> > T;
    BOOST_CONCEPT_CHECK_COMPATIBLE_INPUT_ITERATOR_ARCHETYPE<Tin> in;
    output_iterator_archetype<Tout> out(dummy_cons);
    T value(dummy_cons);
    out = std::replace_copy(in, in, out, value, value);
  }
  {
    // The issue of ?: also affects this function
    typedef null_archetype<> Tout;
    typedef assignable_archetype< convertible_to_archetype<Tout> > Tin;
    BOOST_CONCEPT_CHECK_COMPATIBLE_INPUT_ITERATOR_ARCHETYPE<Tin> in;
    output_iterator_archetype<Tout> out(dummy_cons);
    unary_predicate_archetype<Tin> pred(dummy_cons);
    Tin value(dummy_cons);
    out = std::replace_copy_if(in, in, out, pred, value);
  }
#endif
  {
    typedef assignable_archetype<> FT;
    mutable_forward_iterator_archetype<FT> fi;
    typedef convertible_to_archetype<FT> T;
    T value(dummy_cons);
    std::fill(fi, fi, value);
  }
#if !defined(BOOST_MSVC) || BOOST_WORKAROUND(BOOST_MSVC, >= 1700)
  // fails on MSVC 2010
  {
    typedef null_archetype<> Tout;
    typedef convertible_to_archetype<Tout> T;
    output_iterator_archetype<Tout> out(dummy_cons);
    T value(dummy_cons);
    int n = 1;
    out = std::fill_n(out, n, value);
  }
#endif
  {
    typedef assignable_archetype<> FT;
    typedef convertible_to_archetype<FT> Ret;
    mutable_forward_iterator_archetype<FT> fi;
    generator_archetype<Ret> gen;
    std::generate(fi, fi, gen);
  }
  {
    typedef assignable_archetype<> FT;
    typedef convertible_to_archetype<FT> Ret;
    mutable_forward_iterator_archetype<FT> fi;
    generator_archetype<Ret> gen;
    int n = 1;
    std::generate_n(fi, n, gen);
  }
  {
    typedef assignable_archetype< equality_comparable2_first_archetype<> > FT;
    typedef equality_comparable2_second_archetype<> T;
    mutable_forward_iterator_archetype<FT> fi;
    T value(dummy_cons);
    fi = std::remove(fi, fi, value);
  }
  {
    typedef assignable_archetype<> FT;
    mutable_forward_iterator_archetype<FT> fi;
    typedef null_archetype<> PredArg;
    unary_predicate_archetype<PredArg> pred(dummy_cons);
    fi = std::remove_if(fi, fi, pred);
  }
  // gcc bug
  {
    typedef null_archetype<> Tout;
    typedef equality_comparable2_first_archetype<
      convertible_to_archetype<Tout> > Tin;
    typedef equality_comparable2_second_archetype<> T;
    BOOST_CONCEPT_CHECK_COMPATIBLE_INPUT_ITERATOR_ARCHETYPE<Tin> in;
    output_iterator_archetype<Tout> out(dummy_cons);
    T value(dummy_cons);
    out = std::remove_copy(in, in, out, value);
  }
  {
    typedef null_archetype<> T;
    input_iterator_archetype<T> in;
    output_iterator_archetype<T> out(dummy_cons);
    unary_predicate_archetype<T> pred(dummy_cons);
    out = std::remove_copy_if(in, in, out, pred);
  }
  {
    typedef sgi_assignable_archetype< equality_comparable_archetype<> > T;
    mutable_forward_iterator_archetype<T> fi;
    fi = std::unique(fi, fi);
  }
  {
    typedef null_archetype<int> Arg1;
    typedef null_archetype<char> Arg2;
    typedef sgi_assignable_archetype<
      convertible_to_archetype<Arg1,
      convertible_to_archetype<Arg2> > > FT;
    mutable_forward_iterator_archetype<FT> fi;
    binary_predicate_archetype<Arg1, Arg2> pred(dummy_cons);
    fi = std::unique(fi, fi, pred);
  }
  // gcc bug
  {
    typedef equality_comparable_archetype< sgi_assignable_archetype<> > T;
    BOOST_CONCEPT_CHECK_COMPATIBLE_INPUT_ITERATOR_ARCHETYPE<T> in;
    output_iterator_archetype<T> out(dummy_cons);
    out = std::unique_copy(in, in, out);
  }
  {
    typedef sgi_assignable_archetype<> T;
    input_iterator_archetype<T> in;
    output_iterator_archetype<T> out(dummy_cons);
    binary_predicate_archetype<T, T> pred(dummy_cons);
    out = std::unique_copy(in, in, out, pred);
  }
  {
    typedef sgi_assignable_archetype<> T;
    mutable_bidirectional_iterator_archetype<T> bi;
    std::reverse(bi, bi);
  }
  {
    typedef null_archetype<> Tout;
    typedef convertible_to_archetype<Tout> Tin;
    bidirectional_iterator_archetype<Tin> bi;
    output_iterator_archetype<Tout> out(dummy_cons);
    out = std::reverse_copy(bi, bi, out);
  }
  {
    typedef sgi_assignable_archetype<> T;
    mutable_forward_iterator_archetype<T> fi;
    // Issue, SGI STL is not have void return type, C++ standard does
    std::rotate(fi, fi, fi);
  }
  {
    typedef null_archetype<> Tout;
    typedef convertible_to_archetype<Tout> FT;
    forward_iterator_archetype<FT> fi;
    output_iterator_archetype<Tout> out(dummy_cons);
    out = std::rotate_copy(fi, fi, fi, out);
  }
#ifndef BOOST_NO_CXX98_RANDOM_SHUFFLE
  {
    typedef sgi_assignable_archetype<> T;
    mutable_random_access_iterator_archetype<T> ri;
    std::random_shuffle(ri, ri);
  }
  {
    typedef sgi_assignable_archetype<> T;
    mutable_random_access_iterator_archetype<T> ri;
    unary_function_archetype<std::ptrdiff_t, std::ptrdiff_t> ran(dummy_cons);
    std::random_shuffle(ri, ri, ran);
  }
#else
  {
    typedef sgi_assignable_archetype<> T;
    mutable_random_access_iterator_archetype<T> ri;
    shuffle::URBG urbg;
    std::shuffle(ri, ri, urbg);
  }
#endif
  {
    typedef null_archetype<> PredArg;
    typedef sgi_assignable_archetype<convertible_to_archetype<PredArg> > FT;
    mutable_bidirectional_iterator_archetype<FT> bi;
    unary_predicate_archetype<PredArg> pred(dummy_cons);
    bi = std::partition(bi, bi, pred);
  }
#if !defined(BOOST_MSVC) && !defined(BOOST_EMBTC)
  {
    // fails on MSVC
    typedef null_archetype<> PredArg;
    typedef sgi_assignable_archetype<convertible_to_archetype<PredArg> > FT;
    mutable_forward_iterator_archetype<FT> fi;
    unary_predicate_archetype<PredArg> pred(dummy_cons);
    fi = std::stable_partition(fi, fi, pred);
  }
#endif
  //===========================================================================
  // Sorting Algorithms
  {
    typedef sgi_assignable_archetype<
      less_than_comparable_archetype<> > T;
    mutable_random_access_iterator_archetype<T> ri;
    std::sort(ri, ri);
  }
  {
    typedef null_archetype<> Arg;
    typedef sgi_assignable_archetype<
      convertible_to_archetype<Arg> > T;
    mutable_random_access_iterator_archetype<T> ri;
    binary_predicate_archetype<Arg, Arg> comp(dummy_cons);
    std::sort(ri, ri, comp);
  }
  {
    typedef less_than_comparable_archetype<
        sgi_assignable_archetype<> > ValueType;
    mutable_random_access_iterator_archetype<ValueType> ri;
    std::stable_sort(ri, ri);
  }
  {
    typedef null_archetype<> Arg;
    typedef sgi_assignable_archetype<
      convertible_to_archetype<Arg> > ValueType;
    mutable_random_access_iterator_archetype<ValueType> ri;
    binary_predicate_archetype<Arg, Arg> comp(dummy_cons);
    std::stable_sort(ri, ri, comp);
  }
  {
    typedef sgi_assignable_archetype<
      less_than_comparable_archetype<> > T;
    mutable_random_access_iterator_archetype<T> ri;
    std::partial_sort(ri, ri, ri);
  }

  {
    typedef null_archetype<> Arg;
    typedef sgi_assignable_archetype<
      convertible_to_archetype<Arg> > T;
    mutable_random_access_iterator_archetype<T> ri;
    binary_predicate_archetype<Arg, Arg> comp(dummy_cons);
    std::partial_sort(ri, ri, ri, comp);
  }
  // gcc bug
  {
    // This could be formulated so that the two iterators are not
    // required to have the same value type, but it is messy.
    typedef sgi_assignable_archetype<
      less_than_comparable_archetype<> > T;
    BOOST_CONCEPT_CHECK_COMPATIBLE_INPUT_ITERATOR_ARCHETYPE<T> in;
    mutable_random_access_iterator_archetype<T> ri_out;
    ri_out = std::partial_sort_copy(in, in , ri_out, ri_out);
  }
  {
    typedef sgi_assignable_archetype<> T;
    input_iterator_archetype<T> in;
    mutable_random_access_iterator_archetype<T> ri_out;
    binary_predicate_archetype<T, T> comp(dummy_cons);
    ri_out = std::partial_sort_copy(in, in , ri_out, ri_out, comp);
  }
  {
    typedef sgi_assignable_archetype< less_than_comparable_archetype<> > T;
    mutable_random_access_iterator_archetype<T> ri;
    std::nth_element(ri, ri, ri);
  }
  {
    typedef null_archetype<int> Arg1;
    typedef null_archetype<char> Arg2;
    typedef sgi_assignable_archetype<
      convertible_to_archetype<Arg1,
      convertible_to_archetype<Arg2> > > T;
    mutable_random_access_iterator_archetype<T> ri;
    binary_predicate_archetype<Arg1, Arg2> comp(dummy_cons);
    std::nth_element(ri, ri, ri, comp);
  }
  {
#if defined(__KCC)
    // The KAI version of this uses a one-argument less-than function
    // object.
    typedef less_than_comparable_archetype<> T;
    typedef convertible_to_archetype<T> FT;
#else
    typedef less_than_op_first_archetype<> FT;
    typedef less_than_op_second_archetype<> T;
#endif
    forward_iterator_archetype<FT> fi;
    T value(dummy_cons);
    fi = std::lower_bound(fi, fi, value);
  }
  {
    typedef null_archetype<int> Arg1;
    typedef null_archetype<char> Arg2;
    typedef convertible_to_archetype<Arg1> FT;
    typedef convertible_to_archetype<Arg2> T;
    forward_iterator_archetype<FT> fi;
    T value(dummy_cons);
    binary_predicate_archetype<Arg1, Arg2> comp(dummy_cons);
    fi = std::lower_bound(fi, fi, value, comp);
  }
  {
#if defined(__KCC)
    typedef less_than_comparable_archetype<> T;
    typedef convertible_to_archetype<T> FT;
#else
    // Note, order of T,FT is flipped from lower_bound
    typedef less_than_op_second_archetype<> FT;
    typedef less_than_op_first_archetype<> T;
#endif
    forward_iterator_archetype<FT> fi;
    T value(dummy_cons);
    fi = std::upper_bound(fi, fi, value);
  }
  {
    typedef null_archetype<int> Arg1;
    typedef null_archetype<char> Arg2;
    // Note, order of T,FT is flipped from lower_bound
    typedef convertible_to_archetype<Arg1> T;
    typedef convertible_to_archetype<Arg2> FT;
    forward_iterator_archetype<FT> fi;
    T value(dummy_cons);
    binary_predicate_archetype<Arg1, Arg2> comp(dummy_cons);
    fi = std::upper_bound(fi, fi, value, comp);
  }
#if !defined(BOOST_MSVC) || BOOST_WORKAROUND(BOOST_MSVC, >= 1900)
  // Fails on MSVC 2013 and earlier
  {
#if defined(__KCC)
    typedef less_than_comparable_archetype<> T;
    typedef convertible_to_archetype<T> FT;
#else
    typedef less_than_op_first_archetype<
      less_than_op_second_archetype< null_archetype<>, optag2>, optag1> FT;
    typedef less_than_op_second_archetype<
      less_than_op_first_archetype< null_archetype<>, optag2>, optag1> T;
#endif
    typedef forward_iterator_archetype<FT> FIter;
    FIter fi;
    T value(dummy_cons);
    std::pair<FIter,FIter> p = std::equal_range(fi, fi, value);
    ignore_unused_variable_warning(p);
  }
#endif
  {
    typedef null_archetype<int> Arg1;
    typedef null_archetype<char> Arg2;
    typedef convertible_to_archetype<Arg1,
      convertible_to_archetype<Arg2> > FT;
    typedef convertible_to_archetype<Arg2,
      convertible_to_archetype<Arg1> > T;
    typedef forward_iterator_archetype<FT> FIter;
    FIter fi;
    T value(dummy_cons);
    binary_predicate_archetype<Arg1, Arg2> comp(dummy_cons);
    std::pair<FIter,FIter> p = std::equal_range(fi, fi, value, comp);
    ignore_unused_variable_warning(p);
  }
  {
#if defined(__KCC)
    typedef less_than_op_first_archetype< less_than_comparable_archetype<> > T;
    typedef less_than_op_second_archetype< convertible_to_archetype<T> > FT;
#else
    typedef less_than_op_first_archetype<
      less_than_op_second_archetype<null_archetype<>, optag2>, optag1> FT;
    typedef less_than_op_second_archetype<
      less_than_op_first_archetype<null_archetype<>, optag2>, optag1> T;
#endif
    forward_iterator_archetype<FT> fi;
    T value(dummy_cons);
    bool b = std::binary_search(fi, fi, value);
    ignore_unused_variable_warning(b);
  }
  {
    typedef null_archetype<int> Arg1;
    typedef null_archetype<char> Arg2;
    typedef convertible_to_archetype<Arg1,
      convertible_to_archetype<Arg2> > FT;
    typedef convertible_to_archetype<Arg2,
      convertible_to_archetype<Arg1> > T;
    typedef forward_iterator_archetype<FT> FIter;
    FIter fi;
    T value(dummy_cons);
    binary_predicate_archetype<Arg1, Arg2> comp(dummy_cons);
    bool b = std::binary_search(fi, fi, value, comp);
    ignore_unused_variable_warning(b);
  }
  {
    typedef null_archetype<> Tout;
    typedef less_than_op_first_archetype<
      less_than_op_second_archetype<
      convertible_to_archetype<Tout>, optag2>, optag1 > Tin1;
    typedef less_than_op_second_archetype<
      less_than_op_first_archetype<
      convertible_to_archetype<Tout>, optag2> ,optag1> Tin2;
    // gcc bug
    BOOST_CONCEPT_CHECK_COMPATIBLE_INPUT_ITERATOR_ARCHETYPE<Tin1> in1;
    BOOST_CONCEPT_CHECK_COMPATIBLE_INPUT_ITERATOR_ARCHETYPE<Tin2> in2;
    output_iterator_archetype<Tout> out(dummy_cons);
    out = std::merge(in1, in1, in2, in2, out);
    out = std::set_union(in1, in1, in2, in2, out);
    out = std::set_intersection(in1, in1, in2, in2, out);
    out = std::set_difference(in1, in1, in2, in2, out);
    out = std::set_symmetric_difference(in1, in1, in2, in2, out);
  }
  {
    typedef null_archetype<> T;
    input_iterator_archetype<T> in1;
    input_iterator_archetype<T,2> in2;
    output_iterator_archetype<T> out(dummy_cons);
    binary_predicate_archetype<T, T> comp(dummy_cons);
    out = std::merge(in1, in1, in2, in2, out, comp);
    out = std::set_union(in1, in1, in2, in2, out, comp);
    out = std::set_intersection(in1, in1, in2, in2, out, comp);
    out = std::set_difference(in1, in1, in2, in2, out, comp);
    out = std::set_symmetric_difference(in1, in1, in2, in2, out, comp);
  }
  {
    typedef sgi_assignable_archetype<
      less_than_comparable_archetype<> > T;
    mutable_bidirectional_iterator_archetype<T> bi;
    std::inplace_merge(bi, bi, bi);
  }
  {
    typedef null_archetype<> Arg;
    typedef sgi_assignable_archetype<
      convertible_to_archetype<Arg> > T;
    mutable_bidirectional_iterator_archetype<T> bi;
    binary_predicate_archetype<Arg, Arg> comp(dummy_cons);
    std::inplace_merge(bi, bi, bi, comp);
  }
  // gcc bug
  {
    typedef less_than_op_first_archetype<
      less_than_op_second_archetype<null_archetype<>, optag1>, optag2> Tin1;
    typedef less_than_op_second_archetype<
      less_than_op_first_archetype<null_archetype<>, optag1>, optag2> Tin2;
    BOOST_CONCEPT_CHECK_COMPATIBLE_INPUT_ITERATOR_ARCHETYPE<Tin1> in1;
    BOOST_CONCEPT_CHECK_COMPATIBLE_INPUT_ITERATOR_ARCHETYPE<Tin2> in2;
    bool b = std::includes(in1, in1, in2, in2);
    b = std::lexicographical_compare(in1, in1, in2, in2);
    ignore_unused_variable_warning(b);
  }
  {
    typedef null_archetype<int> Tin;
    input_iterator_archetype<Tin> in1;
    input_iterator_archetype<Tin,1> in2;
    binary_predicate_archetype<Tin, Tin> comp(dummy_cons);
    bool b = std::includes(in1, in1, in2, in2, comp);
    b = std::lexicographical_compare(in1, in1, in2, in2, comp);
    ignore_unused_variable_warning(b);
  }
  {
    typedef sgi_assignable_archetype<
      less_than_comparable_archetype<> > T;
    mutable_random_access_iterator_archetype<T> ri;
    std::push_heap(ri, ri);
    std::pop_heap(ri, ri);
    std::make_heap(ri, ri);
    std::sort_heap(ri, ri);
  }
  {
    typedef null_archetype<> Arg;
    typedef sgi_assignable_archetype<
      convertible_to_archetype<Arg> > T;
    mutable_random_access_iterator_archetype<T> ri;
    binary_predicate_archetype<Arg, Arg> comp(dummy_cons);
    std::push_heap(ri, ri, comp);
    std::pop_heap(ri, ri, comp);
    std::make_heap(ri, ri, comp);
    std::sort_heap(ri, ri, comp);
  }
  {
    typedef less_than_comparable_archetype<> T;
    T a(dummy_cons), b(dummy_cons);
    BOOST_USING_STD_MIN();
    BOOST_USING_STD_MAX();
    const T& c = min BOOST_PREVENT_MACRO_SUBSTITUTION(a, b);
    const T& d = max BOOST_PREVENT_MACRO_SUBSTITUTION(a, b);
    ignore_unused_variable_warning(c);
    ignore_unused_variable_warning(d);
  }
  {
    typedef null_archetype<> Arg;
    binary_predicate_archetype<Arg, Arg> comp(dummy_cons);
    typedef convertible_to_archetype<Arg> T;
    T a(dummy_cons), b(dummy_cons);
    BOOST_USING_STD_MIN();
    BOOST_USING_STD_MAX();
    const T& c = min BOOST_PREVENT_MACRO_SUBSTITUTION(a, b, comp);
    const T& d = max BOOST_PREVENT_MACRO_SUBSTITUTION(a, b, comp);
    ignore_unused_variable_warning(c);
    ignore_unused_variable_warning(d);
  }
  {
    typedef less_than_comparable_archetype<> T;
    forward_iterator_archetype<T> fi;
    fi = std::min_element(fi, fi);
    fi = std::max_element(fi, fi);
  }
  {
    typedef null_archetype<> Arg;
    binary_predicate_archetype<Arg, Arg> comp(dummy_cons);
    typedef convertible_to_archetype<Arg> T;
    forward_iterator_archetype<T> fi;
    fi = std::min_element(fi, fi, comp);
    fi = std::max_element(fi, fi, comp);
  }
  {
    typedef sgi_assignable_archetype<
      less_than_comparable_archetype<> > T;
    mutable_bidirectional_iterator_archetype<T> bi;
    bool b = std::next_permutation(bi, bi);
    b = std::prev_permutation(bi, bi);
    ignore_unused_variable_warning(b);
  }
  {
    typedef null_archetype<> Arg;
    binary_predicate_archetype<Arg, Arg> comp(dummy_cons);
    typedef sgi_assignable_archetype<
      convertible_to_archetype<Arg> > T;
    mutable_bidirectional_iterator_archetype<T> bi;
    bool b = std::next_permutation(bi, bi, comp);
    b = std::prev_permutation(bi, bi, comp);
    ignore_unused_variable_warning(b);
  }
  //===========================================================================
  // Generalized Numeric Algorithms

  {
    // Bummer, couldn't use plus_op because of a problem with
    // mutually recursive types.
    input_iterator_archetype<accum::Tin> in;
    accum::T init(dummy_cons);
    init = std::accumulate(in, in, init);
  }
  {
    typedef null_archetype<int> Arg1;
    typedef null_archetype<char> Arg2;
    typedef sgi_assignable_archetype<
      convertible_to_archetype<Arg1> > T;
    typedef convertible_to_archetype<T> Ret;
    input_iterator_archetype<Arg2> in;
    T init(dummy_cons);
    binary_function_archetype<Arg1, Arg2, Ret> op(dummy_cons);
    init = std::accumulate(in, in, init, op);
  }
  {
    input_iterator_archetype<inner_prod::Tin1> in1;
    input_iterator_archetype<inner_prod::Tin2> in2;
    inner_prod::T init(dummy_cons);
    init = std::inner_product(in1, in1, in2, init);
  }
  {
    typedef null_archetype<int> MultArg1;
    typedef null_archetype<char> MultArg2;
    typedef null_archetype<short> AddArg1;
    typedef null_archetype<long> AddArg2;
    typedef sgi_assignable_archetype<
      convertible_to_archetype<AddArg1> > T;
    typedef convertible_to_archetype<AddArg2> RetMult;
    typedef convertible_to_archetype<T> RetAdd;
    input_iterator_archetype<MultArg1> in1;
    input_iterator_archetype<MultArg2> in2;
    T init(dummy_cons);
    binary_function_archetype<MultArg1, MultArg2, RetMult> mult_op(dummy_cons);
    binary_function_archetype<AddArg1, AddArg2, RetAdd> add_op(dummy_cons);
    init = std::inner_product(in1, in1, in2, init, add_op, mult_op);
  }
  {
    input_iterator_archetype<part_sum::T> in;
    output_iterator_archetype<part_sum::T> out(dummy_cons);
    out = std::partial_sum(in, in, out);
  }
  {
    typedef sgi_assignable_archetype<> T;
    input_iterator_archetype<T> in;
    output_iterator_archetype<T> out(dummy_cons);
    binary_function_archetype<T, T, T> add_op(dummy_cons);
    out = std::partial_sum(in, in, out, add_op);
    binary_function_archetype<T, T, T> subtract_op(dummy_cons);
    out = std::adjacent_difference(in, in, out, subtract_op);
  }
  {
    input_iterator_archetype<part_sum::T> in;
    output_iterator_archetype<part_sum::T> out(dummy_cons);
    out = std::adjacent_difference(in, in, out);
  }
  return 0;
}