double distanceInKilometers(Location l) {
    double earthRadiusKm = 6371.0;
    double dLat = degToRad(l.getLat() - lat);
    double dLon = degToRad(l.getLong() - lon);
    
    double a = sin(dLat/2) * sin(dLat/2) +
               cos(degToRad(lat)) * cos(degToRad(l.getLat())) *
               sin(dLon/2) * sin(dLon/2);
               
    double c = 2 * atan2(sqrt(a), sqrt(1-a));
    return earthRadiusKm * c;
}

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <sstream>
#include <iomanip>

using namespace std;

// Forward Declarations
class User;
class ChatRoom;

// ==================== 1. NOTIFICATION SUBSYSTEM (OBSERVER) ====================
class NotificationObserver {
public:
    virtual void update(const string& message) = 0;
    virtual ~NotificationObserver() {}
};

class UserNotificationObserver : public NotificationObserver {
private:
    string userId;
public:
    explicit UserNotificationObserver(string id) : userId(move(id)) {}
    void update(const string& message) override {
        cout << "[Notification to User " << userId << "]: " << message << endl;
    }
};

class NotificationService {
private:
    map<string, NotificationObserver*> observers;
    NotificationService() {}
    static NotificationService* instance;
public:
    static NotificationService* getInstance() {
        if (!instance) instance = new NotificationService();
        return instance;
    }

    void registerObserver(const string& userId, NotificationObserver* observer) {
        observers[userId] = observer;
    }

    void removeObserver(const string& userId) {
        observers.erase(userId);
    }

    void notifyUser(const string& userId, const string& message) {
        if (observers.find(userId) != observers.end()) {
            observers[userId]->update(message);
        }
    }

    void notifyAll(const string& message) {
        for (auto& pair : observers) {
            pair.second->update(message);
        }
    }
};
NotificationService* NotificationService::instance = nullptr;

// ==================== 2. MODELS & ENUMS ====================
enum class Gender { MALE, FEMALE, NON_BINARY, OTHER };
enum class Swipe { LEFT, RIGHT };

string genderToString(Gender g) {
    switch(g) {
        case Gender::MALE: return "Male";
        case Gender::FEMALE: return "Female";
        case Gender::NON_BINARY: return "Non-Binary";
        default: return "Other";
    }
}

class Location {
private:
    double lat;
    double lon;
    double degToRad(double deg) { return deg * M_PI / 180.0; }
public:
    Location(double lat = 0.0, double lon = 0.0) : lat(lat), lon(lon) {}
    double getLat() const { return lat; }
    double getLon() const { return lon; }

    double distanceInKilometers(const Location& l) const {
        double earthRadiusKm = 6371.0;
        double dLat = (l.lat - lat) * M_PI / 180.0;
        double dLon = (l.lon - lon) * M_PI / 180.0;
        double a = sin(dLat / 2) * sin(dLat / 2) +
                   cos(lat * M_PI / 180.0) * cos(l.lat * M_PI / 180.0) *
                   sin(dLon / 2) * sin(dLon / 2);
        double c = 2 * atan2(sqrt(a), sqrt(1 - a));
        return earthRadiusKm * c;
    }
};

class Interest {
private:
    string name;
    string category;
public:
    Interest(string name, string category) : name(move(name)), category(move(category)) {}
    string getName() const { return name; }
    string getCategory() const { return category; }
};

class UserPreferences {
private:
    vector<Gender> interestedInGenders;
    int minAge;
    int maxAge;
    double maxDistanceKm;
    vector<string> preferredInterestNames;
public:
    UserPreferences(vector<Gender> genders, int minA, int maxA, double maxDist, vector<string> interests)
        : interestedInGenders(move(genders)), minAge(minA), maxAge(maxA), maxDistanceKm(maxDist), preferredInterestNames(move(interests)) {}

