libstdc++-v3/testsuite/util/performance/assoc/timing/tree_order_statistics_test.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2019 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING3.  If not see
  18 // <http://www.gnu.org/licenses/>.
  19
  20
  21 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  22
  23 // Permission to use, copy, modify, sell, and distribute this software
  24 // is hereby granted without fee, provided that the above copyright
  25 // notice appears in all copies, and that both that copyright notice
  26 // and this permission notice appear in supporting documentation. None
  27 // of the above authors, nor IBM Haifa Research Laboratories, make any
  28 // representation about the suitability of this software for any
  29 // purpose. It is provided "as is" without express or implied
  30 // warranty.
  31
  32 /**
  33  * @file tree_order_statistics_test.hpp
  34  * Contains a test for order_statisticsing trees
  35  */
  36
  37 #ifndef PB_DS_TREE_ORDER_STATISTICS_TEST_HPP
  38 #define PB_DS_TREE_ORDER_STATISTICS_TEST_HPP
  39
  40 #include <performance/time/timing_test_base.hpp>
  41 #include <performance/io/xml_formatter.hpp>
  42 #include <common_type/assoc/string_form.hpp>
  43 #include <ext/pb_ds/detail/type_utils.hpp>
  44 #include <iterator>
  45 #include <cstdlib>
  46
  47 namespace __gnu_pbds
  48 {
  49   namespace test
  50   {
  51     namespace detail
  52     {
  53       template<typename Cntnr, bool Native>
  54       class order_statistics_functor
  55       {
  56       public:
  57         order_statistics_functor(Cntnr& container) : m_r_container(container)
  58         { }
  59
  60         void
  61         operator()(std::size_t resolution)
  62         {
  63           enum
  64             {
  65               support_detected =
  66               __gnu_pbds::test::detail::tree_supports_order_statistics<Cntnr>::value
  67             };
  68
  69           PB_DS_STATIC_ASSERT(correct_type, support_detected);
  70
  71           for (std::size_t i = 0; i < resolution; ++i)
  72             {
  73               typename Cntnr::const_iterator it = m_r_container.begin();
  74               typename Cntnr::const_iterator e = m_r_container.end();
  75               const size_t max_size = m_r_container.size();
  76               while (it != e)
  77                 if (m_r_container.order_of_key(*(it++)) > max_size)
  78                   std::abort();
  79             }
  80         }
  81
  82       private:
  83         Cntnr& m_r_container;
  84       };
  85
  86       template<typename Cntnr>
  87       class order_statistics_functor<Cntnr, false>
  88       {
  89       public:
  90         order_statistics_functor(Cntnr& container) : m_r_container(container)
  91         { }
  92
  93         void
  94         operator()(std::size_t resolution)
  95         {
  96           for (std::size_t i = 0; i < resolution; ++i)
  97             {
  98               typedef typename Cntnr::const_iterator const_iterator;
  99               const_iterator b = m_r_container.begin();
 100               const_iterator e = m_r_container.end();
 101               const_iterator it = b;
 102               const size_t max_size = m_r_container.size();
 103               while (it != e)
 104                 {
 105                   const_iterator f_it = m_r_container.find(*(it++));
 106                   if (static_cast<size_t>(std::distance(b, f_it)) > max_size)
 107                     std::abort();
 108                 }
 109             }
 110         }
 111
 112       private:
 113         Cntnr& m_r_container;
 114       };
 115     } // namespace detail
 116
 117     template<bool Support_Order_Statistics>
 118     class tree_order_statistics_test
 119     : private __gnu_pbds::test::detail::timing_test_base
 120     {
 121     public:
 122       tree_order_statistics_test(size_t vn, size_t vs, size_t vm)
 123       : m_vn(vn), m_vs(vs), m_vm(vm)
 124       { }
 125
 126       template<typename Cntnr>
 127       void
 128       operator()(Cntnr);
 129
 130     private:
 131       tree_order_statistics_test(const tree_order_statistics_test& );
 132
 133       template<typename Cntnr>
 134       void
 135       order_statistics(Cntnr& r_container, __gnu_pbds::detail::true_type);
 136
 137       template<typename Cntnr>
 138       void
 139       order_statistics(Cntnr& r_container, __gnu_pbds::detail::false_type);
 140
 141     private:
 142       const size_t m_vn;
 143       const size_t m_vs;
 144       const size_t m_vm;
 145     };
 146
 147     template<bool Support_Order_Statistics>
 148     template<typename Cntnr>
 149     void
 150     tree_order_statistics_test<Support_Order_Statistics>::
 151     operator()(Cntnr)
 152     {
 153       typedef xml_result_set_performance_formatter formatter_type;
 154       formatter_type res_set_fmt(string_form<Cntnr>::name(),
 155                                  string_form<Cntnr>::desc());
 156
 157       for (size_t v = m_vn; v < m_vm; v += m_vs)
 158         {
 159           Cntnr cntnr;
 160           for (size_t ins = 0; ins < v; ++ ins)
 161             cntnr.insert((typename Cntnr::value_type)ins);
 162
 163           __gnu_pbds::test::detail::order_statistics_functor<Cntnr, Support_Order_Statistics>
 164             fn(cntnr);
 165
 166           const double res =
 167             __gnu_pbds::test::detail::timing_test_base::operator()(fn);
 168
 169           res_set_fmt.add_res(v, res / v);
 170         }
 171     }
 172   } // namespace test
 173 } // namespace __gnu_pbds
 174
 175 #endif
 176