/*
  Problem 380. Insert Delete GetRandom
  
  Implement the RandomizedSet class:

    * RandomizedSet() Initializes the RandomizedSet object.

    * bool insert(int val) Inserts an item val into the set if not
    * present. Returns true if the item was not present, false
    * otherwise.      

    * bool remove(int val) Removes an item val from the set if
    * present. Returns true if the item was present, false otherwise.    

    * int getRandom() Returns a random element from the current set of
    * elements (it's guaranteed that at least one element exists when
    * this method is called). Each element must have the same
    * probability of being returned.

    You must implement the functions of the class such that each function
    works in average O(1) time complexity.

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]
*/

#include <bits/stdc++.h>
using namespace std;

class RandomizedSet {
public:
    unordered_set<int> m_set;
    RandomizedSet() {
    }
    
    bool insert(int val) {
        if (m_set.count(val))
            return false;
        m_set.insert(val);        
        return true;        
    }
    
    bool remove(int val) {
        if (!m_set.count(val))
            return false;
        m_set.erase(val);
        return true;
    }
    
    int getRandom() {
        auto beginIter = m_set.begin();
        int n = rand() % m_set.size();
        return *next(beginIter, n);        
    }
};

string tr(bool val) { return val == true ? "true" : "false"; }
string tr(int val) { return to_string(val); }
enum struct Action : int32_t { Insert = 0, Remove, GetRandom };    
string ToString(Action a)
{
    switch (a)
    {
        case Action::Insert: return "Insert";
        case Action::Remove: return "Remove";
        case Action::GetRandom: return "GetRandom";
        default: return "Unknown Action";
    }
}

int main(void)
{
    vector<pair<vector<tuple<Action,int>>,string>> testCases = { // vector
        { // pair
            { // vector of tuple
                {Action::Insert,    1},
                {Action::Remove,    2},
                {Action::Insert,    2},
                {Action::GetRandom, 0},
                {Action::Remove,    1},
                {Action::Insert,    2},
                {Action::GetRandom, 0},
            },
            // expected
            "[null, true, false, true, 2, true, false, 2]",
        },
    };

    for (auto i: testCases) // vector of pairs
    {
        vector<string> output;
        RandomizedSet rs; output.push_back("null");
        string expected = i.second;
        for (auto tc: i.first) // vector of tuple<Action,int>
        {            
            Action a = get<0>(tc);
            int arg = get<1>(tc);
            switch (a)
            {
                case Action::Insert: output.push_back(tr(rs.insert(arg))); break;            
                case Action::Remove: output.push_back(tr(rs.remove(arg))); break;            
                case Action::GetRandom: output.push_back(tr(rs.getRandom())); break;
            }
        }
        cout << "  result: [";
        for (size_t i = 0; i < output.size(); i++)
            cout << output.at(i) << (i < output.size() - 1 ? ", " : "");
        cout << "]\n";
        cout << "expected: " << expected << endl;
        cout << "----------------------------------------------------\n";        
    }
}