/*
Autor: Paweł Marszałek 6SST
Temat: biblioteka stl: opis algorytmów : push_heap pop_heap
*/

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

/* Heap - kopiec, lub jak kto woli, stog, jest struktura danych 
   oparta na drzewie binarnym. Na ogol w strukturze kopca kazdy nastepnik jest
   niewiekszy od swojego poprzednika. (istnieje rowniez mozliwosc stworzenia kopca,
   w ktorym nastepnik jest niemniejszy od poprzednika)
   
   Drzewo binarne, na ktorym opiera się kopiec, jest reprezentowane w postaci tablicy.
   Kopiec sprawia, ze na pierwszej pozycji znajduje sie najwiekszy element 
   (element tablicy o indeksie 0). Kazde nastepne elementy sa indeksowane 
   według reguly:
            jesli rodzic ma index n to jego dzieci maja indeksy 2n+1 i 2n+2
              
   Do korzystania z algorytmow pop_heap i push_heap konieczne jest dodanie pliku
   nagłowkowego <algorithm>. Aby algorytmy te miały sens nalezy wywolac przed ich uzyciem
   algorytm make_heap na odpowiedniej kolekcji danych. Algorytm ten jest opisany w osobnym pliku.
   Uzywanie pop_heap i push_heap na kolekcjach, ktore nie maja charakteru kopca jest bezcelowe.
   
   Uzycie pop_heap sprawia, ze pierwszy element kolekcji w postaci kopca, czyli element najwiekszy,
   zostaje przesuniety na koniec danego zakresu, a struktura kopca pozostaje zachowana 
   dla pozostalych danych.
   Element przesuniety nie jest już elementem kopca, jest gotowy do usuniecia.
   Konstrukcja:
               
   template <class RandomAccessIterator>
            void pop_heap ( RandomAccessIterator first, RandomAccessIterator last );

   template <class RandomAccessIterator, class Compare>
            void pop_heap ( RandomAccessIterator first, RandomAccessIterator last,
                   Compare comp );

   Jak widac sa dwie mozliwosci wywolania algorytmu pop_heap - z dwoma arugmentami 
   lub z trzema. Pierwszy argument, to iterator wskazujacy na poczatek kolekcji danych
   w postaci kopca, wkacznie z elementem do usuniecia. Drugi argument, to iterator 
   wskazujacy na koniec kolekcji. Element usuwany jest umieszczany na pozycji last-1.
   Trzeci, opcjonalny argument, to funkcja, według ktorej okreslony jest porzadek kopca 
   (relacja rozstrzygajaca, ktory element jest "wiekszy").
   Funkcja musi byc postaci:
           bool comp(type a, type b) 
   gdzie type jest typem obiektow przechowywanych w kolekcji. Jezeli trzeci argument
   nie zostanie podany, do porownania uzywany jest operator < .
     
   Algorytm push_heap słuzy do dodawania elementow do struktury danych o charakterze kopca.
   Konstrukcja push_heap jest bardzo podobna do pop_heap:
   
   template <class RandomAccessIterator>
            void push_heap ( RandomAccessIterator first, RandomAccessIterator last );

   template <class RandomAccessIterator, class Compare>
            void push_heap ( RandomAccessIterator first, RandomAccessIterator last,
                   Compare comp );
                  
   Iteratory last i first, podobnie jak poprzednio, wskazuja pewien zakres. Pierwsze elementy
   w tym zakresie powinny byc w postaci kopca, a ostatni element zakresu (pozycja last-1) powinien
   byc elementem, ktory chcemy dodac do kopca. Po wykonaniu algorytmu, element zostanie dodany na
   wlacciwa pozycje tak, aby struktura kopca zostala zachowana. Funkcja comp spelnia te sama role,
   co w algorytmie pop_heap (definiuje w jaki sposob sa porownywane elementy kolekcji) i musi miec
   taka sama postac. Jezeli trzeci argument nie zostanie podany, do porownania uzywany jest 
   operator < .            
*/

struct Chlopiec{
                char* imie;
                int wzrost;
};

void drukuj(Chlopiec chlopak){
     cout<<chlopak.imie<<"("<<chlopak.wzrost<<"), ";     
}

bool comp(struct Chlopiec chlopiec_a, struct Chlopiec chlopiec_b){
     return chlopiec_a.wzrost<chlopiec_b.wzrost;
}

