ceph/src/boost/libs/heap/examples/interface.cpp

   1 /*=============================================================================
   2     Copyright (c) 2010 Tim Blechmann
   3
   4     Use, modification and distribution is subject to the Boost Software
   5     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6     http://www.boost.org/LICENSE_1_0.txt)
   7 =============================================================================*/
   8
   9 #include <iostream>
  10 #include <iomanip>
  11
  12 #include "../../../boost/heap/fibonacci_heap.hpp"
  13
  14 using std::cout;
  15 using std::endl;
  16 using namespace boost::heap;
  17
  18 //[ basic_interface
  19 // PriorityQueue is expected to be a max-heap of integer values
  20 template <typename PriorityQueue>
  21 void basic_interface(void)
  22 {
  23     PriorityQueue pq;
  24
  25     pq.push(2);
  26     pq.push(3);
  27     pq.push(1);
  28
  29     cout << "Priority Queue: popped elements" << endl;
  30     cout << pq.top() << " "; // 3
  31     pq.pop();
  32     cout << pq.top() << " "; // 2
  33     pq.pop();
  34     cout << pq.top() << " "; // 1
  35     pq.pop();
  36     cout << endl;
  37 }
  38 //]
  39
  40 //[ iterator_interface
  41 // PriorityQueue is expected to be a max-heap of integer values
  42 template <typename PriorityQueue>
  43 void iterator_interface(void)
  44 {
  45     PriorityQueue pq;
  46
  47     pq.push(2);
  48     pq.push(3);
  49     pq.push(1);
  50
  51     typename PriorityQueue::iterator begin = pq.begin();
  52     typename PriorityQueue::iterator end = pq.end();
  53
  54     cout << "Priority Queue: iteration" << endl;
  55     for (typename PriorityQueue::iterator it = begin; it != end; ++it)
  56         cout << *it << " "; // 1, 2, 3 in unspecified order
  57     cout << endl;
  58 }
  59 //]
  60
  61 //[ ordered_iterator_interface
  62 // PriorityQueue is expected to be a max-heap of integer values
  63 template <typename PriorityQueue>
  64 void ordered_iterator_interface(void)
  65 {
  66     PriorityQueue pq;
  67
  68     pq.push(2);
  69     pq.push(3);
  70     pq.push(1);
  71
  72     typename PriorityQueue::ordered_iterator begin = pq.ordered_begin();
  73     typename PriorityQueue::ordered_iterator end = pq.ordered_end();
  74
  75     cout << "Priority Queue: ordered iteration" << endl;
  76     for (typename PriorityQueue::ordered_iterator it = begin; it != end; ++it)
  77         cout << *it << " "; // 3, 2, 1 (i.e. 1, 2, 3 in heap order)
  78     cout << endl;
  79 }
  80 //]
  81
  82
  83 //[ merge_interface
  84 // PriorityQueue is expected to be a max-heap of integer values
  85 template <typename PriorityQueue>
  86 void merge_interface(void)
  87 {
  88     PriorityQueue pq;
  89
  90     pq.push(3);
  91     pq.push(5);
  92     pq.push(1);
  93
  94     PriorityQueue pq2;
  95
  96     pq2.push(2);
  97     pq2.push(4);
  98     pq2.push(0);
  99
 100     pq.merge(pq2);
 101
 102     cout << "Priority Queue: merge" << endl;
 103     cout << "first queue: ";
 104     while (!pq.empty()) {
 105         cout << pq.top() << " "; // 5 4 3 2 1 0
 106         pq.pop();
 107     }
 108     cout << endl;
 109
 110     cout << "second queue: ";
 111     while (!pq2.empty()) {
 112         cout << pq2.top() << " "; // 4 2 0
 113         pq2.pop();
 114     }
 115     cout << endl;
 116 }
 117 //]
 118
 119 //[ heap_merge_algorithm
 120 // PriorityQueue is expected to be a max-heap of integer values
 121 template <typename PriorityQueue>
 122 void heap_merge_algorithm(void)
 123 {
 124     PriorityQueue pq;
 125
 126     pq.push(3);
 127     pq.push(5);
 128     pq.push(1);
 129
 130     PriorityQueue pq2;
 131
 132     pq2.push(2);
 133     pq2.push(4);
 134     pq2.push(0);
 135
 136     boost::heap::heap_merge(pq, pq2);
 137
 138     cout << "Priority Queue: merge" << endl;
 139     cout << "first queue: ";
 140     while (!pq.empty()) {
 141         cout << pq.top() << " "; // 5 4 3 2 1 0
 142         pq.pop();
 143     }
 144     cout << endl;
 145
 146     cout << "second queue: ";
 147     while (!pq2.empty()) {
 148         cout << pq2.top() << " "; // 4 2 0
 149         pq2.pop();
 150     }
 151     cout << endl;
 152 }
 153 //]
 154
 155 //[ mutable_interface
 156 // PriorityQueue is expected to be a max-heap of integer values
 157 template <typename PriorityQueue>
 158 void mutable_interface(void)
 159 {
 160     PriorityQueue pq;
 161     typedef typename PriorityQueue::handle_type handle_t;
 162
 163     handle_t t3 = pq.push(3);
 164     handle_t t5 = pq.push(5);
 165     handle_t t1 = pq.push(1);
 166
 167     pq.update(t3, 4);
 168     pq.increase(t5, 7);
 169     pq.decrease(t1, 0);
 170
 171     cout << "Priority Queue: update" << endl;
 172     while (!pq.empty()) {
 173         cout << pq.top() << " "; // 7, 4, 0
 174         pq.pop();
 175     }
 176     cout << endl;
 177 }
 178 //]
 179
 180 //[ mutable_fixup_interface
 181 // PriorityQueue is expected to be a max-heap of integer values
 182 template <typename PriorityQueue>
 183 void mutable_fixup_interface(void)
 184 {
 185     PriorityQueue pq;
 186     typedef typename PriorityQueue::handle_type handle_t;
 187
 188     handle_t t3 = pq.push(3);
 189     handle_t t5 = pq.push(5);
 190     handle_t t1 = pq.push(1);
 191
 192     *t3 = 4;
 193     pq.update(t3);
 194
 195     *t5 = 7;
 196     pq.increase(t5);
 197
 198     *t1 = 0;
 199     pq.decrease(t1);
 200
 201     cout << "Priority Queue: update with fixup" << endl;
 202     while (!pq.empty()) {
 203         cout << pq.top() << " "; // 7, 4, 0
 204         pq.pop();
 205     }
 206     cout << endl;
 207 }
 208 //]
 209
 210 //[ mutable_interface_handle_in_value
 211 struct heap_data
 212 {
 213     fibonacci_heap<heap_data>::handle_type handle;
 214     int payload;
 215
 216     heap_data(int i):
 217         payload(i)
 218     {}
 219
 220     bool operator<(heap_data const & rhs) const
 221     {
 222         return payload < rhs.payload;
 223     }
 224 };
 225
 226 void mutable_interface_handle_in_value(void)
 227 {
 228     fibonacci_heap<heap_data> heap;
 229     heap_data f(2);
 230
 231     fibonacci_heap<heap_data>::handle_type handle = heap.push(f);
 232     (*handle).handle = handle; // store handle in node
 233 }
 234 //]
 235
 236
 237 int main(void)
 238 {
 239     using boost::heap::fibonacci_heap;
 240
 241     cout << std::setw(2);
 242
 243     basic_interface<fibonacci_heap<int> >();
 244     cout << endl;
 245
 246     iterator_interface<fibonacci_heap<int> >();
 247     cout << endl;
 248
 249     ordered_iterator_interface<fibonacci_heap<int> >();
 250     cout << endl;
 251
 252     merge_interface<fibonacci_heap<int> >();
 253     cout << endl;
 254
 255     mutable_interface<fibonacci_heap<int> >();
 256     cout << endl;
 257
 258     mutable_fixup_interface<fibonacci_heap<int> >();
 259
 260     mutable_interface_handle_in_value();
 261 }