CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 4 of 6 · 4 min read

The code

Reserve, trip states and fares.

The driver's reserve step is a single synchronized check-and-set:

class Driver {
    final String id; private Point loc; private DriverState state = DriverState.OFFLINE;

    synchronized boolean tryReserve() {
        if (state != DriverState.AVAILABLE) return false;
        state = DriverState.ON_TRIP;
        return true;
    }
    synchronized void release(Point where) { loc = where; state = DriverState.AVAILABLE; }
}

The trip checks every move against a table of what is legal from the current state:

synchronized void move(TripState next) {
    boolean ok = switch (state) {
        case REQUESTED -> next == TripState.ASSIGNED || next == TripState.CANCELLED;
        case ASSIGNED  -> next == TripState.STARTED  || next == TripState.CANCELLED;
        case STARTED   -> next == TripState.COMPLETED;
        default        -> false;
    };
    if (!ok) throw new IllegalStateException(state + " -> " + next + " not allowed");
    state = next;
}

The service ties them together:

Optional<Trip> request(String rider, Point from, Point to) {
    Trip t = new Trip(nid(), rider, from, to);
    trips.put(t.id, t);
    for (Driver d : matcher.rank(drivers.values(), from)) {
        if (d.tryReserve()) { t.driver = d; t.move(TripState.ASSIGNED); return Optional.of(t); }
    }
    t.move(TripState.CANCELLED);                  // nobody free
    return Optional.empty();
}

long complete(Trip t, int minutes) {
    t.move(TripState.COMPLETED);
    t.driver.release(t.to);                       // the driver is now at the drop-off point
    return fares.fare(t.from.dist(t.to), minutes);
}

void cancel(Trip t) {
    TripState was = t.state();
    t.move(TripState.CANCELLED);
    if (was == TripState.ASSIGNED) t.driver.release(t.driver.loc());
}

The fare rule uses cents (Level 7, module 6), and the surge is a wrapper:

class BaseFare implements FareRule {
    public long fare(double km, int min) { return 5000 + Math.round(km * 1200) + min * 100L; }
}
class Surge implements FareRule {
    final FareRule base; final double mult;
    Surge(FareRule b, double m) { base = b; mult = m; }
    public long fare(double km, int min) { return Math.round(base.fare(km, min) * mult); }
}

The numbers in BaseFare are made up to show the idea: a base of 50.00, 12.00 per kilometre and 1.00 per minute.

A run with three drivers: D1 at (0,0), D2 at (5,0) and D3 at (1,1), all online.

Step Result
Rider asks for a pickup at (4,0) going to (10,0) D2 is assigned, being 1 unit away. The trip is assigned
Start the trip, then complete it after 12 minutes Fare 13400 cents (6 km: 5000 + 7200 + 1200). D2 is now at (10,0) and available
Another rider asks at (0,0) D1 is assigned, since D2 is now far away
Cancel that trip before it starts The trip is cancelled and D1 is available again
Start the cancelled trip Refused: "CANCELLED -> STARTED not allowed"
All drivers go offline, then a rider asks No driver, the answer is empty
The same 6 km, 12 minute trip with a 1.5 surge 20100 cents

A race test: five drivers online, and 40 riders ask at once on 16 threads. Exactly 5 requests succeed, and they hold 5 different drivers, X0 to X4. The other 35 are told no driver is free. Without the atomic tryReserve, one driver could appear on two trips.

Check yourself: 1. What does tryReserve do if the driver is already on a trip? 2. Why does cancel check the state before releasing the driver? 3. How many trips succeed with 5 drivers and 40 simultaneous riders?