1 /***************************************************************************
2  *  examples/containers/pqueue2.cpp
3  *
4  *  Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  *  Copyright (C) 2013 Daniel Feist <daniel.feist@student.kit.edu>
7  *
8  *  Distributed under the Boost Software License, Version 1.0.
9  *  (See accompanying file LICENSE_1_0.txt or copy at
10  *  http://www.boost.org/LICENSE_1_0.txt)
11  **************************************************************************/
12 
13 #include <stxxl/priority_queue>
14 #include <limits>
15 
16 // comparison struct for priority queue where top() returns the biggest contained value:
17 struct Cmp
18 {
operator ()Cmp19     bool operator () (const int& a, const int& b) const
20     { return a < b; }
21 
min_valueCmp22     int min_value() const
23     { return std::numeric_limits<int>::min(); }
24 };
25 
main()26 int main()
27 {
28     // use 64 GiB on main memory and 1 billion items at most
29     typedef stxxl::PRIORITY_QUEUE_GENERATOR<int, Cmp, 64*1024*1024, 1024*1024>::result pq_type;
30     typedef pq_type::block_type block_type;
31 
32     // block_type::raw_size = 262144 bytes
33     // use 64 block read and write pools each to enable overlapping between I/O and computation
34     const unsigned int mem_for_pools = 32 * 1024 * 1024;
35     stxxl::read_write_pool<block_type> pool((mem_for_pools / 2) / block_type::raw_size, (mem_for_pools / 2) / block_type::raw_size);
36 
37     pq_type Q(pool);
38 
39     Q.push(1);
40     Q.push(4);
41     Q.push(2);
42     Q.push(8);
43     Q.push(5);
44     Q.push(7);
45 
46     assert(Q.size() == 6);
47 
48     assert(Q.top() == 8);
49     Q.pop();
50 
51     assert(Q.top() == 7);
52     Q.pop();
53 
54     assert(Q.top() == 5);
55     Q.pop();
56 
57     assert(Q.top() == 4);
58     Q.pop();
59 
60     assert(Q.top() == 2);
61     Q.pop();
62 
63     assert(Q.top() == 1);
64     Q.pop();
65 
66     assert(Q.empty());
67 
68     return 0;
69 }
70