graph/test/relaxed_heap_test.cpp

// Copyright 2004 The Trustees of Indiana University.

// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

//  Authors: Douglas Gregor
//           Andrew Lumsdaine
#ifndef BOOST_RELAXED_HEAP_DEBUG
#  define BOOST_RELAXED_HEAP_DEBUG 0
#endif

#include <boost/pending/relaxed_heap.hpp>
#include <boost/test/minimal.hpp>
#include <utility>
#include <iostream>
#include <vector>
#include <boost/optional.hpp>
#include <boost/random.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/progress.hpp>

typedef std::vector<boost::optional<double> > values_type;
values_type values;

struct less_extvalue
{
  typedef bool result_type;

  bool operator()(unsigned x, unsigned y) const
  {
    assert(values[x] && values[y]);
    return values[x] < values[y];
  }
};

using namespace std;

boost::optional<double> get_min_value()
{
  boost::optional<double> min_value;
  for (unsigned i = 0; i < values.size(); ++i) {
    if (values[i]) {
      if (!min_value || *values[i] < *min_value) min_value = values[i];
    }
  }
  return min_value;
}

void interactive_test()
{
  unsigned max_values;
  cout << "Enter max number of values in the heap> ";
  cin >> max_values;

  values.resize(max_values);
  boost::relaxed_heap<unsigned, less_extvalue> heap(max_values);

  char option;
  do {
    cout << "Enter command> ";
    if (cin >> option) {
      switch (option) {
      case 'i': case 'I':
        {
          unsigned index;
          double value;
          if (cin >> index >> value) {
            if (index >= values.size()) cout << "Index out of range.\n";
            else if (values[index]) cout << "Already in queue.\n";
            else {
              values[index] = value;
              heap.push(index);
              heap.dump_tree();
            }
          }
        }
        break;

      case 'u': case 'U':
        {
          unsigned index;
          double value;
          if (cin >> index >> value) {
            if (index >= values.size()) cout << "Index out of range.\n";
            else if (!values[index]) cout << "Not in queue.\n";
            else {
              values[index] = value;
              heap.update(index);
              heap.dump_tree();
            }
          }
        }
        break;

      case 'r': case 'R':
        {
          unsigned index;
          if (cin >> index) {
            if (index >= values.size()) cout << "Index out of range.\n";
            else if (!values[index]) cout << "Not in queue.\n";
            else {
              heap.remove(index);
              heap.dump_tree();
            }
          }
        }
        break;

      case 't': case 'T':
        {
          if (boost::optional<double> min_value = get_min_value()) {
            cout << "Top value is (" << heap.top() << ", "
                 << *values[heap.top()] << ").\n";
            BOOST_CHECK(*min_value == *values[heap.top()]);
          } else {
            cout << "Queue is empty.\n";
            BOOST_CHECK(heap.empty());
          }
        }
        break;

      case 'd': case 'D':
        {
          if (boost::optional<double> min_value = get_min_value()) {
            unsigned victim = heap.top();
            double value = *values[victim];
            cout << "Removed top value (" << victim << ", " << value << ")\n";
            BOOST_CHECK(*min_value == value);

            heap.pop();
            heap.dump_tree();
            values[victim].reset();
          } else {
            cout << "Queue is empty.\n";
            BOOST_CHECK(heap.empty());
          }
        }
        break;

      case 'q': case 'Q':
        break;

      default:
        cout << "Unknown command '" << option << "'.\n";
      }
    }
  } while (cin && option != 'q' && option != 'Q');
}

void random_test(int n, int iterations, int seed)
{
  values.resize(n);
  boost::relaxed_heap<unsigned, less_extvalue> heap(n);
  boost::minstd_rand gen(seed);
  boost::uniform_int<unsigned> rand_index(0, n-1);
  boost::uniform_real<> rand_value(-1000.0, 1000.0);
  boost::uniform_int<unsigned> which_option(0, 3);

  cout << n << std::endl;

#if BOOST_RELAXED_HEAP_DEBUG > 1
  heap.dump_tree();
#endif

  BOOST_REQUIRE(heap.valid());

#if BOOST_RELAXED_HEAP_DEBUG == 0
  boost::progress_display progress(iterations);
#endif

  for (int iteration = 0; iteration < iterations; ++iteration) {
#if BOOST_RELAXED_HEAP_DEBUG > 1
    std::cout << "Iteration #" << iteration << std::endl;
#endif
    unsigned victim = rand_index(gen);
    if (values[victim]) {
      switch (which_option(gen)) {
      case 0: case 3:
        {
          // Update with a smaller weight
          boost::uniform_real<> rand_smaller((rand_value.min)(), *values[victim]);
          values[victim] = rand_smaller(gen);
          assert(*values[victim] >= (rand_smaller.min)());
          assert(*values[victim] <= (rand_smaller.max)());

#if BOOST_RELAXED_HEAP_DEBUG > 0
          cout << "u " << victim << " " << *values[victim] << std::endl;
          cout.flush();
#endif
          heap.update(victim);
        }
        break;

      case 1:
        {
          // Delete minimum value in the queue.
          victim = heap.top();
          double top_value = *values[victim];
          BOOST_CHECK(*get_min_value() == top_value);
          if (*get_min_value() != top_value) return;
#if BOOST_RELAXED_HEAP_DEBUG > 0
          cout << "d" << std::endl;
          cout.flush();
#endif
          heap.pop();
          values[victim].reset();
#if BOOST_RELAXED_HEAP_DEBUG > 1
          cout << "(Removed " << victim << ")\n";
#endif // BOOST_RELAXED_HEAP_DEBUG > 1
        }
        break;

      case 2:
        {
          // Just remove this value from the queue completely
          values[victim].reset();
#if BOOST_RELAXED_HEAP_DEBUG > 0
          cout << "r " << victim << std::endl;
          cout.flush();
#endif
          heap.remove(victim);
        }
        break;

      default:
        cout << "Random number generator failed." << endl;
        BOOST_CHECK(false);
        return;
        break;
      }
    } else {
      values[victim] = rand_value(gen);
      assert(*values[victim] >= (rand_value.min)());
      assert(*values[victim] <= (rand_value.max)());

#if BOOST_RELAXED_HEAP_DEBUG > 0
      cout << "i " << victim << " " << *values[victim] << std::endl;
      cout.flush();
#endif
      heap.push(victim);
    }

#if BOOST_RELAXED_HEAP_DEBUG > 1
    heap.dump_tree();
#endif // BOOST_RELAXED_HEAP_DEBUG > 1

    BOOST_REQUIRE(heap.valid());

#if BOOST_RELAXED_HEAP_DEBUG == 0
    ++progress;
#endif
  }
}

int test_main(int argc, char* argv[])
{
  if (argc >= 3) {
    int n = boost::lexical_cast<int>(argv[1]);
    int iterations = boost::lexical_cast<int>(argv[2]);
    int seed = (argc >= 4? boost::lexical_cast<int>(argv[3]) : 1);
    random_test(n, iterations, seed);
  } else interactive_test();
  return 0;
}