#include <iostream>
#include <cstring>

using namespace std;

class MyString {
public:
    MyString(const char * s);
    MyString();
    ~MyString();
    char* getStr() const;
    friend ostream & operator<<(ostream& os, const MyString &st);
    MyString & operator=(const MyString& originalString);
private:
    char *str;
    int len;
};

MyString::MyString(const char *s) {
    len = strlen(s);
    str = new char [len + 1];
    strcpy(str, s);
}

MyString::MyString() {
    len = 4;
    str = new char [4];
    strcpy(str, "");
}

MyString::~MyString() {
    cout << "Nicim MyString" << endl;
    delete [] str;
}

char* MyString::getStr() const {
    return str;
}

ostream& operator<<(ostream& os, const MyString &st) {
    os << st.str;
    return os;
}

class MyVector {
public:
    MyVector(const MyString& string);
    MyVector();
    ~MyVector();
    void pushBack(const MyString&);
    int getLen() const;
    void insert(int position, const MyString& newString);
    friend ostream & operator<<(ostream& os, const MyVector &vct);
    MyString operator[](int);
    int binarySearch(const MyString&) const;
private:
    int m_len;
    int m_maxSize;
    MyString *m_array;
    void allocMem();
};

MyVector::MyVector(){
    m_maxSize = 2;
    m_array = new MyString[m_maxSize];
    m_len = 0;
}

MyVector::~MyVector() {
    cout << "Nicim MyVector" << endl;
    delete [] m_array;
}

void MyVector::pushBack(const MyString &tmpString) {
    if (m_len +1 > m_maxSize) {
        allocMem();
    }
    m_array[m_len] = tmpString;
    m_len++;
}

int MyVector::getLen() const {
    return m_len;
}

MyString MyVector::operator[](int i) {
    return m_array[i];
}

MyString& MyString::operator=(const MyString& originalString) {
    if (&originalString == this) return *this;
    delete [] str;
    len = originalString.len;
    str = new char [len+1];
    memcpy(str, originalString.str, len+1);

    return *this;
}

void MyVector::insert(int position, const MyString& newString) {
    if (position == -1) return;
    MyString* tmp = new MyString[m_len+1];
    for (int i = 0; i < m_len+1; i++) {
        if (i < position) tmp[i] = m_array[i];
        else if (i == position) {
            tmp[i] = newString;
        } else if (i > position) {
            tmp[i] = m_array[i-1];
        }
    }
    m_len++;
    delete [] m_array;
    // if (m_len > m_maxSize) {
    //     allocMem();
    // }
    m_array = new MyString[m_len+1];
    for (int i = 0; i < m_len; i++) {
        m_array[i] = tmp[i];
    }
    delete [] tmp;

}

void MyVector::allocMem(){
    m_maxSize = m_len*2;
    MyString* tmp = new MyString[m_len + 1];
    for (int i = 0; i < m_len; i++) {
        tmp[i] = m_array[i];
    }
    delete [] m_array;
    m_array = new MyString[m_maxSize];
    for(int i = 0; i < m_len; i++)
        m_array[i] = tmp[i];
    delete [] tmp;
}

int MyVector::binarySearch(const MyString& newString) const {
    int begin = 0, end = m_len, middle = 0;
    bool found = false;
    while (begin <= end) {
        middle = begin + (end - begin) / 2;
        cout << m_array[middle] << endl;
        if (strcmp(m_array[middle].getStr(), "") == 0) {
            return begin;
        }
        int comp = strcmp(m_array[middle].getStr(), newString.getStr());
        if(comp == 0){
            found = true;
            break;
        }
        else if(comp < 0)
            begin = middle + 1;
        else
            end = middle - 1;
    }

    if(found){
        while(middle >= 0 && strcmp(newString.getStr(), m_array[middle].getStr()))
            middle--;
        return middle;
    }

    return -1;
}

ostream& operator<<(ostream& os, const MyVector &vct) {
    for (int i = 0; i < vct.m_len; i++) {
        os << vct.m_array[i] << " ";
    }
    os << endl;

    return os;
}

int main(int argc, char const *argv[])
{
    MyString mujString("aa");
    MyString mujString2("bb");
    MyString mujString3("cc");
    MyString mujString4("a b");
    MyString mujString5("bvs");
    MyString mujString6("f as");


    MyVector mujVector;
    mujVector.insert(mujVector.binarySearch(mujString), mujString);
    cout<<mujVector<<endl;
    mujVector.insert(mujVector.binarySearch(mujString2), mujString2);
    cout<<mujVector<<endl;
    mujVector.insert(mujVector.binarySearch(mujString3), mujString3);
    cout<<mujVector<<endl;
    mujVector.insert(mujVector.binarySearch(mujString4), mujString4);
    cout<<mujVector<<endl;
    mujVector.insert(mujVector.binarySearch(mujString5), mujString5);
    cout<<mujVector<<endl;
    mujVector.insert(mujVector.binarySearch(mujString6), mujString6);
    cout<<mujVector<<endl;
    cout<<mujVector<<endl;

    return 0;
}