25.heap.cpp

Go to the documentation of this file.

 
// MSVC 6.0 gets an ICE in std::__adjust_heap() in <algorithm.cc>
#if defined (_MSC_VER) && _MSC_VER <= 1300
#  define _RWSTD_NO_EXPLICIT_INSTANTIATION
#endif
 
#include <algorithm>    // for make_heap, sort_heap, push_heap, pop_heap
#include <cstring>      // for strlen, size_t
 
#include <rw_alg_test.h>
#include <rw_value.h>      // for UserClass
#include <rw_driver.h>     // for rw_test()
 
 
_RWSTD_NAMESPACE (std) { 
 
#ifndef _RWSTD_NO_EXPLICIT_INSTANTIATION
 
// 25.3.6.1 - push_heap [lib.push.heap]
template
void
push_heap (RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >, 
           RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >);
 
template
void
push_heap (RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >, 
           RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >, 
           binary_predicate<lt_comp<assign<base<cpy_ctor> > > >);
 
// 25.3.6.2 - pop_heap [lib.pop.heap]
template
void
pop_heap (RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >, 
          RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >);
 
template
void
pop_heap (RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >, 
          RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >, 
          binary_predicate<lt_comp<assign<base<cpy_ctor> > > >);
 
// 25.3.6.3 - make_heap [lib.make.heap]
template
void
make_heap (RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >, 
           RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >);
 
template
void
make_heap (RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >, 
           RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >, 
           binary_predicate<lt_comp<assign<base<cpy_ctor> > > >);
 
// 25.3.6.4 - sort_heap [lib.sort.heap]
template
void
sort_heap (RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >, 
                RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >);
 
template
void
sort_heap (RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >, 
           RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >, 
           binary_predicate<lt_comp<assign<base<cpy_ctor> > > >);
 
#endif // _RWSTD_NO_EXPLICIT_INSTANTIATION
 
}   // namespace std
 
 
template <class T>
struct Less 
{
    static std::size_t funcalls_;
 
    // dummy arguments provided to prevent the class from being
    // default constructible and implicit conversion from int
    Less (int /* dummy */, int /* dummy */) {
        funcalls_ = 0;
    }
 
    // return a type other than bool but one that is implicitly
    // convertible to bool to detect incorrect assumptions
    conv_to_bool operator() (const T &x, const T &y) /* non-const */ {
        ++funcalls_;
        return conv_to_bool::make (x.data_.val_ < y.data_.val_);
    }
 
    static const char* name () { return "Less"; }
 
private:
    void operator= (Less&);   // not assignable
};
 