int main(){
    
    int liczby[]={1,5,23,17,8,99};
    vector<int> wektor(liczby, liczby+6);
    
    cout<<"Poczatkowa zawartosc wektora: "<<endl;
    for(int i=0;i<wektor.size();i++)
            cout<<wektor[i]<<" ";
    // 1 5 23 17 8 99    
    getchar();    
    cout<<endl<<endl;
    
    cout<<"Wektor po uzyciu funkcji make_heap: "<<endl;
    make_heap(wektor.begin(),wektor.end());  
    for(int i=0;i<wektor.size();i++)
            cout<<wektor[i]<<" ";
    // 99 17 23 5 8 1
    getchar();
    cout<<endl<<endl;
                  
    cout<<"Wektor po uzyciu funkcji pop_heap"<<endl;
    pop_heap(wektor.begin(),wektor.end());
    for(int i=0;i<wektor.size();i++)
            cout<<wektor[i]<<" ";
    //23 17 1 5 8 99
    cout<<endl;
    cout<<"Element najwiekszy zostal przesuniety na koniec wektora,"<<endl;
    cout<<"skad mozna go latwo usunac."<<endl;
    cout<<"Element przesuniety nie jest juz w kopcu."<<endl;
    cout<<"Pozostale dane sa w strukturze kopca."<<endl<<endl;
    
    cout<<"Wektor po usunieciu przesunietgo elementu ( uzycie pop_back() ):"<<endl;
    wektor.pop_back();
    for(int i=0;i<wektor.size();i++)
            cout<<wektor[i]<<" ";
    //23 17 1 5 8
    getchar();
    
    cout<<endl<<endl;              
    cout<<"Teraz bedziemy dodawac element do kopca. Niech to bedzie liczba 80."<<endl;
    cout<<"Aby to zrobic, musimy umiescic te liczbe na koncu wektora ( uzycie push_back() )."<<endl;
    cout<<"Wektor ma teraz postac:"<<endl;
    wektor.push_back(80);
    for(int i=0;i<wektor.size();i++)
            cout<<wektor[i]<<" ";
    //23 17 1 5 8 80    
    getchar();    
    
    cout<<endl<<endl;   
    cout<<"Wektor po uzyciu funkcji push_heap"<<endl;
    push_heap(wektor.begin(),wektor.end());
    for(int i=0;i<wektor.size();i++)
            cout<<wektor[i]<<" ";
    //80 17 23 5 8 1
    getchar();
    
    cout<<endl<<endl;    
    cout<<"Dodajmy w podobny sposob liczbe 9."<<endl;
    wektor.push_back(9);
    push_heap(wektor.begin(),wektor.end());
    cout<<"Po dodaniu do kopca wektor ma postac:"<<endl;
    for(int i=0;i<wektor.size();i++)
            cout<<wektor[i]<<" ";
    //80 17 23 5 8 1 9
    getchar();
    
    cout<<endl<<endl;
    cout<<"A teraz stworzymy wektor, ktory bedzie przechowywal informacje o grupie chlopcow."<<endl;
    vector<Chlopiec> chlopaki;
    Chlopiec Alojzy={"Alojzy",182};
    Chlopiec Bonifacy={"Bonifacy",172};
    Chlopiec Pankracy={"Pankracy",195};
    Chlopiec Kajtek={"Kajtek",165};
    Chlopiec Florian={"Florian",198};
    chlopaki.push_back(Alojzy);
    chlopaki.push_back(Bonifacy);
    chlopaki.push_back(Pankracy);
    chlopaki.push_back(Kajtek);
    chlopaki.push_back(Florian);
    for(int i=0;i<chlopaki.size();i++)
            drukuj(chlopaki[i]);
    //Alojzy(182), Bonifacy(172), Pankracy(195), Kajtek(165), Florian(198),    
    getchar();
        
    cout<<endl<<endl;
    cout<<"Wywolujemy funkcje make_heap z trzema argumentami."<<endl;
    cout<<"Za pomoca funkcji comp porownujmy wzrost chlopcow aby ustawic ich w kopcu"<<endl;
    make_heap(chlopaki.begin(),chlopaki.end(),comp);
    cout<<"Wektor wyglada teraz tak:"<<endl;
    for(int i=0;i<chlopaki.size();i++)
            drukuj(chlopaki[i]);
    //Florian(198), Alojzy(182), Pankracy(195), Kajtek(165), Bonifacy(172),
    getchar();
    
    cout<<endl<<endl;
    cout<<"Uzyjemy teraz trojargumentowej funkcji pop_heap do zdjecia najwyzszego chlopca.";
    pop_heap(chlopaki.begin(),chlopaki.end(),comp);
    chlopaki.pop_back();
    cout<<"Wektor wyglada teraz tak:"<<endl;
    for(int i=0;i<chlopaki.size();i++)
            drukuj(chlopaki[i]);
    //Pankracy(195), Alojzy(182), Bonifacy(172), Kajtek(165),
    getchar();
    
    cout<<endl<<endl;
    cout<<"A teraz dodamy go z powrotem za pomoca trojargumentowego push_heap"<<endl;
    chlopaki.push_back(Florian);
    push_heap(chlopaki.begin(),chlopaki.end(),comp);
    cout<<"Wektor wyglada teraz tak:"<<endl;
    for(int i=0;i<chlopaki.size();i++)
            drukuj(chlopaki[i]);
    //Florian(198), Pankracy(195), Bonifacy(172), Kajtek(165), Alojzy(182),
    getchar();
    
    return 0;   
}