home *** CD-ROM | disk | FTP | other *** search
/ Reverse Code Engineering RCE CD +sandman 2000 / ReverseCodeEngineeringRceCdsandman2000.iso / RCE / Ebooks / Thinking in C++ V2 / C20 / PriorityQueue6.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2000-05-25  |  1.6 KB  |  74 lines
  1. //: C20:PriorityQueue6.cpp
  2. // From Thinking in C++, 2nd Edition
  3. // Available at http://www.BruceEckel.com
  4. // (c) Bruce Eckel 1999
  5. // Copyright notice in Copyright.txt
  6. #include <iostream>
  7. #include <queue>
  8. #include <algorithm>
  9. #include <cstdlib>
  10. #include <ctime>
  11. using namespace std;
  12.  
  13. template<class T, class Compare>
  14. class PQV : public vector<T> {
  15.   Compare comp;
  16.   bool sorted;
  17.   void assureHeap() {
  18.     if(sorted) {
  19.       // Turn it back into a heap:
  20.       make_heap(begin(), end(), comp);
  21.       sorted = false;
  22.     }
  23.   }    
  24. public:
  25.   PQV(Compare cmp = Compare()) : comp(cmp) {
  26.     make_heap(begin(), end(), comp);
  27.     sorted = false;
  28.   }
  29.   const T& top() {
  30.     assureHeap();
  31.     return front(); 
  32.   }
  33.   void push(const T& x) {
  34.     assureHeap();
  35.     // Put it at the end:
  36.     push_back(x);
  37.     // Re-adjust the heap:
  38.     push_heap(begin(), end(), comp);
  39.   }
  40.   void pop() {
  41.     assureHeap();
  42.     // Move the top element to the last position:
  43.     pop_heap(begin(), end(), comp);
  44.     // Remove that element:
  45.     pop_back();
  46.   }
  47.   void sort() {
  48.     if(!sorted) {
  49.       sort_heap(begin(), end(), comp);
  50.       reverse(begin(), end());
  51.       sorted = true;
  52.     }
  53.   }
  54. };
  55.  
  56. int main() {
  57.   PQV<int, less<int> > pqi;
  58.   srand(time(0));
  59.   for(int i = 0; i < 100; i++) {
  60.     pqi.push(rand() % 25);
  61.     copy(pqi.begin(), pqi.end(),
  62.       ostream_iterator<int>(cout, " "));
  63.     cout << "\n-----\n";
  64.   }
  65.   pqi.sort();
  66.   copy(pqi.begin(), pqi.end(),
  67.     ostream_iterator<int>(cout, " "));
  68.   cout << "\n-----\n";
  69.   while(!pqi.empty()) {
  70.     cout << pqi.top() << ' ';
  71.     pqi.pop();
  72.   }
  73. } ///:~
  74.