/*  Marek Franciszkiewicz, J1TIZ
    M.Franciszkiewicz@stud.elka.pw.edu.pl

    Temat: Algorytmy STL - reverse, reverse_copy

--- Implementacja algorytmu reverse

    template <class BidirectionalIterator>
        void reverse ( BidirectionalIterator first, BidirectionalIterator last)
        {
            while ((first!=last)&&(first!=--last))
                swap (*first++,*last);
        }

    > Algorytm reverse odwraca kolejnosc elementow wewnatrz zakresu [first, last).
    > Listy udostepniaja funckje skladowa reverse, oferujaca lepsza wydajnosc
      (modyfikowane sa jedynie wskazniki, a nie wartosci elementow).
    > Zlozonosc liniowa: liczba_elementow / 2 zamian

--- Implementacja algorytmu reverse_copy

    template <class BidirectionalIterator, class OutputIterator>
        OutputIterator reverse_copy ( BidirectionalIterator first,
                                BidirectionalIterator last, OutputIterator result )
            {
                while (first!=last) *result++ = *--last;
                return result;
            }

    > Algorytm odwraca kolejnosc elementow z zakresu [first, last) podczas kopiowania
      z kolekcji zrodlowej. Zwracana jest pozycja za ostatnim elementem w kontenerze
      docelowym.
    > Zakres docelowy musi byc odpowiednio duzy lub nalezy uzyc iteratorow wstawiajacych.
    > Zlozonosc liniowa: liczba_elementow przypisan
*/

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <string>
#include <iterator>
#include <algorithm>    /* reverse, reverse_copy */
using namespace std;

/**
*   Funkcja szablonowa wyswietlajaca zawartosc kontenera.
*   Wykorzystuje funkcje copy oraz wyjsciowy iterator
*   strumieniowy.
*/
template<class T>
void print_elements(const T& coll, const char* sep = " ") {

    typedef ostream_iterator<typename T::value_type>    os_iter;

    cout << "\t";
    copy(coll.begin(), coll.end(), os_iter(cout, sep));
    cout << endl;
}

/**
*   Funkcja szablonowa dzielaca string na wyrazy i zapisujaca je
*   w okreslonym kontenerze. Separator przekazywany jest
*   jako ostatni argument funkcji.
*/
template<class T>
void explode_string(const string& str, T* dest_coll,
                    const char* sep = " ") {
    size_t  last = 0,                           /* ostatnia pozycja wystapienia
                                                separatora */
            found = str.find_first_of(sep);     /* pozycja (pierwszego)
                                                wystapienia separatora */
    if (dest_coll == 0L) return;
    /* dopoki pozycja found nie jest rowna koncowi stringa */
    while(found != string::npos) {
        if(found > last)                        /* dodanie do kontenera czesci str */
            dest_coll->push_back(str.substr(last, found - last));

        last = found + 1;                       /* zmiana poczatkowej pozycji
                                                przeszukiwania - na nastepujaca po
                                                found */
        found = str.find_first_of(sep, last);   /* wyszukanie kolejnego wystapienia
                                                separatora - od pozycji last */
    }
    /* dodanie do kontenera ostatniego wyrazu str */
    if(last != string::npos)
        dest_coll->push_back(str.substr(last));
}

/**
*   Definicja przykladowego iteratora wstawiajacego.
*   Elementy wstawiane sa na przemian na poczatek i koniec kontenera.
*/
template <class Container>
class frontback_insert_iterator : public iterator <output_iterator_tag, void,
                                            void, void, void> {
protected:
    Container&  container;
    bool        push_element_front;

public:
    typedef frontback_insert_iterator<Container>    fbi;

    explicit frontback_insert_iterator(Container& cont) :  container(cont),
                                                    push_element_front(false) {}
    /* przeciazenie wymaganych operatorow */
    fbi& operator=(const typename Container::value_type& val) {
        if (push_element_front) {
            container.push_front(val);
            push_element_front = false;
        } else {
            container.push_back(val);
            push_element_front = true;
        }

        return *this;
    }
    fbi& operator*()      { return *this; }
    fbi& operator++()     { return *this; }
    fbi& operator++(int)  { return *this; }
};

/**
*   Funkcja pomocnicza, tworzaca frontback_insert_iterator w wygodny sposob
*/
template <class Container>
inline frontback_insert_iterator<Container>
    frontback_inserter(Container& cont) {
    return frontback_insert_iterator<Container>(cont);
}

/* przyklady uzycia algorytmow reverse i reverse_copy */
int main() {
    const string QUOTE("640 KB pamieci operacyjnej powinno kazdemu wystarczyc");

    vector<string>  quote_vector;
    list<string>    quote_list;

    explode_string(QUOTE, &quote_vector);
    explode_string(QUOTE, &quote_list);

    cout << "CYTAT: " << endl << QUOTE << endl << endl;

    {   /* REVERSE - przykladowe uzycie */

        /* uzycie algorytmu reverse na liscie */
        cout << "REVERSE: quote_list" << endl;
        reverse(quote_list.begin(), quote_list.end());
        print_elements(quote_list);

        /* optymalna wersja algorytmu reverse dla list */
        cout << endl << "REVERSE: quote_list, funkcja skladowa" << endl;
        quote_list.reverse();
        print_elements(quote_list);

        /* odwrocenie wybranego zakresu elementow w wektorze */
        cout << endl << "REVERSE: quote_vector, wybrany zakres" << endl;
        reverse(quote_vector.begin() + 3, quote_vector.end() - 1);
        print_elements(quote_vector);
    }

    cout << endl;

    {   /* REVERSE_COPY - przykladowe uzycie */
        list<string>    quote_list2;
        deque<string>   quote_deque;
        vector<int>     num_vector;
        const int       nums[] = { 1, 2, 3, 4, 5 };

        /* odwrocona kopia elementow kontenera, z wykorzystaniem
        wlasnego iteratora wstawiajacego */
        cout << "REVERSE_COPY: frontback_inserter, wybrany zakres " << endl;
        cout << "quote_vector1 odwrocony i skopiowany do quote_deque" << endl;
        reverse_copy(quote_vector.begin() + 1, quote_vector.end() - 1,
                        frontback_inserter(quote_deque));
        print_elements(quote_deque);

        /* odwrocona kopia z wykorzystaniem standardowego iteratora wstawiajacego */
        cout << endl << "REVERSE_COPY: quote_list2, odwrocona kopia quote_vector" << endl;
        reverse_copy(quote_vector.begin(), quote_vector.end(),
                        back_inserter(quote_list2));
        print_elements(quote_list2);

        /* odwrocona kopia z wykorzystaniem wyjsciowego iteratora strumieniowego */
        cout << endl << "REVERSE_COPY: odwrocona kopia quote_list (ostream_iterator)" << endl << "\t";
        reverse_copy(quote_list.begin(), quote_list.end(),
                        ostream_iterator<string>(cout, " "));

        /* odwrocona kopia bez uzycia iteratorow wstawiajacych */
        cout << endl << endl << "REVERSE_COPY: odwrocona kopia tablicy integerow" << endl;
        num_vector.resize(5);   /* kontener docelowy MUSI zapewnic wystarczajaca ilosc miejsca */
        reverse_copy(nums, nums + 5, num_vector.begin());
        print_elements(num_vector);
    }

    return 0;
}