/* Jan Gajowiak
 *
 * grupa: I1SST
 *
 * temat: "biblioteka stl, opis algorytmów : lower_bound upper_bound"
 * 
 * ---------------------------------------------------------------------------------------
 * 
 * 
 * 
 * Funkcje "lower_bound( first, last, value [, comp] )" oraz "upper_bound( first, last, value [, comp] )" 
 * są standardowymi szablonami funkcji biblioteki "algorithm". Sa to algorytmy niezmieniajace dla posortowanych danych.
 * Obydwie funkcje zwracaja iterator na element ciagu w miejsce ktorego nalezy wstawic dany element
 * tak aby nie zaburzyc posortowanej kolekcji. "lower_boudn" zwraca pierwsze miejsce na ktore
 * mozna wstawic nowy element, "upper_bound" natomiast ostatnia taka pozycje. Obydwie funkcje przeszukuja
 * w zakresie [first;last). Obydwa algorytmy wymagają również, aby dane w podanych zakresach były posortowane
 * ze względu na operator "<" lub obiekt funkcyjny użyty do porownywania. Operacje na nieposortowanych 
 * zbiorach moga byc zrodlem bledu.
 * 
 * 
 * Istnieja dwie wersje szablonu funkcji "lower_bound": 
 *				(analogicznie istnija identyczne dwie wersje "upper_bound")
 *		
 *		template <class ForwardIterator, class LessThanComparable>
 *		ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
 *									const LessThanComparable& value);
 *
 * 		template <class ForwardIterator, class T, class StrictWeakOrdering>
 *		ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
 *									const T& value, StrictWeakOrdering comp);
 * 
 * 
 *       Parametry wejsciowe:
 *			
 * 			ForwardIterator first - element kolekcji od ktorego rozpocznie sie wyszukiwanie
 * 			ForwardIterator last  - element kolekcji ktory jako pierwszy nie bedzie branu pod uwage
 * 			const LessThanComparable& value - element wyszukiwany (do wstawienia)
 * 			StrictWeakOrdering comp - obiekt funkcyjny porownujacy dwa elementy
 *  
 *
 *  W wyniku dzialania obu funkcji zwracany jest iterator na element zbioru. W wypadku "lower_bound"
 *  wskazywana jest pierwsza pozycja, na ktora nalezy wstawic zadany element, aby nie zaburzyc ciagu.
 *  "upper_bound" zwraca ostatnia taka pozycje.
 *  Dla poprawnego dzialania obu algorytmow klasa elementu wyszukiwanego musi dostarczac operator "<"
 *  (w wersji "( first, last, value)") i/lub obiekt funkcji porownujacej (w wersji "( first, last, value, comp)").
 *
 *
 *
 *  Przyklad dzialania algorytmow "lower_bound" oraz "upper_bound" w obu wersjach:
 *
 */


#include <iostream>
#include <vector>
#include <algorithm>	// biblioteka zawierajaca "upper_bound" oraz "lower_bound"

using namespace std;


//Klasa reprezentujaca punkt na plaszczyznie z dwoma wspolrzednymi oraz charakterystycznym znakiem
class Punkt
{
public:
	
	static int numer;	
	int x, y;		//wspolrzedne punktu
	char znak;		//charakterystyczny znak dla danego punktu
	
	Punkt(const int &a, const int &b){x=a;y=b; znak = 'A'+(numer++);};

	bool operator<(const Punkt &d)const  //operator "<" porownuje punkty przy uzyciu "X"
	{
		if(this->x < d.x)
			return true; 
		return false;
	};

};
int Punkt::numer = 0;


//Obiekt funkcyjny do porownywania dwoch obiektow klasy Punkt
//Porownuje obiekty klasy Punkt przy uzyciu "y"
class rowne
{
public:
	bool operator()(const Punkt &a, const Punkt &b)
	{
		return ( a.y < b.y) ? true : false;
	};
};


int main()
{ 
	vector<Punkt> punkty;		//wektor przechowujacy obiekty klasy Punkt

	// Wypelnianie wektora punktami:
	punkty.push_back(Punkt(1,1));
	punkty.push_back(Punkt(1,1));
	punkty.push_back(Punkt(2,1));
	punkty.push_back(Punkt(2,2));
	punkty.push_back(Punkt(2,2));
	punkty.push_back(Punkt(3,2));
	punkty.push_back(Punkt(3,3));
	punkty.push_back(Punkt(3,3));

	// Wyswietlenie elementow wektora:
	cout<<"Elementy wektora:"<<endl;
	for(int i=0;i!=punkty.size();i++)
		cout<< punkty[i].x << " - " << punkty[i].y << " (" << punkty[i].znak << "); " <<endl;
	cout<<endl<<endl;
	
	// Iteratory wskazujace na elementy wektora z punktami
	vector<Punkt>::iterator it1;
	vector<Punkt>::iterator it2;
	
	// element do wstawienia
	Punkt poszukiwany = Punkt(2,2);

	// wyszukiwanie pozycji na wstawienie elementu do wstawienia
	it1=lower_bound(punkty.begin(),punkty.end(),poszukiwany);
	it2=upper_bound(punkty.begin(),punkty.end(),poszukiwany);
	
	cout<< "Element do wstawienia: " << poszukiwany.x << " - " << poszukiwany.y;
	cout<<endl<<endl<<endl<<endl;

	cout<< "Element mozna wstawic w miejsca: (operator< porownujacy X)" <<endl;
	cout<< "pierwsza pozycja (lower_bound): " << it1->znak <<endl;
	cout<< "ostatnia pozycja (upper_bound): " << it2->znak <<endl<<endl;


	it1=lower_bound(punkty.begin(),punkty.end(),poszukiwany,rowne());
	it2=upper_bound(punkty.begin(),punkty.end(),poszukiwany,rowne());
	

	cout<< "Element mozna wstawic w miejsca: (funktor porownujacy Y)" <<endl;
	cout<< "pierwsza pozycja (lower_bound): " << it1->znak <<endl;
	cout<< "ostatnia pozycja (upper_bound): " << it2->znak <<endl;
}