Ride Pooling Logic

// ─── JAVA BLUEPRINT ──────────────────────────────────────────────────────────
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;

enum StopType { PICKUP, DROPOFF }

class Location {
    final double x;
    final double y;

    public Location(double x, double y) {
        this.x = x;
        this.y = y;
    }

    public double distanceTo(Location other) {
        return Math.sqrt(Math.pow(this.x - other.x, 2) + Math.pow(this.y - other.y, 2));
    }
}

class Stop {
    private final StopType type;
    private final String riderId;
    private final Location location;

    public Stop(StopType type, String riderId, Location location) {
        this.type = type;
        this.riderId = riderId;
        this.location = location;
    }

    public StopType getType() { return type; }
    public String getRiderId() { return riderId; }
    public Location getLocation() { return location; }
}

class RideRequest {
    private final String riderId;
    private final Location pickup;
    private final Location dropoff;
    private final double maxDetourFactor; // e.g., 1.5 means max distance is 1.5 * direct distance

    public RideRequest(String riderId, Location pickup, Location dropoff, double maxDetourFactor) {
        this.riderId = riderId;
        this.pickup = pickup;
        this.dropoff = dropoff;
        this.maxDetourFactor = maxDetourFactor;
    }

    public String getRiderId() { return riderId; }
    public Location getPickup() { return pickup; }
    public Location getDropoff() { return dropoff; }
    public double getMaxDetourFactor() { return maxDetourFactor; }

    public double getDirectDistance() {
        return pickup.distanceTo(dropoff);
    }
}

// Strategy Pattern for Fare Splitting
interface FareSplittingStrategy {
    Map<String, Double> calculateFareSplits(PooledRoute route, double baseRatePerKm);
}

class SegmentBasedFareSplitStrategy implements FareSplittingStrategy {
    @Override
    public Map<String, Double> calculateFareSplits(PooledRoute route, double baseRatePerKm) {
        List<Stop> stops = route.getStops();
        Map<String, Double> finalFares = new HashMap<>();
        if (stops.size() < 2) return finalFares;

        Set<String> activeRiders = new HashSet<>();
        Location currentPos = stops.get(0).getLocation();

        for (int i = 0; i < stops.size(); i++) {
            Stop stop = stops.get(i);
            
            if (i > 0) {
                Location nextPos = stop.getLocation();
                double segmentDist = currentPos.distanceTo(nextPos);
                double segmentCost = segmentDist * baseRatePerKm;

                if (!activeRiders.isEmpty()) {
                    double splitCost = segmentCost / activeRiders.size();
                    for (String rider : activeRiders) {
                        finalFares.put(rider, finalFares.getOrDefault(rider, 0.0) + splitCost);
                    }
                }
                currentPos = nextPos;
            }

            if (stop.getType() == StopType.PICKUP) {
                activeRiders.add(stop.getRiderId());
            } else {
                activeRiders.remove(stop.getRiderId());
            }
        }
        return finalFares;
    }
}

class PooledRoute {
    private final String driverId;
    private final int capacity;
    private final List<Stop> stops = new ArrayList<>();
    private final Map<String, RideRequest> riderRequests = new HashMap<>();

    public PooledRoute(String driverId, int capacity, Location startLocation) {
        this.driverId = driverId;
        this.capacity = capacity;
        // Seed driver start location stop
        this.stops.add(new Stop(StopType.PICKUP, "DRIVER", startLocation));
    }

    public String getDriverId() { return driverId; }
    public int getCapacity() { return capacity; }
    public List<Stop> getStops() { return stops; }

    public double calculateTotalDistance() {
        return getRouteDistance(stops);
    }

    public boolean tryInsertRider(RideRequest req) {
        int bestPickupIdx = -1;
        int bestDropoffIdx = -1;
        double minDistance = Double.MAX_VALUE;

        // Iterate over all insertion points
        for (int i = 1; i <= stops.size(); i++) {
            for (int j = i; j <= stops.size(); j++) {
                List<Stop> testStops = new ArrayList<>(stops);
                testStops.add(i, new Stop(StopType.PICKUP, req.getRiderId(), req.getPickup()));
                testStops.add(j + 1, new Stop(StopType.DROPOFF, req.getRiderId(), req.getDropoff()));

                if (isValidRoute(testStops, req)) {
                    double dist = getRouteDistance(testStops);
                    if (dist < minDistance) {
                        minDistance = dist;
                        bestPickupIdx = i;
                        bestDropoffIdx = j;
                    }
                }
            }
        }

        if (bestPickupIdx != -1) {
            stops.add(bestPickupIdx, new Stop(StopType.PICKUP, req.getRiderId(), req.getPickup()));
            stops.add(bestDropoffIdx + 1, new Stop(StopType.DROPOFF, req.getRiderId(), req.getDropoff()));
            riderRequests.put(req.getRiderId(), req);
            return true;
        }
        return false;
    }

