//ALG ARRAY HEADER
#ifndef _ALGORITHMARRAY_H_
#define _ALGORITHMARRAY_H_

#define WRONG_POS -9999
#include <iostream>
#include <cstdlib>

template <typename T>
class AlgorithmArray
{
    private:

    T *array;
    int length;

    bool checkPos(int pos);
    void resizeArray();

    public:

    AlgorithmArray();
    AlgorithmArray(int length);
    AlgorithmArray(const AlgorithmArray<T> &array);
    ~AlgorithmArray();

    void setValue       (int pos, T value);
    void exchange       (int pos1, int pos2);
    void removeElement  (int pos);
    void print          ();
    T    getValue       (int pos);
    int  getLength      ();
};




#endif

//ALG ARRAY IMPL
#include "AlgorithmArray.h"

template <typename T>
AlgorithmArray<T>::AlgorithmArray() : AlgorithmArray(1)
{

}

template <typename T>
AlgorithmArray<T>::AlgorithmArray(int length)
{
    this->array  = new T[length + 1];
    this->length = length;
}

template <typename T>
AlgorithmArray<T>::AlgorithmArray(const AlgorithmArray<T> &array)
{
    this->array  = array.array;
    this->length = array.length;
}

template <typename T>
AlgorithmArray<T>::~AlgorithmArray()
{
    // delete[] this->array;
}

template <typename T>
bool AlgorithmArray<T>::checkPos(int pos)
{
    return (pos > this->length || pos < 0) ? false : true;
}

template <typename T>
void AlgorithmArray<T>::resizeArray()
{
    T *temp = new T[this->length * 2 + 1];

    for (int i = 1; i <= this->length; i++)
    {
        temp[i] = this->array[i];
    }

    delete[] this->array;

    this->array = temp;
    this->length = 2 * this->length;
}

template <typename T>
void AlgorithmArray<T>::setValue(int pos, T value)
{
    if (!checkPos(pos)) {
        this->resizeArray();
    }
    this->array[pos] = value;
}

template <typename T>
void AlgorithmArray<T>::exchange(int pos1, int pos2)
{
    T temp = this->array[pos1];
    this->array[pos1] = this->array[pos2];
    this->array[pos2] = temp;
}

template <typename T>
void AlgorithmArray<T>::removeElement(int pos)
{
    if (checkPos(pos)) {
        for (int i = pos; i < length; i++)
            this->array[i] = this->array[i+1];
    }
}

template <typename T>
void AlgorithmArray<T>::print()
{
    std::cout << "Array: ";

    for (int i = 1; i <= this->length; i++)
    {
        std::cout << this->array[i] << " ";
    }
    std::cout << std::endl;
}

template <typename T>
T AlgorithmArray<T>::getValue(int pos)
{
    if (checkPos(pos)) {
        return this->array[pos];
    } else {
        return WRONG_POS;
    }
}

template <typename T>
int AlgorithmArray<T>::getLength()
{
    return this->length;
}

template class AlgorithmArray<int>;

//INSERTION SORT HEADER

#ifndef _INSERTIONSORT_H_
#define _INSERTIONSORT_H_

#include <iostream>

#include "../algorithmarray/AlgorithmArray.h"

template <typename T>
class InsertionSort
{
    private:
    AlgorithmArray<T> array;

    public:

    InsertionSort();
    InsertionSort(int length);
    InsertionSort(AlgorithmArray<T> array);

    void sort();
    AlgorithmArray<T> getArray();
};

#endif

//INSERTION SORT IMPL

#include "InsertionSort.h"

template <typename T>
InsertionSort<T>::InsertionSort()
{
    this->array = AlgorithmArray<T>();
}

template <typename T>
InsertionSort<T>::InsertionSort(int length)
{
    this->array = AlgorithmArray<T>(length);
}

template <typename T>
InsertionSort<T>::InsertionSort(AlgorithmArray<T> array)
{
    AlgorithmArray<T> newArray = AlgorithmArray<T>(array.getLength());

    for (int i = 1; i <= array.getLength(); i++)
    {
        newArray.setValue(i, array.getValue(i));
    }
    this->array = newArray;
}

template <typename T>
void InsertionSort<T>::sort()
{
    int key, i;

    for (int j = 2; j <= this->array.getLength(); j++)
    {
        key = this->array.getValue(j);
        i = j - 1;

        while (i > 0 && this->array.getValue(i) > key)
        {
            this->array.setValue(i + 1, this->array.getValue(i));
            i = i - 1;
        }

        this->array.setValue(i + 1, key);
    }
}

template <typename T>
AlgorithmArray<T> InsertionSort<T>::getArray()
{
    return this->array;
}

template class InsertionSort<int>;

//MAIN

#include <iostream>
#include "InsertionSort.h"

int main(void)
{
    AlgorithmArray<int> array = AlgorithmArray<int>();

    array.setValue(1, 10);
    array.setValue(2, -3);
    array.setValue(3, 50);
    array.setValue(4, 40);
    array.setValue(5, 70);
    array.setValue(6, -9);
    array.setValue(7, 20);

    array.print();

    InsertionSort<int> alg(array);

    alg.sort();

    alg.getArray().print();

    return 0;
}