    bool isGenderAllowed(Gender g) const {
        return find(interestedInGenders.begin(), interestedInGenders.end(), g) != interestedInGenders.end();
    }
    bool isAgeAllowed(int age) const { return age >= minAge && age <= maxAge; }
    bool isDistanceAllowed(double dist) const { return dist <= maxDistanceKm; }
};

class Message {
private:
    string senderId;
    string content;
    time_t timestamp;
public:
    Message(string sId, string cnt) : senderId(move(sId)), content(move(cnt)), timestamp(time(nullptr)) {}
    string getSenderId() const { return senderId; }
    string getContent() const { return content; }
    string getFormattedTime() const {
        char buf[80];
        struct tm timeinfo;
        localtime_r(&timestamp, &timeinfo);
        strftime(buf, sizeof(buf), "%Y-%m-%d %H:%M:%S", &timeinfo);
        return string(buf);
    }
};

class ChatRoom {
private:
    string roomId;
    vector<string> participantIds;
    vector<Message> messages;
public:
    ChatRoom(string rId, string u1, string u2) : roomId(move(rId)) {
        participantIds.push_back(u1);
        participantIds.push_back(u2);
    }

    void addMessage(const string& senderId, const string& content) {
        messages.emplace_back(senderId, content);
    }

    void displayChat() const {
        cout << "\n--- Chat Room [" << roomId << "] ---" << endl;
        for (const auto& msg : messages) {
            cout << "[" << msg.getFormattedTime() << "] User " << msg.getSenderId() << ": " << msg.getContent() << endl;
        }
        cout << "-----------------------------------" << endl;
    }
};

class UserProfile {
private:
    string name;
    int age;
    Gender gender;
    string bio;
    vector<string> photos;
    vector<Interest> interests;
    Location location;
public:
    UserProfile(string name, int age, Gender gender, string bio, Location loc)
        : name(move(name)), age(age), gender(gender), bio(move(bio)), location(loc) {}

    void addInterest(const Interest& i) { interests.push_back(i); }
    void addPhoto(const string& p) { photos.push_back(p); }
    
    string getName() const { return name; }
    int getAge() const { return age; }
    Gender getGender() const { return gender; }
    Location getLocation() const { return location; }
    vector<Interest> getInterests() const { return interests; }

    void display() const {
        cout << "Profile: " << name << ", " << age << " (" << genderToString(gender) << ")" << endl;
        cout << "Bio: " << bio << endl;
        cout << "Interests: ";
        for (const auto& i : interests) cout << i.getName() << " ";
        cout << endl;
    }
};

class User {
private:
    string userId;
    UserProfile profile;
    UserPreferences preferences;
    map<string, Swipe> swipeHistory;
    NotificationObserver* observer;
public:
    User(string id, UserProfile prof, UserPreferences prefs)
        : userId(move(id)), profile(move(prof)), preferences(move(prefs)) {
        observer = new UserNotificationObserver(userId);
        NotificationService::getInstance()->registerObserver(userId, observer);
    }

    ~User() {
        NotificationService::getInstance()->removeObserver(userId);
        delete observer;
    }

    string getId() const { return userId; }
    UserProfile& getProfile() { return profile; }
    UserPreferences& getPreferences() { return preferences; }

    void swipe(string targetId, Swipe action) {
        swipeHistory[targetId] = action;
    }

    bool hasLiked(string targetId) const {
        auto it = swipeHistory.find(targetId);
        return it != swipeHistory.end() && it->second == Swipe::RIGHT;
    }

    bool hasInteractedWith(string targetId) const {
        return swipeHistory.find(targetId) != swipeHistory.end();
    }

    void displayProfile() const {
        profile.display();
    }
};

// ==================== 3. GEOSPATIAL & LOCATION STRATEGY ====================
class LocationStrategy {
public:
    virtual vector<User*> findNearby(Location loc, double maxDistKm, const vector<User*>& allUsers) = 0;
    virtual ~LocationStrategy() {}
};