    private boolean isValidRoute(List<Stop> routeStops, RideRequest newReq) {
        int currentRiders = 0;
        // Verify capacity is never violated
        for (Stop stop : routeStops) {
            if (stop.getType() == StopType.PICKUP && !stop.getRiderId().equals("DRIVER")) {
                currentRiders++;
            } else if (stop.getType() == StopType.DROPOFF) {
                currentRiders--;
            }
            if (currentRiders > capacity) return false;
        }

        // Verify detour constraint for all riders including the new one
        Map<String, Double> actualDistances = calculateTravelDistances(routeStops);
        
        // 1. Check existing riders
        for (Map.Entry<String, RideRequest> entry : riderRequests.entrySet()) {
            double actual = actualDistances.getOrDefault(entry.getKey(), 0.0);
            double limit = entry.getValue().getDirectDistance() * entry.getValue().getMaxDetourFactor();
            if (actual > limit) return false;
        }

        // 2. Check the candidate rider
        double candidateActual = actualDistances.getOrDefault(newReq.getRiderId(), 0.0);
        double candidateLimit = newReq.getDirectDistance() * newReq.getMaxDetourFactor();
        return candidateActual <= candidateLimit;
    }

    private Map<String, Double> calculateTravelDistances(List<Stop> routeStops) {
        Map<String, Double> distanceMap = new HashMap<>();
        Map<String, Double> startAccumulated = new HashMap<>();
        
        double currentTotal = 0.0;
        Location prev = routeStops.get(0).getLocation();

        for (Stop stop : routeStops) {
            currentTotal += prev.distanceTo(stop.getLocation());
            prev = stop.getLocation();

            if (stop.getType() == StopType.PICKUP && !stop.getRiderId().equals("DRIVER")) {
                startAccumulated.put(stop.getRiderId(), currentTotal);
            } else if (stop.getType() == StopType.DROPOFF) {
                double pickupTotal = startAccumulated.getOrDefault(stop.getRiderId(), 0.0);
                distanceMap.put(stop.getRiderId(), currentTotal - pickupTotal);
            }
        }
        return distanceMap;
    }

    private double getRouteDistance(List<Stop> routeStops) {
        if (routeStops.size() < 2) return 0.0;
        double distance = 0.0;
        for (int i = 0; i < routeStops.size() - 1; i++) {
            distance += routeStops.get(i).getLocation().distanceTo(routeStops.get(i + 1).getLocation());
        }
        return distance;
    }
}

class RideMatchingManager {
    private final List<PooledRoute> activeRoutes = new CopyOnWriteArrayList<>();
    private final ReentrantLock lock = new ReentrantLock();

    public void addRoute(PooledRoute route) {
        activeRoutes.add(route);
    }

    public boolean matchRider(RideRequest request) {
        lock.lock();
        try {
            for (PooledRoute route : activeRoutes) {
                if (route.tryInsertRider(request)) {
                    System.out.println("Matched Rider " + request.getRiderId() + " to Driver " + route.getDriverId());
                    return true;
                }
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

    public List<PooledRoute> getActiveRoutes() {
        return activeRoutes;
    }
}

// Complete Simulation
public class Main {
    public static void main(String[] args) {
        RideMatchingManager manager = new RideMatchingManager();

        // 1. Create a route representing a driver from origin (0, 0)
        PooledRoute route = new PooledRoute("D-101", 3, new Location(0.0, 0.0));
        manager.addRoute(route);

        // 2. Submit concurrent or sequential ride requests
        System.out.println("--- Submitting ride request 1 (R-1) ---");
        RideRequest req1 = new RideRequest("R-1", new Location(1.0, 1.0), new Location(5.0, 5.0), 1.5);
        boolean success1 = manager.matchRider(req1);
        System.out.println("Match success: " + success1);

        System.out.println("\n--- Submitting ride request 2 (R-2) with close overlap ---");
        RideRequest req2 = new RideRequest("R-2", new Location(2.0, 1.5), new Location(4.5, 4.0), 1.4);
        boolean success2 = manager.matchRider(req2);
        System.out.println("Match success: " + success2);

        // 3. Compute final segment splits
        System.out.println("\n--- Calculating Fair splits for overlapping segments ---");
        FareSplittingStrategy splitStrategy = new SegmentBasedFareSplitStrategy();
        Map<String, Double> splits = splitStrategy.calculateFareSplits(route, 2.5); // $2.5 per unit distance
        for (Map.Entry<String, Double> entry : splits.entrySet()) {
            System.out.println("Rider " + entry.getKey() + " Fare: $" + String.format("%.2f", entry.getValue()));
        }
    }
}