#include <iostream>
using namespace std;

class Entry {
private:
    string _name; // name
    string _room; // room
public:
    Entry() = default; // for allocation
    Entry(string n, string r) : _name{n}, _room{r} {};
    string name() { return _name; }
    string room() { return _room; }
    void set_room(string r) { _room = r; }
};

class AddressBook {
private:
    int size = 0; // size
    Entry* entries; // pointer to beginning of memory block for entries
    void sort_entries();
public:
    class EntryDoesNotExist{};
    AddressBook() : entries{new Entry[0]} {};
    ~AddressBook() { delete[] entries; }
    void add(string name, string room);
    void move(string name, string room);
    void remove(string name);
    void clear();
    string find(string name);
    void print_sorted();
};

void AddressBook::add(string name, string room)
{
    size++; // increment size
    Entry* extended = new Entry[size]; // allocate size+1 Entries on heap
    if (!extended) throw runtime_error("Could not allocate memory");
    for (int i = 0; i < size - 1; i++) {
        extended[i] = entries[i]; // copy old Entries over to a new block
    }
    Entry e{name, room};
    extended[size - 1] = e;
    delete[] entries; // deallocate old block
    entries = extended; // point entries to a new block
}

void AddressBook::remove(string name)
{
    string _ = find(name); // only for error handling, return value is not needed

    size--; // decrement size
    Entry* reduced = new Entry[size]; // allocate size-1 Entries on heap
    if (!reduced) throw runtime_error("Could not allocate memory");
    for (int i = 0; i < size; i++) {
        if (entries[i].name() == name) {
            reduced[i] = entries[i+1]; // skip over the record to remove
        } else {
            reduced[i] = entries[i];
        }
    }
    delete[] entries; // deallocate original entries
    entries = reduced; // point entries to a reduced block
}


string AddressBook::find(string name)
{
    for (int i = 0; i < size; i++)
        if (entries[i].name() == name) return entries[i].room();
    throw EntryDoesNotExist();
}

void AddressBook::move(string name, string room)
{
    for (int i = 0; i < size; i++)
        if (entries[i].name() == name) entries[i].set_room(room);
}

void AddressBook::print_sorted()
{
    sort_entries();
    for (int i = 0; i < size; i++) {
        cout << entries[i].name() << " is in room " << entries[i].room() << endl;
    }
}

void AddressBook::clear()
{
    size = 0;
    Entry* empty = new Entry[size];
    delete[] entries; // deallocate original entries
    entries = empty; // point to new empty block
}

// Bubble sort from sratch. We sort in place by swapping through pointers.
// I know it's not ideal, but in our case we don't care
// about the specific ordering of elements inside the structure,
// so might as well re-sort them before each print.
// (it seems natural to me to make the print function an instance method,
// so it maps better to the interface)
void AddressBook::sort_entries()
{
    bool swap_needed = true; // initial pass
    for (int i = 1; i <= size && swap_needed; i++) {
        swap_needed = false; // break early if no more swaps needed
        for (int j = 0; j < size-1; j++) {
            // Two passes to sort by name and by room
            if (entries[j].name() > entries[j+1].name()) {
                swap(entries[j+1], entries[j]);
                swap_needed = true;
            }
            if (entries[j].room() > entries[j+1].room()) {
                swap(entries[j+1], entries[j]);
                swap_needed = true;
            }
        }
    }
}

void operate_on_input(AddressBook& ab)
{
    while(cin) {
        cout << "> ";
        string operation;
        cin >> operation;
        if (operation == "add") {
            string name, room;
            cin >> name >> room;
            ab.add(name, room);
        } else if (operation == "list") {
            ab.print_sorted();
        } else if (operation == "remove") {
            string name;
            cin >> name;
            ab.remove(name);
        } else if (operation == "move") {
            string name, room;
            cin >> name >> room;
            ab.move(name, room);
        } else if (operation == "find") {
            string name;
            cin >> name;
            string room = ab.find(name);
            cout << name << " is in room " << room << endl;
        } else if (operation == "clear") {
            ab.clear();
        } else if (operation == "exit") {
            break;
        }
    }
}

int main()
{
    AddressBook ab;
    try {
        operate_on_input(ab);
    } catch (AddressBook::EntryDoesNotExist) {
        cerr << "error: entry does not exist" << endl;
    }

    return 0;
}