/* Tomasz Kowalski, grupa I1ISI
 * Praca domowa ZPR, semestr 2008Z
 * Opis kontenera std:deque
 * 
 * Deque to skrót od double-ended queue - kolekcja, która
 * może być używana jak kolejka od obu jej końców. Jest to zapewnione
 * przez sprytny sposób alokacji: "mapa node'ów" stałego rozmiaru
 * zawierających elementy rozrasta się od środka w obie strony.
 * 
 * Większość operacji działa w amortyzowanym czasie stałym.
 */

// ten plik włącza wszystko co potrzebne do korzystania z std::deque
#include <deque>
// dla celów demonstracyjnych wypisywane są komunikaty
#include <iostream>
// jeden z alternatywnych alokatorów - odkomentować dla kompilatora gcc
//#include <ext/malloc_allocator.h>
// definicja wyjątku std::out_of_range
#include <stdexcept>
using namespace std;


// wypisanie zawartości deque
template<typename T>
ostream& operator<<(ostream& os, const deque<T>& d);
// wypisanie zawartości od końca
template<typename T>
void printr(const deque<T>& d);


int main(int argc, char** argv) {
	// utworzenie pustego kontenera, o rozmiarze mapy=8 i
	// zalokowanym jednym node o pojemności 512/sizeof(int) elementów
	deque<int> d1;
	// wykorzystanie allocatora innego niż domyślny.
	// Allocator można podać dodatkowo też do innych konstruktorów
	// poniższe działa tylko w kompilatorze gcc
	//deque<int> d2(__gnu_cxx::malloc_allocator<int>());
	int n=5;
	int val=3;
	// wypełnia deque na starcie 'n' kopiami 'val'
	deque<int> d3(n, val);
	// skopiowanie zawartości d3 do d4
	deque<int> d4(d3);
	// skopiowanie pewnego przedziału elementów z d3 do d5
	// dla deque(left, right) skopiowany będzie przedział [left,right)
	deque<int> d5(d3.begin()+1, d3.end());
	// skopiowanie zawartości przez operator przypisania.
	d1=d5; 

	// iterator wskazujący na pierwszy element w d5
	deque<int>::iterator i5b=d5.begin();
	// iterator wskazujący na element za ostatnim w d5
	deque<int>::iterator i5e=d5.end();
	for(int i=1; i5b!=i5e; i++,i5b++)
		*i5b=i;

	// przykład użycia const_iteratorów
	cout<<"##### po przypisaniu rosnacego ciagu do d5:"<<endl;
	cout<<"d5 w przód: "<<d5<<endl;
	cout<<"d5 w tył:   "; printr(d5);
	// aktualny rozmiar
	cout<<"rozmiar d5: "<<d5.size()<<" elementów"<<endl;
	// maksymalny możliwy rozmiar d5
	cout<<"maks. rozmiar d5: "<<d5.max_size()<<" elementów"<<endl<<endl;
	
	// d1 zostanie wyczyszczone i wypełnione n+3 kopiami val-1
	d1.assign(n+3, val-1); 
	// d1 wyczyszczone i wypełnione podanym przedziałem
	d1.assign(d5.begin(), d5.end());
	// typ podanego do assign iteratora może być dowolny
	string s="samochod";
	d1.assign(s.begin(), s.end());
	cout<<"##### po przypisaniu \"samochod\" do d1:"<<endl;
	cout<<"początek d1: "<<d1.front()<<" ("<<(char)d1.front()<<")"<<endl;
	cout<<"koniec d1: "<<d1.back()<<" ("<<(char)d1.back()<<")"<<endl;
	cout<<endl;
	
	// pobranie obiektu allocatora dla deque d1
	allocator<int> alloc=d1.get_allocator();
	
	int n2=10;
	int val2=5;
	// jeśli nowy rozmiar jest mniejszy od obecnego, to ucina koniec
	// jeśli większy to nowe miejsca wypełnia 'val2'
	d5.resize(n2, val2);
	cout<<"##### po d5 resize:"<<endl;
	cout<<"zawartość d5: "<<d5<<endl;
	cout<<"czy d5 pusty: "<<d5.empty()<<endl;
	
	// pobranie jednego z elementów w deque. Wszelkie pobieranie zwraca
	// referencję i jeśli obiekt jest stały, to referencja też;
	
	// operator[] nie sprawdza czy poprawny indeks
	cout<<"10. element d5 ([]): "<<d5[9]<<endl;
	cout<<"11. element d5 (at): ";
	// at(): pobieranie z kontrolą poprawności. std::out_of_range rzucany przy błedzie
	try {
		cout<<d5.at(10)<<endl;
	}
	catch(const out_of_range& ex) {
		cout<<"at rzuciło wyjątek: "<<ex.what()<<endl;
	}
	cout<<endl;
	
	cout<<"##### modyfikacje zawartosci d5:"<<endl;
	d5.at(d5.size()-2)=8;
	cout<<"zmiana przedostatniego elementu (at): "<<d5<<endl;
	
	// dodanie 
	d5.push_front(-1);
	d5.push_back(-1);
	cout<<"dodane -1 na pocz. i kon. (push_front|push_back): "<<d5<<endl;
	
	// usunięcie pierwszego elementu z kolejki
	d5.pop_front();
	// usuniecie ostatniego elementu
	d5.pop_back();
	cout<<"usuniete -1 na pocz. i kon. (pop_front|pop_back): "<<d5<<endl;
	
	// wstawia -1 przed pozycję wskazaną iteratorem
	d5.insert(d5.begin()+2, -1);
	int n3=3;
	// wstawia n razy val przed iterator
	// insert(iter, n, val)
	d5.insert(d5.end()-2, n3, -1);
	cout<<"dodane -1 blisko poczatku i konca d5 (insert): "<<d5<<endl;
	// wstawienie przed wskazaną pozycję środkową, jakiegokolwiek
	// przedziału transformowalnego do typu przechowywanego w deque
	d5.insert(d5.begin()+d5.size()/2, s.begin()+2, s.end()-1);
	cout<<"dodany fragment \"samochod\" w środku d5 (insert): "<<d5<<endl;
	cout<<endl;
	
	// usuwanie zawsze musi mieć podane pozycje poprzez iteratory;
	// można podać jedną pozycję ...
	d5.erase(d5.begin()+2);
	// ... lub jakiś zakres
	d1.erase(d5.begin()+d5.size()/2, d5.end()-3);
	
	cout<<"##### swapowanie zawartości d1 i d5:"<<endl;
	cout<<"d1 przed zmiana: "<<d1<<endl;
	cout<<"d5 przed zmiana: "<<d5<<endl;
	// zamiana zawartości dwóch deque.
	// Działa w czasie stałym - przepisanie 4 wskaźników.
	d1.swap(d5); 
	// swap(d1,d5); // to samo co wyżej
	cout<<"d1 po zmianie: "<<d1<<endl;
	cout<<"d5 po zmianie: "<<d5<<endl;
	
	// usunięcie całej zawartości d1
	d1.clear();
	
	// dostępne operatory relacji między deque'ami:
	// ==, <, !=, >, <=, >=. Działają zgodnie z porządkiem
	// leksykograficznym
}

// wypisanie zawartości deque
template<typename T>
ostream& operator<<(ostream& os, const deque<T>& d) {
	for(typename deque<T>::const_iterator i=d.begin(); i!=d.end(); ++i)
		cout<<(*i)<<' ';
	return os;
}

// wypisanie zawartości deque od końca
template<typename T>
void printr(const deque<T>& d) {
	for(typename deque<T>::const_reverse_iterator i=d.rbegin(); i!=d.rend(); ++i)
		cout<<(*i)<<' ';
	cout<<endl;
}