aaaaaaaa

class Compare
{
public:
    virtual int CompareElements(void* e1, void* e2) = 0;
};

class CompareInt :public Compare
{
    int CompareElements(void* e1, void* e2)
    {
        int a = *((int*)e1);
        int b = *((int*)e2);

        return a > b ? 1 : (a == b ? 0 : -1);
    }
};

template<class T>

class ArrayIterator
{
private:

    T** Current;

public:
    ArrayIterator(T** p) { Current = p; }
    ArrayIterator<T>& operator ++ ()
    {
        Current++;
        return *this;
    }

    ArrayIterator<T>& operator -- ()
    {
        Current--;
        return *this;
    }

    bool operator= (ArrayIterator<T> & start)
    {
        Current = start.Current;
        return true;
    }

    bool operator!=(ArrayIterator<T> &start)
    {
        if (Current != (start.Current + 1))
            return true;
        return false;
    }

    T* GetElement() { return *Current; }

};

template<class T>

class Array

{

private:

    T** List; // lista cu pointeri la obiecte de tipul T*

    int Capacity; // dimensiunea listei de pointeri

    int Size; // cate elemente sunt in lista

public:

    Array() { Capacity = Size = 0; } // Lista nu e alocata, Capacity si Size = 0

    ~Array() {}; // destructor

    Array(int capacity)// Lista e alocata cu 'capacity' elemente
    {
        List = new T*[capacity];
        for (int i = 0; i < capacity; i++)
            List[i] = new T;
        Capacity = capacity;
        Size = 0;
    }

    Array(const Array<T>& vector)// constructor de copiere
    {
        Capacity = vector.Capacity;
        Size = vector.Size;
        List = new T*[Capacity];
        for (int i = 0; i < Capacity; i++)
            List[i] = new T;

        for (int k = 0; k < Size; k++)
            memcpy(List[k], vector.List[k++], sizeof(T));
    }



    T& operator[] (int index) // arunca exceptie daca index este out of range
    {
        if (index < 0 || index >= Size)
            throw "Index out of range";

        return *List[index];
    }

    const Array<T>& operator+=(const T& element) // adauga un element de tipul T la sfarsitul listei si returneaza this
    {
        if (Size >= Capacity - 1)
            throw "No more space";

        memcpy(List[Size++], &element, sizeof(T));
        //List[Size++] = (T*)element;
        return *this;
    }

    const Array<T>& Insert(int index, const T& element) // adauga un element pe pozitia index, retureaza this. Daca index e invalid arunca o exceptie
    {
        if (index < 0 || index > Size)
            throw std::out_of_range("OoR la Inserare");

        if (Size + 1 > Capacity)
            throw "Overflow.";


        for (int i = Size; i > index; i--)
            memcpy(List[i], List[i - 1], sizeof(T));

        memcpy(List[index], &element, sizeof(T));

        Size++;

        return *this;
    }

    const Array<T>& Insert(int index, const Array<T>& elemente) // adauga o lista pe pozitia index, retureaza this. Daca index e invalid arunca o exceptie
    {
        if (index < 0 || index > Size)
            throw std::out_of_range("OoR la Inserare");

        if (Size + elemente.Size > Capacity)
            throw "Overflow.";

        //0 1 2
        //1 2 3 - 12 11
        //12 11 1 2 3
        // 0  1 2 3 4
        for (int i = (Size + elemente.Size - 1); i > (index + elemente.Size - 1); i--)
            memcpy(List[i], List[i - elemente.Size], sizeof(T));


        for (int i = 0; i < elemente.Size; i++)
            memcpy(List[i + index], elemente.List[i], sizeof(T));

        Size += elemente.Size;

        return *this;
    }

    const Array<T>& Delete(int index) // sterge un element de pe pozitia index, returneaza this. Daca index e invalid arunca o exceptie
    {
        if (index < 0 || index >= Size)
            throw std::out_of_range("OoR la stergere");

        for (int i = index; i < Size; i++)
            memcpy(List[i], List[i + 1], sizeof(T));

        Size--;

        return *this;
    }



