//	Łukasz Mirtecki, 3961/D, E1
//  l.mirtecki@elka.pw.edu.pl    
//	Algorytm : adjacent_difference (STL)

/*	adjacent_difference jest nazwą przeciążonej funkcji występującej w dwóch postaciach :

	template <class InputIterator, class OutputIterator>
	OutputIterator adjacent_difference(InputIterator first, InputIterator last, 
                                   OutputIterator result);

	template <class InputIterator, class OutputIterator, class BinaryFunction>
	OutputIterator adjacent_difference(InputIterator first, InputIterator last,
                                   OutputIterator result,
                                   BinaryFunction binary_op);

	Funkcja adjacent_difference() w zakresie określonym przez iteratory //first//, //last// 
	dokonuje odejmowania kolejnych przylegających do siebie elementów. Element *first przypisywany 
	jest do elementu *result będącym iteratorem na kolekcje wynikową. Dla każdego elementu iteratora 
	i w zakresie [first + 1, last), różnica *i oraz *(i - 1) przypisywana jest do *(result + (i - first)).
	Dzięki temu, iż oprócz składowania różnic w kolekcji wynikowej na pierwszej pozycji przechowujemy 
	pierwszy element możemy odtworzyć kolekcję wejściową na podstawie, której powstał wynik. Operacją 
	odwrotną do adjacent_difference, którą można użyć do tego celu jest jest partial_sum.
	Nie ma przeciwwskazań aby iterator wynikowy był tożsamy z wejściowym umożliwiając obliczanie 
	różnic na kolekcji 'w miejscu'.

	===== Wymagany nagłówek =====
	#include<numeric>

	===== Parametry ===== 
	Wymagania dla obu wersji:
		first  - iterator wskazujący początek zakresu wejściowego
		last   - iterator wskazujący koniec zakresu wejściowego
		result - iterator wskazujący początek kolekcji wyjściowej
		Wartości dla typu InputIterator dają się konwertować do wartości dla typu OutputIterator
		[first, last) jest poprawnym zakresem 
		[result, result + (last - first)) jest poprawnym zakresem 

	Dodatkowe wymagania dla pierwszej wersji:
		Wartość zwracana x - y jest zdefiniowana i daje się konwertować do wartości OutputIterator. 

	Dodatkowe wymagania dla drugiej wersji:
		BinaryFunction jest funkcją binarną.
		Wartości dla typu InputIterator dają się konwertować odpowiednio do wartości pierwszego i drugiego argumentu funkcji binarnej. 
		Wynik funkcji binarnej dają się konwertować do wartości dla typu OutputIterator. 
			
	===== Złożoność =====
	Liniowa. brak operacji jeśli [first, last) jest przedziałem pustym, w przeciwnym przypadku dokładnie (last - first) - 1 operacji. 
*/


//#include "stdafx.h"

// Nagłówek główny
#include <numeric>

// Nagłówki pomocnicze dla przykładu
#include <vector>
#include <list>
#include <functional>
#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
   list <int> L1; // Lista wejściowa
   list <int>::iterator LIter1, LIterend, LIterend2;

   vector<int> V1( 10 ), V2( 10 ); // Kontenery wyjściowe
   vector<int>::iterator VIter1, VIter2, VIterend, VIterend2;

   int t; // Wypełnienie  kolekcji wejściowej {1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
   for ( t = 1 ; t <= 10 ; t++ )
      L1.push_back( t * t );

   cout << "Kolekcja wejsciowa L1 :\n ( " ;
   for ( LIter1 = L1.begin( ) ; LIter1 != L1.end( ) ; ++LIter1 )
      cout << *LIter1 << " ";
   cout << ")." << endl;

   //  Zastosowanie pierwszej wersji algorytmu
   //  Standardowa użycie adjacent_difference na liście, wynik zwracany przypisany do wektora
   VIterend = adjacent_difference ( L1.begin ( ) , L1.end ( ) , V1.begin ( ) );
   
   cout << "Kolekcja wyjsciowa, standardowe adjacent_differences:\n ( " ;
   for ( VIter1 = V1.begin( ) ; VIter1 != VIterend ; ++VIter1 )
      cout << *VIter1 << " ";
   cout << ")." << endl;

   //  Zastosowanie drugiej wersji algorytmu
   //  Użycie adjacent_difference z funkcją binarną - mnożenie - na liście, wynik zwracany przypisany do wektora
   VIterend2 = adjacent_difference ( L1.begin ( ) , L1.end ( ) , V2.begin ( ) , 
      multiplies<int>( ) );
   
   cout << "Kolekcja wyjsciowa, adjacent_differences dla funcji binarnej - mnozenia:\n ( " ;
   for ( VIter2 = V2.begin( ) ; VIter2 != VIterend2 ; ++VIter2 )
      cout << *VIter2 << " ";
   cout << ")." << endl;

   // Zastosowanie algorytmu 'w miejscu'
   LIterend2 = adjacent_difference ( L1.begin ( ) , L1.end ( ) , L1.begin ( ) );
   cout << "Kolekcja wyjsciowa i wejsciowa tozsame, adjacent_differences w miesjcu na L1:\n ( " ;
   for ( LIter1 = L1.begin( ) ; LIter1 != LIterend2 ; ++LIter1 )
      cout << *LIter1 << " ";
   cout << ")." << endl;


	//-----------------------------------------------------------------------------
	//  Zastosowanie algorytmu 'w rzeczywistym' przypadku
	typedef vector < int > IntegerArray;
	typedef ostream_iterator < int, char, char_traits<char> > IntOstreamIt;

	// iterator ostream drukujący liczny całkowite int zakończone znakiem spacji
    IntOstreamIt itOstream(cout," ");

    // Inicjalizacja tablic
    // Sytaucja :
	//			Podróżując jesteśmy w stanie mierzyć odległości
	//			pomiędzy miastem wyjazdu a miastem w którym aktualnie
	//			się znajdujemy (np. licznik w samolocie)
	IntegerArray rgIA;
    rgIA.push_back(5661); //  San Francisco - Berlin
    rgIA.push_back(7456); //  Kair
    rgIA.push_back(10995); // Kalkuta
    rgIA.push_back(17019); // Cape Town
    rgIA.push_back(24394); // Hong Kong
    rgIA.push_back(30376); // Londyn
    rgIA.push_back(35758); // Los Angeles

    // Wydruk tablicy wejściowej
    copy(rgIA.begin(),rgIA.end(),itOstream);
    cout << endl;

    // Chcemy znaleźć odległości jakie musieliśmy przebyć
	// miedzy poszczególnymi miastami
	// Wykorzystujemy  adjacent_difference()
    IntegerArray rgDifferences(7);
    IntegerArray::iterator itDifferences = rgDifferences.begin();
    adjacent_difference(rgIA.begin(),rgIA.end(),itDifferences); // Oblicznie roznic

    // Wydruk 'odległości' pomiędzy miastami
    // Należy pamiętać ze pierwszy element nie jest różnica !
    cout << "Kolejne roznice pomiedzy miastami: ";
    copy(rgDifferences.begin()+1,rgDifferences.end(),itOstream);
    cout << endl;
}