// Leet 1396. Design Underground System

/*
An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.

Implement the UndergroundSystem class:

void checkIn(int id, string stationName, int t)
A customer with a card ID equal to id, checks in at the station stationName at time t.
A customer can only be checked into one place at a time.
void checkOut(int id, string stationName, int t)
A customer with a card ID equal to id, checks out from the station stationName at time t.
double getAverageTime(string startStation, string endStation)
Returns the average time it takes to travel from startStation to endStation.
The average time is computed from all the previous traveling times from startStation to endStation that happened directly, meaning a check in at startStation followed by a check out from endStation.
The time it takes to travel from startStation to endStation may be different from the time it takes to travel from endStation to startStation.
There will be at least one customer that has traveled from startStation to endStation before getAverageTime is called.
You may assume all calls to the checkIn and checkOut methods are
consistent. If a customer checks in at time t1 then checks out at timet2, then t1 < t2.
All events happen in chronological order.

Example 1:

Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

Output
[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);

undergroundSystem.checkOut(45, "Waterloo", 15);  // Customer 45 "Leyton" -> "Waterloo" in 15-3 = 12
undergroundSystem.checkOut(27, "Waterloo", 20);  // Customer 27 "Leyton" -> "Waterloo" in 20-10 = 10
undergroundSystem.checkOut(32, "Cambridge", 22); // Customer 32 "Paradise" -> "Cambridge" in 22-8 = 14

undergroundSystem.getAverageTime("Paradise", "Cambridge"); // return 14.00000. One trip "Paradise" -> "Cambridge", (14) / 1 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 11.00000. Two trips "Leyton" -> "Waterloo", (10 + 12) / 2 = 11
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 11.00000
undergroundSystem.checkOut(10, "Waterloo", 38);  // Customer 10 "Leyton" -> "Waterloo" in 38-24 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 12.00000. Three trips "Leyton" -> "Waterloo", (10 + 12 + 14) / 3 = 12
Example 2:

Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]

Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // Customer 2 "Leyton" -> "Paradise" in 30-21 = 9
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667, (5 + 6 + 9) / 3 = 6.66667
 

Constraints:

1 <= id, t <= 106
1 <= stationName.length, startStation.length, endStation.length <= 10
All strings consist of uppercase and lowercase English letters and digits.
There will be at most 2 * 104 calls in total to checkIn, checkOut, and getAverageTime.
Answers within 10-5 of the actual value will be accepted.
*/

#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

class UndergroundSystem {
public:
    struct PairHash {
        std::size_t operator()(const std::pair<std::string, std::string>& p) const noexcept {
            auto h1 = std::hash<std::string>{}(p.first);
            auto h2 = std::hash<std::string>{}(p.second);
            return h1 ^ (h2 << 1); // Simple combination; avoid collisions
        }
    };
    
    typedef pair<string /* station name */, int /* time */> StationInfo;
    typedef unordered_map<int /* custID */, StationInfo> CustMap;
    CustMap custMap;

    // Route statistics: (start, end) → (total time sum, trip count)
    struct RouteStats
    {
        int64_t totalTime = 0;
        int tripCount = 0;

        void print() { cout << format("   totalTime: {} tripCount: {}\n", totalTime, tripCount); }
    };
    
    typedef pair<string /* start station */, string /* end station */> StationsKey;
    unordered_map<StationsKey, RouteStats, PairHash> routeMap;
    
    UndergroundSystem() {};
    
    void checkIn(int id, string startStationName, int startTime) {
        custMap[id]={move(startStationName),startTime};
    }
    
    void checkOut(int id, string endStationName, int endTime) {
        auto it = custMap.find(id);
        // should always have a start/end

        const auto& [startStationName, startTime] = it->second;        

        cout << format("checkIn id: {}  start: {:<10} time: {:>4}\n", id , startStationName, startTime);
        cout << format("checOut id: {}    end: {:<10} time: {:>4}\n", id , endStationName, endTime);

        auto& stats = routeMap[{startStationName,endStationName}];
        stats.totalTime += endTime - startTime;
        stats.tripCount++;
        stats.print();        
    }
    
    double getAverageTime(string startStation, string endStation) {
        auto it = routeMap.find({move(startStation), move(endStation)});
        // iterator should be valid
        return double(it->second.totalTime)/it->second.tripCount;
    }
};

class UndergroundSystem_xAI {
public:
    // Current check-ins: customer id → (startStation, checkInTime)
    std::unordered_map<int, std::pair<std::string, int>> checkIns;

    // Route statistics: (start, end) → (total time sum, trip count)
    struct RouteStats {
        long long total = 0;
        int count = 0;
    };
    
    // Need hash for pair<string,string> in unordered_map (C++11/14 style)
    struct PairHash {
        std::size_t operator()(const std::pair<std::string, std::string>& p) const {
            return std::hash<std::string>{}(p.first) ^ 
                   (std::hash<std::string>{}(p.second) << 1);  // simple but decent
        }
    };
    
    std::unordered_map<std::pair<std::string, std::string>, RouteStats, PairHash> routes;

    UndergroundSystem_xAI() = default;

    void checkIn(int id, std::string stationName, int t) {
        // Production note: real system should check if already checked in
        checkIns[id] = {std::move(stationName), t};
    }

