#include <vector>
#include <deque>
#include <iterator>
#include <string>
#include <iostream>
#include <functional>
#include <algorithm>
#include <utility>
#include <ctype.h>


using namespace std;

template <typename T > void printi ( const T & start,const T & end) {
        T it(start);
        for ( ;it != end; ++it) {
        		std::cout << *it << " "; 
        }
    }

void print (string & value) 
{
	cout<<value<<" ";
}

char to_l (char c)
{
	return tolower(c);
}
string toLower(const string & v)
{
	string ret(v);
	transform(ret.begin(), ret.end(), ret.begin(),  to_l);
	return ret;
}

bool descending_caseinsensitive(const string & a, const string & b)
{
	return toLower(b) < toLower(a);
}

bool descending_casesensitive(const string & a, const string & b)
{
	return b < a;
}

bool ascending_caseinsensitive(const string & a, const string & b)
{
	return toLower(a) < toLower(b);
}

int compare(int a, int b)
{
	return b < a;
}
int main()
{
	int t[] = { 1, 10, 8, 6, 5, 4, 3, 2, 7, 9 };
	deque <int> d1( t, t+10 );
	cout<<"Source deque:\n";
	cout<<"1: "; 	printi ( d1.begin(), d1.end() );cout<<endl;
	cout<<"Sort - ascending:\n";
	sort( d1.begin(), d1.end() );
	cout<<"1: "; 	printi( d1.begin(), d1.end() );cout<<endl;
        cout<<"Find range [4,7]:\n";
	deque <int> ::iterator it1 = lower_bound( d1.begin(), d1.end(), 4);
	deque <int> ::iterator it2 = upper_bound( d1.begin(), d1.end(), 7);
	printi ( it1, it2 ); cout<<endl;
	cout<<"Finding single value\n";
	pair <deque <int>::iterator, deque <int>::iterator> p = equal_range( d1.begin(), d1.end(),4 );
	printi ( p.first, p.second ); cout<<endl;

	cout<<"--------------------------------------------------\n";

	cout<<"Sort - descending:\n";
	sort( d1.begin(), d1.end(), compare);
	cout<<"1: "; 	printi( d1.begin(), d1.end() );cout<<endl;

	cout<<"Finding range [7,4]:\n";
	it1 =lower_bound( d1.begin(), d1.end(), 6, compare );
	it2 = upper_bound( d1.begin(), d1.end(), 4, compare );
	printi( it1, it2); cout<<endl;
	cout<<"Finding single value\n";
	p = equal_range( d1.begin(), d1.end(), 4, compare );
	printi( p.first, p.second ); cout<<endl;

        cout<<"--------------------------------------------------\n";

        string st[]={"Adam", "dana", "bea", "aDAM", "BEA", "bEA", "BEa", "cila", "Cila", "adam"};
	vector <string> v1(10);
	
	copy(st, st+10, v1.begin());
	cout<<"Source collection:\n";
	cout<<"v1: "; for_each( v1.begin(), v1.end(), print); cout<<endl;
	
	cout<<"Sorting in ascending order:\n";
	cout<<"Normal sort:\n";
	sort(v1.begin(), v1.end());
	cout<<"v1: "; for_each( v1.begin(), v1.end(), print); cout<<endl;
	cout<<"Stable sort:\n";
	copy(st, st+10, v1.begin());
	stable_sort(v1.begin(), v1.end(), ascending_caseinsensitive);
	cout<<"v1: "; for_each( v1.begin(), v1.end(), print); cout<<endl<<endl;

	cout<<"Sorting in descending order:\n";
	cout<<"Normal sort:\n";
	sort(v1.begin(), v1.end(), descending_casesensitive );
	cout<<"v1: "; for_each( v1.begin(), v1.end(), print); cout<<endl;
	cout<<"Stable sort:\n";
	copy(st, st+10, v1.begin());
	stable_sort( v1.begin(), v1.end(), descending_caseinsensitive );
	cout<<"v1: "; for_each( v1.begin(), v1.end(), print); cout<<endl<<endl;
	return 0;
}