/*
*	Marcin Wyrzykowski H1ISI				Praca Domowa ZPR
*	Algorytm Includes
*
* Algorytm Includes sprawdza czy posortowany zakres elementów zawiera wszytkie
* elementy znajdujące się w innym posortowanym zakresie elementów.
* Relacja mniejszości elementów może zostać określony przez binarny predykat.
*
*/

/*
Prototypy:
includes jest przeciążoną nazwą, istnieją dwie wersje funkcje:

template <class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, InputIterator2 last2);

template <class InputIterator1, class InputIterator2, class StrictWeakOrdering>
bool includes(InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, InputIterator2 last2, 
              StrictWeakOrdering comp);

Pierwsza wersja porównuje elementy wykorzystując "operator<".
Druga wersja porównuje elementy wykorzystując podany przez użytkownika obiekt funkcyjny.

Opis parametrów:
	first1 - iterator wskazujący pierwszy element pierwszego zakresu elementów
	last1 - iterator wskazujący element za ostatnim elemetntem pierwszego zakresu elementów
	first2 - iterator wskazujący pierwszy element drugiego zakresu elementów
	last2 - iterator wskazujący element za ostatnim elemetntem drugiego zakresu elementów
	comp - obiekt funkcyjny określający relacje mniejszoći. Pobiera dwa argumenty i	
		zwraca "true" jeżeli warunek jest spełnimu lub "false" wpp.

Warunki wstępne dla argumentów:
	Zarówno pierwszy i drugi zakres elementów powinien być posortowany w porządku rosnącym 
	z użyciem odpowiedniego operatora:
		- dla pierwszej wersji - "operator<",
		- dla drugiej wersji - podany przez użytkownika obiekt funkcyjny "comp".
	InputIterator1 i InputIterator2 są iteratorami do tych samych typów.

Zwracana wartość:
	"true" jeśli dla każdego elementu z [first2, last2) istnieje odpowiednik w [first1, last1),
	wpp. "false". 
	Jeśli elementy powtarzają się istotna jest liczba powtórzeń odpowiadających elementów.
	
Złożoność:
	Liniowa. Zero porównań jeśli jeden z zakresów jest pusty,
	wpp. maksymalnie 2 * ((last1 - first1) + (last2 - first2)) - 1 porównań. 

*/

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <cmath>
#include <functional>

using namespace std;

//obiekt funkcyjny porównujący wartości bezwględne elementów(pomijający znak)
//używany w drugim przykładzie
	struct less_mag_fabs : public binary_function<float, float, bool> {
		bool operator()(float x, float y) { return fabs(x) < fabs(y); }
	};

int main()
{
///////////////////////////////////////////////////////////////////////////////
//Przyklad1 dla pierwszej wersji funkcji incudes
	cout<<"Przyklad1 - pierwsza wersja funkcji incudes"<<endl;

	bool result;

	string s1("abcde");
	string s2("abd");
	string s3("ax");
	string s4("aaabccde");
	string s5("aaacc");
	string s6("aaaccc");
	
	//tworzymy wektory char'ów,
	//wektory powinny zawierać posortowane leksykograficznie elementy
	vector<char> vector1(s1.begin(), s1.end());
	vector<char> vector2(s2.begin(), s2.end());
	vector<char> vector3(s3.begin(), s3.end());
	vector<char> vector4(s4.begin(), s4.end());
	vector<char> vector5(s5.begin(), s5.end());
	vector<char> vector6(s6.begin(), s6.end());
	
	//includes sprawdza czy dla wszystkich charów zawartych w wektorze drugim istnieją
	//odpowiedniki w wektorze pierwszym. Istotna jest liczba powtórzeń elementów.
	//wydruki postaci 'xx' zawarte w 'yy', gdzie 'xx' oznacza kolejne chary 
	cout <<"'"<< s2 << "' zawarte w '" << s1 << "'- ";
	result = includes(vector1.begin(), vector1.end(), vector2.begin(), vector2.end());
	if (result) cout<<"true"; else cout<<"false";
	cout<< endl;

	cout <<"'"<< s3 << "' zawarte w '" << s1 << "'- ";
	result = includes(vector1.begin(), vector1.end(), vector3.begin(), vector3.end());
	if (result) cout<<"true"; else cout<<"false";
	cout<< endl;

	cout <<"'"<< s5 << "' zawarte w '" << s4 << "'- ";
	result = includes(vector4.begin(), vector4.end(), vector5.begin(), vector5.end());
	if (result) cout<<"true"; else cout<<"false";
	cout<< endl;

	cout <<"'"<< s6 << "' zawarte w '" << s4 << "'- ";
	result = includes(vector4.begin(), vector4.end(), vector6.begin(), vector6.end());
	if (result) cout<<"true"; else cout<<"false";
	cout<< endl;

////////////////////////////////////////////////////////////////////////////////////
//Przyklad dla drugiej wersji funkcji includes 
// - z uzyciem obiektu funkcyjnego do porownywania.

	cout<<"Przyklad2 - z uzyciem obiektu funkcyjnego do porownywania"<<endl;
	
	deque<float> deque_;
	deque_.push_back(-4);
	deque_.push_back(-6);
	deque_.push_back(3);
	deque_.push_back(5);

	vector<float> vector_;
	vector_.push_back(-4);
	vector_.push_back(3);
	vector_.push_back(6);

	//sortowanie z uwzględnieniem wartości bezwzględnych elementów
	sort(deque_.begin(), deque_.end(), less_mag_fabs() );
	sort(vector_.begin(), vector_.end(), less_mag_fabs());
	
	//includes sprawdza czy dla wartości bezwględnej kolejnych elementów z vector_
	//istnieją w deque_ odpowiadające elementy o równej wartości bezwględnej.
	cout <<"vector_ zawarte w deque_ - ";
	result = includes(deque_.begin(), deque_.end(), vector_.begin(), vector_.end(),  			 less_mag_fabs());
	
	if (result) cout<<"true"; else cout<<"false";
	cout<<endl;

  return 0;
}