    void checkOut(int id, std::string stationName, int t) {
        auto it = checkIns.find(id);
        if (it == checkIns.end()) {
            // Invalid checkout — in interview: discuss logging/alerting
            return;
        }

        const auto& [startStation, startTime] = it->second;
        int travelTime = t - startTime;

        auto& stats = routes[{std::move(startStation), std::move(stationName)}];
        stats.total += travelTime;
        stats.count++;

        checkIns.erase(it);  // Crucial — prevent memory leak & wrong future calculations
    }

    double getAverageTime(std::string startStation, std::string endStation) {
        auto it = routes.find({std::move(startStation), std::move(endStation)});
        if (it == routes.end() || it->second.count == 0) {
            return 0.0;  // or throw — discuss in interview
        }
        return static_cast<double>(it->second.total) / it->second.count;
    }
};

/**
 * Your UndergroundSystem object will be instantiated and called as such:
 * UndergroundSystem* obj = new UndergroundSystem();
 * obj->checkIn(id,stationName,t);
 * obj->checkOut(id,stationName,t);
 * double param_3 = obj->getAverageTime(startStation,endStation);
 */

#define PRINT_TRIP(start, end, avgTime, expected)                       \
    cout << format("{:>15}-->{} avgTime: {:.4f}\n", start, end, avgTime); \
    EXPECT_DOUBLE_EQ(expected, avgTime);

void testCase1()
{
//    Input
//["UndergroundSystem",
//    "checkIn","checkIn","checkIn",
//    "checkOut","checkOut","checkOut",
//    "getAverageTime",
//    "getAverageTime",
//    "checkIn",
//    "getAverageTime",
//    "checkOut","
//    getAverageTime"]
//[[],
//    [45,"Leyton",3],
//    [32,"Paradise",8],
//    [27,"Leyton",10],
//    
//    [45,"Waterloo",15],
//    [27,"Waterloo",20],
//    [32,"Cambridge",22],
//    
//    ["Paradise","Cambridge"],
//    ["Leyton","Waterloo"],
//    
//    [10,"Leyton",24],
//    ["Leyton","Waterloo"],
//    
//    [10,"Waterloo",38],
//    ["Leyton","Waterloo"]]
// Output
// [null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

    UndergroundSystem s;

    cout << format("{:-^10}TestCase 1{:-^10}\n", '-', '-');    

    s.checkIn(45,"Leyton",3);
    s.checkIn(32,"Paradise",8);
    s.checkIn(27,"Leyton",10);
    
    s.checkOut(45,"Waterloo",15);
    s.checkOut(27,"Waterloo",20);
    s.checkOut(32,"Cambridge",22);

    // getAvgTime Paradise,Cambridge
    {
        UndergroundSystem::StationsKey key({"Paradise", "Cambridge"});
        double avgTime = s.getAverageTime(key.first, key.second);
        PRINT_TRIP(key.first, key.second, avgTime, 14.0);
    }
    // getAverageTime Leyton, Waterloo
    {
        UndergroundSystem::StationsKey key({"Leyton", "Waterloo"});
        double avgTime = s.getAverageTime(key.first, key.second);
        PRINT_TRIP(key.first, key.second, avgTime, 11.0);
    }

    cout << "checkIn(10,Leyton,24)" << endl;
    s.checkIn(10,"Leyton",24);

    // getAverageTime Leyton, Waterloo
    {
        UndergroundSystem::StationsKey key({"Leyton", "Waterloo"});
        double avgTime = s.getAverageTime(key.first, key.second);
        PRINT_TRIP(key.first, key.second, avgTime, 11.0);
    }

    cout << "checkOut(10,Waterloo,38)" << endl;
    s.checkOut(10,"Waterloo",38);    

    // getAverageTime Leyton, Waterloo
    {
        UndergroundSystem::StationsKey key({"Leyton", "Waterloo"});
        double avgTime = s.getAverageTime(key.first, key.second);
        PRINT_TRIP(key.first, key.second, avgTime, 12.0);
    }
}

void testCase2()
{
// Input    
//["UndergroundSystem",
//    "checkIn",
//    "checkOut",
//    "getAverageTime",
//    "checkIn",
//    "checkOut",
//    "getAverageTime",
//    "checkIn",
//    "checkOut",
//    "getAverageTime"]
//[[],
//    [10,"Leyton",3],
//    [10,"Paradise",8],
//    ["Leyton","Paradise"],
//    [5,"Leyton",10],
//    [5,"Paradise",16],
//    ["Leyton","Paradise"],
//    [2,"Leyton",21],
//    [2,"Paradise",30],
//    ["Leyton","Paradise"]]
// Output
// [null,null,null,5.00000,null,null,5.50000,null,null,6.66667]

    cout << format("{:-^10}TestCase 2{:-^10}\n", '-', '-');
    
    UndergroundSystem s;
    double avgTime;
    
    s.checkIn(10,"Leyton",3);
    s.checkOut(10,"Paradise",8);
    avgTime = s.getAverageTime("Leyton","Paradise");
    PRINT_TRIP("Leyton", "Paradise", avgTime, 5.0);

    s.checkIn(5,"Leyton",10);
    s.checkOut(5,"Paradise",16);
    avgTime = s.getAverageTime("Leyton","Paradise");
    PRINT_TRIP("Leyton", "Paradise", avgTime, 5.5);    

    s.checkIn(2,"Leyton",21);
    s.checkOut(2,"Paradise",30);
    avgTime = s.getAverageTime("Leyton","Paradise");
    PRINT_TRIP("Leyton", "Paradise", avgTime, 6.666666666666667);
}

int main(void)
{
    testCase1();
    testCase2();    
}