5. Ride-Sharing Service (Uber/Lyft) Advanced

interface MatchingStrategy {
  Optional<Driver> match(Ride ride, List<Driver> candidates);
}

interface FareStrategy {
  Money calculate(Ride ride);
}

class RideService {
  Ride requestRide(Rider rider, Location pickup, Location dropoff);
  void acceptRide(String rideId, Driver driver);
  void rejectRide(String rideId, Driver driver);     // triggers re-match
  void startRide(String rideId);                     // ARRIVED -> IN_PROGRESS
  Ride completeRide(String rideId);                  // computes + charges fare
  void cancelRide(String rideId, Actor by);
}

interface MatchingStrategy {
  Optional<Driver> match(Ride ride, List<Driver> candidates);
}

interface FareStrategy {
  Money calculate(Ride ride);
}

class RideService {
  Ride requestRide(Rider rider, Location pickup, Location dropoff) { throw new UnsupportedOperationException(); }
  void acceptRide(String rideId, Driver driver) { throw new UnsupportedOperationException(); }
  void rejectRide(String rideId, Driver driver) { throw new UnsupportedOperationException(); }   // triggers re-match
  void startRide(String rideId) { throw new UnsupportedOperationException(); }                    // ARRIVED -> IN_PROGRESS
  Ride completeRide(String rideId) { throw new UnsupportedOperationException(); }                  // computes + charges fare
  void cancelRide(String rideId, Actor by) { throw new UnsupportedOperationException(); }
}

class MatchingStrategy {
public:
  virtual std::optional<Driver> match(Ride ride, const std::vector<Driver>& candidates) = 0;
};

class FareStrategy {
public:
  virtual Money calculate(Ride ride) = 0;
};

class RideService {
public:
  Ride requestRide(std::shared_ptr<Rider> rider, Location pickup, Location dropoff);
  void acceptRide(const std::string& rideId, std::shared_ptr<Driver> driver);
  void rejectRide(const std::string& rideId, std::shared_ptr<Driver> driver);   // triggers re-match
  void startRide(const std::string& rideId);                                   // ARRIVED -> IN_PROGRESS
  Ride completeRide(const std::string& rideId);                                 // computes + charges fare
  void cancelRide(const std::string& rideId, std::shared_ptr<Actor> by);
};

class MatchingStrategy {
  match(ride, candidates) { throw new Error('not implemented'); }
}

class FareStrategy {
  calculate(ride) { throw new Error('not implemented'); }
}

class RideService {
  requestRide(rider, pickup, dropoff) { throw new Error('not implemented'); }
  acceptRide(rideId, driver) { throw new Error('not implemented'); }
  rejectRide(rideId, driver) { throw new Error('not implemented'); }   // triggers re-match
  startRide(rideId) { throw new Error('not implemented'); }            // ARRIVED -> IN_PROGRESS
  completeRide(rideId) { throw new Error('not implemented'); }         // computes + charges fare
  cancelRide(rideId, by) { throw new Error('not implemented'); }
}

interface MatchingStrategy {
  match(ride: Ride, candidates: Driver[]): Driver | null;
}

interface FareStrategy {
  calculate(ride: Ride): Money;
}

class RideService {
  requestRide(rider: Rider, pickup: Location, dropoff: Location): Ride { throw new Error('not implemented'); }
  acceptRide(rideId: string, driver: Driver): void { throw new Error('not implemented'); }
  rejectRide(rideId: string, driver: Driver): void { throw new Error('not implemented'); }   // triggers re-match
  startRide(rideId: string): void { throw new Error('not implemented'); }                    // ARRIVED -> IN_PROGRESS
  completeRide(rideId: string): Ride { throw new Error('not implemented'); }                  // computes + charges fare
  cancelRide(rideId: string, by: Actor): void { throw new Error('not implemented'); }
}

requestRide(rider, pickup, dropoff):
  ride = Ride.create(rider, pickup, dropoff, status=REQUESTED)
  candidates = geoIndex.findNearby(pickup, radius=DEFAULT_RADIUS)
  while candidates not empty:
    driver = matchingStrategy.match(ride, candidates)
    if driver is None: break
    if driver.tryReserve():           // atomic CAS: AVAILABLE -> RESERVED
      ride.transitionTo(MATCHED, driver)
      notificationService.onRideStatusChanged(ride)
      return ride
    candidates.remove(driver)         // someone else grabbed it first, retry
  ride.transitionTo(NO_DRIVER_FOUND)
  return ride

completeRide(rideId):
  ride = rides.get(rideId)
  ride.transitionTo(COMPLETED)        // throws if not currently IN_PROGRESS
  baseFare = fareStrategy.calculate(ride)     // may itself be a decorator chain
  ride.fare = baseFare
  paymentGateway.charge(ride.rider, baseFare)
  driver.release()                    // RESERVED/ON_TRIP -> AVAILABLE
  notificationService.onRideStatusChanged(ride)
  return ride

Ride requestRide(Rider rider, Location pickup, Location dropoff) {
  Ride ride = Ride.create(rider, pickup, dropoff, REQUESTED);
  List<Driver> candidates = geoIndex.findNearby(pickup, DEFAULT_RADIUS);
  while (!candidates.isEmpty()) {
    Optional<Driver> driver = matchingStrategy.match(ride, candidates);
    if (driver.isEmpty()) break;
    if (driver.get().tryReserve()) {          // atomic CAS: AVAILABLE -> RESERVED
      ride.transitionTo(MATCHED, driver.get());
      notificationService.onRideStatusChanged(ride);
      return ride;
    }
    candidates.remove(driver.get());   // someone else grabbed it first, retry
  }
  ride.transitionTo(NO_DRIVER_FOUND);
  return ride;
}

Ride completeRide(String rideId) {
  Ride ride = rides.get(rideId);
  ride.transitionTo(COMPLETED);        // throws if not currently IN_PROGRESS
  Money baseFare = fareStrategy.calculate(ride);   // may itself be a decorator chain
  ride.fare = baseFare;
  paymentGateway.charge(ride.rider, baseFare);
  driver.release();                    // RESERVED/ON_TRIP -> AVAILABLE
  notificationService.onRideStatusChanged(ride);
  return ride;
}

Ride requestRide(std::shared_ptr<Rider> rider, Location pickup, Location dropoff) {
  Ride ride = Ride::create(rider, pickup, dropoff, REQUESTED);
  auto candidates = geoIndex.findNearby(pickup, DEFAULT_RADIUS);
  while (!candidates.empty()) {
    auto driver = matchingStrategy.match(ride, candidates);
    if (!driver.has_value()) break;
    if (driver->tryReserve()) {          // atomic CAS: AVAILABLE -> RESERVED
      ride.transitionTo(MATCHED, *driver);
      notificationService.onRideStatusChanged(ride);
      return ride;
    }
    candidates.erase(std::remove(candidates.begin(), candidates.end(), *driver), candidates.end());   // someone else grabbed it first, retry
  }
  ride.transitionTo(NO_DRIVER_FOUND);
  return ride;
}

Ride completeRide(const std::string& rideId) {
  Ride ride = rides.get(rideId);
  ride.transitionTo(COMPLETED);        // throws if not currently IN_PROGRESS
  Money baseFare = fareStrategy.calculate(ride);   // may itself be a decorator chain
  ride.fare = baseFare;
  paymentGateway.charge(ride.rider, baseFare);
  driver->release();                   // RESERVED/ON_TRIP -> AVAILABLE
  notificationService.onRideStatusChanged(ride);
  return ride;
}

function requestRide(rider, pickup, dropoff) {
  const ride = Ride.create(rider, pickup, dropoff, REQUESTED);
  let candidates = geoIndex.findNearby(pickup, DEFAULT_RADIUS);
  while (candidates.length > 0) {
    const driver = matchingStrategy.match(ride, candidates);
    if (driver === null) break;
    if (driver.tryReserve()) {          // atomic CAS: AVAILABLE -> RESERVED
      ride.transitionTo(MATCHED, driver);
      notificationService.onRideStatusChanged(ride);
      return ride;
    }
    candidates = candidates.filter(d => d !== driver);   // someone else grabbed it first, retry
  }
  ride.transitionTo(NO_DRIVER_FOUND);
  return ride;
}

function completeRide(rideId) {
  const ride = rides.get(rideId);
  ride.transitionTo(COMPLETED);        // throws if not currently IN_PROGRESS
  const baseFare = fareStrategy.calculate(ride);   // may itself be a decorator chain
  ride.fare = baseFare;
  paymentGateway.charge(ride.rider, baseFare);
  driver.release();                    // RESERVED/ON_TRIP -> AVAILABLE
  notificationService.onRideStatusChanged(ride);
  return ride;
}

