/**
 * Marcin Korniluk, I1ISI
 * praca domowa ZPR: std::set_union
 *
 * Algorytm set_union służy do konstruowania sumy dwóch zbiorów posortowanych.
 *
 * template <class InputIterator1, class InputIterator2, class OutputIterator>
 * OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
 *							InputIterator2 first2, InputIterator2 last2,
 *							OutputIterator result);
 *
 * template <class InputIterator1, class InputIterator2, class OutputIterator, class StrictWeakOrdering>
 * OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
 *							InputIterator2 first2, InputIterator2 last2,
 *							OutputIterator result, StrictWeakOrdering comp);
 *
 * Dla pierwszego sposobu wywołania do porównywania elementów służy operator <, dla drugiego podana
 * przez użytkownika funkcja. Jeśli element A pojawia się w zbiorze 1 m razy, i w zbiorze 2 n razy,
 * to w zbiorze wynikowym będzie max(m,n) razy. Algorytm jest stabilny, tzn kolejności elementów są zachowane
 */

#pragma warning (disable:4521)	//bug kompilatora cl.exe, 'multiple copy constructors specified'

#include <vector>
#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;

class Person{	//prosta klasa do testowania sumy zbiorów
	string name;
	unsigned age;
	Person(){}	//nie pozwalamy na tworzenie osoby bez imienia

public:
	Person(string name,unsigned age):name(name),age(age){}	//wystarczą domyślne konstruktory kopiujące

	inline const string &getName() const {		return name;	}
	inline void setName(const string &val) {	name=string(val);	}
	inline unsigned int getAge() const {		return age;	}
	inline void setAge(unsigned int val) {		age = val;	}

	/**
	 * Operator porownania na potrzeby sortowania elementow. Algorytm set_union domyslnie do porownywania
	 * elementow uzywa operatora <
	 */
	bool operator<(const Person &person2)const{
		if(age!=person2.age){
			return age<person2.age;
		}else{
			return name.compare(person2.name)<0?true:false;
		}
	}
};

struct lessPerson{	//funktor do porównywania osób
	bool operator()(const Person& person1, const Person& person2) const{
		return person1<person2;
	}
};

ostream& operator<<(ostream &os, Person const &person){	//operator strumienia do wypisywania wyników na ekran
	os << person.getName().c_str()<< ", "<< (person.getAge());
	return os;
}

template<class Type,class Order>
void mergeSort(Type *table, unsigned length,Order order){
	/**
	 * Funkcja sortująca algorytmem merge sort jest klasycznym zastosowaniem scalania zbiorow uporzadkowanych.
	 * Dzielimy rekurencyjnie dany zbior, a nastepnie scalamy
	 */
	if(length<2)
		return;
	unsigned center=length/2;
	mergeSort(table,center,order);	//rekurencja
	mergeSort(table+center,length-center,order);
	vector<Type> temp;
	set_union(table,table+center,table+center,table+length,insert_iterator<vector<Type> >(temp,temp.begin()),order);
	copy(temp.begin(),temp.end(),table);
}

int main(){
	/**
	* Jakich potrzeba liter, zeby moc napisac wyrazy 'Alibaba' i 'Alladyn'? Uwzgledniamy wielkosc liter
	* i ilosc wystapien, piszemy tylko jeden wyraz na raz
	*/
	string Alladyn="Alladyn",Alibaba="Alibaba";
	vector<char> chars,charsFunctor;
	sort(Alladyn.begin(),Alladyn.end());	//oba zbiory muszą być posortowane, wiec najpierw
	sort(Alibaba.begin(),Alibaba.end());	//sortujemy literki uzywajac std::sort

	/**
	* Wynik operacji: A a a b b d i l l n y
	*/
	set_union(Alladyn.begin(),Alladyn.end(),Alibaba.begin(),Alibaba.end(),insert_iterator<vector<char> >(chars,chars.begin()));

	cout<<"suma zbiorow (operator <):"<<endl;
	for(unsigned i=0;i<chars.size();i++)		cout<<(chars[i])<< " ";	//wypisz literki
	cout<<endl<<endl;

	/**
	* Złączmy zbiory używając wbudowanego funktora std::less
	* Wynik operacji: A a a b b d i l l n y
	*/
	set_union(Alladyn.begin(),Alladyn.end(),Alibaba.begin(),Alibaba.end(),insert_iterator<vector<char> >(charsFunctor,charsFunctor.begin()),less<char>());

	cout<<"suma zbiorow (funktor std::less<char>):"<<endl;
	for(unsigned i=0;i<charsFunctor.size();i++)		cout<<(charsFunctor[i])<< " ";	//wypisz literki
	cout<<endl<<endl;

	/**
	* Tworzymy dwie tablice z osobami. W tablicy 'city' są ludzie mieszkający w mieście X,
	* a w tablicy corporation są ludzie pracujący w firmie Y. Wyświetlamy wszystkich ludzi znajdujących się
	* w południe w okolicy. Oba zbiory są posortowane
	*/
	Person city[]={Person("Tommy",3),Person("Cindy",5),Person("Mike",7),Person("Hannah",21),Person("Jake",25)};
	Person corporation[]={Person("Hannah",21),Person("Jake",25),Person("Mike",34)};
	vector<Person> allPeople,allPeopleFunctor;

	/**
	* Suma zbiorów stworzy zbiór wynikowy zawierający wszystkie różne od siebie obiekty z obu zbiorów
	* Jake jest miejscowy, więc się powtarza w obu tablicach, są dwie osoby o imieniu Mike, ale różnią się wiekiem
	*/
	set_union(city,city+5,corporation,corporation+3,insert_iterator<vector<Person> >(allPeople,allPeople.begin()));

	/**
	* wynik operacji:
	* Tommy, 3
	* Cindy, 5
	* Mike, 7
	* Hannah, 21
	* Jake, 25
	* Mike, 34
	*/

	cout<<"suma zbiorów (operator Person::<):"<<endl;
	for(unsigned i=0;i<allPeople.size();i++)		cout<<(allPeople[i])<< endl;	//wypisz ludzi
	cout<<endl;

	/**
	* A teraz używając funktora lessPerson
	*/
	set_union(city,city+5,corporation,corporation+3,insert_iterator<vector<Person> >(allPeopleFunctor,allPeopleFunctor.begin()),lessPerson());

	cout<<"suma zbiorow (funktor lessPerson):"<<endl;
	for(unsigned i=0;i<allPeopleFunctor.size();i++)		cout<<(allPeopleFunctor[i])<< endl;	//wypisz ludzi
	cout<<endl;

	/**
	* Sortujemy zbiór liczb za pomocą naszej funkji mergeSort z funktorem std::less<float>.
	* Najpierw generujemy zbiór floatów
	*/
	const unsigned NUMBER_COUNT=10;
	float number[NUMBER_COUNT];
	for(unsigned i=0;i<NUMBER_COUNT;i++){
		number[i]=100*(float)rand()/(float)RAND_MAX;
	}
	cout<<"sortowanie mergeSort z uzyciem set_union:"<<endl;
	for(unsigned i=0;i<NUMBER_COUNT;i++)		cout<<(number[i])<< " ";	//wypisz wygenerowane liczby

	mergeSort<float>((float*)number,NUMBER_COUNT,less<float>());	//sortujemy

	cout<<endl<<"posortowane:"<<endl;
	for(unsigned i=0;i<NUMBER_COUNT;i++)		cout<<(number[i])<< " ";	//wypisz posortowane
	cout<<endl<<endl;

	system("PAUSE");
}