Range Tracker

A download manager fetches a huge file in pieces and keeps track of which bytes it has. Ranges are half-open: (left, right) means the bytes left, left + 1, ..., right - 1. Build a RangeTracker class:

• RangeTracker() starts with nothing tracked.
• add(left, right) marks every byte in [left, right) as tracked. Bytes that were already tracked stay tracked.
• remove(left, right) marks every byte in [left, right) as not tracked.
• covers(left, right) returns True if every byte in [left, right) is tracked, and False otherwise.
• total() returns how many bytes are tracked.
• ranges() returns the tracked bytes as a list of (left, right) tuples sorted by left, merged so that no two ranges overlap or touch.

Examples

rt = RangeTracker()
rt.add(10, 20)
rt.add(30, 40)
rt.covers(12, 18)    # returns True
rt.covers(15, 35)    # returns False
rt.add(20, 30)
rt.covers(15, 35)    # returns True
rt.remove(25, 27)
rt.ranges()          # returns [(10, 25), (27, 40)]
rt.total()           # returns 28

Constraints

• 0 <= left < right <= 10^18 in every call, so a set of every tracked byte would be enormous
• Up to 70,000 calls; ranges() is called rarely
• Going through every tracked range on each call is too slow when there are tens of thousands of them.