function requestRide(rider: Rider, pickup: Location, dropoff: Location): Ride {
  const ride: Ride = Ride.create(rider, pickup, dropoff, REQUESTED);
  let candidates: Driver[] = geoIndex.findNearby(pickup, DEFAULT_RADIUS);
  while (candidates.length > 0) {
    const driver: Driver | null = matchingStrategy.match(ride, candidates);
    if (driver === null) break;
    if (driver.tryReserve()) {          // atomic CAS: AVAILABLE -> RESERVED
      ride.transitionTo(MATCHED, driver);
      notificationService.onRideStatusChanged(ride);
      return ride;
    }
    candidates = candidates.filter(d => d !== driver);   // someone else grabbed it first, retry
  }
  ride.transitionTo(NO_DRIVER_FOUND);
  return ride;
}

function completeRide(rideId: string): Ride {
  const ride: Ride = rides.get(rideId);
  ride.transitionTo(COMPLETED);        // throws if not currently IN_PROGRESS
  const baseFare: Money = fareStrategy.calculate(ride);   // may itself be a decorator chain
  ride.fare = baseFare;
  paymentGateway.charge(ride.rider, baseFare);
  driver.release();                    // RESERVED/ON_TRIP -> AVAILABLE
  notificationService.onRideStatusChanged(ride);
  return ride;
}

// Ride-Sharing Service (Uber/Lyft) — full LLD implementation with demo.
// Single-file Java translation of the Mermaid class diagram in section J.
import java.util.*;

public class p5 {

    // ---------- Value objects ----------

    static final class Money {
        final long cents;
        private Money(long c) { cents = c; }
        static Money of(double dollars) { return new Money(Math.round(dollars * 100)); }
        Money times(double factor) { return new Money(Math.round(cents * factor)); }
        public String toString() { return String.format("$%.2f", cents / 100.0); }
    }

    /** Immutable geo point. Distance math lives here; storage/indexing is GeoIndex's job. */
    static final class Location {
        final double lat, lng;
        Location(double lat, double lng) { this.lat = lat; this.lng = lng; }
        /** Haversine great-circle distance in kilometers. */
        double distanceTo(Location o) {
            double R = 6371.0;
            double dLat = Math.toRadians(o.lat - lat);
            double dLng = Math.toRadians(o.lng - lng);
            double a = Math.sin(dLat / 2) * Math.sin(dLat / 2)
                    + Math.cos(Math.toRadians(lat)) * Math.cos(Math.toRadians(o.lat))
                    * Math.sin(dLng / 2) * Math.sin(dLng / 2);
            return R * 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
        }
    }

    static final class Vehicle {
        final String make, model, plate, type;
        Vehicle(String make, String model, String plate, String type) {
            this.make = make; this.model = model; this.plate = plate; this.type = type;
        }
    }

    // ---------- Identity hierarchy ----------

    static abstract class User {
        final String id, name, phone;
        double rating = 5.0;
        User(String id, String name, String phone) { this.id = id; this.name = name; this.phone = phone; }
    }

    static final class Rider extends User {
        final String paymentMethod;
        Rider(String id, String name, String phone, String paymentMethod) {
            super(id, name, phone); this.paymentMethod = paymentMethod;
        }
        Ride requestRide(RideService service, Location pickup, Location dropoff) {
            return service.requestRide(this, pickup, dropoff);
        }
    }

    enum DriverStatus { AVAILABLE, RESERVED, ON_TRIP }

    static final class Driver extends User {
        final Vehicle vehicle; // composition: owned by this driver profile
        Location currentLocation; // composition: has no meaning detached from the driver
        DriverStatus status = DriverStatus.AVAILABLE;
        Driver(String id, String name, String phone, Vehicle vehicle, Location location) {
            super(id, name, phone); this.vehicle = vehicle; this.currentLocation = location;
        }
        /** Atomic (in a real system, CAS-guarded) check-and-set: AVAILABLE -> RESERVED. */
        boolean tryReserve() {
            if (status == DriverStatus.AVAILABLE) { status = DriverStatus.RESERVED; return true; }
            return false;
        }
        void release() { status = DriverStatus.AVAILABLE; }
        void markOnTrip() { status = DriverStatus.ON_TRIP; }
        void updateLocation(Location loc) { this.currentLocation = loc; }
        void accept(RideService service, String rideId) { service.acceptRide(rideId, this); }
        void reject(RideService service, String rideId) { service.rejectRide(rideId, this); }
    }

    // ---------- Ride: guarded state machine ----------

    enum RideStatus { REQUESTED, MATCHED, ACCEPTED, ARRIVED, IN_PROGRESS, COMPLETED, CANCELLED, NO_DRIVER_FOUND }

    static final class Ride {
        final String id;
        final Rider rider; // association — rider exists independently of the ride
        final Location pickup, dropoff;
        Driver driver; // association — set once matched
        RideStatus status = RideStatus.REQUESTED;
        Money fare;
        final long requestedAt = System.currentTimeMillis();

        private static final Map<RideStatus, Set<RideStatus>> ALLOWED = new HashMap<>();
        static {
            ALLOWED.put(RideStatus.REQUESTED, EnumSet.of(RideStatus.MATCHED, RideStatus.NO_DRIVER_FOUND, RideStatus.CANCELLED));
            ALLOWED.put(RideStatus.MATCHED, EnumSet.of(RideStatus.ACCEPTED, RideStatus.REQUESTED, RideStatus.CANCELLED));
            ALLOWED.put(RideStatus.ACCEPTED, EnumSet.of(RideStatus.ARRIVED, RideStatus.CANCELLED));
            ALLOWED.put(RideStatus.ARRIVED, EnumSet.of(RideStatus.IN_PROGRESS, RideStatus.CANCELLED));
            ALLOWED.put(RideStatus.IN_PROGRESS, EnumSet.of(RideStatus.COMPLETED));
            ALLOWED.put(RideStatus.COMPLETED, EnumSet.noneOf(RideStatus.class));
            ALLOWED.put(RideStatus.CANCELLED, EnumSet.noneOf(RideStatus.class));
            ALLOWED.put(RideStatus.NO_DRIVER_FOUND, EnumSet.noneOf(RideStatus.class));
        }

        Ride(String id, Rider rider, Location pickup, Location dropoff) {
            this.id = id; this.rider = rider; this.pickup = pickup; this.dropoff = dropoff;
        }

        /** Guarded transition — throws if the target state isn't reachable from the current one. */
        void transitionTo(RideStatus next, Driver withDriver) {
            if (!ALLOWED.get(status).contains(next)) {
                throw new IllegalStateException("Illegal ride transition: " + status + " -> " + next);
            }
            status = next;
            if (withDriver != null) driver = withDriver;
        }
    }

    // ---------- GeoIndex ----------

    /** Spatial lookup of drivers via a coarse lat/lng grid. Ranking is left to MatchingStrategy. */
    static final class GeoIndex {
        private static final double GRID_DEG = 0.05; // ~5km buckets
        private final Map<String, Set<Driver>> buckets = new HashMap<>();
        private final Map<String, String> driverBucket = new HashMap<>();

        private String bucketKey(Location loc) {
            long gx = Math.round(loc.lat / GRID_DEG);
            long gy = Math.round(loc.lng / GRID_DEG);
            return gx + ":" + gy;
        }

        void register(Driver driver) { update(driver, driver.currentLocation); }

        void update(Driver driver, Location loc) {
            String old = driverBucket.get(driver.id);
            if (old != null) buckets.getOrDefault(old, Collections.emptySet()).remove(driver);
            String k = bucketKey(loc);
            buckets.computeIfAbsent(k, x -> new HashSet<>()).add(driver);
            driverBucket.put(driver.id, k);
            driver.updateLocation(loc);
        }

        /** Scans the 3x3 neighborhood of grid cells and filters by real distance. */
        List<Driver> findNearby(Location loc, double radiusKm) {
            long gx = Math.round(loc.lat / GRID_DEG);
            long gy = Math.round(loc.lng / GRID_DEG);
            List<Driver> result = new ArrayList<>();
            for (long dx = -1; dx <= 1; dx++) {
                for (long dy = -1; dy <= 1; dy++) {
                    Set<Driver> cell = buckets.get((gx + dx) + ":" + (gy + dy));
                    if (cell == null) continue;
                    for (Driver d : cell) {
                        if (d.currentLocation.distanceTo(loc) <= radiusKm) result.add(d);
                    }
                }
            }
            return result;
        }
    }

