From 3484495b3d061038210aa19fc20ed28834dcc1da Mon Sep 17 00:00:00 2001
From: Marshall Clow <mclow.lists@gmail.com>
Date: Mon, 30 Jun 2014 05:04:20 +0000
Subject: [PATCH] Add checking for the complexity guarantees in the standard

llvm-svn: 212017
---
 .../make.heap/make_heap_comp.pass.cpp                    | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)

diff --git a/libcxx/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp b/libcxx/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp
index ed76fa2..7bbdd09 100644
--- a/libcxx/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp
+++ b/libcxx/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp
@@ -17,6 +17,9 @@
 #include <algorithm>
 #include <functional>
 #include <cassert>
+
+#include "counting_predicates.hpp"
+
 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 #include <memory>
 
@@ -34,9 +37,20 @@ void test(unsigned N)
     int* ia = new int [N];
     for (int i = 0; i < N; ++i)
         ia[i] = i;
+    {
     std::random_shuffle(ia, ia+N);
     std::make_heap(ia, ia+N, std::greater<int>());
     assert(std::is_heap(ia, ia+N, std::greater<int>()));
+    }
+
+    {
+    binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>()));
+    std::random_shuffle(ia, ia+N);
+    std::make_heap(ia, ia+N, std::ref(pred));
+    assert(pred.count() <= 3*N);
+    assert(std::is_heap(ia, ia+N, pred));   
+    }
+
     delete [] ia;
 }
 
@@ -48,6 +62,8 @@ int main()
     test(3);
     test(10);
     test(1000);
+    test(10000);
+    test(100000);
 
 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
     {
-- 
2.7.4