boost_1_45_0/libs/graph/example/bucket_sorter.cpp

//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// Distributed under 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)
//=======================================================================
#include <boost/config.hpp>
#include <vector>
#include <iostream>

#include <stdlib.h>
#include <boost/pending/bucket_sorter.hpp>

template <class Integral>
struct trivial_id {
  std::size_t operator[](Integral i) {
    return i;
  }
  std::size_t operator[](Integral i) const {
    return i;
  }
};


int main() {
  using namespace std;
  using boost::bucket_sorter;
  
  const std::size_t N = 10;

  vector<std::size_t> bucket(N);
  for (std::size_t i=0; i<N; i++) {
    bucket[i] = rand() % N;
    cout.width(6);
    cout << "Number " << i << " has its bucket "  << bucket[i] << endl;
  }

  typedef trivial_id<int> ID;
  typedef bucket_sorter<std::size_t, int, 
    vector<std::size_t>::iterator, ID> BS;
  BS my_bucket_sorter(N, N, bucket.begin());

  for (std::size_t ii=0; ii<N; ii++)
    my_bucket_sorter.push(ii);
    
  std::size_t j;
  for (j=0; j<N; j++) {
    cout << "The bucket " << j;
    if ( ! my_bucket_sorter[j].empty() ) {
      cout << " has number ";
      do {
        int v = my_bucket_sorter[j].top();
        my_bucket_sorter[j].pop();
        cout << v << " ";
      } while ( ! my_bucket_sorter[j].empty() );
      cout << endl;
    } else {
      cout << " has no number associated with." << endl;
    }
  }

  for (std::size_t k=0; k<N; k++)
    my_bucket_sorter.push(k);

  my_bucket_sorter.remove(5);
  my_bucket_sorter.remove(7);

  cout << "Afer remove number 5 and 7, check correctness again." << endl;

  for (j=0; j<N; j++) {
    cout << "The bucket " << j;
    if ( ! my_bucket_sorter[j].empty() ) {
      cout << " has number ";
      do {
        int v = my_bucket_sorter[j].top();
        my_bucket_sorter[j].pop();
        cout << v << " ";
      } while ( ! my_bucket_sorter[j].empty() );
      cout << endl;
    } else {
      cout << " has no number associated with." << endl;
    }
  }

  std::size_t iii;
  for (iii=0; iii<N; iii++) {
    std::size_t current = rand() % N;
    if ( ! my_bucket_sorter[current].empty() ) {
      int v = my_bucket_sorter[current].top();
      my_bucket_sorter[current].pop();
      bucket[v] = rand() % N;
      my_bucket_sorter.push(v);
    }
  }

  for (iii=0; iii<N; iii++) {
    std::size_t current = rand() % N;
    if ( ! my_bucket_sorter[current].empty() ) {
      int v = my_bucket_sorter[current].top();
      bucket[v] = rand() % N;
      my_bucket_sorter.update(v);
    }
  }

    return 0;
}