/*
	Piotr Płoński, GIBE
	Sposób użycia random_sample, random_sample_n
	Przygotowane na podstawie:
	http://www.sgi.com/tech/stl/random_sample.html
	http://www.sgi.com/tech/stl/random_sample_n.html

	Obie funkcje random_sample i random_sample_n pochodzą z rozszerzenia SGI
	i nie są częscią standardu C++.

	*** random_sample ***
	random_sample przeładowywuje dwie funkcje:
	
	template <class InputIterator, class RandomAccessIterator>
	RandomAccessIterator random_sample(InputIterator first, 
										InputIterator last,
    									RandomAccessIterator ofirst, 
										RandomAccessIterator olast) 

	template <class InputIterator, class RandomAccessIterator,
  	class RandomNumberGenerator>
	RandomAccessIterator random_sample(InputIterator first, 
										InputIterator last,
    									RandomAccessIterator ofirst, 
										RandomAccessIterator olast,
    									RandomNumberGenerator& rand) 

	Opis działania:
	Losowo kopiuje n elementów z zakresu [first, last) do zakresu [ofirst, olast),
	gdzie n = min(last-first, olast-ofirst). Każdy element ze zbioru wejściowego 
	może pojawić się tylko raz w zbiorze wyjściowym, elementy są wybierane z jednakowym 
	prawdopodobieństwem. Elementy na wyjściu mogą pojawić się w dowolnej kolejności. 
	Pierwsza wersja random_sample kozysta z wewnętrznego generatora liczb losowych, 
	druga wersja pobiera jako argument funktor(obiekt funkcję) zdefiniowanego przez 
	użytkownika generatora. Elementem zwracanym przez random_sample jest element ofirst+n.
	
	Parametry:
	InputIterator - iterator który może być inkrementowany by uzyskać dostęp do następnego obiektu
	RandomAccessIterator - iterator który może być inkrementowany i dekrementownay	
						   (kroki mogą być różnej długości)
	RandomNumberGenerator - obiekt-funkcja, który pozwala na genrowanie liczb całkowitych z 
							zakresu [0, N) np.: jeżeli f jest Random Number Generator to f(N) zwraca
							liczbę całkowitą mniejszą N i wiekszą lub równą zero

	*** random_sample_n ***
	random_sample_n przładowywuje dwie funkcje:
	
	template <class ForwardIterator, class OutputIterator, class Distance>
	OutputIterator random_sample_n(ForwardIterator first, 
									ForwardIterator last,
                               		OutputIterator out, 
									Distance n)

	template <class ForwardIterator, class OutputIterator, class Distance,
    class RandomNumberGenerator>
	OutputIterator random_sample_n(ForwardIterator first, 
									ForwardIterator last,
                               		OutputIterator out,
									Distance n,
                               		RandomNumberGenerator& rand)

	Opis działania:
	Losowo kopiuje m elementów z zakresu [first, last) do zakresu [out, out+m), gdzie
	m = min(last-first, n). Każdy element wejściowy może pojawić się na wyjściu dokładnie 
	raz, elementy wybierane są z jednakowym	prawdopodobieństwem. Elementy na wyjściu są losowe 
	ale zachowują porządek tak jak były ustawione na wejściu (ważna różnica między random_sample !).  
	Pierwsza wersja random_sample_n kozysta z wewnętrznego generatora liczb losowych, 
	druga wersja pobiera jako argument funktor(obiekt funkcję) zdefiniowanego przez 
	użytkownika generatora. Funkcja zwraca element out+m.

	Parametry:
	ForwardIterator - iterator który pozwala tylko pobierać następne elementy
	OutputIterator - iterator w którym można zapisać wartość do wskazywanej pozycji i przesunąć się
					 do wskazywania na następny element ale nie można odczytać wartości i cofnąć się.
	Distance - wartość całkowita wyznaczająca liczbę elementów na wyjściu
	RandomNumberGenerator - funktor (zachowanie takie samo jak dal random_sample), wartość
							Distance jest jego argumentem


	Złożoność obu algorytmów jest liniowa.
*/		
#include <iostream>
#include <ext/algorithm>
#include <time.h>
#include <vector>
#include <iterator>

using namespace std;

/*
	Funktor - obiekt który może być wywołany tak jakby był funkcją.
	Obiekt ten definiuje operator().
*/
struct RandomNumberGenerator
{
	int operator()(int r)
	{
		return rand()%r;	
	}
};

int main () 
{
	// inicjacja zarodka generatora
	srand(time(NULL));
	int i;
	const int N = 10;
	const int n = 6;
	int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	int B[n];
	
	/* random_sample */ 
	cout << "random_sample\n";
	int *ret_val;	// wskaźnik na wartość zwracaną
	ret_val = __gnu_cxx::random_sample(A, A+N, B, B+n); // przykład działania
	cout << *(ret_val-1) << endl;	// wartość zwrócona
	for(i = 0; i < n; ++i)
		cout << B[i] << " ";		// wartości na wyjściu
	cout << endl;	

	RandomNumberGenerator rng;     	// funktor 
	cout << rng(13) << endl;		// przykład użycia funktora
	__gnu_cxx::random_sample(A, A+N, B, B+n, rng);		// wersja z genratorem zewnętrznym 
	copy(B, B + n, ostream_iterator<int>(cout, " "));  	// wypisanie z użyciem operatora ostream_iterator
	cout << endl;										// i funkcji copy

	/* random_sample_n */
	cout << "random_sample_n\n";
	vector<int> vec;				// wektor do zapisu elementów wyjściowych
	vector<int>::const_iterator it;
	insert_iterator<vector<int> > ii(vec, vec.begin()); // insert_iterator do wstawiania elementów do wektora
	__gnu_cxx::random_sample_n(A, A+N, ii, n);		// przykład działania funkcji
	for(it = vec.begin(); it != vec.end(); ++it)
		cout << *it << " ";
	cout << endl;
	
	const int M = 6;
	const int m = 3;
	string AA[] = {"ola", "ala", "ela", "ele", "alo", "olo"}; // przykład działania funkcji na tablicy ze stringami
	// funkcja z generatorem zewnetrznym i wynikiem działania przekazywanym od razu na standardowe wyjście	
	__gnu_cxx::random_sample_n(AA, AA+M, ostream_iterator<string>(cout ," "), m, rng); 
	cout << endl;

  return 0;
}