3508. Implement Router

Design a data structure that can efficiently manage data packets in a network router. Each data packet consists of the following attributes:

• source: A unique identifier for the machine that generated the packet.
• destination: A unique identifier for the target machine.
• timestamp: The time at which the packet arrived at the router.

Implement the Router class:

Router(int memoryLimit): Initializes the Router object with a fixed memory limit.

• memoryLimit is the maximum number of packets the router can store at any given time.
• If adding a new packet would exceed this limit, the oldest packet must be removed to free up space.

bool addPacket(int source, int destination, int timestamp): Adds a packet with the given attributes to the router.

• A packet is considered a duplicate if another packet with the same source, destination, and timestamp already exists in the router.
• Return true if the packet is successfully added (i.e., it is not a duplicate); otherwise return false.

int[] forwardPacket(): Forwards the next packet in FIFO (First In First Out) order.

• Remove the packet from storage.
• Return the packet as an array [source, destination, timestamp].
• If there are no packets to forward, return an empty array.

int getCount(int destination, int startTime, int endTime):

• Returns the number of packets currently stored in the router (i.e., not yet forwarded) that have the specified destination and have timestamps in the inclusive range [startTime, endTime].

Note that queries for addPacket will be made in increasing order of timestamp.

class Router {
    deque<vector<int>> packets;
    unordered_map<int,deque<int>> destPackets;
    set<vector<int>> setPackets;
    int size;
public:
    Router(int memoryLimit) : size(memoryLimit) {
    }

    bool addPacket(int source, int destination, int timestamp) {
        if(setPackets.count({source, destination, timestamp})) return false;
        if(packets.size() == size) forwardPacket();
        vector<int> packet{source,destination,timestamp};
        destPackets[destination].push_back(timestamp);
        setPackets.insert(packet);
        packets.push_back(packet);
        return true;
    }

    vector<int> forwardPacket() {
        if(packets.size() == 0) return {};
        vector<int> res = packets[0]; packets.pop_front();
        destPackets[res[1]].pop_front();
        setPackets.erase(res);
        return res;
    }

    int getCount(int destination, int startTime, int endTime) {
        return std::upper_bound(destPackets[destination].begin(), destPackets[destination].end(),endTime) -
                std::lower_bound(destPackets[destination].begin(), destPackets[destination].end(),startTime);
    }
};

/**
 * Your Router object will be instantiated and called as such:
 * Router* obj = new Router(memoryLimit);
 * bool param_1 = obj->addPacket(source,destination,timestamp);
 * vector<int> param_2 = obj->forwardPacket();
 * int param_3 = obj->getCount(destination,startTime,endTime);
 */