#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>

//A quicksort algoritmus implementálásakor felhasználtam a következo kodot: http://www.cplusplus.com/forum/beginner/119660/
/**, amelyet átalakítottam, hogy az indices tömböt rendezze, de a Datán történjenek az összehasonlítások.
Ez az átalakítás nem volt sikeres, és foképp ebben kérném a segítségedet!
**/

template <class T>
class  IndexVector {
private:
    size_t sequenceNum = 0; //ezt állítgatva tudjuk befolyásolni, hogy melyik szemüvegen keresztül lássuk a tömböt. A default érték a Data eredeti sorrendje.
    size_t number_of_sequences = 1; //hány darab rendezettsége létezik a tömbnek.
    size_t _size = 0;
    std::vector<T> Data;
    std::vector<std::vector<size_t>> indices; //nem kell kézi eroforráskezelés.
    std::vector<std::function<bool(T const &, T const &)>> sorting_functions;
public:
    IndexVector(){
        indices.push_back(std::vector<size_t>());
        sorting_functions.push_back(std::function<bool(T const &, T const &)>());
    }
    IndexVector(size_t size): _size(size), Data(size) {
        indices.push_back(std::vector<size_t>());
        sorting_functions.push_back(std::function<bool(T const &, T const &)>());
        size_t i = 0;
        std::generate( indices.back().begin(), indices.back().end(), [&i]() { return i++; } );
    }
    IndexVector(size_t size, const T & initial): _size(size), Data(initial) {
        indices.push_back(std::vector<size_t>());
        sorting_functions.push_back(std::function<bool(T const &, T const &)>());
        size_t i = 0;
        std::generate( indices.back().begin(), indices.back().end(), [&i]() { return i++; } );
    }

    size_t get_size() const {
        return _size;
    }
    void set_sequenceNum(size_t num){ //kiválaszt rendezettséget. num=0 a default. A kiválasztott rendezettség az operator[]-nak lesz nagyon fontos.
        sequenceNum = num;
    }
    void push_back(const T& value){ //elrontja a rendezettségeket! Hívása után szükséges a felhasználónak meghívni a sort_all függvényt!
        for ( auto& item : indices ) //minden rendezettséghez hozzáadok egy plusz elemet, aminek az értéke _size
        {
            item.push_back(_size);
        }

        Data.push_back(value); //adat betöltése
        ++_size; // tömbméret növekedésének jelzése
    }
    void sort_all(){ //felhasználó dolga, hogy feltöltés után újrarendezzen.
        size_t tmp = sequenceNum; //mentés
        for(size_t i = 1; i<number_of_sequences; i++){
            set_sequenceNum(i); //ideiglenesen át kell állítani, mert a quicksort() a sequenceNum indexu rendezést rendezi.
            quickSort( 0 , _size-1 );
        }
        set_sequenceNum(tmp); //betöltés
    }
    void add_sort(std::function<bool(T const &, T const &)> fptr = std::greater<T>()){
        sorting_functions.push_back(fptr); //elmentem a rendezofuggvenyt

        indices.push_back( std::vector<size_t>(_size) ); //Felveszek egy új indextömböt a fuggvenyhez.

        size_t i = 0;
        std::generate( indices.back().begin(), indices.back().end(), [&i]() { return i++; } ); //ezt feltöltöm 0,1,2,3,4,5....-el

        number_of_sequences++; //Ebben ebben tagváltozóban jelzem, hogy létrejött egy új rendezés.
        quickSort(0 , _size-1); //Végül rendezem a sorrendet a fuggveny szerint.
    }



    T& operator[](size_t idx){ //írás
        if(idx+1 > _size){ //túlindexelés esetén, nyúlik a tömb 0-ás értékekkel, amiket majd felülír a felhasználó.
            for(size_t i = 0; i < idx + 1 - _size; i++ ){ //pl: idx = 6, _size = 4. -> [3]-ig hivatkozható. 6-3 = 3 push_back kell.
                push_back(0);
            }
        }
        return Data[indices[sequenceNum][idx]];
    }

    /**Ez a függvény SOSE hívódik! Miért nem? Olvasásra is az író op[] hivodik.
    Azért tartom szükségesnek, mert túlindexelés esetén csak akkor szabad nyúlnia a tömbnek, ha írok bele.
    Hogyan lehetne lekezelni ezt a mukodési hibát?**/
    /*
    const T & operator[](size_t idx) const { //olvasás
        return Data[indices[sequenceNum][idx]];
    }
*/

