Array

#ifndef ARRAY_H
#define ARRAY_H

#include <cstdlib>
#include <stdexcept>
#include <algorithm>
#include <functional>

template<typename T>
class Array
{
public:

    Array(const size_t, const T&);

    ~Array();

    size_t size() const;

    bool empty() const;

    T& get(size_t) const;

    T& operator[] (size_t) const;

    void push(const T&);

    T& pop();

    T& back() const;

    void insert(size_t, const T&);

    void unsafe_insert(size_t, const T&);

    T& erase(size_t);

    T& unsafe_erase(size_t);

    void clear();

    void sort();

    void sort_by(std::function<bool(const T&, const T&)>);

    bool is_sorted();

    size_t find(const T&) const;

    void resize(size_t, const T&);

    void unsafe_resize(size_t);

private:

    T* container_;
    size_t size_;
    bool sort_status_;

};



/**
 * Конструктор класса Array
 * Параметры:
 * @param size_ - текущий размер массива;
 * @param container_ - содержимое массива
 * @param sort_status_ - проверка массива на отсортированность
 * Весь Array инициализируется elem
 * Т.к. при выделении памяти под Array может возникнуть ошибка,
 * мы это проверяем
 */

template <typename T>
Array<T>::Array(const size_t len, const T& elem)
{
    size_ = len;
    container_ = static_cast<T*>(malloc(size_ * sizeof(T)));
    if (container_ == nullptr) throw std::runtime_error("memory allocation error");
    for (size_t i = 0; i < size_; i++) container_[i] = elem;
    sort_status_ = true;
}

/**
 *Деструктор для Array
 */

template<typename T>
Array<T>::~Array()
{
    free(container_);
}

/**
 * @return размер массива
 */

template<typename T>
size_t Array<T>::size() const
{
    const size_t len = size_;
    return len;
}

/**
 * Метод empty() проверяет Array на пустоту
 * @return размер > 0 ?
 */

template<typename T>
bool Array<T>::empty() const
{
    return size_ > 0;
}

/**
 * Метод push() добавляет @param value в конец
 * Т.к. функция realloc() может вернуть нулевой указатель
 * в случае неудачного перевыделения памяти,
 * мы делаем проверку на нулевой указатель
 * Так же осуществляется проверка на отсортированность
 */

template<typename T>
void Array<T>::push(const T& value)
{
    container_ = static_cast<T*>(realloc(container_, (++size_) * sizeof(T)));
    if (container_ == nullptr) throw std::runtime_error("memory reallocation error");
    container_[size_ - 1] = value;
    if (size_ == 1 || container_[size_ - 2] <= container_[size_ - 1]) sort_status_ = true;
    else sort_status_ = false;
}

/**
 * Метод pop() удаляет последний элемент Array.
 * Т.к. Array может быть пустым, мы проверяем его на пустоту.
 * Если массив пуст, то ошибка.
 * Т.к. функция realloc() может вернуть нулевой указатель
 * в случае неудачного перевыделения памяти,
 * мы делаем проверку на нулевой указатель.
 * @return удаленный элемент
 */

template<typename T>
T& Array<T>::pop()
{
    if (size_ == 0) throw std::out_of_range("array is empty");
    const T end = container_[size_ - 1];
    container_ = static_cast<T*>(realloc(container_, (--size_) * sizeof(T)));
    if (container_ == nullptr) throw std::runtime_error("memory reallocation error");
    return end;
}

/**
 * @return последний элемент Array,
 * если тот не пуст, иначе сообщает об ошибке
 */

template<typename T>
T& Array<T>::back() const
{
    if (size_ == 0) throw std::out_of_range("array is empty");
    else return container_[size_ - 1];
}

/**
 * Метод insert() добавляет @param value на место @param index.
 * index может выходить за пределы массива,
 * поэтому мы делаем проверку.
 * Т.к. функция realloc() может вернуть нулевой указатель
 * в случае неудачного перевыделения памяти,
 * мы делаем проверку на нулевой указатель.
 * Статуc отсортированности так же проверяется
 */

template<typename T>
void Array<T>::insert(const size_t index, const T& value)
{
    container_ = static_cast<T*>(realloc(container_, (++size_) * sizeof(T)));
    if (container_ == nullptr) throw std::runtime_error("memory reallocation error");
    if (index >= size_) throw std::out_of_range("index out of range");
    container_[size_ - 1] = value;
    for (size_t i = size_ - 1; i > index; i--) std::swap(container_[i], container_[i - 1]);
    if (sort_status_)
    {
        if (index >= 0 && index < size_ - 1) // 2 соседа
        {
            if (container_[index] >= container_[index - 1] && container_[index] <= container_[index + 1]) sort_status_ = true;
            else sort_status_ = false;
        }
        else if (index == size_ - 1) // последний
        {
            if (container_[index] >= container_[index - 1]) sort_status_ = true;
            else sort_status_ = false;
        }
        else // первый
        {
            if (container_[index] <= container_[index + 1]) sort_status_ = true;
            else sort_status_ = false;
        }
    }
    else is_sorted();
}

/**
 *  ___________________
 * |                   |
 * | НЕБЕЗОПАСНЫЙ КОД  |
 * |___________________|
 *
 * Метод добавляет на место @param index
 * значение @param value.
 * Никаких проверок, в том числе на отсортированность не выполняется.
 * Не рекомендуется использовать в безопасном коде
 */

template<typename T>
void Array<T>::unsafe_insert(const size_t index, const T& value)
{
    container_ = static_cast<T*>(realloc(container_, (++size_) * sizeof(T)));
    container_[size_ - 1] = value;
    for (size_t i = size_ - 1; i > index; i--) std::swap(container_[i], container_[i - 1]);
}

