/*
 *  merge.cpp
 *  Author: Rafal Surowiecki I1ISI
 *  Praca domowa : ZPR 2008/2009Z
 */

/*
 * Algorytm merge scala elementy dwoch posortowanych ciagow w jeden posortowany.
 * Wartosci porownywane sa operatorem ">" lub funkcja podana jako argument.
 *
 */

/*
 * template <class InputIterator1, class InputIterator2, class OutputIterator>
 *   OutputIterator merge ( InputIterator1 first1, InputIterator1 last1,
 *                            InputIterator2 first2, InputIterator2 last2,
 *                                                     OutputIterator result );
 *
 * template <class InputIterator1, class InputIterator2,
 *           class OutputIterator, class Compare>
 *             OutputIterator merge ( InputIterator1 first1, InputIterator1 last1,
 *                                      InputIterator2 first2, InputIterator2 last2,
 *                                      OutputIterator result, Compare comp );
 */


#include <iostream>
#include <algorithm> //biblioteka w ktorej znajduje sie std::merge
#include <vector>
using namespace std;

/*
 * Algorytm merge moze być wykorzystany do implementacji algorytmu merge sort;
 */
void merge_sort(int* base, unsigned length) {

	if (length == 1)
		return;
	else {
		unsigned centre = length / 2;
		merge_sort(base, centre);
		merge_sort(base + centre, length - centre);
		int* tab = new int[length];
		merge(base, base + centre, base + centre, base + length , tab);
		for (unsigned i = 0; i < length; i++)
			*(base + i) = tab[i];
		delete[] tab;

	}

}


//funkcja pomocnicza do wyswietlania zawartosci kontenerow
template<class Iterator> void print(Iterator it, unsigned ile) {
	for (unsigned i = 0; i < ile; i++) {
		cout << *it << " ";
		it++;
	}

	cout << endl;
}
/*
 * Funkcja do porownywania intow.
 */
bool cmp(int a, int b) {
	return a < b ? false : true;
}

int main() {
	//Dane wejsciowe - dwa posortowane kontenery
	int a[] = { 1, 3, 5, 7, 9 };
	int b[] = { 2, 4, 6, 8, 8 };
	cout << "Dane wejsciowe I:" << endl;
	print(a, 5);
	print(b, 5);
	//Miejsce na dane wyjsciowe
	vector<int> wynik(10);
	vector<int>::iterator it;
	/*
	 * Wywolanie funkcji merge z parametrami:
	 * a 	- iterator wskazujacy pierwszy element 1 kolekcji
	 * a+5 	- iterator wskazujacy miejsce za ostatnim elementem 1 kolekcji
	 * b 	- iterator wskazujacy pierwszy element 2 kolekcji
	 * b+5 	- iterator wskazujacy miejsce za ostatnim elementem 1 kolekcji
	 * wynik.begin()	- wskazuje poczatek kolekcji do ktorej ma zostać zapisany wynik funkcji.
	 */
	merge(a, a + 5, b, b + 5, wynik.begin());

	cout << "Wynik I:" << endl;
	print(wynik.begin(), wynik.size());
	//sortuje ciagi malejaco
	sort(a, a + 5, cmp);
	sort(b, b + 5, cmp);
	//wyswietlam dane wejsciowe
	cout << "Dane wejsciowe II:" << endl;
	print(a, 5);
	print(b, 5);

	/*
	 * Wywolanie funkcji merge z parametrami:
	 * a 	- iterator wskazujacy pierwszy element 1 kolekcji
	 * a+5 	- iterator wskazujacy miejsce za ostatnim elementem 1 kolekcji
	 * b 	- iterator wskazujacy pierwszy element 2 kolekcji
	 * b+5 	- iterator wskazujacy miejsce za ostatnim elementem 1 kolekcji
	 * wynik.begin()	- wskazuje poczatek kolekcji do ktorej ma zostać zapisany wynik funkcji.
	 * cmp	- wskaźnik na funkcje porownujaca.
	 */
	merge(a, a + 5, b, b + 5, wynik.begin(), cmp);

	//wyswietlam dane wyjsciowe
	cout << "Wynik II: " << endl;
	print(wynik.begin(), wynik.size());

	cout << "Przyklad wykorzystania - > merge sort: " << endl;
	int c[] = { 1, 21, 66, 43, 63, 82, 223, 44, 65, 86 };
	//wypisuje dane do posortowania
	print(c, 10);
	//sortuje merge_sortem
	merge_sort(c, 10);
	//wypisuje wynik
	print(c, 10);
	cout << endl;

	return 0;
}