    const Array<T> & operator=(const Array<T> & vector)
    {
        Array<T> arr;
        arr.Capacity = vector.Capacity;
        arr.Size = vector.Size;
        arr.List = new T*[Capacity];
        for (int i = 0; i < Capacity; i++)
            arr.List[i] = new T;

        for (int k = 0; k < arr.Size; k++)
            memcpy(arr.List[k], vector.List[k], sizeof(T));

        return arr;
    }

    bool operator==(const Array<T> &vector)
    {
        if (Size != vector.Size)
            return false;

        for (int i = 0; i < Size; i++)
            if (List[i] != vector.List[i])
                return false;

        return true;
    }



    void Sort(); // sorteaza folosind comparatia intre elementele din T

    void Sort(int(*compare)(const T&, const T&)); // sorteaza folosind o functie de comparatie

    void Sort(Compare *comparator); // sorteaza folosind un obiect de comparatie



                                    // functii de cautare - returneaza pozitia elementului sau -1 daca nu exista

    int BinarySearch(const T& element) // cauta un element folosind binary search in Array
    {
        int st, dr, m;
        st = 0;
        dr = Size - 1;

        while (st <= dr)
        {
            m = (st + dr) / 2;
            if (element < *List[m])
                dr = m - 1;
            else if (element > *List[m])
                st = m + 1;
            else
                return m;
        }

        return -1;
    }

    int BinarySearch(const T& element, int(*compare)(const T&, const T&))//  cauta un element folosind binary search si o functie de comparatie
    {
        int st, dr, m, rez;
        st = 0;
        dr = Size - 1;

        while (st <= dr)
        {
            m = (st + dr) / 2;
            rez = compare(element, *List[m]);
            if (rez == -1)
                dr = m - 1;
            else if (rez == 1)
                st = m + 1;
            else
                return m;
        }

        return -1;
    }

    int BinarySearch(const T& element, Compare *comparator)//  cauta un element folosind binary search si un comparator
    {
        int st, dr, m, rez;
        st = 0;
        dr = Size - 1;

        while (st <= dr)
        {
            m = (st + dr) / 2;
            rez = comparator->CompareElements((void*)(&element), List[m]);
            if (rez == -1)
                dr = m - 1;
            else if (rez == 1)
                st = m + 1;
            else
                return m;
        }

        return -1;
    }


    //cautare normala, folosind operatorul de comparatie '=='
    int Find(const T& x) // cauta un element in Array - returneaza pozitia
    {
        for (int i = 0; i < Size; i++)
            if (x == *List[i])
                return i;
        return -1;
    }

    //cautare folosind ca argument o functie de comparatie.
    //Trebuie definita - in main - o functie de comparatie pentru fiecare tip(una pentru int, una pentru char etc) si data ca argument din main)
    //CONVENTIE: functia de compare returneaza: 0 - elemente egale, 1 - primul e mai mare, -1 - al doilea e mai mare
    int Find(const T& element, int(*compare)(const T&, const T&))//  cauta un element folosind o functie de comparatie
    {
        for (int i = 0; i < Size; i++)
            if (compare(element, *List[i]) == 0)
                return i;
        return -1;
    }

    //cautare folosind ca argument o clasa de comparatie
    //trebuie definita pentru fiecare TIP o clasa derivata din clasa compare care sa implementeze functia CompareElements
    //CONVENTIE: 0 = elemente egale, 1 = primul mai mare, -1 = al doilea mai mare
    int Find(const T& element, Compare *comparator)//  cauta un element folosind un comparator
    {
        for (int i = 0; i < Size; i++)
            if (comparator->CompareElements((void*)(&element), List[i]) == 0)
                return i;
        return -1;
    }



    int GetSize()
    {
        return Size;
    }

    int GetCapacity()
    {
        return Capacity;
    }



    ArrayIterator<T> GetBeginIterator()
    {
        ArrayIterator<T> it(List);
        return it;
    }

    ArrayIterator<T> GetEndIterator()
    {
        ArrayIterator<T> it(List + Size - 1);
        return it;
    }

};