Detect Gaps in a UDP Feed

Exchange market data arrives over UDP multicast, because TCP's guarantees are bought with retransmissions and head-of-line blocking that a feed handler cannot afford. UDP gives you none of them: packets are dropped, delivered twice, and delivered out of order, and the only thing you get is a sequence number in every packet.

So the first job of every feed handler is to work out what it did not get.

Implement find_gaps(seqs, 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):

• missing: the sequences never seen, as inclusive (low, high) 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, a bitmap, a range() over the span, a set difference against a range, will exhaust memory or time. Work in packets.
• All values returned are exact integers.