//
//  samost 2.cpp
//  Zadach C++
//
//  Created by Хмелев Саша on 30/05/2017.
//  Copyright © 2017 Хмелев Саша. All rights reserved.
//
/* Необходимо реализовать шаблон списка L, который содержит объекты произвольного типа. Список должен обладать возможностями добавления (только в начало), удаления (только с конца) и быстрой сортировки */

#include <iostream>
using namespace std;

template <class T>
class List {

    class Element {
    public:
        Element *front, *cur, *next;
        T value;
    };

protected:
    Element* front;
    Element* next;
public:
    size_t size;
    T* arr;
    // конструктор
    List() {
        size = 0;
        front = nullptr;
        next = nullptr;
        arr = nullptr;
    }
    // добавление в начало
    virtual void addfront(T x) {
        if(front == nullptr) {
            front = new Element;
            front->next = nullptr;
            front->value = x;
        }
        else {
            Element* mesto = front;
            front = new Element;
            front->next = mesto;
            front->value = x;
            size++;
        }
    }
    // удаление с конца
    virtual T pop() {
        T popped;
        Element* forward;
        Element* penult;
        forward = front;
        while (forward->next) {
            penult = forward;
            forward = forward->next;
        }
        popped = forward->value;
        penult->next = nullptr; //?
        delete forward;
        size--;
        return popped;
        }
    // перегрузка оператора [] для того, чтобы к элементам списка было удобнее обращаться
    Element* operator[] (int i) {
        if (i<0 || i>size)
            return NULL;
        Element* cur = front;
        for (int k = 0; k<i; k++) {
            cur = cur->next;
        }
        return cur;
    }
    // функция для перехода от списка к массиву
    virtual T listToArr(T L, int i) {
        if (!arr) {
            arr = new T[size];
        }
        arr[i] = L;
        return 0;
    }
    // фунцкция быстрой сортировки (надо разобраться с ЛУЧШИМ СЛУЧАЕМ)
    virtual void q_sort(int left, size_t right) {
        int l_hold, r_hold;
        l_hold = left;
        r_hold = right;
        T pivot = arr[left];
        while (left < right) {
            while ((arr[right] >= pivot) && (left < right))
                right--;
            if (left != right) {
                arr[left] = arr[right];
                left++;
            }
            while ((arr[left] <= pivot) && (left < right))
                left++;
            if (left != right) {
                arr[right] = arr[left];
                right--;
            }
        }
        arr[left] = pivot;
        pivot = left;
        left = l_hold;
        right = r_hold;
        if (left < pivot)
            q_sort(left, pivot - 1);
        if (right > pivot)
            q_sort(pivot + 1, right);
    }
    // функция для печати, работающая ток с массивом
    virtual void print() {
        for (int i = 0; i <= size; i++)
            cout << arr[i] << " ";
    }

    // деструктор
    ~List() {
        cout << "\nList destructor is working" << endl;
        if (arr)
            delete[] arr;
        arr = NULL;
        while (size)
            pop();
    }

};


int main() {
    List<char> L;
    //List<int> L;

    L.addfront('a');
    //L.addfront(0);
    L.addfront('b');
    //L.addfront(1);
    L.addfront('c');
    //L.addfront(2);
    L.addfront('d');
    //L.addfront(3);
    L.addfront('e');

    cout << "\nЭлементы нашего списка, добавляющиеся в начало: " << endl;

    for (int i = 0; i <= L.size; i++) {
        L.listToArr(L[i]->value, i);
        cout << L.arr[i] << " ";
    }

    cout << "\n\nУдалили элемент с конца. Вот этот элемент: " << L.pop() << endl;

    cout << endl << "Переписали список в массив, применили быструю сортировку: \n";
    L.q_sort(0, L.size);

    L.print();

    cout << endl;

    return 0;
}