src/third_party/libc++/trunk/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp

   1 //===----------------------------------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is dual licensed under the MIT and the University of Illinois Open
   6 // Source Licenses. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 // <algorithm>
  11
  12 // template<RandomAccessIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
  13 //   requires ShuffleIterator<Iter> && CopyConstructible<Compare>
  14 //   void
  15 //   make_heap(Iter first, Iter last, Compare comp);
  16
  17 #include <algorithm>
  18 #include <functional>
  19 #include <cassert>
  20
  21 #include "counting_predicates.hpp"
  22
  23 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  24 #include <memory>
  25
  26 struct indirect_less
  27 {
  28     template <class P>
  29     bool operator()(const P& x, const P& y)
  30         {return *x < *y;}
  31 };
  32
  33 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  34
  35 void test(unsigned N)
  36 {
  37     int* ia = new int [N];
  38     {
  39     for (int i = 0; i < N; ++i)
  40         ia[i] = i;
  41     std::random_shuffle(ia, ia+N);
  42     std::make_heap(ia, ia+N, std::greater<int>());
  43     assert(std::is_heap(ia, ia+N, std::greater<int>()));
  44     }
  45
  46 //  Ascending
  47     {
  48     binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>()));
  49     for (int i = 0; i < N; ++i)
  50         ia[i] = i;
  51     std::make_heap(ia, ia+N, std::ref(pred));
  52     assert(pred.count() <= 3*N);
  53     assert(std::is_heap(ia, ia+N, pred));
  54     }
  55
  56 //  Descending
  57     {
  58     binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>()));
  59     for (int i = 0; i < N; ++i)
  60         ia[N-1-i] = i;
  61     std::make_heap(ia, ia+N, std::ref(pred));
  62     assert(pred.count() <= 3*N);
  63     assert(std::is_heap(ia, ia+N, pred));
  64     }
  65
  66 //  Random
  67     {
  68     binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>()));
  69     std::random_shuffle(ia, ia+N);
  70     std::make_heap(ia, ia+N, std::ref(pred));
  71     assert(pred.count() <= 3*N);
  72     assert(std::is_heap(ia, ia+N, pred));
  73     }
  74
  75     delete [] ia;
  76 }
  77
  78 int main()
  79 {
  80     test(0);
  81     test(1);
  82     test(2);
  83     test(3);
  84     test(10);
  85     test(1000);
  86     test(10000);
  87     test(100000);
  88
  89 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  90     {
  91     const int N = 1000;
  92     std::unique_ptr<int>* ia = new std::unique_ptr<int> [N];
  93     for (int i = 0; i < N; ++i)
  94         ia[i].reset(new int(i));
  95     std::random_shuffle(ia, ia+N);
  96     std::make_heap(ia, ia+N, indirect_less());
  97     assert(std::is_heap(ia, ia+N, indirect_less()));
  98     delete [] ia;
  99     }
 100 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 101 }