    // ---------- Strategies ----------

    interface MatchingStrategy {
        Optional<Driver> match(Ride ride, List<Driver> candidates);
    }

    static final class NearestDriverStrategy implements MatchingStrategy {
        public Optional<Driver> match(Ride ride, List<Driver> candidates) {
            return candidates.stream()
                    .filter(d -> d.status == DriverStatus.AVAILABLE)
                    .min(Comparator.comparingDouble(d -> d.currentLocation.distanceTo(ride.pickup)));
        }
    }

    interface FareStrategy {
        Money calculate(Ride ride);
    }

    static final class DistanceTimeFareStrategy implements FareStrategy {
        private static final double BASE = 2.50, PER_KM = 1.25, PER_MIN = 0.20, AVG_SPEED_KMH = 30.0;
        public Money calculate(Ride ride) {
            double distanceKm = ride.pickup.distanceTo(ride.dropoff);
            double minutes = (distanceKm / AVG_SPEED_KMH) * 60.0;
            return Money.of(BASE + PER_KM * distanceKm + PER_MIN * minutes);
        }
    }

    /** Decorator: multiplies any wrapped FareStrategy's result during high demand. Not a rival Strategy. */
    static final class SurgeFareDecorator implements FareStrategy {
        private final FareStrategy wrapped;
        private final double multiplier;
        SurgeFareDecorator(FareStrategy wrapped, double multiplier) { this.wrapped = wrapped; this.multiplier = multiplier; }
        public Money calculate(Ride ride) { return wrapped.calculate(ride).times(multiplier); }
    }

    // ---------- Observer ----------

    static final class NotificationService {
        void onRideStatusChanged(Ride ride) {
            System.out.println("[notify] ride " + ride.id + " -> " + ride.status
                    + (ride.driver != null ? " (driver " + ride.driver.name + ")" : ""));
        }
    }

    // ---------- RideService (facade) ----------

    static final class RideService {
        private static final double DEFAULT_RADIUS_KM = 5.0;
        private final GeoIndex geoIndex;
        private final MatchingStrategy matchingStrategy;
        private final FareStrategy fareStrategy;
        private final NotificationService notificationService;
        private final Map<String, Ride> rides = new HashMap<>();
        private int counter = 0;

        RideService(GeoIndex geoIndex, MatchingStrategy matchingStrategy, FareStrategy fareStrategy,
                    NotificationService notificationService) {
            this.geoIndex = geoIndex; this.matchingStrategy = matchingStrategy;
            this.fareStrategy = fareStrategy; this.notificationService = notificationService;
        }

        Ride requestRide(Rider rider, Location pickup, Location dropoff) {
            Ride ride = new Ride("R-" + (++counter), rider, pickup, dropoff);
            rides.put(ride.id, ride);
            attemptMatch(ride, Collections.emptySet());
            return ride;
        }

        /** Core matching loop: rank candidates, reserve atomically, retry on lost race. */
        private void attemptMatch(Ride ride, Set<String> excludedDriverIds) {
            List<Driver> candidates = geoIndex.findNearby(ride.pickup, DEFAULT_RADIUS_KM);
            candidates.removeIf(d -> excludedDriverIds.contains(d.id));
            while (!candidates.isEmpty()) {
                Optional<Driver> chosen = matchingStrategy.match(ride, candidates);
                if (chosen.isEmpty()) break;
                Driver driver = chosen.get();
                if (driver.tryReserve()) { // atomic CAS: AVAILABLE -> RESERVED
                    ride.transitionTo(RideStatus.MATCHED, driver);
                    notificationService.onRideStatusChanged(ride);
                    return;
                }
                candidates.remove(driver); // someone else grabbed it first, retry
            }
            ride.transitionTo(RideStatus.NO_DRIVER_FOUND, null);
            notificationService.onRideStatusChanged(ride);
        }

        void acceptRide(String rideId, Driver driver) {
            Ride ride = rides.get(rideId);
            if (ride.driver != driver) throw new IllegalStateException("Driver mismatch for ride " + rideId);
            ride.transitionTo(RideStatus.ACCEPTED, driver);
            notificationService.onRideStatusChanged(ride);
        }

        /** Rejection releases the driver and re-triggers matching, excluding the driver who just rejected. */
        void rejectRide(String rideId, Driver driver) {
            Ride ride = rides.get(rideId);
            driver.release();
            ride.transitionTo(RideStatus.REQUESTED, null);
            ride.driver = null;
            attemptMatch(ride, Set.of(driver.id));
        }

        void arriveAtPickup(String rideId) {
            Ride ride = rides.get(rideId);
            ride.transitionTo(RideStatus.ARRIVED, null);
        }

        void startRide(String rideId) {
            Ride ride = rides.get(rideId);
            ride.transitionTo(RideStatus.IN_PROGRESS, null); // ARRIVED -> IN_PROGRESS
            ride.driver.markOnTrip();
            notificationService.onRideStatusChanged(ride);
        }

        Ride completeRide(String rideId) {
            Ride ride = rides.get(rideId);
            ride.transitionTo(RideStatus.COMPLETED, null); // throws if not currently IN_PROGRESS
            Money fare = fareStrategy.calculate(ride); // may itself be a decorator chain
            ride.fare = fare;
            System.out.println("[payment] charged " + fare + " to " + ride.rider.name);
            ride.driver.release(); // RESERVED/ON_TRIP -> AVAILABLE
            notificationService.onRideStatusChanged(ride);
            return ride;
        }

        void cancelRide(String rideId, String cancelledBy) {
            Ride ride = rides.get(rideId);
            if (ride.driver != null) ride.driver.release();
            ride.transitionTo(RideStatus.CANCELLED, null);
            System.out.println("[cancel] ride " + rideId + " cancelled by " + cancelledBy);
            notificationService.onRideStatusChanged(ride);
        }
    }

    // ---------- Demo ----------

    public static void main(String[] args) {
        GeoIndex geoIndex = new GeoIndex();
        MatchingStrategy matching = new NearestDriverStrategy();
        FareStrategy fare = new SurgeFareDecorator(new DistanceTimeFareStrategy(), 1.5); // 1.5x surge active
        NotificationService notifications = new NotificationService();
        RideService rideService = new RideService(geoIndex, matching, fare, notifications);

        Driver d1 = new Driver("d1", "Sam", "555-1", new Vehicle("Toyota", "Camry", "ABC-123", "Sedan"), new Location(37.77, -122.42));
        Driver d2 = new Driver("d2", "Jamie", "555-2", new Vehicle("Honda", "Civic", "XYZ-987", "Sedan"), new Location(37.80, -122.41));
        geoIndex.register(d1);
        geoIndex.register(d2);

        Rider rider = new Rider("r1", "Priya", "555-9", "card-ending-4242");
        Ride ride = rider.requestRide(rideService, new Location(37.775, -122.418), new Location(37.79, -122.40));
        System.out.println("After match: status=" + ride.status + " driver=" + (ride.driver != null ? ride.driver.name : "none"));

        ride.driver.accept(rideService, ride.id);
        rideService.arriveAtPickup(ride.id);
        rideService.startRide(ride.id);
        Ride completed = rideService.completeRide(ride.id);
        System.out.println("Final status=" + completed.status + " fare=" + completed.fare);
    }
}

// Ride-Sharing Service (Uber/Lyft) — full LLD implementation with demo.
// Single-file C++ translation of the Mermaid class diagram in section J.
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <memory>
#include <optional>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <stdexcept>

// ---------- Value objects ----------
struct Money {
    long long cents = 0;
    static Money of(double dollars) { return Money{ (long long)std::llround(dollars * 100) }; }
    Money times(double factor) const { return Money{ (long long)std::llround(cents * factor) }; }
    std::string str() const {
        std::ostringstream os;
        os << "$" << (cents / 100) << "." << (cents % 100 < 10 ? "0" : "") << (cents % 100);
        return os.str();
    }
};

// Immutable geo point. Distance math lives here; storage/indexing is GeoIndex's job.
struct Location {
    double lat, lng;
    double distanceTo(const Location& o) const {
        const double R = 6371.0;
        double dLat = (o.lat - lat) * M_PI / 180.0;
        double dLng = (o.lng - lng) * M_PI / 180.0;
        double a = std::sin(dLat / 2) * std::sin(dLat / 2)
                 + std::cos(lat * M_PI / 180.0) * std::cos(o.lat * M_PI / 180.0)
                 * std::sin(dLng / 2) * std::sin(dLng / 2);
        return R * 2 * std::atan2(std::sqrt(a), std::sqrt(1 - a));
    }
};

