Boost_1_39_0/libs/graph/example/bucket_sorter.cpp

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9 #include <boost/config.hpp>
  10 #include <vector>
  11 #include <iostream>
  12
  13 #include <stdlib.h>
  14 #include <boost/pending/bucket_sorter.hpp>
  15
  16 template <class Integral>
  17 struct trivial_id {
  18   std::size_t operator[](Integral i) {
  19     return i;
  20   }
  21   std::size_t operator[](Integral i) const {
  22     return i;
  23   }
  24 };
  25
  26
  27 int main() {
  28   using namespace std;
  29   using boost::bucket_sorter;
  30
  31   const std::size_t N = 10;
  32
  33   vector<std::size_t> bucket(N);
  34   for (std::size_t i=0; i<N; i++) {
  35     bucket[i] = rand() % N;
  36     cout.width(6);
  37     cout << "Number " << i << " has its bucket "  << bucket[i] << endl;
  38   }
  39
  40   typedef trivial_id<int> ID;
  41   typedef bucket_sorter<std::size_t, int,
  42     vector<std::size_t>::iterator, ID> BS;
  43   BS my_bucket_sorter(N, N, bucket.begin());
  44
  45   for (std::size_t ii=0; ii<N; ii++)
  46     my_bucket_sorter.push(ii);
  47
  48   std::size_t j;
  49   for (j=0; j<N; j++) {
  50     cout << "The bucket " << j;
  51     if ( ! my_bucket_sorter[j].empty() ) {
  52       cout << " has number ";
  53       do {
  54         int v = my_bucket_sorter[j].top();
  55         my_bucket_sorter[j].pop();
  56         cout << v << " ";
  57       } while ( ! my_bucket_sorter[j].empty() );
  58       cout << endl;
  59     } else {
  60       cout << " has no number associated with." << endl;
  61     }
  62   }
  63
  64   for (std::size_t k=0; k<N; k++)
  65     my_bucket_sorter.push(k);
  66
  67   my_bucket_sorter.remove(5);
  68   my_bucket_sorter.remove(7);
  69
  70   cout << "Afer remove number 5 and 7, check correctness again." << endl;
  71
  72   for (j=0; j<N; j++) {
  73     cout << "The bucket " << j;
  74     if ( ! my_bucket_sorter[j].empty() ) {
  75       cout << " has number ";
  76       do {
  77         int v = my_bucket_sorter[j].top();
  78         my_bucket_sorter[j].pop();
  79         cout << v << " ";
  80       } while ( ! my_bucket_sorter[j].empty() );
  81       cout << endl;
  82     } else {
  83       cout << " has no number associated with." << endl;
  84     }
  85   }
  86
  87   std::size_t iii;
  88   for (iii=0; iii<N; iii++) {
  89     std::size_t current = rand() % N;
  90     if ( ! my_bucket_sorter[current].empty() ) {
  91       int v = my_bucket_sorter[current].top();
  92       my_bucket_sorter[current].pop();
  93       bucket[v] = rand() % N;
  94       my_bucket_sorter.push(v);
  95     }
  96   }
  97
  98   for (iii=0; iii<N; iii++) {
  99     std::size_t current = rand() % N;
 100     if ( ! my_bucket_sorter[current].empty() ) {
 101       int v = my_bucket_sorter[current].top();
 102       bucket[v] = rand() % N;
 103       my_bucket_sorter.update(v);
 104     }
 105   }
 106
 107     return 0;
 108 }