/* Autor: Andrzej Żukowski Grupa: I1ISI									*
 * 																		*
 * Temat: Kolejka priorytetowa											*
 * 																		*
 * 																		*/

/* Priority queue znajduje się w <queue>, a więc należy je dołączyć 	*/
#include<queue>
#include<iostream>
#include<map>
#include<set>

using namespace std;



/* Typ danych służący pokazaniu działania kolejnki na własnym type		*/
	class OwnType {
	public:
		string s_;
		int i_;
		OwnType(string s, int i):s_(s), i_(i) {}
		/* Należy przeciążyć opeartor < lub operatora > wzależności od 	*
		 * tego którego będziemy używać do porównywania	*/
		bool operator<(const OwnType compare) const{
			return i_<compare.i_;
		}
		bool operator>(const OwnType compare) const{
							return i_>compare.i_;
		}


	};


	/* Klasa porównująca dwie liczby int na podstawie ich ostatnich cyfr*/
	class Compare{
		public:
			/* Funkcja zwraca true, jeżeli a ma mniejszy priorytet niż b*/
			bool operator()(int a, int b) const {
				return a%10<b%10;
			}
	};


int main() {

	/* Kolejka jest kontenerem w postaci szablonu, należy więc 			*
	 * poprawnie ją skonkretyzować. 									*/
	priority_queue<int> pq;

	/* Wstawianie do kolejki - operacja push()							*/
	pq.push(12);
	pq.push(13);
	pq.push(9);
	pq.push(16);
	pq.push(11);
	pq.push(10);

	/* Czytanie elementu z kolejki - top()								*
	 * Usuwanie pierwszego elementu z kolejki - pop()					*
	 * Sprawdzanie czy kolejka jest pusta - push()						*
	 * Sprawdzanie wielkosci kolejki - size()							*
	 * Sprawdzenie czy kolejka jest pusta								*/
	cout<<"Test 1:"<<endl;

	while(!pq.empty()){
		cout<<"Liczba elementów: "<<pq.size()<<" Pierwszy element: "<<pq.top()<<endl;
		pq.pop();
	}

	/*Istnieje możliwość tworzenia kolejki z istniejącego już kontenera		*/
		vector<string> v;
		//dodanie elementów do kontenera
		v.push_back("trasa");
		v.push_back("dom");
		v.push_back("zamek");

	/* W tym celu należy jako agumenty konstruktora podać iterator na pierwszy
	 * element w kontenerze i na element za ostatnim który chcemy dodać		*
	 * W tym przykładzie pierwszy i drugi element							*/

		vector<string>::iterator i;
		i=v.begin();
		++i;
		++i;

	/* Kolejka priorytetowa domyślnie jest implementowana na std::vector	*
	 * można jednak zmienić implementację na dowolną klasę typu		 		*
	 *  Random Access Container np. deque									*/

		priority_queue<string, deque<string> > pqDeque(v.begin(), i);
		cout<<endl<<endl<<"Test 2: "<<endl;
		while(!pqDeque.empty()){
				cout<<"Liczba elementów: "<<pqDeque.size()<<" Pierwszy element: "<<pqDeque.top()<<endl;
				pqDeque.pop();
			}

	/* Domyślnie obiekty są porównywane za pomocą operatora < (obiekty < 	*
	 * mają niższy piorytet. Można to jednak zmienić zmieniając funkcję 	*
	 * porównującą na greater wtedy używany jest operator > i obiekty > 	*
	 * mają priorytet niższy.												*/

		priority_queue<string, vector<string>, greater<string> > priorityQueGreater;

	/* Można także do kolejki dostarczyć własnej funkcji porównującej		*/

		priority_queue<int, vector<int>, Compare > ownCompare;

		ownCompare.push(10);
		ownCompare.push(18);
		ownCompare.push(9);
		ownCompare.push(2);
		cout<<endl<<endl<<"Test 3: "<<endl;
		while(!ownCompare.empty()){
				cout<<"Liczba elementów: "<<ownCompare.size()<<" Pierwszy element: "<<ownCompare.top()<<endl;
				ownCompare.pop();
			}

	/* W kolejce można używać własnych typów								*/

	/* Wykorzystanie przeciążonego operatora < 								*/
			priority_queue<OwnType> ownType;


			OwnType zak("WSWN", 200);
			OwnType ucz("UW", 30000);
			OwnType ins("PJWSTK",1000);
			OwnType wydz("PW", 15000);
			ownType.push(zak);
			ownType.push(ins);
			ownType.push(wydz);
			ownType.push(ucz);
			cout<<endl<<endl<<"Test 4: "<<endl;
			while(!ownType.empty()){
					cout<<"Liczba elementów: "<<ownType.size()<<endl;
					cout<<"Uczelnia: "<<ownType.top().s_<<" liczba studentow: "<<ownType.top().i_<<endl;
					ownType.pop();
				}

	/* Wykorzystanie przeciążonego operatora >								*/
			priority_queue<OwnType, vector<OwnType>, greater<OwnType> > ownTypeGreater;

}