//: C07:PriorityQueue7.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.
// Prioritní fronta která vám předá vektor
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <queue>
#include <vector>
using namespace std;

template<class T, class Compare> class PQV {
  vector<T> v;
  Compare comp;
public:
  // nepotřebujete volat make_heap(); je prázdná:
  PQV(Compare cmp = Compare()) : comp(cmp) {}
  void push(const T& x) {
    v.push_back(x); // vložit na konec
    // Přenastavit hromadu:
    push_heap(v.begin(), v.end(), comp);
  }
  void pop() {
  	// Přesunout vrchní prvek na poslední pozici:
    pop_heap(v.begin(), v.end(), comp);
    v.pop_back(); // Odstranit ten prvek
  }
  const T& top() { return v.front(); }
  bool empty() const { return v.empty(); }
  int size() const { return v.size(); }
  typedef vector<T> TVec;
  TVec getVector() {
    TVec r(v.begin(), v.end());
    // Již je to hromada
    sort_heap(r.begin(), r.end(), comp);
    // Uspořádat v pořadí prioritní fronty: 
    reverse(r.begin(), r.end());
    return r;
  }
};

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