#include <iostream>
#include <conio.h>
#include <exception>

using namespace std;

class exceptionDivide : public exception{
    virtual const char* what() const throw(){
        return "ERROR: DIVIDE-IMPOSSIBLE";
    }
};

template <typename Type>
class Array {
    Type** List; // lista cu pointeri la obiecte de tipul T*

    int Capacity; // dimensiunea listei de pointeri

    int Size; // cate elemente sunt in lista

public:
    Array(); // Lista nu e alocata, Capacity si Size = 0

    void Print();

    Type& operator[] (int index); // arunca exceptie daca index este out of range

    const Array<Type>& Insert(int index, Type &newElem); // adauga un element pe pozitia index, retureaza this. Daca index e invalid arunca o exceptie

    void Sort(bool(*compare)(const Type, const Type)); // sorteaza folosind o functie de comparatie

    int Find(const Type& elem); // cauta un element in Array

    int BinarySearch(Type & elem); // cauta un element folosind binary search in Array

    int GetSize();
    int GetCapacity();
};

template <typename Type>
bool isLesser(const Type arg1,const Type arg2) {
    return arg1 < arg2;
}

int main() {
    Array<int> arr;
    int x = 3;
    int y = 5;
    int z = 4;
    int t = 6;
    try {
        arr.Insert(0, x);
        arr.Insert(1, y);
        arr.Insert(2, x);
        arr.Insert(1, y);
        arr.Insert(2, x);
        arr.Insert(2, t);
        arr.Insert(3, x);
        arr.Insert(95, x);
    }
    catch(exception e){
        cout << e.what();
    }
    arr.Print();
    cout << arr.Find(y) << "\n";

    arr.Sort(isLesser);
    arr.Print();
    cout << arr.BinarySearch(y) << "\n";
    _getch();
}

template<typename Type>
Array<Type>::Array(){
    List = nullptr;
    Capacity = 0;
    Size = 0;
}

template<typename Type>
void Array<Type>::Print(){
    for (int i = 0; i < Size; i++) {
        cout << *List[i] << " ";
    }
    cout << "\n";
}

template<typename Type>
Type & Array<Type>::operator[](int index){
    if (index < 0 or index >= Size) {
        throw exception("Signal 11");
    }
    return List[index];
}

template<typename Type>
const Array<Type>& Array<Type>::Insert(int index, Type & newElem){
    if (Capacity == 0) {
        List = new Type*[100];
        Capacity = 100;
        Size = 0;
    }

    if (index > Size or index < 0) {
        throw exception("Signal 11\n");
    }

    if (index != Size) {
        for (int i = Size; i >= index; i--) {
            List[i + 1] = List[i];
        }
    }

    List[index] = &newElem;
    Size++;

    return *this;
}

template<typename Type>
void Array<Type>::Sort(bool(*compare)(const Type, const Type)){
    for (int i = 0; i < Size; i++) {
        for (int j = i + 1; j < Size; j++) {
            if (!compare(*List[i], *List[j])) {
                auto aux = List[i];
                List[i] = List[j];
                List[j] = aux;
            }
        }
    }
}

template<typename Type>
int Array<Type>::Find(const Type & elem){
    for (int i = 0; i < Size; i++) {
        if (&elem == List[i]) {
            return i;
        }
    }
    return Size;
}

template<typename Type>
int Array<Type>::BinarySearch(Type & elem){
    int left = 0;
    int right = Size - 1;
    int middle = (left + right - 1) / 2;

    while (left != right) {
        if (List[middle] == &elem)
            return middle;
        if (*List[middle] > elem)
            right = middle;
        else
            left = middle;
        middle = (left + right - 1) / 2;
    }
    return -1;
}

template<typename Type>
int Array<Type>::GetSize(){
    return Size;
}

template<typename Type>
int Array<Type>::GetCapacity(){
    return Capacity;
}