ceph/src/boost/libs/graph/test/relaxed_heap_test.cpp

   1 // Copyright 2004 The Trustees of Indiana University.
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Douglas Gregor
   8 //           Andrew Lumsdaine
   9 #ifndef BOOST_RELAXED_HEAP_DEBUG
  10 #  define BOOST_RELAXED_HEAP_DEBUG 0
  11 #endif
  12
  13 #include <boost/pending/relaxed_heap.hpp>
  14 #include <boost/test/minimal.hpp>
  15 #include <utility>
  16 #include <iostream>
  17 #include <vector>
  18 #include <boost/optional.hpp>
  19 #include <boost/random.hpp>
  20 #include <boost/lexical_cast.hpp>
  21 #include <boost/progress.hpp>
  22
  23 typedef std::vector<boost::optional<double> > values_type;
  24 values_type values;
  25
  26 struct less_extvalue
  27 {
  28   typedef bool result_type;
  29
  30   bool operator()(unsigned x, unsigned y) const
  31   {
  32     assert(values[x] && values[y]);
  33     return values[x] < values[y];
  34   }
  35 };
  36
  37 using namespace std;
  38
  39 boost::optional<double> get_min_value()
  40 {
  41   boost::optional<double> min_value;
  42   for (unsigned i = 0; i < values.size(); ++i) {
  43     if (values[i]) {
  44       if (!min_value || *values[i] < *min_value) min_value = values[i];
  45     }
  46   }
  47   return min_value;
  48 }
  49
  50 void interactive_test()
  51 {
  52   unsigned max_values;
  53   cout << "Enter max number of values in the heap> ";
  54   cin >> max_values;
  55
  56   values.resize(max_values);
  57   boost::relaxed_heap<unsigned, less_extvalue> heap(max_values);
  58
  59   char option;
  60   do {
  61     cout << "Enter command> ";
  62     if (cin >> option) {
  63       switch (option) {
  64       case 'i': case 'I':
  65         {
  66           unsigned index;
  67           double value;
  68           if (cin >> index >> value) {
  69             if (index >= values.size()) cout << "Index out of range.\n";
  70             else if (values[index]) cout << "Already in queue.\n";
  71             else {
  72               values[index] = value;
  73               heap.push(index);
  74               heap.dump_tree();
  75             }
  76           }
  77         }
  78         break;
  79
  80       case 'u': case 'U':
  81         {
  82           unsigned index;
  83           double value;
  84           if (cin >> index >> value) {
  85             if (index >= values.size()) cout << "Index out of range.\n";
  86             else if (!values[index]) cout << "Not in queue.\n";
  87             else {
  88               values[index] = value;
  89               heap.update(index);
  90               heap.dump_tree();
  91             }
  92           }
  93         }
  94         break;
  95
  96       case 'r': case 'R':
  97         {
  98           unsigned index;
  99           if (cin >> index) {
 100             if (index >= values.size()) cout << "Index out of range.\n";
 101             else if (!values[index]) cout << "Not in queue.\n";
 102             else {
 103               heap.remove(index);
 104               heap.dump_tree();
 105             }
 106           }
 107         }
 108         break;
 109
 110       case 't': case 'T':
 111         {
 112           if (boost::optional<double> min_value = get_min_value()) {
 113             cout << "Top value is (" << heap.top() << ", "
 114                  << *values[heap.top()] << ").\n";
 115             BOOST_CHECK(*min_value == *values[heap.top()]);
 116           } else {
 117             cout << "Queue is empty.\n";
 118             BOOST_CHECK(heap.empty());
 119           }
 120         }
 121         break;
 122
 123       case 'd': case 'D':
 124         {
 125           if (boost::optional<double> min_value = get_min_value()) {
 126             unsigned victim = heap.top();
 127             double value = *values[victim];
 128             cout << "Removed top value (" << victim << ", " << value << ")\n";
 129             BOOST_CHECK(*min_value == value);
 130
 131             heap.pop();
 132             heap.dump_tree();
 133             values[victim].reset();
 134           } else {
 135             cout << "Queue is empty.\n";
 136             BOOST_CHECK(heap.empty());
 137           }
 138         }
 139         break;
 140
 141       case 'q': case 'Q':
 142         break;
 143
 144       default:
 145         cout << "Unknown command '" << option << "'.\n";
 146       }
 147     }
 148   } while (cin && option != 'q' && option != 'Q');
 149 }
 150
 151 void random_test(int n, int iterations, int seed)
 152 {
 153   values.resize(n);
 154   boost::relaxed_heap<unsigned, less_extvalue> heap(n);
 155   boost::minstd_rand gen(seed);
 156   boost::uniform_int<unsigned> rand_index(0, n-1);
 157   boost::uniform_real<> rand_value(-1000.0, 1000.0);
 158   boost::uniform_int<unsigned> which_option(0, 3);
 159
 160   cout << n << std::endl;
 161
 162 #if BOOST_RELAXED_HEAP_DEBUG > 1
 163   heap.dump_tree();
 164 #endif
 165
 166   BOOST_REQUIRE(heap.valid());
 167
 168 #if BOOST_RELAXED_HEAP_DEBUG == 0
 169   boost::progress_display progress(iterations);
 170 #endif
 171
 172   for (int iteration = 0; iteration < iterations; ++iteration) {
 173 #if BOOST_RELAXED_HEAP_DEBUG > 1
 174     std::cout << "Iteration #" << iteration << std::endl;
 175 #endif
 176     unsigned victim = rand_index(gen);
 177     if (values[victim]) {
 178       switch (which_option(gen)) {
 179       case 0: case 3:
 180         {
 181           // Update with a smaller weight
 182           boost::uniform_real<> rand_smaller((rand_value.min)(), *values[victim]);
 183           values[victim] = rand_smaller(gen);
 184           assert(*values[victim] >= (rand_smaller.min)());
 185           assert(*values[victim] <= (rand_smaller.max)());
 186
 187 #if BOOST_RELAXED_HEAP_DEBUG > 0
 188           cout << "u " << victim << " " << *values[victim] << std::endl;
 189           cout.flush();
 190 #endif
 191           heap.update(victim);
 192         }
 193         break;
 194
 195       case 1:
 196         {
 197           // Delete minimum value in the queue.
 198           victim = heap.top();
 199           double top_value = *values[victim];
 200           BOOST_CHECK(*get_min_value() == top_value);
 201           if (*get_min_value() != top_value) return;
 202 #if BOOST_RELAXED_HEAP_DEBUG > 0
 203           cout << "d" << std::endl;
 204           cout.flush();
 205 #endif
 206           heap.pop();
 207           values[victim].reset();
 208 #if BOOST_RELAXED_HEAP_DEBUG > 1
 209           cout << "(Removed " << victim << ")\n";
 210 #endif // BOOST_RELAXED_HEAP_DEBUG > 1
 211         }
 212         break;
 213
 214       case 2:
 215         {
 216           // Just remove this value from the queue completely
 217           values[victim].reset();
 218 #if BOOST_RELAXED_HEAP_DEBUG > 0
 219           cout << "r " << victim << std::endl;
 220           cout.flush();
 221 #endif
 222           heap.remove(victim);
 223         }
 224         break;
 225
 226       default:
 227         cout << "Random number generator failed." << endl;
 228         BOOST_CHECK(false);
 229         return;
 230         break;
 231       }
 232     } else {
 233       values[victim] = rand_value(gen);
 234       assert(*values[victim] >= (rand_value.min)());
 235       assert(*values[victim] <= (rand_value.max)());
 236
 237 #if BOOST_RELAXED_HEAP_DEBUG > 0
 238       cout << "i " << victim << " " << *values[victim] << std::endl;
 239       cout.flush();
 240 #endif
 241       heap.push(victim);
 242     }
 243
 244 #if BOOST_RELAXED_HEAP_DEBUG > 1
 245     heap.dump_tree();
 246 #endif // BOOST_RELAXED_HEAP_DEBUG > 1
 247
 248     BOOST_REQUIRE(heap.valid());
 249
 250 #if BOOST_RELAXED_HEAP_DEBUG == 0
 251     ++progress;
 252 #endif
 253   }
 254 }
 255
 256 int test_main(int argc, char* argv[])
 257 {
 258   if (argc >= 3) {
 259     int n = boost::lexical_cast<int>(argv[1]);
 260     int iterations = boost::lexical_cast<int>(argv[2]);
 261     int seed = (argc >= 4? boost::lexical_cast<int>(argv[3]) : 1);
 262     random_test(n, iterations, seed);
 263   } else interactive_test();
 264   return 0;
 265 }