class BasicLocationStrategy : public LocationStrategy {
public:
    vector<User*> findNearby(Location loc, double maxDistKm, const vector<User*>& allUsers) override {
        vector<User*> result;
        for (User* u : allUsers) {
            double dist = loc.distanceInKilometers(u->getProfile().getLocation());
            if (dist <= maxDistKm) {
                result.push_back(u);
            }
        }
        return result;
    }
};

class LocationService {
private:
    LocationStrategy* strategy;
    LocationService() : strategy(new BasicLocationStrategy()) {}
    static LocationService* instance;
public:
    static LocationService* getInstance() {
        if (!instance) instance = new LocationService();
        return instance;
    }
    void setStrategy(LocationStrategy* s) {
        delete strategy;
        strategy = s;
    }
    vector<User*> findNearbyUsers(Location loc, double maxDist, const vector<User*>& allUsers) {
        return strategy->findNearby(loc, maxDist, allUsers);
    }
};
LocationService* LocationService::instance = nullptr;

// ==================== 4. MATCHING & SCORING ENGINE (CHAIN OF RESPONSIBILITY) ====================
class Matcher {
public:
    virtual double calculateScore(User* u1, User* u2) = 0;
    virtual ~Matcher() {}
};

class BasicDetailsMatcher : public Matcher {
public:
    double calculateScore(User* u1, User* u2) override {
        // Verify cross-preferences
        bool u1LikesU2Gender = u1->getPreferences().isGenderAllowed(u2->getProfile().getGender());
        bool u2LikesU1Gender = u2->getPreferences().isGenderAllowed(u1->getProfile().getGender());
        if (!u1LikesU2Gender || !u2LikesU1Gender) return 0.0;

        bool u1LikesU2Age = u1->getPreferences().isAgeAllowed(u2->getProfile().getAge());
        bool u2LikesU1Age = u2->getPreferences().isAgeAllowed(u1->getProfile().getAge());
        if (!u1LikesU2Age || !u2LikesU1Age) return 0.0;

        return 5.0; // Base baseline score
    }
};

class InterestMatcher : public Matcher {
private:
    Matcher* nextMatcher;
public:
    explicit InterestMatcher(Matcher* next) : nextMatcher(next) {}
    double calculateScore(User* u1, User* u2) override {
        double baseScore = nextMatcher ? nextMatcher->calculateScore(u1, u2) : 0.0;
        if (baseScore == 0.0) return 0.0;

        auto i1 = u1->getProfile().getInterests();
        auto i2 = u2->getProfile().getInterests();
        int sharedCount = 0;
        for (const auto& inter1 : i1) {
            for (const auto& inter2 : i2) {
                if (inter1.getName() == inter2.getName()) sharedCount++;
            }
        }
        return baseScore + (sharedCount * 1.5);
    }
};

class LocationMatcher : public Matcher {
private:
    Matcher* nextMatcher;
public:
    explicit LocationMatcher(Matcher* next) : nextMatcher(next) {}
    double calculateScore(User* u1, User* u2) override {
        double baseScore = nextMatcher ? nextMatcher->calculateScore(u1, u2) : 0.0;
        if (baseScore == 0.0) return 0.0;

        double dist = u1->getProfile().getLocation().distanceInKilometers(u2->getProfile().getLocation());
        double proximityBonus = max(0.0, 3.0 - (dist / 5.0)); // Closer gets higher bonus
        return baseScore + proximityBonus;
    }
};

// ==================== 5. ORCHESTRATOR (DATING APP) ====================
class DatingApp {
private:
    map<string, User*> users;
    vector<ChatRoom*> chatRooms;
    Matcher* matchChain;
    DatingApp() {
        // Setup Chain: Location -> Interest -> BasicDetails
        matchChain = new LocationMatcher(new InterestMatcher(new BasicDetailsMatcher()));
    }
    static DatingApp* instance;
public:
    static DatingApp* getInstance() {
        if (!instance) instance = new DatingApp();
        return instance;
    }