struct Vehicle {
    std::string make, model, plate, type;
};

// ---------- Identity hierarchy ----------
struct User {
    std::string id, name, phone;
    double rating = 5.0;
    User(std::string id, std::string name, std::string phone) : id(std::move(id)), name(std::move(name)), phone(std::move(phone)) {}
    virtual ~User() = default;
};

class RideService; // fwd decl
struct Ride;

struct Rider : public User {
    std::string paymentMethod;
    Rider(std::string id, std::string name, std::string phone, std::string pm)
        : User(std::move(id), std::move(name), std::move(phone)), paymentMethod(std::move(pm)) {}
    // `self` is this Rider's own shared_ptr, passed in by the caller (C++ has no shared_from_this
    // without inheriting enable_shared_from_this) — kept simple for this single-file demo.
    std::shared_ptr<Ride> requestRide(RideService& service, std::shared_ptr<Rider> self,
                                       const Location& pickup, const Location& dropoff);
};

enum class DriverStatus { AVAILABLE, RESERVED, ON_TRIP };

struct Driver : public User {
    Vehicle vehicle;              // composition: owned by this driver profile
    Location currentLocation;     // composition: has no meaning detached from the driver
    DriverStatus status = DriverStatus::AVAILABLE;
    Driver(std::string id, std::string name, std::string phone, Vehicle v, Location loc)
        : User(std::move(id), std::move(name), std::move(phone)), vehicle(std::move(v)), currentLocation(loc) {}

    // Atomic (in a real system, CAS-guarded) check-and-set: AVAILABLE -> RESERVED.
    bool tryReserve() {
        if (status == DriverStatus::AVAILABLE) { status = DriverStatus::RESERVED; return true; }
        return false;
    }
    void release() { status = DriverStatus::AVAILABLE; }
    void markOnTrip() { status = DriverStatus::ON_TRIP; }
    void updateLocation(const Location& loc) { currentLocation = loc; }
    void accept(RideService& service, const std::string& rideId, std::shared_ptr<Driver> self);
    void reject(RideService& service, const std::string& rideId, std::shared_ptr<Driver> self);
};

// ---------- Ride: guarded state machine ----------
enum class RideStatus { REQUESTED, MATCHED, ACCEPTED, ARRIVED, IN_PROGRESS, COMPLETED, CANCELLED, NO_DRIVER_FOUND };

std::string toString(RideStatus s) {
    switch (s) {
        case RideStatus::REQUESTED: return "REQUESTED";
        case RideStatus::MATCHED: return "MATCHED";
        case RideStatus::ACCEPTED: return "ACCEPTED";
        case RideStatus::ARRIVED: return "ARRIVED";
        case RideStatus::IN_PROGRESS: return "IN_PROGRESS";
        case RideStatus::COMPLETED: return "COMPLETED";
        case RideStatus::CANCELLED: return "CANCELLED";
        case RideStatus::NO_DRIVER_FOUND: return "NO_DRIVER_FOUND";
    }
    return "?";
}

struct Ride {
    std::string id;
    std::shared_ptr<Rider> rider; // association — rider exists independently of the ride
    Location pickup, dropoff;
    std::shared_ptr<Driver> driver; // association — set once matched
    RideStatus status = RideStatus::REQUESTED;
    std::optional<Money> fare;

    Ride(std::string id, std::shared_ptr<Rider> rider, Location pickup, Location dropoff)
        : id(std::move(id)), rider(std::move(rider)), pickup(pickup), dropoff(dropoff) {}

    static bool allowed(RideStatus from, RideStatus to) {
        switch (from) {
            case RideStatus::REQUESTED: return to == RideStatus::MATCHED || to == RideStatus::NO_DRIVER_FOUND || to == RideStatus::CANCELLED;
            case RideStatus::MATCHED: return to == RideStatus::ACCEPTED || to == RideStatus::REQUESTED || to == RideStatus::CANCELLED;
            case RideStatus::ACCEPTED: return to == RideStatus::ARRIVED || to == RideStatus::CANCELLED;
            case RideStatus::ARRIVED: return to == RideStatus::IN_PROGRESS || to == RideStatus::CANCELLED;
            case RideStatus::IN_PROGRESS: return to == RideStatus::COMPLETED;
            default: return false; // COMPLETED / CANCELLED / NO_DRIVER_FOUND are terminal
        }
    }

    // Guarded transition — throws if the target state isn't reachable from the current one.
    void transitionTo(RideStatus next, std::shared_ptr<Driver> withDriver) {
        if (!allowed(status, next)) throw std::logic_error("Illegal ride transition: " + toString(status) + " -> " + toString(next));
        status = next;
        if (withDriver) driver = withDriver;
    }
};

// ---------- GeoIndex ----------
// Spatial lookup of drivers via a coarse lat/lng grid. Ranking is left to MatchingStrategy.
class GeoIndex {
    static constexpr double GRID_DEG = 0.05; // ~5km buckets
    std::unordered_map<std::string, std::vector<std::shared_ptr<Driver>>> buckets;
    std::unordered_map<std::string, std::string> driverBucket;

    std::string bucketKey(const Location& loc) const {
        long gx = std::lround(loc.lat / GRID_DEG);
        long gy = std::lround(loc.lng / GRID_DEG);
        return std::to_string(gx) + ":" + std::to_string(gy);
    }

public:
    void registerDriver(std::shared_ptr<Driver> driver) { update(driver, driver->currentLocation); }

    void update(std::shared_ptr<Driver> driver, const Location& loc) {
        auto it = driverBucket.find(driver->id);
        if (it != driverBucket.end()) {
            auto& vec = buckets[it->second];
            vec.erase(std::remove_if(vec.begin(), vec.end(), [&](auto& d){ return d->id == driver->id; }), vec.end());
        }
        std::string k = bucketKey(loc);
        buckets[k].push_back(driver);
        driverBucket[driver->id] = k;
        driver->updateLocation(loc);
    }

    // Scans the 3x3 neighborhood of grid cells and filters by real distance.
    std::vector<std::shared_ptr<Driver>> findNearby(const Location& loc, double radiusKm) const {
        long gx = std::lround(loc.lat / GRID_DEG);
        long gy = std::lround(loc.lng / GRID_DEG);
        std::vector<std::shared_ptr<Driver>> result;
        for (long dx = -1; dx <= 1; dx++) {
            for (long dy = -1; dy <= 1; dy++) {
                auto it = buckets.find(std::to_string(gx + dx) + ":" + std::to_string(gy + dy));
                if (it == buckets.end()) continue;
                for (auto& d : it->second) {
                    if (d->currentLocation.distanceTo(loc) <= radiusKm) result.push_back(d);
                }
            }
        }
        return result;
    }
};

// ---------- Strategies ----------
class MatchingStrategy {
public:
    virtual ~MatchingStrategy() = default;
    virtual std::optional<std::shared_ptr<Driver>> match(const Ride& ride, std::vector<std::shared_ptr<Driver>>& candidates) = 0;
};

class NearestDriverStrategy : public MatchingStrategy {
public:
    std::optional<std::shared_ptr<Driver>> match(const Ride& ride, std::vector<std::shared_ptr<Driver>>& candidates) override {
        std::shared_ptr<Driver> best;
        double bestDist = 1e18;
        for (auto& d : candidates) {
            if (d->status != DriverStatus::AVAILABLE) continue;
            double dist = d->currentLocation.distanceTo(ride.pickup);
            if (dist < bestDist) { bestDist = dist; best = d; }
        }
        if (!best) return std::nullopt;
        return best;
    }
};

class FareStrategy {
public:
    virtual ~FareStrategy() = default;
    virtual Money calculate(const Ride& ride) = 0;
};

class DistanceTimeFareStrategy : public FareStrategy {
    static constexpr double BASE = 2.50, PER_KM = 1.25, PER_MIN = 0.20, AVG_SPEED_KMH = 30.0;
public:
    Money calculate(const Ride& ride) override {
        double distanceKm = ride.pickup.distanceTo(ride.dropoff);
        double minutes = (distanceKm / AVG_SPEED_KMH) * 60.0;
        return Money::of(BASE + PER_KM * distanceKm + PER_MIN * minutes);
    }
};

// Decorator: multiplies any wrapped FareStrategy's result during high demand. Not a rival Strategy.
class SurgeFareDecorator : public FareStrategy {
    std::shared_ptr<FareStrategy> wrapped;
    double multiplier;
public:
    SurgeFareDecorator(std::shared_ptr<FareStrategy> w, double m) : wrapped(std::move(w)), multiplier(m) {}
    Money calculate(const Ride& ride) override { return wrapped->calculate(ride).times(multiplier); }
};

