Detect Gaps in a UDP Feed

Implement find_gaps(seqs, first_seq). Given the sequence numbers of the packets that arrived, it reports which sequences are missing, how many arrivals were duplicates, and how many packets arrived.

Exchange market data arrives over UDP multicast, because TCP's guarantees cost retransmissions and head-of-line blocking that a feed handler cannot afford. UDP drops packets, delivers them twice and delivers them out of order. The only help it gives is a sequence number in every packet, so the first job of a feed handler is to work out what it did not get.

std::tuple<std::vector<std::pair<long long, long long>>, long long, long long> find_gaps(
    const std::vector<long long>& seqs, long long first_seq);

• seqs: the sequence numbers of the packets that arrived, in arrival order, which may be out of order and may repeat.
• first_seq: the sequence the capture is supposed to start at.

Return {missing, duplicates, received}. Each missing range is an inclusive {low, high} pair.

• missing: the sequences never seen, as inclusive ranges in ascending order, covering first_seq up to the highest sequence received. Nothing beyond the highest received counts as missing: you cannot tell a lost packet from a packet that has not been sent yet.
• duplicates: how many arrivals carried a sequence already seen.
• received: how many distinct sequences arrived.

If nothing arrived at all, return {{}, duplicates, 0}.

Examples

find_gaps({1, 2, 5, 4, 8}, 1);
// {{{3, 3}, {6, 7}}, 0, 5}

find_gaps({7, 8, 8, 9, 7, 12}, 7);
// {{{10, 11}}, 2, 4}

The first has 5 arriving before 4, which is reordering rather than loss and changes nothing: 3 is missing, and so are 6 and 7 as one range. In the second, 8 and 7 both arrive twice, which is what a retransmit request looks like from here, and the real hole is 10 to 11.

Constraints

• Up to \( 5 \times 10^5 \) arrivals. Sequence numbers are 64-bit non-negative integers, all at least first_seq.
• The sequence space is not the packet count. A feed that drops a multicast group for a minute leaves a hole of hundreds of millions of sequences, and the hidden performance case has one. Anything proportional to highest - first_seq will exhaust memory or time. Work in packets. The C++ performance case places the outage fifty billion sequences wide. That rules out a bitmap, a loop over the span, and a set difference against the span.
• All values returned are exact integers.