libs/heap/test/mutable_heap_tests.hpp

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