    /**Ez az a fuggveny, ami futasi idoben elszall. Sajnos nem tudtam kideriteni, hogy miert...**/
    //beépített rendezofuggvények nem használhatóak, mert azok vagy az indices-t vagy a Datát rendeznék.
    //Nekem arra lenne szükségem, hogy a indices-t rendezzék, de az Datán végezzem el az összehasonlítást,
    //amire az indeces-on keresztül hivatkozok.
    //Sajnos saját magamnak kell implementálnom az algoritmust:
    void quickSort(int start, int end){
        if (start < end)
            {
                int p = partition(start, end);

                quickSort(start, p - 1);

                quickSort(p + 1, end);
            }
    }

    T partition(int start, int end){
        //szokványos quicksort algoritmus annyi különbséggel,
        //hogy minden összehasonlításnál az indices-on keresztül hivatkozok a Datára,
        //miközben csak az Indices-t rendezem.
        T pivotValue = Data[indices[sequenceNum][0]]; /**ITT SZÁLL EL A PROGRAM**/
        int pivotPosition = indices[sequenceNum][0];

        for (int pos = indices[sequenceNum][start + 1]; pos <= end; pos++){
            if (sorting_functions[sequenceNum](Data[pos], pivotValue)){

                std::swap(indices[sequenceNum][pivotPosition + 1], indices[sequenceNum][pos]);
                std::swap(indices[sequenceNum][pivotPosition], indices[sequenceNum][pivotPosition + 1]);
                pivotPosition = indices[sequenceNum][pivotPosition + 1];
            }
        }
        return pivotPosition;
    }
};
/**Ezeket a függvényeket etetném meg tesztelésképpen az add_sort-tal, de nem eszi meg oket.**/
template <typename D>
bool greater(D a, D b){ //teszteléshez majd
        return a>b;
}
template <typename G>
bool less(G a, G b){

        return b>a;
}
int main(){
    IndexVector<int> test;
//push_backel is feltöltheto a tomb
//    test.push_back(5);
//    test.push_back(4);
//    test.push_back(7);
//    test.push_back(1);
//    test.push_back(4);
//    test.push_back(2);
//    test.push_back(6);
//    test.push_back(3);
//    test.push_back(8);
//    test.push_back(12);
//    test.push_back(11);
//    test.push_back(14);
//    test.push_back(9);
//    test.push_back(13);
//    test.push_back(10);
//és túlindexeléssel is.
//túlindexelés esetén a tömbhoz push_backelödik egy 0as elem, ami majd felul lesz írva.
test[0] = 5;
test[1] = 4;
test[2] = 7;
test[3] = 1;
test[4] = 4;
test[5] = 2;
test[6] = 6;
test[7] = 3;
test[8] = 8;
test[9] = 12;
test[10] = 11;
test[11] = 14;
test[12] = 9;
test[13] = 13;
test[14] = 10;

/**erre elszáll a program és ez így van jól.**/
//std::cout << test[20];
/**erre megnyúlik a tömb, pedig ezt nem akartam! Csak olvasásra szabad nyúlnia a tömbnek!**/
//test[20];

//a sequenceNum default értéke 0, ami mindig a tömb eredeti sorrendje.
    std::cout << "feltoltesi sorrend: ";
    for (size_t i = 0; i<test.get_size(); i++ ){ //0-ás sequence
        std::cout << test[i] << " ";
    }
    std::cout << std::endl << std::endl;


    test.set_sequenceNum(1);
    /**rossz a paramétertípus. miért? Rosszul hívom? Miért nem eszi meg az add_sort()?**/
    //test.add_sort(greater);

    /**ITT SZÁLL EL A PROGRAM**/
    test.add_sort(); //1-es sequence: greater (default add_sort paraméter)
    std::cout << "csokkeno sorrend: ";
    for (size_t i = 0; i<test.get_size(); i++ ){
        std::cout << test[i] << " ";
    }
    std::cout << std::endl << std::endl;


    test.set_sequenceNum(2);
    /**a lambda függvényt pedig megeszi az add_sort()**/
    test.add_sort([] (int a, int b) {return a < b;}); //2-es sequence: less
    std::cout << "novekvo sorrend: ";
    for (size_t i = 0; i<test.get_size(); i++ ){
        std::cout << test[i] << " ";
    }
    std::cout << std::endl << std::endl;
}