1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
require 'forwardable'
require 'hitimes'
require 'timers/timer'
module Timers
# Maintains an ordered list of events, which can be cancelled.
class Events
# Represents a cancellable handle for a specific timer event.
class Handle
def initialize(time, callback)
@time = time
@callback = callback
end
# The absolute time that the handle should be fired at.
attr :time
# Cancel this timer, O(1).
def cancel!
# The simplest way to keep track of cancelled status is to nullify the
# callback. This should also be optimal for garbage collection.
@callback = nil
end
# Has this timer been cancelled? Cancelled timer's don't fire.
def cancelled?
@callback.nil?
end
def > other
@time > other.to_f
end
def to_f
@time
end
# Fire the callback if not cancelled with the given time parameter.
def fire(time)
if @callback
@callback.call(time)
end
end
end
def initialize
# A sequence of handles, maintained in sorted order, future to present.
# @sequence.last is the next event to be fired.
@sequence = []
end
# Add an event at the given time.
def schedule(time, callback)
handle = Handle.new(time.to_f, callback)
index = bisect_left(@sequence, handle)
# Maintain sorted order, O(logN) insertion time.
@sequence.insert(index, handle)
return handle
end
# Returns the first non-cancelled handle.
def first
while handle = @sequence.last
if handle.cancelled?
@sequence.pop
else
return handle
end
end
# @sequence.reverse.find { |handle| !handle.cancelled? }
end
# Returns the number of pending (possibly cancelled) events.
def size
@sequence.size
end
# Fire all handles for which Handle#time is less than the given time.
def fire(time)
pop(time).reverse_each do |handle|
handle.fire(time)
end
end
private
# Efficiently take k handles for which Handle#time is less than the given
# time.
def pop(time)
index = bisect_left(@sequence, time)
@sequence.pop(@sequence.size - index)
end
# Return the left-most index where to insert item e, in a list a, assuming
# a is sorted in descending order.
def bisect_left(a, e, l = 0, u = a.length)
while l < u
m = l + (u-l).div(2)
if a[m] > e
l = m+1
else
u = m
end
end
return l
end
end
end
|
