/*
* main.cpp
* @author Rafał Dziedzicki(rafal.dziedzicki@gmail.com) H1ISI1
* Program demonstruje dzialanie i wykorzystanie funkcji szablonowyej find_end.
*/


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

using namespace std;

/* Find_end jest przeciążoną funkcją, istnieją:
*
*template <class ForwardIterator1, class ForwardIterator2>
*ForwardIterator1 
*find_end(ForwardIterator1 first1, ForwardIterator1 last1, 
*         ForwardIterator2 first2, ForwardIterator2 last2);
*
*template <class ForwardIterator1, class ForwardIterator2, 
*          class BinaryPredicate>
*ForwardIterator1 
*find_end(ForwardIterator1 first1, ForwardIterator1 last1, 
*         ForwardIterator2 first2, ForwardIterator2 last2,
*         BinaryPredicate comp);
*
*Właściwie lepszą nazwą dla algorytmu find_end byłaby search_end, ponieważ działanie algorytmu search oraz find_end jest dosyć podobne.
*Oba poszukują dopasowania sekwencji [first2, last2) w sekwencji [first1, last1). Różnica polega na tym, że search zwraca iterator wskazujący
*na pierwszy obiekt w pierwszym dopasowaniu, a find_end na pierwszy w ostatnim dopasowaniu.
*
*W przypadku braku dopasowania find_end zwraca last1
*
*Różnica pomiędzy dwiema wersjami algorytmu find_end polega na sposobie w jaki algorytm uznaje dwa	elementy za równe. Pierwsza wersja wykorzystuje
*operator==, natomiast druga BinaryPredicat.
*
*find_end jest zdefiniowany w nagłówku <algorithm> w STL oraz poza standardem, w nagłówku algo.h
*
*Wymagania na typy:
*Dla wersji pierwszej:
*
*    * ForwardIterator1 typu Forward Iterator.
*    * ForwardIterator2 typu Forward Iterator.
*    * wartość ForwardIterator1-a jest typu EqualityComparable.
*    * wartość ForwardIterator2-a jest typu EqualityComparable.
*    * Obiekty będące wartościami ForwardIterator1-a muszą być porównywane z obiektami będącymi wartościami ForwardIterator2-a. 
*
*For the second version:
*
*    * ForwardIterator1 typu Forward Iterator.
*    * ForwardIterator2 typu Forward Iterator.
*    * BinaryPredicate typu Binary Predicate.
*    * wartość ForwardIterator1-a musi być konwertowana na typ pierwszego argumentu dla BinaryPredicate.
*    * wartość ForwardIterator2-a musi być konwertowana na typ drugiego argumentu dla BinaryPredicate. 
*
*Złożoność:
*Liczba porównań jest proporcjonalna do (last1 - first1) * (last2 - first2).
*
*Przykłady użycia:
*/

//pierwsza wersja algorytmu find_end 
void find_end_type1(){
     
	 //utworzenie napisu oraz suffixu
	 char* s = "executable.exe";
     char* suffix = "exe";

     const int N = strlen(s);
     const int N_suf = strlen(suffix);

     char* location = find_end(s, s + N,
                            suffix, suffix + N_suf);
	if (location != s + N) {
		cout << "Znaleziono dopasowanie dla " << suffix << " w " << s << endl;
		cout << s << endl;

    int i;

	for (i = 0; i < (location - s); ++i)
        cout << ' ';
  
	for (i = 0; i < N_suf; ++i)
        cout << '^';
    cout << endl;
  }
    else
        cout << "Nie znaleziono dopasowania dla " << suffix << " w " << s << endl;

}

// przykład użycia algorytmu z predykatem binarnym
void find_end_type2(){

	//utworzenie wektora skladajacego sie z 3 takich samych ciagow liczb
	vector<int> wektor;
	for (int i=0; i<3; ++i){
		for (int j=0; j<10; ++j){
			wektor.push_back(j);
		}
	}

	//utworzenie krotkiego sufixu, ktory bedzie poszukiwany we wczesniej utworzonym wektorze
	vector<int> suffix;
	suffix.push_back(5);
	suffix.push_back(6);

	//wypisanie wstepnego komentarza:
	cout << "Szukanie dopasowania dla ";
	for(vector<int>::iterator i = suffix.begin(); i!=suffix.end(); ++i){
		cout << *i;
	}
	cout << " w ";
	for(vector<int>::iterator i = wektor.begin(); i!=wektor.end(); ++i){
		cout << *i;
	}
	
	cout << endl;
	
	//wyszykanie dopasowania
	vector<int>::iterator iter = find_end(wektor.begin(), wektor.end(), suffix.begin(), suffix.end(), equal_to<int>());

	//jesli funkcja find_end zwrocila element nie bedacy last1 to wypisywany jest komentarz o znalezieniu
	//wraz z ilustracja znalezionego sufiksu w wektorze
	if(iter != wektor.end()){
		cout << "Znaleziono:\n";
		for(vector<int>::iterator i = wektor.begin(); i!=wektor.end(); ++i){
			cout << *i;
		}
		cout << endl;
		for(int i=0; i<iter-wektor.begin(); ++i){
			cout << ' ';
		}
		for(int i=0; i<suffix.size(); ++i){
			cout << '^';
		}
		cout << endl;
	}else{
		cout << "Nie znaleziono.\n";
	}
}


int main()
{
	find_end_type1();
	find_end_type2();
	return 0;
}