class Router {
public:
Router(int memoryLimit): memoryLimit_{memoryLimit}, size_{0} {
}
bool addPacket(int source, int destination, int timestamp) {
if (!p_.insert(getKey(source, destination, timestamp)).second){
return false;
}
if (size_ == memoryLimit_) {
forwardPacket(); // remove the oldest.
}
packets_.emplace_back(source, destination, timestamp);
c_[destination].emplace_back(timestamp);
++size_;
return true;
}
vector<int> forwardPacket() {
if (size_ == 0) return {};
auto [src, dst, timestamp] = packets_.front();
packets_.pop_front();
--size_;
c_[dst].pop_front();
p_.erase(getKey(src, dst, timestamp));
return {src, dst, timestamp};
}
int getCount(int destination, int startTime, int endTime) {
if (!c_.count(destination)) return 0;
const auto& q = c_[destination];
auto it1 = lower_bound(begin(q), end(q), startTime);
auto it2 = upper_bound(begin(q), end(q), endTime);
return it2 - it1;
}
private:
// https://zxi.mytechroad.com/blog/uncategorized/leetcode-3508-implement-router/
string getKey(int s, int d, int t) {
return to_string(s) + "_" + to_string(d) + "_" + to_string(t);
}
int memoryLimit_;
int size_;
unordered_set<string> p_; // {f'{src}_{dst}_{timestamp}'}
deque<tuple<int, int, int>> packets_; // {{src, dst, timestamp}}
unordered_map<int, deque<int>> c_; // {dst -> timestamp}
};