// ---------- Observer ----------
class NotificationService {
public:
    void onRideStatusChanged(const Ride& ride) {
        std::cout << "[notify] ride " << ride.id << " -> " << toString(ride.status)
                  << (ride.driver ? (" (driver " + ride.driver->name + ")") : "") << "\n";
    }
};

// ---------- RideService (facade) ----------
class RideService {
    static constexpr double DEFAULT_RADIUS_KM = 5.0;
    GeoIndex& geoIndex;
    MatchingStrategy& matchingStrategy;
    FareStrategy& fareStrategy;
    NotificationService& notificationService;
    std::unordered_map<std::string, std::shared_ptr<Ride>> rides;
    int counter = 0;

    void attemptMatch(std::shared_ptr<Ride> ride, const std::unordered_set<std::string>& excludedDriverIds) {
        auto candidates = geoIndex.findNearby(ride->pickup, DEFAULT_RADIUS_KM);
        candidates.erase(std::remove_if(candidates.begin(), candidates.end(),
            [&](auto& d){ return excludedDriverIds.count(d->id) > 0; }), candidates.end());
        while (!candidates.empty()) {
            auto chosen = matchingStrategy.match(*ride, candidates);
            if (!chosen.has_value()) break;
            auto driver = chosen.value();
            if (driver->tryReserve()) { // atomic CAS: AVAILABLE -> RESERVED
                ride->transitionTo(RideStatus::MATCHED, driver);
                notificationService.onRideStatusChanged(*ride);
                return;
            }
            candidates.erase(std::remove(candidates.begin(), candidates.end(), driver), candidates.end());
        }
        ride->transitionTo(RideStatus::NO_DRIVER_FOUND, nullptr);
        notificationService.onRideStatusChanged(*ride);
    }

public:
    RideService(GeoIndex& g, MatchingStrategy& m, FareStrategy& f, NotificationService& n)
        : geoIndex(g), matchingStrategy(m), fareStrategy(f), notificationService(n) {}

    std::shared_ptr<Ride> requestRide(std::shared_ptr<Rider> rider, const Location& pickup, const Location& dropoff) {
        auto ride = std::make_shared<Ride>("R-" + std::to_string(++counter), rider, pickup, dropoff);
        rides[ride->id] = ride;
        attemptMatch(ride, {});
        return ride;
    }

    void acceptRide(const std::string& rideId, std::shared_ptr<Driver> driver) {
        auto ride = rides[rideId];
        if (ride->driver != driver) throw std::logic_error("Driver mismatch for ride " + rideId);
        ride->transitionTo(RideStatus::ACCEPTED, driver);
        notificationService.onRideStatusChanged(*ride);
    }

    // Rejection releases the driver and re-triggers matching, excluding the driver who just rejected.
    void rejectRide(const std::string& rideId, std::shared_ptr<Driver> driver) {
        auto ride = rides[rideId];
        driver->release();
        ride->transitionTo(RideStatus::REQUESTED, nullptr);
        ride->driver = nullptr;
        attemptMatch(ride, {driver->id});
    }

    void arriveAtPickup(const std::string& rideId) {
        rides[rideId]->transitionTo(RideStatus::ARRIVED, nullptr);
    }

    void startRide(const std::string& rideId) {
        auto ride = rides[rideId];
        ride->transitionTo(RideStatus::IN_PROGRESS, nullptr); // ARRIVED -> IN_PROGRESS
        ride->driver->markOnTrip();
        notificationService.onRideStatusChanged(*ride);
    }

    std::shared_ptr<Ride> completeRide(const std::string& rideId) {
        auto ride = rides[rideId];
        ride->transitionTo(RideStatus::COMPLETED, nullptr); // throws if not currently IN_PROGRESS
        Money fare = fareStrategy.calculate(*ride); // may itself be a decorator chain
        ride->fare = fare;
        std::cout << "[payment] charged " << fare.str() << " to " << ride->rider->name << "\n";
        ride->driver->release(); // RESERVED/ON_TRIP -> AVAILABLE
        notificationService.onRideStatusChanged(*ride);
        return ride;
    }

    void cancelRide(const std::string& rideId, const std::string& cancelledBy) {
        auto ride = rides[rideId];
        if (ride->driver) ride->driver->release();
        ride->transitionTo(RideStatus::CANCELLED, nullptr);
        std::cout << "[cancel] ride " << rideId << " cancelled by " << cancelledBy << "\n";
        notificationService.onRideStatusChanged(*ride);
    }
};

std::shared_ptr<Ride> Rider::requestRide(RideService& service, std::shared_ptr<Rider> self,
                                          const Location& pickup, const Location& dropoff) {
    return service.requestRide(self, pickup, dropoff);
}

void Driver::accept(RideService& service, const std::string& rideId, std::shared_ptr<Driver> self) {
    service.acceptRide(rideId, self);
}
void Driver::reject(RideService& service, const std::string& rideId, std::shared_ptr<Driver> self) {
    service.rejectRide(rideId, self);
}

// ---------- Demo ----------
int main() {
    GeoIndex geoIndex;
    NearestDriverStrategy matching;
    auto baseFarePtr = std::make_shared<DistanceTimeFareStrategy>();
    SurgeFareDecorator surgeFare(baseFarePtr, 1.5); // 1.5x surge active
    NotificationService notifications;
    RideService rideService(geoIndex, matching, surgeFare, notifications);

    auto d1 = std::make_shared<Driver>("d1", "Sam", "555-1", Vehicle{"Toyota", "Camry", "ABC-123", "Sedan"}, Location{37.77, -122.42});
    auto d2 = std::make_shared<Driver>("d2", "Jamie", "555-2", Vehicle{"Honda", "Civic", "XYZ-987", "Sedan"}, Location{37.80, -122.41});
    geoIndex.registerDriver(d1);
    geoIndex.registerDriver(d2);

    auto rider = std::make_shared<Rider>("r1", "Priya", "555-9", "card-ending-4242");
    auto ride = rider->requestRide(rideService, rider, Location{37.775, -122.418}, Location{37.79, -122.40});
    std::cout << "After match: status=" << toString(ride->status)
              << " driver=" << (ride->driver ? ride->driver->name : "none") << "\n";

    ride->driver->accept(rideService, ride->id, ride->driver);
    rideService.arriveAtPickup(ride->id);
    rideService.startRide(ride->id);
    auto completed = rideService.completeRide(ride->id);
    std::cout << "Final status=" << toString(completed->status) << " fare=" << completed->fare->str() << "\n";
    return 0;
}

// Ride-Sharing Service (Uber/Lyft) — full LLD implementation with demo.
// Single-file Node/JS translation of the Mermaid class diagram in section J.
'use strict';

// ---------- Value objects ----------
class Money {
  constructor(cents) { this.cents = cents; }
  static of(dollars) { return new Money(Math.round(dollars * 100)); }
  times(factor) { return new Money(Math.round(this.cents * factor)); }
  toString() { return `$${Math.floor(this.cents / 100)}.${String(this.cents % 100).padStart(2, '0')}`; }
}

// Immutable geo point. Distance math lives here; storage/indexing is GeoIndex's job.
class Location {
  constructor(lat, lng) { this.lat = lat; this.lng = lng; }
  distanceTo(o) { // haversine great-circle distance in km
    const R = 6371.0;
    const dLat = (o.lat - this.lat) * Math.PI / 180;
    const dLng = (o.lng - this.lng) * Math.PI / 180;
    const a = Math.sin(dLat / 2) ** 2
      + Math.cos(this.lat * Math.PI / 180) * Math.cos(o.lat * Math.PI / 180) * Math.sin(dLng / 2) ** 2;
    return R * 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
  }
}

class Vehicle {
  constructor(make, model, plate, type) { this.make = make; this.model = model; this.plate = plate; this.type = type; }
}

// ---------- Identity hierarchy ----------
class User {
  constructor(id, name, phone) { this.id = id; this.name = name; this.phone = phone; this.rating = 5.0; }
}

class Rider extends User {
  constructor(id, name, phone, paymentMethod) { super(id, name, phone); this.paymentMethod = paymentMethod; }
  requestRide(rideService, pickup, dropoff) { return rideService.requestRide(this, pickup, dropoff); }
}

const DriverStatus = Object.freeze({ AVAILABLE: 'AVAILABLE', RESERVED: 'RESERVED', ON_TRIP: 'ON_TRIP' });

