#include <iostream>
#include <map>
#include <string>
#include <functional>

using namespace std;

class ConsistentHashing {
private:
    // hash position -> server name
    map<size_t, string> ring;

    size_t getHash(const string& value) {
        return hash<string>{}(value);
    }

public:
    void addServer(const string& server) {
        size_t hashValue = getHash(server);

        ring[hashValue] = server;

        cout << "Added " << server
             << " at position " << hashValue << "\n";
    }

    void removeServer(const string& server) {
        size_t hashValue = getHash(server);

        ring.erase(hashValue);

        cout << "Removed " << server << "\n";
    }

    string getServer(const string& key) {
        if (ring.empty())
            return "No servers available";

        size_t keyHash = getHash(key);

        // Find the first server clockwise
        auto it = ring.lower_bound(keyHash);

        // If we reached the end of the ring,
        // wrap around to the first server
        if (it == ring.end()) {
            it = ring.begin();
        }

        return it->second;
    }

    void printRing() {
        cout << "\n--- Hash Ring ---\n";

        for (auto& [hashValue, server] : ring) {
            cout << hashValue
                 << " -> "
                 << server << "\n";
        }
    }
};

int main() {

    ConsistentHashing ch;

    // Add servers
    ch.addServer("Server-A");
    ch.addServer("Server-B");
    ch.addServer("Server-C");

    ch.printRing();

    cout << "\n--- Key Mapping ---\n";

    string keys[] = {
        "user_101",
        "user_102",
        "user_103",
        "user_104",
        "user_105"
    };

    for (const string& key : keys) {
        cout << key
             << " -> "
             << ch.getServer(key)
             << "\n";
    }

    // Add a new server
    cout << "\nAdding Server-D...\n\n";

    ch.addServer("Server-D");

    cout << "--- Key Mapping After Adding Server-D ---\n";

    for (const string& key : keys) {
        cout << key
             << " -> "
             << ch.getServer(key)
             << "\n";
    }

    return 0;
}