#include <iostream>
using namespace std;

template <class T>
class Median{
private:
    T* array;
    unsigned numElements;
public:
    Median();
    unsigned size();
    void empty();
    void print();
    void insert(T& item);
    T median();
};
template<class T>
Median<T>::Median() {
    numElements = 0;
    array = new T[numElements];
}

template<class T>
unsigned Median<T>::size() {
    return numElements;
}

template<class T>
void Median<T>::empty() {
    if(array != NULL){
        delete[] array;
    }
    numElements = 0;
    array = new T[0];
}

template<class T>
void Median<T>::print() {
    for(unsigned i=0; i<Median::numElements; i++){
        cout<<array[i]<<"\t";
    }
}

template<class T>
void Median<T>::insert(T &item) {

    //create a copy temp array before increasing the size
    T* temp = new T[numElements];
    for(unsigned i=0; i<Median::numElements; i++) {
        temp[i] = array[i];
    }

    if(array != NULL){
        delete[] array;
    }
    numElements++;
    array = new T[numElements];

    //restore the available items
    if(numElements>2) {
        unsigned posToInsert = 0;
        bool isFound = false;
        if(item<=temp[0]){
            isFound = true;
        }else {
            for (unsigned i = 0; i < Median::numElements - 2; i++) {
                if (temp[i] <= item && temp[i + 1] >= item) {
                    posToInsert = i + 1;
                    isFound = true;
                }
            }
        }
        if(!isFound){
            posToInsert=numElements-1;
        }

        unsigned posNow = 0;
        bool  isInserted = false;
        for (unsigned i = 0; i < Median::numElements-1; i++) {
            if(i!=posToInsert){
                array[posNow++] = temp[i];
            }else{
                array[posNow++] = item;
                array[posNow++] = temp[i];
                isInserted = true;
            }
        }

        if(!isInserted){
            array[posNow] = item;
        }

    }else{
        if(numElements==1) {
            array[0] = item;
        } else{
            if(item<temp[0]){
                array[0] = item;
                array[1] = temp[0];
            }else{
                array[0] = temp[0];
                array[1] = item;
            }
        }
    }

}

template<class T>
T Median<T>::median() {
    return nullptr;
}



int main() {
    Median<int> median;

    int num = 8;
    median.insert(num);

    int num2 = 4;
    median.insert(num2);


    num = 9;
    median.insert(num);

    num = 5;
    median.insert(num);



    num = 2;
    median.insert(num);


    num = 3;
    median.insert(num);

    num = 1;
    median.insert(num);


    num = 13;
    median.insert(num);
    median.print();


    return 0;
}