/****************************************/
/*	Autor: Wiktor Jóźwicki     		    */
/*	Mail: wjozwick@stud.elka.pw.edu.pl  */			
/*	Temat: biblioteka stl,	       	    */
/*	algorytmy	inplace merge    		*/
/****************************************/

/*
template <class BidirectionalIterator>
inline void inplace_merge(BidirectionalIterator first,
                          BidirectionalIterator middle,
                          BidirectionalIterator last);

template <class BidirectionalIterator, class StrictWeakOrdering>
inline void inplace_merge(BidirectionalIterator first,
                          BidirectionalIterator middle,
                          BidirectionalIterator last, StrictWeakOrdering comp);
                          
	-- Parametry --
	* first - iterator wskazujący początek pierwszego zakresu
	* middle - iterator wskazujący koniec pierwszego zakresu i jednocześnie początek drugiego zakresu
	* last - iterator wskazujący koniec drugiego zakresu
	* comp - argument opcjonalny, wskaźnik na funkcję testującą poprzedzanie drugiego obiektu przez pierwszy
	
    Algorytm zawarty w Standard Template Library. Funkcja inplace_merge() łączy dwa uporządkowane rosnąco zakresy 
    [first, middle) oraz [middle, last) w jeden zakres [first, last) uporządkowany rosnąco. Algorytm jest stabilny.
    W pierwszej wersji funkcji do porównywania elementów używany jest operator<. W drugiej wersji możliwe jest dostarczenie
    własnego funktora testującego poprzedzanie elementów. Funkcja testująca pobiera 2 argumenty i zwraca wartość logiczną
    TRUE w przypadku, gdy pierwszy argument poprzedza drugi; jeśli zamienimy argumenty miejscami otrzymamy FALSE.
    
    Złożoność pesymistyczna algorytmu to O(N log(N)).
    
*/

#include <algorithm>
#include <list>
#include <functional>
#include <iostream>

/**
 * Funkcja testująca podzielność drugiego argumentu przez pierwszy
 * Zwraca TRUE w przypadku gdy drugi argument jest podzielny przez pierwszy, w przeciwnym wypadku FALSE
 */
const bool divisible(const int &arg1, const int &arg2)
{
    return !(arg2 % arg1);
}



int main(){
    
    /**
     * Inicjalizacja struktur danych do demonstracji działania algorytmu
     */
    std::list<int> container, containerDesc, containerDivis;
    std::list<int>::iterator it;
    
    container.push_back(13);        containerDesc.push_back(13);        containerDivis.push_back(2);        
    container.push_back(15);        containerDesc.push_back(11);        containerDivis.push_back(8);
    container.push_back(17);        containerDesc.push_back(9);         containerDivis.push_back(32);
    container.push_back(19);        containerDesc.push_back(7);         containerDivis.push_back(128);
    
    container.push_back(8);         containerDesc.push_back(20);        containerDivis.push_back(1);
    container.push_back(10);        containerDesc.push_back(12);        containerDivis.push_back(4);
    container.push_back(14);        containerDesc.push_back(8);         containerDivis.push_back(16);
    container.push_back(18);        containerDesc.push_back(5);         containerDivis.push_back(64);
    container.push_back(28);        containerDesc.push_back(0);         containerDivis.push_back(1024);
    
    /**
     * 1. Wypisanie początkowej zawartości container na wyjście
     */
    std::cout << "1. poczatkowa zawartosc container'a to:" << std::endl;
    for(it = container.begin(); it != container.end(); ++it)
             std::cout << *it << " ";
    std::cout << std::endl <<std::endl;
    
    /**
     * 2. Próba użycia algorytmu przy niespełnionym warunku uporządkowania jednego z zakresów
     * zakres pierwszy:       13, 15, 17
     * zakres drugi:          19, 8, 10, 14, 18, 28
     * Na wyjściu otrzymamy niepożądaną kolejność elementów (w tym przypadku niezmienioną)
     */
    std::inplace_merge(container.begin(), ++(++(++container.begin())), container.end());
    
    std::cout << "2. wynik dzialania funkcji przy braku uporzadkowania rosnacego:" << std::endl;
    for(it = container.begin(); it != container.end(); ++it)
             std::cout << *it << " ";
    std::cout << std::endl <<std::endl;
    
    
    /**
     * 3. Najprostsze użycie algorytmu inplace_merge tworzące jeden rosnąco
     * posortowany zakres z dwóch oddzielnie uporządkowanych
     * zakres pierwszy:       13, 15, 17, 19
     * zakres drugi:          8, 10, 14, 18, 28
     */
    std::inplace_merge(container.begin(), ++(++(++(++container.begin()))), container.end());
    
    std::cout << "3. zawartosc container'a po wykonaniu inplace_merge to:" << std::endl;
    for(it = container.begin(); it != container.end(); ++it)
             std::cout << *it << " ";
    std::cout << std::endl <<std::endl;
    
    /**
     * 4. Wypisanie początkowej zawartości containerDesc na wyjście
     */
    std::cout << "4. poczatkowa zawartosc containerDesc'a to:" << std::endl;
    for(it = containerDesc.begin(); it != containerDesc.end(); ++it)
             std::cout << *it << " ";
    std::cout << std::endl <<std::endl;
    
    /**
     * 5. Wykorzystanie opcjonalnego argumentu funkcji inplace_merge()
     * Tym razem załóżmy że chcemy uzyskać uporządkowanie malejące z dwóch malejących zakresów
     * Do tego celu posłużę się funktorem greater<T> (nagłówek: #include <functional>)
     * zakres pierwszy:       13, 11, 9, 7
     * zakres drugi:          20, 12, 8, 5, 0    
     */
    std::inplace_merge(containerDesc.begin(), ++(++(++(++containerDesc.begin()))), containerDesc.end(), std::greater<int>());
    
    std::cout << "5. zawartosc containerDesc'a po wykonaniu inplace_merge z odwroconym uporzadkowaniem to:" << std::endl;
    for(it = containerDesc.begin(); it != containerDesc.end(); ++it)
             std::cout << *it << " ";
    std::cout << std::endl <<std::endl;
    
    /**
     * 6. Wypisanie początkowej zawartości containerDivis na wyjście
     */
    std::cout << "6. poczatkowa zawartosc containerDivis'a to:" << std::endl;
    for(it = containerDivis.begin(); it != containerDivis.end(); ++it)
             std::cout << *it << " ";
    std::cout << std::endl <<std::endl;
    
    /**
     * 7. Wykorzystanie opcjonalnego argumentu funkcji inplace_merge()
     * Tym razem utworzyłem funkcję bool divisible(int, int), która zwraca TRUE w przypadku gdy
     * drugi argument jest podzielny przez pierwszy, w przeciwnym wypadku FALSE
     * funkcja zostanie wykorzystana przez inplace_merge
     * zakres pierwszy:       2, 8, 32, 128
     * zakres drugi:          1, 4, 16, 64, 1024
     */
    std::inplace_merge(containerDivis.begin(), ++(++(++(++containerDivis.begin()))), containerDivis.end(), divisible);
    
    std::cout << "7. zawartosc containerDivis'a po wykonaniu inplace_merge z dostarczona funkcja divisible:" << std::endl;
    for(it = containerDivis.begin(); it != containerDivis.end(); ++it)
             std::cout << *it << " ";
    std::cout << std::endl <<std::endl;

    return 0;    
}