A website logs every click as an event (time, user), in order of time (times never decrease). A visit of a user is a maximal run of that user's clicks in which consecutive clicks are at most gap apart; a click more than gap after the user's previous one starts a new visit.
Write a generator visits(events, gap) that yields every visit as a tuple (user, start, end, clicks): the times of its first and last click and its number of clicks. The stream may be endless, so a visit must be yielded as soon as it is certain to be finished: when an event arrives whose time is more than gap after the visit's last click, and before any later event is read. If one event finishes several visits, yield them ordered by end, then by user. When the stream ends, yield the visits still open in the same order.
Helpers available with Run: stream(items), first(gen, n), clicks(seed, users) (an endless click stream) and events_read(visits, events, k, gap), which counts the events pulled from the list events by the time the first k visits were taken.
Examples
Input: first(visits(stream([(0, "a"), (5, "b"), (20, "a"), (40, "b"), (41, "a"), (90, "c")]), 30), 10)
Output: [("b", 5, 5, 1), ("b", 40, 40, 1), ("a", 0, 41, 3), ("c", 90, 90, 1)]
Explanation: At time 40, b's first visit is finished (40 > 5 + 30); a's is not (20 + 30 >= 40), and a's
click at 41 extends it. At time 90 both open visits are finished: b's ends at 40, a's at 41. The stream
then ends and c's visit comes out.
Input: first(visits(stream([(0, "z"), (0, "y"), (10, "x")]), 5), 10)
Output: [("y", 0, 0, 1), ("z", 0, 0, 1), ("x", 10, 10, 1)]
Input: events_read(visits, [(0, "a"), (5, "b"), (20, "a"), (40, "b"), (41, "a"), (90, "c")], 1, 30)
Output: 4
Constraints
- The stream may be endless; the tests take up to 3000 visits, with thousands of visits open at once.
1 <= gap; times are integers; users are strings.
Goals
- Turn an endless event stream into a stream of finished groups
- Decide the earliest moment at which a group can no longer change
- Keep the per-event work small even with thousands of open groups