/**
 * Метод erase() удаляет элемент по @param index.
 * index может выходить за пределы массива,
 * поэтому мы делаем проверку.
 * Т.к. функция realloc() может вернуть нулевой указатель
 * в случае неудачного перевыделения памяти,
 * мы делаем проверку на нулевой указатель.
 * @return удалённый элемент
 */

template<typename T>
T& Array<T>::erase(const size_t index)
{
    if (index >= size_) throw std::out_of_range("index out of range");
    const T elem = container_[index];
    for (size_t i = index; i < size_ - 1; i++) std::swap(container_[i], container_[i + 1]);
    container_ = static_cast<T*>(realloc(container_, (--size_) * sizeof(T)));
    if (container_ == nullptr) throw std::runtime_error("memory reallocation error");
    is_sorted();
    return elem;
}

/**
 *  ___________________
 * |                   |
 * | НЕБЕЗОПАСНЫЙ КОД  |
 * |___________________|
 *
 * Метод удаляет элемент по @param index.
 * Не рекомендуется использовать в безопасном коде
 * @return удалённый элемент
 */

template<typename T>
T& Array<T>::unsafe_erase(const size_t index)
{
    const T elem = container_[index];
    for (size_t i = index; i < size_ - 1; i++) std::swap(container_[i], container_[i + 1]);
    container_ = static_cast<T*>(realloc(container_, (--size_) * sizeof(T)));
    return elem;
}

/*
 * Метод clear() очищает Array
 * И меняет значения
 * size_ на ноль и sort_status_ на true
 */

template<typename T>
void Array<T>::clear()
{
    size_ = 0;
    container_ = static_cast<T*>(realloc(container_, 0));
    if (container_ == nullptr) throw std::runtime_error("memory reallocation error");
    sort_status_ = true;
}

/*
 * Сортировка Array
 */

template<typename T>
void Array<T>::sort()
{
    if (sort_status_) return;
    std::sort(container_, container_ + size_);
    sort_status_ = true;
}

/**
 * !!! ДЛЯ ПРОДВИНУТЫХ ПОЛЬЗОВАТЕЛЕЙ !!!
 *
 * @param your_function - пользовательская функция для сортировки.
 * Функция задаётся как функция сравнения для std::sort,
 *
 * которая возвращает:
 * @return 1, когда arg1 > arg2
 * @return 0, когда arg1 == arg2
 * @return -1, когда arg1 < arg2
 *
 * И имеет параметры:
 * @param const void*
 * @param const void*
 */

template<typename T>
void Array<T>::sort_by(std::function<bool(const T&, const T&)> your_function)
{
    if (sort_status_) return;
    std::sort(container_, container_ + size_, your_function);
    sort_status_ = true;
}

/*
 * Поверка на отсортированность массива.
 * Если массив до этого был отсортированн,
 * то проверки не будет,
 * иначе будет тотальная проверка за O(n)
 */

template<typename T>
bool Array<T>::is_sorted()
{
    if (!sort_status_)
    {
        for (size_t i = 0; i < size_ - 1; i++)
        {
            if (container_[i] > container_[i + 1])
            {
                sort_status_ = false;
                return false;
            }
        }
        sort_status_ = true;
        return true;
    }
    return true;
}

/**
 * Метод find() ищет @param value в Array
 * Если нашли значение, то @return индекс
 * Иначе @return размер массива + 1
 */

template<typename T>
size_t Array<T>::find(const T& value) const
{
    return std::find(container_, container_ + size_, value);
}

/**
 * Метод resize() изменяет размер Array на @param new_size
 * Если новый размер больше предыдущего,
 * то новые элементы инициализируются
 * @param elem, иначе удаляются
 * Также осуществляется проверка на отсортированность
 */

template<typename T>
void Array<T>::resize(const size_t new_size, const T& elem)
{
    container_ = static_cast<T*>(realloc(container_, new_size * sizeof(T)));
    if (container_ == nullptr) throw std::runtime_error("memory reallocation error");
    if (new_size > size_) for (size_t i = size_; i < new_size; i++) container_[i] = elem;
    if (new_size > size_)
    {
        if (elem >= container_[size_ - 1]) sort_status_ = true;
        else sort_status_ = false;
    }
    size_ = new_size;
}

/**
 *  ___________________
 * |                   |
 * | НЕБЕЗОПАСНЫЙ КОД  |
 * |___________________|
 *
 * Метод unsafe_resize() изменяет размер Array на @param new_size
 * Методом не рекомендуется пользоваться в безопасном коде,
 * т.к. при увеличении размера, новые элементы
 * становятся неинициализированными,
 * а статус сортировки не проверяется
 */

template<typename T>
void Array<T>::unsafe_resize(const size_t new_size)
{
    container_ = static_cast<T*>(realloc(container_, new_size * sizeof(T)));
    if (container_ == nullptr) throw std::runtime_error("memory reallocation error");
    size_ = new_size;
}

/**
 * Метод get() возвращает ссылку на элемент
 * массива по @param index.
 * Т.к. index может выходить за пределы массива,
 * мы проверяем это
 */

template<typename T>
T& Array<T>::get(const size_t index) const
{
    if (index >= size_) throw std::out_of_range("index out of range");
    return container_[index];
}

/*
 * Оператор [] делает всё то, что и метод get()
 */

template<typename T>
T& Array<T>::operator[](const size_t index) const
{
    return get(index);
}

#endif // ARRAY_H