BG Metro

Napisati klasu metro koja implementira sistem za praćenje putnika u metro mreži. Klasa treba da podržava sledeće operacije:

Sve operacije treba da budu implementirane tako da rade u očekivanoj vremenskoj složenosti $O(1)$.

Ulaz

Sa standardnog ulaza se učitavaju naredbe u formatu:

Izlaz

Na standardni izlaz ispisati rezultate izvršavanja naredbi a. Ukoliko ne postoje podaci za zadatu rutu, ispisati poruku Nema podataka za zadatu rutu na standardni izlaz za greške.

Primer

stdin

i 1 Vukov_spomenik 10
i 2 Vukov_spomenik 20
o 1 Novi_Beograd 45
o 2 Novi_Beograd 45
a Vukov_spomenik Novi_Beograd
i 3 Karadjordjev_park 30
o 3 Vukov_spomenik 38
a Karadjordjev_park Vukov_spomenik
i 4 Vukov_spomenik 50
o 4 Novi_Beograd 65
a Vukov_spomenik Novi_Beograd
a Vukov_spomenik Zemun

stdout

30
8
25

stderr

Nema podataka za zadatu rutu

Rešenje

main.cpp

#include <iostream>
#include <string>
#include <unordered_map>
#include <utility>

namespace matf
{
	/* Klasa za metro */
	class metro
	{
		public:
			typedef unsigned int PassengerID;
			typedef unsigned int Time;

			typedef struct {
				std::string station_name;
				Time timestamp;
			} CheckInInfo;

			typedef struct {
				Time total_time;
				size_t trip_count;
			} RouteStats;

			struct Route {
				std::string start_station;
				std::string end_station;

				bool operator==(const Route &other) const noexcept {
					return start_station == other.start_station && end_station == other.end_station;
				}
			};

		public:
			/* Evidentira ulazak putnika u stanicu */
			void check_in(const PassengerID id, const std::string& station_name, const Time t)
			{
				active_check_ins[id] = { station_name, t };
			}

			/* Evidentira izlazak putnika iz stanice */
			void check_out(const PassengerID id, const std::string& station_name, const Time t)
			{
				auto it = active_check_ins.find(id);
				if (it == active_check_ins.end()) {
					throw std::invalid_argument("Putnik nije evidentiran na ulazu");
				}

				const CheckInInfo& check_in_info = it->second;
				std::string route_start = check_in_info.station_name;
				Time start_time = check_in_info.timestamp;

				Route route = { route_start, station_name };
				RouteStats& stats = travel_stats[route];
				stats.total_time += (t - start_time); // ukupno vreme
				stats.trip_count += 1; // broj putovanja

				active_check_ins.erase(it);
			}

			/* Vraca prosecno vreme putovanja izmedju dve stanice */
			double get_average_time(const std::string& start_station, const std::string& end_station) const
			{
				Route route = { start_station, end_station };
				auto it = travel_stats.find(route);
				if (it == travel_stats.end() || it->second.trip_count == 0) {
					throw std::invalid_argument("Nema podataka za zadatu rutu");
				}

				const RouteStats& stats = it->second;
				return ((double) stats.total_time) / stats.trip_count;
			}

		private:
			// Hash functor za tip Route
			struct route_hash {
				size_t operator()(const Route &r) const noexcept {
					return std::hash<std::string>{}(r.start_station) ^ (std::hash<std::string>{}(r.end_station) << 1);
				}
			};

		private:
			std::unordered_map<PassengerID, CheckInInfo> active_check_ins;
			std::unordered_map<Route, RouteStats, route_hash> travel_stats;
	};
};

int main(void)
{
	matf::metro metro_system;

	char op;

	while (std::cin >> op) {
		if (op == 'i') { // check-in
			matf::metro::PassengerID id; std::string station; matf::metro::Time time;
			std::cin >> id >> station >> time;
			metro_system.check_in(id, station, time);
		} else if (op == 'o') { // check-out
			matf::metro::PassengerID id; std::string station; matf::metro::Time time;
			std::cin >> id >> station >> time;
			metro_system.check_out(id, station, time);
		} else if (op == 'a') { // average time
			std::string start_station, end_station;
			std::cin >> start_station >> end_station;
			try {
				double avg_time = metro_system.get_average_time(start_station, end_station);
				std::cout << avg_time << std::endl;
			} catch (const std::invalid_argument& e) {
				std::cerr << e.what() << std::endl;
			}
		}
	}

	return 0;
}