class Driver extends User {
  constructor(id, name, phone, vehicle, location) {
    super(id, name, phone);
    this.vehicle = vehicle;            // composition: owned by this driver profile
    this.currentLocation = location;   // composition: has no meaning detached from the driver
    this.status = DriverStatus.AVAILABLE;
  }
  // Atomic (in a real system, CAS-guarded) check-and-set: AVAILABLE -> RESERVED.
  tryReserve() {
    if (this.status === DriverStatus.AVAILABLE) { this.status = DriverStatus.RESERVED; return true; }
    return false;
  }
  release() { this.status = DriverStatus.AVAILABLE; }
  markOnTrip() { this.status = DriverStatus.ON_TRIP; }
  updateLocation(loc) { this.currentLocation = loc; }
  accept(rideService, rideId) { rideService.acceptRide(rideId, this); }
  reject(rideService, rideId) { rideService.rejectRide(rideId, this); }
}

// ---------- Ride: guarded state machine ----------
const RideStatus = Object.freeze({
  REQUESTED: 'REQUESTED', MATCHED: 'MATCHED', ACCEPTED: 'ACCEPTED', ARRIVED: 'ARRIVED',
  IN_PROGRESS: 'IN_PROGRESS', COMPLETED: 'COMPLETED', CANCELLED: 'CANCELLED', NO_DRIVER_FOUND: 'NO_DRIVER_FOUND',
});

const ALLOWED_TRANSITIONS = {
  [RideStatus.REQUESTED]: new Set([RideStatus.MATCHED, RideStatus.NO_DRIVER_FOUND, RideStatus.CANCELLED]),
  [RideStatus.MATCHED]: new Set([RideStatus.ACCEPTED, RideStatus.REQUESTED, RideStatus.CANCELLED]),
  [RideStatus.ACCEPTED]: new Set([RideStatus.ARRIVED, RideStatus.CANCELLED]),
  [RideStatus.ARRIVED]: new Set([RideStatus.IN_PROGRESS, RideStatus.CANCELLED]),
  [RideStatus.IN_PROGRESS]: new Set([RideStatus.COMPLETED]),
  [RideStatus.COMPLETED]: new Set(),
  [RideStatus.CANCELLED]: new Set(),
  [RideStatus.NO_DRIVER_FOUND]: new Set(),
};

class Ride {
  constructor(id, rider, pickup, dropoff) {
    this.id = id;
    this.rider = rider;       // association — rider exists independently of the ride
    this.pickup = pickup;
    this.dropoff = dropoff;
    this.driver = null;       // association — set once matched
    this.status = RideStatus.REQUESTED;
    this.fare = null;
    this.requestedAt = Date.now();
  }

  // Guarded transition — throws if the target state isn't reachable from the current one.
  transitionTo(next, withDriver) {
    if (!ALLOWED_TRANSITIONS[this.status].has(next)) {
      throw new Error(`Illegal ride transition: ${this.status} -> ${next}`);
    }
    this.status = next;
    if (withDriver) this.driver = withDriver;
  }
}

// ---------- GeoIndex ----------
// Spatial lookup of drivers via a coarse lat/lng grid. Ranking is left to MatchingStrategy.
class GeoIndex {
  constructor() {
    this.GRID_DEG = 0.05; // ~5km buckets
    this.buckets = new Map();
    this.driverBucket = new Map();
  }
  _bucketKey(loc) {
    const gx = Math.round(loc.lat / this.GRID_DEG);
    const gy = Math.round(loc.lng / this.GRID_DEG);
    return `${gx}:${gy}`;
  }
  register(driver) { this.update(driver, driver.currentLocation); }
  update(driver, loc) {
    const old = this.driverBucket.get(driver.id);
    if (old && this.buckets.has(old)) {
      this.buckets.set(old, this.buckets.get(old).filter((d) => d.id !== driver.id));
    }
    const k = this._bucketKey(loc);
    if (!this.buckets.has(k)) this.buckets.set(k, []);
    this.buckets.get(k).push(driver);
    this.driverBucket.set(driver.id, k);
    driver.updateLocation(loc);
  }
  // Scans the 3x3 neighborhood of grid cells and filters by real distance.
  findNearby(loc, radiusKm) {
    const gx = Math.round(loc.lat / this.GRID_DEG);
    const gy = Math.round(loc.lng / this.GRID_DEG);
    const result = [];
    for (let dx = -1; dx <= 1; dx++) {
      for (let dy = -1; dy <= 1; dy++) {
        const cell = this.buckets.get(`${gx + dx}:${gy + dy}`);
        if (!cell) continue;
        for (const d of cell) {
          if (d.currentLocation.distanceTo(loc) <= radiusKm) result.push(d);
        }
      }
    }
    return result;
  }
}

// ---------- Strategies ----------
class MatchingStrategy {
  match(ride, candidates) { throw new Error('not implemented'); } // eslint-disable-line no-unused-vars
}

class NearestDriverStrategy extends MatchingStrategy {
  match(ride, candidates) {
    let best = null, bestDist = Infinity;
    for (const d of candidates) {
      if (d.status !== DriverStatus.AVAILABLE) continue;
      const dist = d.currentLocation.distanceTo(ride.pickup);
      if (dist < bestDist) { bestDist = dist; best = d; }
    }
    return best;
  }
}

class FareStrategy {
  calculate(ride) { throw new Error('not implemented'); } // eslint-disable-line no-unused-vars
}

class DistanceTimeFareStrategy extends FareStrategy {
  calculate(ride) {
    const BASE = 2.50, PER_KM = 1.25, PER_MIN = 0.20, AVG_SPEED_KMH = 30.0;
    const distanceKm = ride.pickup.distanceTo(ride.dropoff);
    const minutes = (distanceKm / AVG_SPEED_KMH) * 60.0;
    return Money.of(BASE + PER_KM * distanceKm + PER_MIN * minutes);
  }
}

// Decorator: multiplies any wrapped FareStrategy's result during high demand. Not a rival Strategy.
class SurgeFareDecorator extends FareStrategy {
  constructor(wrapped, multiplier) { super(); this.wrapped = wrapped; this.multiplier = multiplier; }
  calculate(ride) { return this.wrapped.calculate(ride).times(this.multiplier); }
}

// ---------- Observer ----------
class NotificationService {
  onRideStatusChanged(ride) {
    console.log(`[notify] ride ${ride.id} -> ${ride.status}${ride.driver ? ` (driver ${ride.driver.name})` : ''}`);
  }
}

// ---------- RideService (facade) ----------
class RideService {
  constructor(geoIndex, matchingStrategy, fareStrategy, notificationService) {
    this.DEFAULT_RADIUS_KM = 5.0;
    this.geoIndex = geoIndex;
    this.matchingStrategy = matchingStrategy;
    this.fareStrategy = fareStrategy;
    this.notificationService = notificationService;
    this.rides = new Map();
    this.counter = 0;
  }

  requestRide(rider, pickup, dropoff) {
    const ride = new Ride(`R-${++this.counter}`, rider, pickup, dropoff);
    this.rides.set(ride.id, ride);
    this._attemptMatch(ride, new Set());
    return ride;
  }

  // Core matching loop: rank candidates, reserve atomically, retry on lost race.
  _attemptMatch(ride, excludedDriverIds) {
    let candidates = this.geoIndex.findNearby(ride.pickup, this.DEFAULT_RADIUS_KM)
      .filter((d) => !excludedDriverIds.has(d.id));
    while (candidates.length > 0) {
      const driver = this.matchingStrategy.match(ride, candidates);
      if (!driver) break;
      if (driver.tryReserve()) { // atomic CAS: AVAILABLE -> RESERVED
        ride.transitionTo(RideStatus.MATCHED, driver);
        this.notificationService.onRideStatusChanged(ride);
        return;
      }
      candidates = candidates.filter((d) => d.id !== driver.id); // someone else grabbed it first, retry
    }
    ride.transitionTo(RideStatus.NO_DRIVER_FOUND, null);
    this.notificationService.onRideStatusChanged(ride);
  }

  acceptRide(rideId, driver) {
    const ride = this.rides.get(rideId);
    if (ride.driver !== driver) throw new Error(`Driver mismatch for ride ${rideId}`);
    ride.transitionTo(RideStatus.ACCEPTED, driver);
    this.notificationService.onRideStatusChanged(ride);
  }

  // Rejection releases the driver and re-triggers matching, excluding the driver who just rejected.
  rejectRide(rideId, driver) {
    const ride = this.rides.get(rideId);
    driver.release();
    ride.transitionTo(RideStatus.REQUESTED, null);
    ride.driver = null;
    this._attemptMatch(ride, new Set([driver.id]));
  }

