//: C07:PriorityQueue6.cpp
// Z knihy "Myslíme v jazyce C++, část 2" od Bruce Eckela a Chucka Allisona.
// (c) 1995-2004 MindView, Inc. Všechna práva vyhrazena.
// Přečtěte si podmínky používání zdrojových kódů umístěné v souboru 
// 'Licence.txt' dodávaném spolu s balíčkem kódu dostupným na www.MindView.net.
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <queue>
using namespace std;

template<class T, class Compare>
class PQV : public vector<T> {
  Compare comp;
  bool setrideno;
  void zajistitHromadu() {
    if(setrideno) {
      // Převést ji zpět na hromadu:
      make_heap(this->begin(),this->end(), comp);
      setrideno = false;
    }
  }
public:
  PQV(Compare cmp = Compare()) : comp(cmp) {
    make_heap(this->begin(),this->end(), comp);
    setrideno = false;
  }
  const T& top() {
    zajistitHromadu();
    return this->front();
  }
  void push(const T& x) {
    zajistitHromadu();
    this->push_back(x); // vložit to nakonec
    // Přenastavit hromadu:
    push_heap(this->begin(),this->end(), comp);
  }
  void pop() {
    zajistitHromadu();
    // Přesunout nejvyšší prvek na poslední pozici
    pop_heap(this->begin(),this->end(), comp);
    this->pop_back();// Odstranit tento prvek
  }
  void sort() {
    if(!setrideno) {
      sort_heap(this->begin(),this->end(), comp);
      reverse(this->begin(),this->end());
      setrideno = true;
    }
  }
};

int main() {
  PQV< int, less<int> > pqi;
  srand(time(0));
  for(int i = 0; i < 100; i++) {
    pqi.push(rand() % 25);
    copy(pqi.begin(), pqi.end(),
      ostream_iterator<int>(cout, " "));
    cout << "\n-----" << endl;
  }
  pqi.sort();
  copy(pqi.begin(), pqi.end(),
    ostream_iterator<int>(cout, " "));
  cout << "\n-----" << endl;
  while(!pqi.empty()) {
    cout << pqi.top() << ' ';
    pqi.pop();
  }
} ///:~