template<class T> std::size_t Less<T>::funcalls_;
 
 
// helper function to verify that the sequence is a valid heap
template <class T>
bool is_heap (const T* seq, const std::size_t len)
{
  std::size_t parent = 0;
  for (std::size_t child = 1; child < len; ++child) {
 
      if (seq [parent].data_.val_ < seq [child].data_.val_) 
          return false;
 
      if ((child & 1) == 0)
          ++parent;
  }
 
  return true;
}
 
 
// exercises push_heap, pop_heap, make_heap, sort_heap: 25.3.6.1 - 25.3.6.4
template <class T, class Predicate>
void test_heap_operation (int               line,
                          const char       *src,
                          const T*,
                          const Predicate  *ppred,
                          const std::size_t finx)
{
    static const char* const fnames[] = {
        "make_heap", "push_heap", "pop_heap", "sort_heap"
    };
 
    typedef RandomAccessIter<T> RandIter;
    RandIter rand_iter (0, 0, 0);
 
    const char* const itname  = type_name (rand_iter, (T*)0);
    const char* const fname   = fnames[finx];
    const char* const funname = Predicate::name();
 
    const std::size_t nsrc = std::strlen (src);
 
    T* const xsrc     = T::from_char (src, nsrc);
    T* const xsrc_end = xsrc + nsrc;
 
    int val = xsrc[0].data_.val_;
 
    const RandIter first = make_iter (xsrc,     xsrc, xsrc_end, rand_iter);
    const RandIter last  = make_iter (xsrc_end, xsrc, xsrc_end, rand_iter);
 
    const Predicate pred (0, 0);
 
    const std::size_t last_n_op_lt = T::n_total_op_lt_;
 
    // for convenience
#define HEAP_OP(opname) \
    if (ppred) opname (first, last, pred); else opname (first, last)
 
    std::size_t ops = 0;
 
    // exercise heap operation and compute the expected complexity
    switch (finx) {
    case 0: HEAP_OP (std::make_heap); ops = 3 * nsrc; break;
    case 1: HEAP_OP (std::push_heap); ops = ilog2 (nsrc); break;
    case 2: HEAP_OP (std::pop_heap);  ops = 2 * ilog2 (nsrc); break;
    case 3: HEAP_OP (std::sort_heap); ops = nsrc * ilog2 (nsrc); break;
    }            
 
    const std::size_t n_ops_lt = ppred ? 
        Predicate::funcalls_ : T::n_total_op_lt_ - last_n_op_lt;
 
    const std::size_t len = 2 != finx ? nsrc : nsrc - 1;
    static const int cwidth = sizeof (T);
 
    if (2 == finx) {     // pop_heap special verification
        // verify that the maximal element is in 
        // the end of the sequence: 25.3.6.2, p2
        rw_assert (val == xsrc[nsrc - 1].data_.val_, 0, line,
                   "line %d std::%s <%s%{?}, %s%{;}> (\"%s\", ...) ==> "
                   "\"%{X=*.*}\", last is %#c, expected %#c",
                   __LINE__, fname, itname, ppred, funname, src, 
                   cwidth, int (nsrc), -1, xsrc,
                   xsrc [nsrc - 1].data_.val_, val);
    }
 
    if (3 == finx) {     // sort_heap special verification
        // verify that we got a sorted sequence: 25.3.6.4, p1
        rw_assert (is_sorted_lt (xsrc, xsrc_end), 0, line,
                   "line %d std::%s <%s%{?}, %s%{;}> (\"%s\", ...) ==> "
                   "\"%{X=*.*}\" is not sorted",
                   __LINE__, fname, itname, ppred, funname, src, 
                   cwidth, int (nsrc), -1, xsrc);
    }
    else {  
        // verify that we got a heap: 
        // 25.3.6.1, p2; 25.3.6.2, p2; 25.3.6.3, p1
        rw_assert (is_heap (xsrc, len), 0, line,
                   "line %d std::%s <%s%{?}, %s%{;}> (\"%s\", ...) ==> "
                   "\"%{X=*.*}\" is not a heap",
                   __LINE__, fname, itname, ppred, funname, src, 
                   cwidth, int (len), -1, xsrc);
    }
 
    // verify the complexity: 
    // 25.3.6.1, p3; 25.3.6.2, p3; 25.3.6.3, p2; 25.3.6.4, p2
    rw_assert (n_ops_lt <= ops, 0, line,
               "line %d std::%s <%s%{?}, %s%{;}> (\"%s\", ...) ==> "
               "\"%{X=*.*}\" complexity: got %zu invocations of %s, "
               "expected no more %zu",
               __LINE__, fname, itname, ppred, funname, src, 
               cwidth, int (nsrc), -1, xsrc, n_ops_lt, 
               ppred ? "predicate" : "operator< ()", ops);
 
    delete[] xsrc;
}
 
 
template <class T, class Predicate>
void test_make_heap (const T*,
                     const Predicate *ppred)
{
    rw_info (0, 0, 0,
             "std::make_heap (%s, %1$s%{?}, %s%{;})",
             "RandomAccessIterator", 0 != ppred, Predicate::name ());
 
#define TEST(src)                                               \
    test_heap_operation (__LINE__, src, (T*)0, ppred, 0)
 
    TEST ("a");
    TEST ("ab");
    TEST ("ba");
 
    TEST ("abcde");
    TEST ("acbed");
    TEST ("cbade");
    TEST ("debca");
    TEST ("ecace");
    TEST ("accee");
    TEST ("caced");
 
    TEST ("abcdefghij");
    TEST ("bcdeafghij");
    TEST ("dcbeafihgj");
    TEST ("badcfehgji");
    TEST ("ebadcfhijg");
 
    TEST ("jihgfedcba");
    TEST ("ijhgefdcab");
 
    TEST ("ababababab");
    TEST ("babbbababb");
 
#undef TEST
}
 
 
template <class T, class Predicate>
void test_push_heap (const T*,
                     const Predicate *ppred)
{
    rw_info (0, 0, 0,
             "std::push_heap (%s, %1$s%{?}, %s%{;})",
             "RandomAccessIterator", 0 != ppred, Predicate::name ());
 
#define TEST(src)                                               \
    test_heap_operation (__LINE__, src, (T*)0, ppred, 1)
 
    TEST ("a");
    TEST ("ab");
    TEST ("ba");
 
    TEST ("bac");
    TEST ("cba");
    TEST ("aac");
 
    TEST ("ecdaba");
    TEST ("ecdabc");
    TEST ("ecdabe");
 
    TEST ("jighefcadj");
    TEST ("jighefcada");
    TEST ("jighefcadh");
 
    TEST ("jhigcfbeda");
    TEST ("jhigcfbedj");
    TEST ("jhigcfbedh");
    TEST ("jhigcfbedf");
    TEST ("jhigcfbede");
    TEST ("jhigcfbedg");
 
    TEST ("bbbbbaaaaa");
    TEST ("bbbbbaaaab");
 
#undef TEST
}
 
 
template <class T, class Predicate>
void test_pop_heap (const T*,
                     const Predicate *ppred)
{
    rw_info (0, 0, 0,
             "std::pop_heap (%s, %1$s%{?}, %s%{;})",
             "RandomAccessIterator", 0 != ppred, Predicate::name ());
 
#define TEST(src)                                               \
    test_heap_operation (__LINE__, src, (T*)0, ppred, 2)
 
    TEST ("a");
    TEST ("ba");
 
    TEST ("aaa");
    TEST ("cba");
    TEST ("caa");
 
    TEST ("ecdab");
    TEST ("ecdab");
    TEST ("ecdab");
 
    TEST ("jighefcadb");
    TEST ("jighcfdbea");
    TEST ("jhigcfbeda");
    TEST ("jihgfedacb");
    TEST ("iihegfabdc");
    TEST ("iihgfedcba");
    TEST ("iihgefdcab");
 
    TEST ("bbbbbaaaaa");
 
#undef TEST
}
 
 
template <class T, class Predicate>
void test_sort_heap (const T*,
                     const Predicate *ppred)
{
    rw_info (0, 0, 0,
             "std::sort_heap (%s, %1$s%{?}, %s%{;})",
             "RandomAccessIterator", 0 != ppred, Predicate::name());
 
#define TEST(src)                                               \
    test_heap_operation (__LINE__, src, (T*)0, ppred, 3)
 
    TEST ("a");
    TEST ("ba");
 
    TEST ("aaa");
    TEST ("cba");
    TEST ("caa");
 
    TEST ("ecdab");
    TEST ("ecdab");
    TEST ("ecdab");
 
    TEST ("jighefcadb");
    TEST ("jighcfdbea");
    TEST ("jhigcfbeda");
    TEST ("jihgfedacb");
    TEST ("iihegfabdc");
    TEST ("iihgfedcba");
    TEST ("iihgefdcab");
 
    TEST ("bbbbbaaaaa");
 
#undef TEST
}
 
 
/* extern */ int rw_opt_no_make_heap;          // --no-make_heap
/* extern */ int rw_opt_no_push_heap;          // --no-push_heap
/* extern */ int rw_opt_no_pop_heap;           // --no-pop_heap
/* extern */ int rw_opt_no_sort_heap;          // --no-sort_heap
/* extern */ int rw_opt_no_predicate;          // --no-predicate
 
 
template <class T, class Predicate>
void test_heap_operations (const T*,
                           const Predicate *ppred)
{
    if (rw_opt_no_make_heap) {
        rw_note (0, __FILE__, __LINE__, 
                 "std::make_heap test disabled");
    }
    else {
        test_make_heap ((T*)0, ppred);
    }
 
    if (rw_opt_no_push_heap) {
        rw_note (0, __FILE__, __LINE__, 
                 "std::push_heap test disabled");
    }
    else {
        test_push_heap ((T*)0, ppred);
    }
 
    if (rw_opt_no_pop_heap) {
        rw_note (0, __FILE__, __LINE__, 
                 "std::pop_heap test disabled");
    }
    else {
        test_pop_heap ((T*)0, ppred);
    }
 
    if (rw_opt_no_sort_heap) {
        rw_note (0, __FILE__, __LINE__, 
                 "std::sort_heap test disabled");
    }
    else {
        test_sort_heap ((T*)0, ppred);
    }
}
 
 
static int run_test (int, char*[])
{
    test_heap_operations ((UserClass*)0, (Less<UserClass>*)0);
 
    if (rw_opt_no_predicate) {
        rw_note (0, __FILE__, __LINE__, 
                 "heap operations predicate test disabled");
    }
    else {
        test_heap_operations ((UserClass*)0, (Less<UserClass>*)1);
    }
 
    return 0;
}
 
 
 
int main (int argc, char *argv[])
{
    return rw_test (argc, argv, __FILE__,
                    "lib.alg.heap.operations",
                    0 /* no comment */, run_test,
                    "|-no-make_heap#"
                    "|-no-push_heap#"
                    "|-no-pop_heap#"
                    "|-no-sort_heap#"
                    "|-no-predicate",
                    &rw_opt_no_make_heap,
                    &rw_opt_no_push_heap,
                    &rw_opt_no_pop_heap,
                    &rw_opt_no_sort_heap,
                    &rw_opt_no_predicate);
}