  arriveAtPickup(rideId) { this.rides.get(rideId).transitionTo(RideStatus.ARRIVED, null); }

  startRide(rideId) {
    const ride = this.rides.get(rideId);
    ride.transitionTo(RideStatus.IN_PROGRESS, null); // ARRIVED -> IN_PROGRESS
    ride.driver.markOnTrip();
    this.notificationService.onRideStatusChanged(ride);
  }

  completeRide(rideId) {
    const ride = this.rides.get(rideId);
    ride.transitionTo(RideStatus.COMPLETED, null); // throws if not currently IN_PROGRESS
    const fare = this.fareStrategy.calculate(ride); // may itself be a decorator chain
    ride.fare = fare;
    console.log(`[payment] charged ${fare.toString()} to ${ride.rider.name}`);
    ride.driver.release(); // RESERVED/ON_TRIP -> AVAILABLE
    this.notificationService.onRideStatusChanged(ride);
    return ride;
  }

  cancelRide(rideId, cancelledBy) {
    const ride = this.rides.get(rideId);
    if (ride.driver) ride.driver.release();
    ride.transitionTo(RideStatus.CANCELLED, null);
    console.log(`[cancel] ride ${rideId} cancelled by ${cancelledBy}`);
    this.notificationService.onRideStatusChanged(ride);
  }
}

// ---------- Demo ----------
function main() {
  const geoIndex = new GeoIndex();
  const matching = new NearestDriverStrategy();
  const fare = new SurgeFareDecorator(new DistanceTimeFareStrategy(), 1.5); // 1.5x surge active
  const notifications = new NotificationService();
  const rideService = new RideService(geoIndex, matching, fare, notifications);

  const d1 = new Driver('d1', 'Sam', '555-1', new Vehicle('Toyota', 'Camry', 'ABC-123', 'Sedan'), new Location(37.77, -122.42));
  const d2 = new Driver('d2', 'Jamie', '555-2', new Vehicle('Honda', 'Civic', 'XYZ-987', 'Sedan'), new Location(37.80, -122.41));
  geoIndex.register(d1);
  geoIndex.register(d2);

  const rider = new Rider('r1', 'Priya', '555-9', 'card-ending-4242');
  const ride = rider.requestRide(rideService, new Location(37.775, -122.418), new Location(37.79, -122.40));
  console.log(`After match: status=${ride.status} driver=${ride.driver ? ride.driver.name : 'none'}`);

  ride.driver.accept(rideService, ride.id);
  rideService.arriveAtPickup(ride.id);
  rideService.startRide(ride.id);
  const completed = rideService.completeRide(ride.id);
  console.log(`Final status=${completed.status} fare=${completed.fare.toString()}`);
}

if (require.main === module) {
  main();
}

module.exports = {
  Money, Location, Vehicle, User, Rider, Driver, DriverStatus, Ride, RideStatus,
  GeoIndex, MatchingStrategy, NearestDriverStrategy, FareStrategy, DistanceTimeFareStrategy,
  SurgeFareDecorator, NotificationService, RideService,
};

// Ride-Sharing Service (Uber/Lyft) — full LLD implementation with demo.
// Single-file TypeScript translation of the Mermaid class diagram in section J.

// ---------- Value objects ----------
class Money {
  private constructor(public readonly cents: number) {}
  static of(dollars: number): Money { return new Money(Math.round(dollars * 100)); }
  times(factor: number): Money { return new Money(Math.round(this.cents * factor)); }
  toString(): string { return `$${Math.floor(this.cents / 100)}.${String(this.cents % 100).padStart(2, '0')}`; }
}

// Immutable geo point. Distance math lives here; storage/indexing is GeoIndex's job.
class Location {
  constructor(public readonly lat: number, public readonly lng: number) {}
  distanceTo(o: Location): number { // haversine great-circle distance in km
    const R = 6371.0;
    const dLat = (o.lat - this.lat) * Math.PI / 180;
    const dLng = (o.lng - this.lng) * Math.PI / 180;
    const a = Math.sin(dLat / 2) ** 2
      + Math.cos(this.lat * Math.PI / 180) * Math.cos(o.lat * Math.PI / 180) * Math.sin(dLng / 2) ** 2;
    return R * 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
  }
}

class Vehicle {
  constructor(
    public readonly make: string, public readonly model: string,
    public readonly plate: string, public readonly type: string,
  ) {}
}

// ---------- Identity hierarchy ----------
abstract class User {
  rating = 5.0;
  constructor(public readonly id: string, public readonly name: string, public readonly phone: string) {}
}

class Rider extends User {
  constructor(id: string, name: string, phone: string, public readonly paymentMethod: string) {
    super(id, name, phone);
  }
  requestRide(rideService: RideService, pickup: Location, dropoff: Location): Ride {
    return rideService.requestRide(this, pickup, dropoff);
  }
}

enum DriverStatus { AVAILABLE = 'AVAILABLE', RESERVED = 'RESERVED', ON_TRIP = 'ON_TRIP' }

class Driver extends User {
  status: DriverStatus = DriverStatus.AVAILABLE;
  constructor(
    id: string, name: string, phone: string,
    public readonly vehicle: Vehicle,       // composition: owned by this driver profile
    public currentLocation: Location,       // composition: has no meaning detached from the driver
  ) { super(id, name, phone); }

  // Atomic (in a real system, CAS-guarded) check-and-set: AVAILABLE -> RESERVED.
  tryReserve(): boolean {
    if (this.status === DriverStatus.AVAILABLE) { this.status = DriverStatus.RESERVED; return true; }
    return false;
  }
  release(): void { this.status = DriverStatus.AVAILABLE; }
  markOnTrip(): void { this.status = DriverStatus.ON_TRIP; }
  updateLocation(loc: Location): void { this.currentLocation = loc; }
  accept(rideService: RideService, rideId: string): void { rideService.acceptRide(rideId, this); }
  reject(rideService: RideService, rideId: string): void { rideService.rejectRide(rideId, this); }
}

// ---------- Ride: guarded state machine ----------
enum RideStatus {
  REQUESTED = 'REQUESTED', MATCHED = 'MATCHED', ACCEPTED = 'ACCEPTED', ARRIVED = 'ARRIVED',
  IN_PROGRESS = 'IN_PROGRESS', COMPLETED = 'COMPLETED', CANCELLED = 'CANCELLED', NO_DRIVER_FOUND = 'NO_DRIVER_FOUND',
}

const ALLOWED_TRANSITIONS: Record<RideStatus, Set<RideStatus>> = {
  [RideStatus.REQUESTED]: new Set([RideStatus.MATCHED, RideStatus.NO_DRIVER_FOUND, RideStatus.CANCELLED]),
  [RideStatus.MATCHED]: new Set([RideStatus.ACCEPTED, RideStatus.REQUESTED, RideStatus.CANCELLED]),
  [RideStatus.ACCEPTED]: new Set([RideStatus.ARRIVED, RideStatus.CANCELLED]),
  [RideStatus.ARRIVED]: new Set([RideStatus.IN_PROGRESS, RideStatus.CANCELLED]),
  [RideStatus.IN_PROGRESS]: new Set([RideStatus.COMPLETED]),
  [RideStatus.COMPLETED]: new Set(),
  [RideStatus.CANCELLED]: new Set(),
  [RideStatus.NO_DRIVER_FOUND]: new Set(),
};

class Ride {
  driver: Driver | null = null;   // association — set once matched
  status: RideStatus = RideStatus.REQUESTED;
  fare: Money | null = null;
  readonly requestedAt: number = Date.now();

  constructor(
    public readonly id: string,
    public readonly rider: Rider,   // association — rider exists independently of the ride
    public readonly pickup: Location,
    public readonly dropoff: Location,
  ) {}

  // Guarded transition — throws if the target state isn't reachable from the current one.
  transitionTo(next: RideStatus, withDriver: Driver | null): void {
    if (!ALLOWED_TRANSITIONS[this.status].has(next)) {
      throw new Error(`Illegal ride transition: ${this.status} -> ${next}`);
    }
    this.status = next;
    if (withDriver) this.driver = withDriver;
  }
}

// ---------- GeoIndex ----------
// Spatial lookup of drivers via a coarse lat/lng grid. Ranking is left to MatchingStrategy.
class GeoIndex {
  private readonly GRID_DEG = 0.05; // ~5km buckets
  private readonly buckets = new Map<string, Driver[]>();
  private readonly driverBucket = new Map<string, string>();

