#include <iostream>
#include <cstdlib>
#include <locale>

using namespace std;
struct Node //узел в списке для храниения неиспользуемых массивов
{
    double* arr_data;
    int size;
    Node* next;
};
class List
{
private:
    Node* head; //"голова" связанного списка
public:
    List()
    {
        head = NULL;
    }
    //метод, добавляющий новый узел в список
    void addNode(int size, double* pointer)
    {
        Node* nd = new Node;
        nd->arr_data = pointer;
        nd->size = size;
        nd->next = NULL;
        if (head == NULL)
            head = nd;
        else
        {
            Node* current = head;
            while (current->next != NULL)
                current = current->next;
            current->next = nd;
        }
    }

    void print_all_list()//печатает содержимое всех элементов сохранённых масивов
    {
        Node* current = head;
        while (current != NULL)
        {
            for (int i = 0; i < current->size; i++)
            {
                cout << current->arr_data[i] << endl;
            }
            current = current->next;
        }
    }




};

class d_array
{

private:
    List list;
    double* arr;
    int size;

public:
    d_array(int size_ar)
    {

        this->size = size_ar;
        if (size < 1)
        {
            cout << "error: the size of array should be more than 0" << endl;
            exit(-1);
        }
        else
        {
            arr = new double[size_ar];
            for (int i = 0; i < size_ar; i++)
            {
                arr[i] = 0;
            }
            cout << "Первоначальный массив: ";
            print_array();

        }

    }
    void reallocation(int n_size)//функция изменения размера памяти
    {

        if (n_size == size)
        {
            return;
            print_array();
        }
        else if (n_size < size && n_size > 0)
        {
            double* ne_array = new double[n_size];
            for (size_t i = 0; i < n_size; i++)
            {
                ne_array[i] = arr[i];
            }
            arr = ne_array;
            size = n_size;
            list.addNode(size, arr);
            print_array();
        }
        else if (n_size > size)
        {
            double* new_array = new double[n_size];
            for (size_t i = 0; i < size; i++)
            {
                new_array[i] = arr[i];
            }
            for (size_t i = size; i < n_size; i++)
            {
                new_array[i] = 0;
            }
            size = n_size;
            list.addNode(size, arr);
            arr = new_array;
            print_array();
        }
        else if (n_size <= 0)
        {
            cout << "error: the size of array should be more than 0" << endl;
            exit(-1);
        }


    }
    void push_back(double value)//функция добавления элемента в конец массива
    {
        double* new_array = new double[size + 1];
        for (int i = 0; i < size; i++)
        {
            new_array[i] = arr[i];
        }
        new_array[size] = value;
        list.addNode(size, arr);
        this->arr = new_array;
        this->size++;
        print_array();
    }

    void Insert(double value, int index)//функция вставки элемента по индексу
    {
        if (index < size && index >= 0)
        {
            double* new_array = new double[size + 1];
            new_array[size] = value;
            for (int i = 0; i < size; i++)
            {
                new_array[i] = arr[i];
            }
            size++;
            for (size_t i = size - 1; i >= index + 1; i--)
            {
                double rem = new_array[i];
                new_array[i] = new_array[i - 1];
                new_array[i - 1] = rem;
            }

            list.addNode(size, arr);
            arr = new_array;
            size++;
            print_array();

        }
        else if (index >= size)
        {
            cout << "warning: Index out of range. The element " << value << " was added at the end of array" << endl;
            push_back(value);
            print_array();
        }
        else if (index < 0)
        {
            cout << "error: Index out of range." << endl;
            exit(-5);
        }

    }

    double* get_pointer(int index)//функция получения ссылки на эелемент для прямого доступа к значению
    {
        if (index >= 0 && index < size)
        {
            return this->arr + index;
        }
        else
        {
            cout << "error: Index out of range." << endl;
            exit(-5);
        }

    }

    int get_size()//возвращает колчество элементов
    {
        return size;
    }

