testsuite_counter_type.h (counter_type::operator<(const counter_type&)): Update less_compare_count.

2014-10-07  François Dumont  <fdumont@gcc.gnu.org>

	* testsuite/util/testsuite_counter_type.h
	(counter_type::operator<(const counter_type&)): Update
	less_compare_count.
	* testsuite/25_algorithms/make_heap/complexity.cc: New.
	* testsuite/25_algorithms/pop_heap/complexity.cc: New.
	* testsuite/25_algorithms/push_heap/complexity.cc: New.
	* testsuite/25_algorithms/sort_heap/complexity.cc: New.

From-SVN: r215985

6 files changed, 224 insertions, 1 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 6120d26..c2ed337 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,13 @@
+2014-10-07  François Dumont  <fdumont@gcc.gnu.org>
+
+	* testsuite/util/testsuite_counter_type.h
+	(counter_type::operator<(const counter_type&)): Update
+	less_compare_count.
+	* testsuite/25_algorithms/make_heap/complexity.cc: New.
+	* testsuite/25_algorithms/pop_heap/complexity.cc: New.
+	* testsuite/25_algorithms/push_heap/complexity.cc: New.
+	* testsuite/25_algorithms/sort_heap/complexity.cc: New.
+
 2014-10-06  Rüdiger Sonderfeld  <ruediger@c-plusplus.de>
 	    Jonathan Wakely  <jwakely@redhat.com>
 
diff --git a/libstdc++-v3/testsuite/25_algorithms/make_heap/complexity.cc b/libstdc++-v3/testsuite/25_algorithms/make_heap/complexity.cc
new file mode 100644
index 0000000..cfe1a7a
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/make_heap/complexity.cc
@@ -0,0 +1,50 @@
+// Copyright (C) 2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <random>
+#include <vector>
+#include <algorithm>
+
+#include <testsuite_counter_type.h>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  using __gnu_test::counter_type;
+  const std::size_t nb_values = 1000;
+
+  std::random_device dev;
+  std::uniform_int_distribution<int> dist;
+  std::vector<counter_type> values;
+  values.reserve(nb_values);
+  for (std::size_t i = 0; i != nb_values; ++i)
+    values.push_back(dist(dev));
+
+  counter_type::reset();
+
+  std::make_heap(values.begin(), values.end());
+
+  VERIFY( counter_type::less_compare_count <= 3.0 * nb_values );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/pop_heap/complexity.cc b/libstdc++-v3/testsuite/25_algorithms/pop_heap/complexity.cc
new file mode 100644
index 0000000..75ed37e
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/pop_heap/complexity.cc
@@ -0,0 +1,53 @@
+// Copyright (C) 2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <cmath>
+#include <random>
+#include <vector>
+#include <algorithm>
+
+#include <testsuite_counter_type.h>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  using __gnu_test::counter_type;
+  const std::size_t nb_values = 1000;
+
+  std::random_device dev;
+  std::uniform_int_distribution<int> dist;
+  std::vector<counter_type> values;
+  values.reserve(nb_values);
+  for (std::size_t i = 0; i != nb_values; ++i)
+    values.push_back(dist(dev));
+
+  std::make_heap(values.begin(), values.end());
+
+  counter_type::reset();
+
+  std::pop_heap(values.begin(), values.end());
+
+  VERIFY( counter_type::less_compare_count <= 2.0 * std::log(nb_values) );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/push_heap/complexity.cc b/libstdc++-v3/testsuite/25_algorithms/push_heap/complexity.cc
new file mode 100644
index 0000000..90c4457
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/push_heap/complexity.cc
@@ -0,0 +1,54 @@
+// Copyright (C) 2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <cmath>
+#include <random>
+#include <vector>
+#include <algorithm>
+
+#include <testsuite_counter_type.h>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  using __gnu_test::counter_type;
+  const std::size_t nb_values = 1000;
+
+  std::random_device dev;
+  std::uniform_int_distribution<int> dist;
+  std::vector<counter_type> values;
+  values.reserve(nb_values);
+  for (std::size_t i = 0; i != nb_values; ++i)
+    values.push_back(dist(dev));
+
+  std::make_heap(values.begin(), values.end());
+  values.push_back(dist(dev));
+
+  counter_type::reset();
+
+  std::push_heap(values.begin(), values.end());
+
+  VERIFY( counter_type::less_compare_count <= std::log(values.size()) );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/sort_heap/complexity.cc b/libstdc++-v3/testsuite/25_algorithms/sort_heap/complexity.cc
new file mode 100644
index 0000000..b847e27
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/sort_heap/complexity.cc
@@ -0,0 +1,53 @@
+// Copyright (C) 2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <cmath>
+#include <random>
+#include <vector>
+#include <algorithm>
+
+#include <testsuite_counter_type.h>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  using __gnu_test::counter_type;
+  const std::size_t nb_values = 1000;
+
+  std::random_device dev;
+  std::uniform_int_distribution<int> dist;
+  std::vector<counter_type> values;
+  values.reserve(nb_values);
+  for (std::size_t i = 0; i != nb_values; ++i)
+    values.push_back(dist(dev));
+
+  std::make_heap(values.begin(), values.end());
+
+  counter_type::reset();
+
+  std::sort_heap(values.begin(), values.end());
+
+  VERIFY( counter_type::less_compare_count <= 2.0 * nb_values * std::log(nb_values) );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/util/testsuite_counter_type.h b/libstdc++-v3/testsuite/util/testsuite_counter_type.h
index 43a9ea3..157ab25 100644
--- a/libstdc++-v3/testsuite/util/testsuite_counter_type.h
+++ b/libstdc++-v3/testsuite/util/testsuite_counter_type.h
@@ -95,7 +95,10 @@ namespace __gnu_test
     { return val == rhs.val; }
 
     bool operator<(const counter_type& rhs) const
-    { return val < rhs.val; }
+    {
+      ++less_compare_count;
+      return val < rhs.val;
+    }
   };
 
   int counter_type::default_count = 0;