/* 
Bartłomiej Jurek, gr. H1SIDAK
*/

/*
OPIS ALGORYTMU
Algorytm set_intersection służy do wyznaczenia posortowanego przecięcia dwóch 
zbiorów, których elementy zawarte są w dwóch posortowanyc kontenerach. 
Elementy te leżą w zakresach [first1, last1), [first2, last2). 
Wartością zwracaną jest koniec wyjściowego zbioru.

Dostępne są następujące wersje algorytmu:

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                OutputIterator result);

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class StrictWeakOrdering>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                OutputIterator result, 
                                StrictWeakOrdering comp);

Pierwsza zakłada, że elementy są posortowane standardowym operatorem <. Jeśli
tak nie jest i dostarczono własnego komparatora, który zapewnia zachowanie 
relacji słabego porządku, można użyć wersji drugiej.

set_intersection jest stabilny, czyli elementy w zwróconym kontenerze będą w 
relatywnie tym samym porządku co w pierwszym argumencie oraz że elementy są
kopiowane raczej z pierwszego niż drugiego kontenera.

Złożoność algorytmu jest liniowa.
*/

/*
OPIS PROBLEMU
Załóżmy, że dysponujemy klasą hodowcy psów rasowych (Breeder), która zawiera 
listę gatunków psów, które są przez niego hodowane.
Dla dwóch hodowców należy wyznaczyć te gatunki, które są hodowane przez obydwu,
aby można było ich użyć w reprodukcji.
W tym celu posłużymy się algorytmem set_intersection.
*/

#include <algorithm> // set_intersection, for_each
#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;

// pomocniczy szablon służący do wyświetlania elementów z kolekcji w jednym wierszu
template <typename T>
void show_collection(const T& col)
{
	for (T::const_iterator i = col.begin(); i != col.end(); ++i)
	{
		cout << *i << ",  ";
	}
	cout << endl;
}
// pomocnicza definicja typu
typedef std::vector<std::string> StringVector;

// klasa hodowcy
class Breeder
{
public:
	Breeder(const char* breeds[], size_t size)
	{
		for (unsigned i = 0; i < size; ++i)
		{
			breeds_.push_back(string(breeds[i]));
		}
	}
	// Zwraca referencję do posortowanych wektorów ras psów
	StringVector& getSortedBreeds() 
	{	
		std::sort(breeds_.begin(),breeds_.end());
		return breeds_;
	}
private:
	StringVector breeds_;
};

/*
Funkcja wyznaczająca rasy psów wspólne dla dwóch hodowców 
*/
StringVector CommonBreeds(Breeder& a, Breeder& b)
{
	StringVector common_breeds;
	// do umieszczania elementów w wyjściowym kontenerze common_breeds użyto
	// iteratora wyjściowego, back_inserter, który umieszcza elementy na
	// końcu kontenera
	std::set_intersection(a.getSortedBreeds().begin(),a.getSortedBreeds().end(),
						  b.getSortedBreeds().begin(),b.getSortedBreeds().end(),
						  std::back_inserter(common_breeds));
	return common_breeds;
}

int main()
{
	// tablice ras psów dla dwóch hodowców
	const char* breeds1[] = {"boxer", "terrier","spaniel","mastiff","chart",
							 "shar-pei","bullterier"};

	const char* breeds2[] = {"terrier", "shar-pei","spaniel", "mastiff", 
							 "chihuahua","fila brasileiro","bullmastiff"};
	const unsigned SIZE = 7;

	// utworzenie hodowców
	Breeder one(breeds1, SIZE);
	Breeder two(breeds2, SIZE);

	// wyznaczenie ras psów, które są hodowane przez obu hodowców
	StringVector common_breeds = CommonBreeds(one,two);

	// wyświetlenie rezultatów
	cout << "Rasy hodowcy 1:" << endl;
	show_collection<StringVector>(one.getSortedBreeds());
	cout << endl;
	
	cout << "Rasy hodowcy 2:" << endl;
	show_collection<StringVector>(two.getSortedBreeds());
	cout << endl;

	cout << "Wspolne rasy psow:" << endl;
	show_collection<StringVector>(common_breeds);

	std::cin.get();
	return 0;
}