    void remove(int index)//удалить элемент по индексу
    {
        if (index < size && index >= 0)
        {
            arr[index] = 0;
            for (int i = index; i < size - 1; i++)
            {
                double rem = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = rem;
            }
            size--;
            double* new_array = new double[size];
            for (size_t i = 0; i < size; i++)
            {
                new_array[i] = arr[i];
            }
            arr = new_array;
            list.addNode(size, arr);
            print_array();
        }
        else
        {
            cout << "error: Index out of range" << endl;
            exit(-2);
        }

    }

private:
    void q_sort(double* numbers, int left, int right)
    {

        double pivot;
        int l_hold = left;
        int r_hold = right;
        pivot = numbers[left];
        while (left < right)
        {
            while ((numbers[right] >= pivot) && (left < right))
                right--;
            if (left != right)
            {
                numbers[left] = numbers[right];
                left++;
            }
            while ((numbers[left] <= pivot) && (left < right))
                left++;
            if (left != right)
            {
                numbers[right] = numbers[left];
                right--;
            }
        }
        numbers[left] = pivot;
        pivot = left;
        left = l_hold;
        right = r_hold;
        if (left < pivot)
            q_sort(numbers, left, pivot - 1);
        if (right > pivot)
            q_sort(numbers, pivot + 1, right);

    }

    void q_sort_desc(double* numbers, int left, int right)
    {
        double pivot;
        int l_hold = left;
        int r_hold = right;
        pivot = numbers[left];
        while (left < right)
        {
            while ((numbers[right] <= pivot) && (left < right))
                right--;
            if (left != right)
            {
                numbers[left] = numbers[right];
                left++;
            }
            while ((numbers[left] >= pivot) && (left < right))
                left++;
            if (left != right)
            {
                numbers[right] = numbers[left];
                right--;
            }
        }
        numbers[left] = pivot;
        pivot = left;
        left = l_hold;
        right = r_hold;
        if (left < pivot)
            q_sort_desc(numbers, left, pivot - 1);
        if (right > pivot)
            q_sort_desc(numbers, pivot + 1, right);

    }
    int b_search(double* arr, double key)
    {

        int left = 0, right = size;
        while (left <= right)
        {

            int middle = (left + right) / 2;

            if (key == arr[middle])
            {
                return middle;
            }
            else if (key < arr[middle])
            {

                right = middle - 1;
            }
            else
            {

                left = middle + 1;
            }
        }
        return -1;
    }

public:
    void sort_ascending()//сортировка по возрасатанию
    {


        q_sort(arr, 0, size - 1);
        print_array();

    }
    void sort_descending()//сортировка по убыванию
    {
        q_sort_desc(arr, 0, size - 1);
        print_array();
    }

    int binary_search(int key)//бинарный поиск
    {
        double* b_arr = new double[size];
        for (size_t i = 0; i < size; i++)
        {
            b_arr[i] = arr[i];
        }
        q_sort(b_arr, 0, size);
        int index = b_search(b_arr, key);
        if (index < 0)
        {
            cout << "warning: could not find this element: " << key << endl;
            return -1;
        }
        int index_arr = -1;
        for (size_t i = 0; i < size; i++)
        {
            if (b_arr[index] == arr[i])
            {
                index_arr = i;
            }
        }
        return index_arr;
    }

    ~d_array()
    {

    }
    void print_array()
    {
        for (int i = 0; i < size; i++)
        {
            printf("%.2f ", arr[i]);

        }
        printf("\n");
    }

};

int main()
{
    setlocale(0, "Rus");
    cout << "Создание массива размера 26 "<<endl;
    d_array array(26);
    cout << "Изменение размера памяти (9) "<<endl;
    array.reallocation(9);

    double ini = 345.00;
    cout << "Вставка элемента 345.00 на места с индексами 0..9 "<<endl;
    for (int i = 0; i < 5; i++)
    {
        array.Insert(ini, i);
        ini--;
    }

    cout.setf(ios::hex);
    cout << "Адрес 15 элемента в памяти: " << uppercase << hex << array.get_pointer(15) << endl;
    cout.setf(ios::dec);
    cout << "Размер массива: " << array.get_size() << endl;
    cout << "Добавление элемента 78 в конец массива" << endl;
    array.push_back(78);
    cout << "Удаление элемента по индексу 5" << endl;
    array.remove(5);
    cout << "Сортировка по возрастанию" << endl;
    array.sort_ascending();
    cout << "Сортировка по убыванию" << endl;
    array.sort_descending();
    cout << "Удаление элемента по индексу 6" << endl;
    array.remove(6);

    int element_to_find = 344;
    cout << "Индекс элемента " << element_to_find << " в массиве: " << array.binary_search(element_to_find) << endl;

}