    void createUser(string id, UserProfile prof, UserPreferences prefs) {
        users[id] = new User(id, prof, prefs);
    }

    User* getUserById(string id) {
        if (users.find(id) != users.end()) return users[id];
        return nullptr;
    }

    void swipeUser(string senderId, string targetId, Swipe action) {
        User* sender = getUserById(senderId);
        User* target = getUserById(targetId);
        if (!sender || !target) return;

        sender->swipe(targetId, action);
        cout << "User " << senderId << " swiped " << (action == Swipe::RIGHT ? "RIGHT" : "LEFT") << " on User " << targetId << endl;

        // Check for Match condition
        if (action == Swipe::RIGHT && target->hasLiked(senderId)) {
            string roomId = senderId + "_" + targetId;
            ChatRoom* room = new ChatRoom(roomId, senderId, targetId);
            chatRooms.push_back(room);

            NotificationService::getInstance()->notifyUser(senderId, "It's a Match with User " + targetId + "!");
            NotificationService::getInstance()->notifyUser(targetId, "It's a Match with User " + senderId + "!");
        }
    }

    ChatRoom* getChatRoom(string u1, string u2) {
        for (auto room : chatRooms) {
            // Simple check (in production use bidirectional lookup)
            return room; 
        }
        return nullptr;
    }

    void sendMessage(string senderId, string receiverId, string content) {
        ChatRoom* room = getChatRoom(senderId, receiverId);
        if (room) {
            room->addMessage(senderId, content);
            NotificationService::getInstance()->notifyUser(receiverId, "New message from User " + senderId);
        } else {
            cout << "No active chat room found between " << senderId << " and " << receiverId << endl;
        }
    }
};
DatingApp* DatingApp::instance = nullptr;

// ==================== 6. DRIVER PROGRAM (HAPPY FLOW) ====================
int main() {
    DatingApp* app = DatingApp::getInstance();

    // Setup User 1: Rohan
    Location loc1(28.6139, 77.2090); // New Delhi
    UserProfile prof1("Rohan", 28, Gender::MALE, "Software Developer & Traveler", loc1);
    prof1.addInterest(Interest("Coding", "Tech"));
    prof1.addInterest(Interest("Travel", "Lifestyle"));
    UserPreferences prefs1({Gender::FEMALE}, 25, 30, 20.0, {"Coding", "Travel"});
    app->createUser("U1", prof1, prefs1);

    // Setup User 2: नेहा (Neha)
    Location loc2(28.7041, 77.1025); // Nearby Delhi
    UserProfile prof2("Neha", 27, Gender::FEMALE, "Art Teacher & Explorer", loc2);
    prof2.addInterest(Interest("Coding", "Tech"));
    prof2.addInterest(Interest("Painting", "Art"));
    UserPreferences prefs2({Gender::MALE}, 26, 32, 25.0, {"Coding", "Art"});
    app->createUser("U2", prof2, prefs2);

    cout << "=== Profiles Initialized ===" << endl;
    app->getUserById("U1")->displayProfile();
    cout << endl;
    app->getUserById("U2")->displayProfile();

    cout << "\n=== Executing Swipes & Matching ===" << endl;
    // Rohan swipes right on Neha
    app->swipeUser("U1", "U2", Swipe::RIGHT);
    // Neha swipes right on Rohan (Triggers Match)
    app->swipeUser("U2", "U1", Swipe::RIGHT);

    cout << "\n=== Exchanging Real-Time Messages ===" << endl;
    app->sendMessage("U1", "U2", "Hi Neha! Great to match with you.");
    app->sendMessage("U2", "U1", "Hi Rohan! How are you doing?");

    // Display Chat Room
    ChatRoom* room = app->getChatRoom("U1", "U2");
    if (room) {
        room->displayChat();
    }

    return 0;
}