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
10 #include <boost/config.hpp>
11 #include <vector>
12 #include <iostream>
13
14 #include <stdlib.h>
15 #include <boost/pending/bucket_sorter.hpp>
16
main()17 int main()
18 {
19 using namespace std;
20 using boost::bucket_sorter;
21
22 const std::size_t N = 10;
23
24 vector< std::size_t > bucket(N);
25 for (std::size_t i = 0; i < N; i++)
26 {
27 bucket[i] = rand() % N;
28 cout.width(6);
29 cout << "Number " << i << " is in bucket " << bucket[i] << endl;
30 }
31
32 typedef boost::identity_property_map ID;
33 typedef bucket_sorter< std::size_t, int, vector< std::size_t >::iterator,
34 ID >
35 BS;
36 BS my_bucket_sorter(N, N, bucket.begin());
37
38 for (std::size_t ii = 0; ii < N; ii++)
39 my_bucket_sorter.push(ii);
40
41 std::size_t j;
42 for (j = 0; j < N; j++)
43 {
44 cout << "The bucket " << j;
45 if (!my_bucket_sorter[j].empty())
46 {
47 cout << " has number ";
48 do
49 {
50 int v = my_bucket_sorter[j].top();
51 my_bucket_sorter[j].pop();
52 cout << v << " ";
53 } while (!my_bucket_sorter[j].empty());
54 cout << endl;
55 }
56 else
57 {
58 cout << " has no number associated with it." << endl;
59 }
60 }
61
62 for (std::size_t k = 0; k < N; k++)
63 my_bucket_sorter.push(k);
64
65 my_bucket_sorter.remove(5);
66 my_bucket_sorter.remove(7);
67
68 cout << "After removing numbers 5 and 7, check correctness again." << endl;
69
70 for (j = 0; j < N; j++)
71 {
72 cout << "The bucket " << j;
73 if (!my_bucket_sorter[j].empty())
74 {
75 cout << " has number ";
76 do
77 {
78 int v = my_bucket_sorter[j].top();
79 my_bucket_sorter[j].pop();
80 cout << v << " ";
81 } while (!my_bucket_sorter[j].empty());
82 cout << endl;
83 }
84 else
85 {
86 cout << " has no number associated with it." << endl;
87 }
88 }
89
90 std::size_t iii;
91 for (iii = 0; iii < N; iii++)
92 {
93 std::size_t current = rand() % N;
94 if (!my_bucket_sorter[current].empty())
95 {
96 int v = my_bucket_sorter[current].top();
97 my_bucket_sorter[current].pop();
98 bucket[v] = rand() % N;
99 my_bucket_sorter.push(v);
100 }
101 }
102
103 for (iii = 0; iii < N; iii++)
104 {
105 std::size_t current = rand() % N;
106 if (!my_bucket_sorter[current].empty())
107 {
108 int v = my_bucket_sorter[current].top();
109 bucket[v] = rand() % N;
110 my_bucket_sorter.update(v);
111 }
112 }
113
114 return 0;
115 }
116