ceph/src/boost/libs/heap/test/mutable_heap_tests.hpp

   1 /*=============================================================================
   2     Copyright (c) 2010 Tim Blechmann
   3
   4     Use, modification and distribution is subject to the Boost Software
   5     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6     http://www.boost.org/LICENSE_1_0.txt)
   7 =============================================================================*/
   8
   9 // random uses boost.fusion, which clashes with boost.test
  10 //#define USE_BOOST_RANDOM
  11
  12 #ifdef USE_BOOST_RANDOM
  13 #include <boost/random.hpp>
  14 #else
  15 #include <cstdlib>
  16 #endif
  17
  18 #include "common_heap_tests.hpp"
  19
  20
  21 #define PUSH_WITH_HANDLES(HANDLES, Q, DATA)                 \
  22     std::vector<typename pri_queue::handle_type> HANDLES;   \
  23                                                             \
  24     for (unsigned int k = 0; k != data.size(); ++k)         \
  25         HANDLES.push_back(Q.push(DATA[k]));
  26
  27
  28
  29 template <typename pri_queue>
  30 void pri_queue_test_update_decrease(void)
  31 {
  32     for (int i = 0; i != test_size; ++i) {
  33         pri_queue q;
  34         test_data data = make_test_data(test_size);
  35         PUSH_WITH_HANDLES(handles, q, data);
  36
  37         *handles[i] = -1;
  38         data[i] = -1;
  39         q.update(handles[i]);
  40
  41         std::sort(data.begin(), data.end());
  42         check_q(q, data);
  43     }
  44 }
  45
  46 template <typename pri_queue>
  47 void pri_queue_test_update_decrease_function(void)
  48 {
  49     for (int i = 0; i != test_size; ++i) {
  50         pri_queue q;
  51         test_data data = make_test_data(test_size);
  52         PUSH_WITH_HANDLES(handles, q, data);
  53
  54         data[i] = -1;
  55         q.update(handles[i], -1);
  56
  57         std::sort(data.begin(), data.end());
  58         check_q(q, data);
  59     }
  60 }
  61
  62 template <typename pri_queue>
  63 void pri_queue_test_update_function_identity(void)
  64 {
  65     for (int i = 0; i != test_size; ++i) {
  66         pri_queue q;
  67         test_data data = make_test_data(test_size);
  68         PUSH_WITH_HANDLES(handles, q, data);
  69
  70         q.update(handles[i], data[i]);
  71
  72         std::sort(data.begin(), data.end());
  73         check_q(q, data);
  74     }
  75 }
  76
  77 template <typename pri_queue>
  78 void pri_queue_test_update_shuffled(void)
  79 {
  80     pri_queue q;
  81     test_data data = make_test_data(test_size);
  82     PUSH_WITH_HANDLES(handles, q, data);
  83
  84     test_data shuffled (data);
  85     random_shuffle(shuffled.begin(), shuffled.end());
  86
  87     for (int i = 0; i != test_size; ++i)
  88         q.update(handles[i], shuffled[i]);
  89
  90     check_q(q, data);
  91 }
  92
  93
  94 template <typename pri_queue>
  95 void pri_queue_test_update_increase(void)
  96 {
  97     for (int i = 0; i != test_size; ++i) {
  98         pri_queue q;
  99         test_data data = make_test_data(test_size);
 100         PUSH_WITH_HANDLES(handles, q, data);
 101
 102         data[i] = data.back()+1;
 103         *handles[i] = data[i];
 104         q.update(handles[i]);
 105
 106         std::sort(data.begin(), data.end());
 107         check_q(q, data);
 108     }
 109 }
 110
 111 template <typename pri_queue>
 112 void pri_queue_test_update_increase_function(void)
 113 {
 114     for (int i = 0; i != test_size; ++i) {
 115         pri_queue q;
 116         test_data data = make_test_data(test_size);
 117         PUSH_WITH_HANDLES(handles, q, data);
 118
 119         data[i] = data.back()+1;
 120         q.update(handles[i], data[i]);
 121
 122         std::sort(data.begin(), data.end());
 123         check_q(q, data);
 124     }
 125 }
 126
 127 template <typename pri_queue>
 128 void pri_queue_test_decrease(void)
 129 {
 130     for (int i = 0; i != test_size; ++i) {
 131         pri_queue q;
 132         test_data data = make_test_data(test_size);
 133         PUSH_WITH_HANDLES(handles, q, data);
 134
 135         *handles[i] = -1;
 136         data[i] = -1;
 137         q.decrease(handles[i]);
 138
 139         std::sort(data.begin(), data.end());
 140         check_q(q, data);
 141     }
 142 }
 143
 144 template <typename pri_queue>
 145 void pri_queue_test_decrease_function(void)
 146 {
 147     for (int i = 0; i != test_size; ++i) {
 148         pri_queue q;
 149         test_data data = make_test_data(test_size);
 150         PUSH_WITH_HANDLES(handles, q, data);
 151
 152         data[i] = -1;
 153         q.decrease(handles[i], -1);
 154
 155         std::sort(data.begin(), data.end());
 156         check_q(q, data);
 157     }
 158 }
 159
 160 template <typename pri_queue>
 161 void pri_queue_test_decrease_function_identity(void)
 162 {
 163     for (int i = 0; i != test_size; ++i) {
 164         pri_queue q;
 165         test_data data = make_test_data(test_size);
 166         PUSH_WITH_HANDLES(handles, q, data);
 167
 168         q.decrease(handles[i], data[i]);
 169
 170         check_q(q, data);
 171     }
 172 }
 173
 174
 175 template <typename pri_queue>
 176 void pri_queue_test_increase(void)
 177 {
 178     for (int i = 0; i != test_size; ++i) {
 179         pri_queue q;
 180         test_data data = make_test_data(test_size);
 181         PUSH_WITH_HANDLES(handles, q, data);
 182
 183         data[i] = data.back()+1;
 184         *handles[i] = data[i];
 185         q.increase(handles[i]);
 186
 187         std::sort(data.begin(), data.end());
 188         check_q(q, data);
 189     }
 190 }
 191
 192 template <typename pri_queue>
 193 void pri_queue_test_increase_function(void)
 194 {
 195     for (int i = 0; i != test_size; ++i) {
 196         pri_queue q;
 197         test_data data = make_test_data(test_size);
 198         PUSH_WITH_HANDLES(handles, q, data);
 199
 200         data[i] = data.back()+1;
 201         q.increase(handles[i], data[i]);
 202
 203         std::sort(data.begin(), data.end());
 204         check_q(q, data);
 205     }
 206 }
 207
 208 template <typename pri_queue>
 209 void pri_queue_test_increase_function_identity(void)
 210 {
 211     for (int i = 0; i != test_size; ++i) {
 212         pri_queue q;
 213         test_data data = make_test_data(test_size);
 214         PUSH_WITH_HANDLES(handles, q, data);
 215
 216         q.increase(handles[i], data[i]);
 217
 218         check_q(q, data);
 219     }
 220 }
 221
 222 template <typename pri_queue>
 223 void pri_queue_test_erase(void)
 224 {
 225 #ifdef USE_BOOST_RANDOM
 226     boost::mt19937 rng;
 227 #endif
 228
 229     for (int i = 0; i != test_size; ++i)
 230     {
 231         pri_queue q;
 232         test_data data = make_test_data(test_size);
 233         PUSH_WITH_HANDLES(handles, q, data);
 234
 235         for (int j = 0; j != i; ++j)
 236         {
 237 #ifdef USE_BOOST_RANDOM
 238             boost::uniform_int<> range(0, data.size() - 1);
 239             boost::variate_generator<boost::mt19937&, boost::uniform_int<> > gen(rng, range);
 240
 241             int index = gen();
 242 #else
 243             int index = std::rand() % (data.size() - 1);
 244 #endif
 245             q.erase(handles[index]);
 246             handles.erase(handles.begin() + index);
 247             data.erase(data.begin() + index);
 248         }
 249
 250         std::sort(data.begin(), data.end());
 251         check_q(q, data);
 252     }
 253 }
 254
 255
 256 template <typename pri_queue>
 257 void run_mutable_heap_update_tests(void)
 258 {
 259     pri_queue_test_update_increase<pri_queue>();
 260     pri_queue_test_update_decrease<pri_queue>();
 261
 262     pri_queue_test_update_shuffled<pri_queue>();
 263 }
 264
 265 template <typename pri_queue>
 266 void run_mutable_heap_update_function_tests(void)
 267 {
 268     pri_queue_test_update_increase_function<pri_queue>();
 269     pri_queue_test_update_decrease_function<pri_queue>();
 270     pri_queue_test_update_function_identity<pri_queue>();
 271 }
 272
 273
 274 template <typename pri_queue>
 275 void run_mutable_heap_decrease_tests(void)
 276 {
 277     pri_queue_test_decrease<pri_queue>();
 278     pri_queue_test_decrease_function<pri_queue>();
 279     pri_queue_test_decrease_function_identity<pri_queue>();
 280 }
 281
 282 template <typename pri_queue>
 283 void run_mutable_heap_increase_tests(void)
 284 {
 285     pri_queue_test_increase<pri_queue>();
 286     pri_queue_test_increase_function<pri_queue>();
 287     pri_queue_test_increase_function_identity<pri_queue>();
 288 }
 289
 290 template <typename pri_queue>
 291 void run_mutable_heap_erase_tests(void)
 292 {
 293     pri_queue_test_erase<pri_queue>();
 294 }
 295
 296 template <typename pri_queue>
 297 void run_mutable_heap_test_handle_from_iterator(void)
 298 {
 299     pri_queue que;
 300
 301     que.push(3);
 302     que.push(1);
 303     que.push(4);
 304
 305     que.update(pri_queue::s_handle_from_iterator(que.begin()),
 306                6);
 307 }
 308
 309
 310 template <typename pri_queue>
 311 void run_mutable_heap_tests(void)
 312 {
 313     run_mutable_heap_update_function_tests<pri_queue>();
 314     run_mutable_heap_update_tests<pri_queue>();
 315     run_mutable_heap_decrease_tests<pri_queue>();
 316     run_mutable_heap_increase_tests<pri_queue>();
 317     run_mutable_heap_erase_tests<pri_queue>();
 318     run_mutable_heap_test_handle_from_iterator<pri_queue>();
 319 }
 320
 321 template <typename pri_queue>
 322 void run_ordered_iterator_tests()
 323 {
 324     pri_queue_test_ordered_iterators<pri_queue>();
 325 }