  private bucketKey(loc: Location): string {
    const gx = Math.round(loc.lat / this.GRID_DEG);
    const gy = Math.round(loc.lng / this.GRID_DEG);
    return `${gx}:${gy}`;
  }

  register(driver: Driver): void { this.update(driver, driver.currentLocation); }

  update(driver: Driver, loc: Location): void {
    const old = this.driverBucket.get(driver.id);
    if (old && this.buckets.has(old)) {
      this.buckets.set(old, this.buckets.get(old)!.filter((d) => d.id !== driver.id));
    }
    const k = this.bucketKey(loc);
    if (!this.buckets.has(k)) this.buckets.set(k, []);
    this.buckets.get(k)!.push(driver);
    this.driverBucket.set(driver.id, k);
    driver.updateLocation(loc);
  }

  // Scans the 3x3 neighborhood of grid cells and filters by real distance.
  findNearby(loc: Location, radiusKm: number): Driver[] {
    const gx = Math.round(loc.lat / this.GRID_DEG);
    const gy = Math.round(loc.lng / this.GRID_DEG);
    const result: Driver[] = [];
    for (let dx = -1; dx <= 1; dx++) {
      for (let dy = -1; dy <= 1; dy++) {
        const cell = this.buckets.get(`${gx + dx}:${gy + dy}`);
        if (!cell) continue;
        for (const d of cell) {
          if (d.currentLocation.distanceTo(loc) <= radiusKm) result.push(d);
        }
      }
    }
    return result;
  }
}

// ---------- Strategies ----------
interface MatchingStrategy {
  match(ride: Ride, candidates: Driver[]): Driver | null;
}

class NearestDriverStrategy implements MatchingStrategy {
  match(ride: Ride, candidates: Driver[]): Driver | null {
    let best: Driver | null = null;
    let bestDist = Infinity;
    for (const d of candidates) {
      if (d.status !== DriverStatus.AVAILABLE) continue;
      const dist = d.currentLocation.distanceTo(ride.pickup);
      if (dist < bestDist) { bestDist = dist; best = d; }
    }
    return best;
  }
}

interface FareStrategy {
  calculate(ride: Ride): Money;
}

class DistanceTimeFareStrategy implements FareStrategy {
  calculate(ride: Ride): Money {
    const BASE = 2.50, PER_KM = 1.25, PER_MIN = 0.20, AVG_SPEED_KMH = 30.0;
    const distanceKm = ride.pickup.distanceTo(ride.dropoff);
    const minutes = (distanceKm / AVG_SPEED_KMH) * 60.0;
    return Money.of(BASE + PER_KM * distanceKm + PER_MIN * minutes);
  }
}

// Decorator: multiplies any wrapped FareStrategy's result during high demand. Not a rival Strategy.
class SurgeFareDecorator implements FareStrategy {
  constructor(private readonly wrapped: FareStrategy, private readonly multiplier: number) {}
  calculate(ride: Ride): Money { return this.wrapped.calculate(ride).times(this.multiplier); }
}

// ---------- Observer ----------
class NotificationService {
  onRideStatusChanged(ride: Ride): void {
    console.log(`[notify] ride ${ride.id} -> ${ride.status}${ride.driver ? ` (driver ${ride.driver.name})` : ''}`);
  }
}

// ---------- RideService (facade) ----------
class RideService {
  private readonly DEFAULT_RADIUS_KM = 5.0;
  private readonly rides = new Map<string, Ride>();
  private counter = 0;

  constructor(
    private readonly geoIndex: GeoIndex,
    private readonly matchingStrategy: MatchingStrategy,
    private readonly fareStrategy: FareStrategy,
    private readonly notificationService: NotificationService,
  ) {}

  requestRide(rider: Rider, pickup: Location, dropoff: Location): Ride {
    const ride = new Ride(`R-${++this.counter}`, rider, pickup, dropoff);
    this.rides.set(ride.id, ride);
    this.attemptMatch(ride, new Set());
    return ride;
  }

  // Core matching loop: rank candidates, reserve atomically, retry on lost race.
  private attemptMatch(ride: Ride, excludedDriverIds: Set<string>): void {
    let candidates = this.geoIndex.findNearby(ride.pickup, this.DEFAULT_RADIUS_KM)
      .filter((d) => !excludedDriverIds.has(d.id));
    while (candidates.length > 0) {
      const driver = this.matchingStrategy.match(ride, candidates);
      if (!driver) break;
      if (driver.tryReserve()) { // atomic CAS: AVAILABLE -> RESERVED
        ride.transitionTo(RideStatus.MATCHED, driver);
        this.notificationService.onRideStatusChanged(ride);
        return;
      }
      candidates = candidates.filter((d) => d.id !== driver.id); // someone else grabbed it first, retry
    }
    ride.transitionTo(RideStatus.NO_DRIVER_FOUND, null);
    this.notificationService.onRideStatusChanged(ride);
  }

  acceptRide(rideId: string, driver: Driver): void {
    const ride = this.rides.get(rideId)!;
    if (ride.driver !== driver) throw new Error(`Driver mismatch for ride ${rideId}`);
    ride.transitionTo(RideStatus.ACCEPTED, driver);
    this.notificationService.onRideStatusChanged(ride);
  }

  // Rejection releases the driver and re-triggers matching, excluding the driver who just rejected.
  rejectRide(rideId: string, driver: Driver): void {
    const ride = this.rides.get(rideId)!;
    driver.release();
    ride.transitionTo(RideStatus.REQUESTED, null);
    ride.driver = null;
    this.attemptMatch(ride, new Set([driver.id]));
  }

  arriveAtPickup(rideId: string): void { this.rides.get(rideId)!.transitionTo(RideStatus.ARRIVED, null); }

  startRide(rideId: string): void {
    const ride = this.rides.get(rideId)!;
    ride.transitionTo(RideStatus.IN_PROGRESS, null); // ARRIVED -> IN_PROGRESS
    ride.driver!.markOnTrip();
    this.notificationService.onRideStatusChanged(ride);
  }

  completeRide(rideId: string): Ride {
    const ride = this.rides.get(rideId)!;
    ride.transitionTo(RideStatus.COMPLETED, null); // throws if not currently IN_PROGRESS
    const fare = this.fareStrategy.calculate(ride); // may itself be a decorator chain
    ride.fare = fare;
    console.log(`[payment] charged ${fare.toString()} to ${ride.rider.name}`);
    ride.driver!.release(); // RESERVED/ON_TRIP -> AVAILABLE
    this.notificationService.onRideStatusChanged(ride);
    return ride;
  }

  cancelRide(rideId: string, cancelledBy: string): void {
    const ride = this.rides.get(rideId)!;
    if (ride.driver) ride.driver.release();
    ride.transitionTo(RideStatus.CANCELLED, null);
    console.log(`[cancel] ride ${rideId} cancelled by ${cancelledBy}`);
    this.notificationService.onRideStatusChanged(ride);
  }
}

// ---------- Demo ----------
function main(): void {
  const geoIndex = new GeoIndex();
  const matching = new NearestDriverStrategy();
  const fare = new SurgeFareDecorator(new DistanceTimeFareStrategy(), 1.5); // 1.5x surge active
  const notifications = new NotificationService();
  const rideService = new RideService(geoIndex, matching, fare, notifications);

  const d1 = new Driver('d1', 'Sam', '555-1', new Vehicle('Toyota', 'Camry', 'ABC-123', 'Sedan'), new Location(37.77, -122.42));
  const d2 = new Driver('d2', 'Jamie', '555-2', new Vehicle('Honda', 'Civic', 'XYZ-987', 'Sedan'), new Location(37.80, -122.41));
  geoIndex.register(d1);
  geoIndex.register(d2);

  const rider = new Rider('r1', 'Priya', '555-9', 'card-ending-4242');
  const ride = rider.requestRide(rideService, new Location(37.775, -122.418), new Location(37.79, -122.40));
  console.log(`After match: status=${ride.status} driver=${ride.driver ? ride.driver.name : 'none'}`);

  ride.driver!.accept(rideService, ride.id);
  rideService.arriveAtPickup(ride.id);
  rideService.startRide(ride.id);
  const completed = rideService.completeRide(ride.id);
  console.log(`Final status=${completed.status} fare=${completed.fare!.toString()}`);
}

main();

export {
  Money, Location, Vehicle, User, Rider, Driver, DriverStatus, Ride, RideStatus,
  GeoIndex, MatchingStrategy, NearestDriverStrategy, FareStrategy, DistanceTimeFareStrategy,
  SurgeFareDecorator, NotificationService, RideService,
};