1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
15 # Register, update and discard events in a timeline.
17 # A queue of event is used to register objects associated with a start time and
18 # a duration and to return them when they are active.
20 # The main class is `EventQueue`. It controls a timeline and register events.
21 # Event can be any kind of object, usually specific time-related domain objects should be used.
23 # The auxiliary class `EventInfo` registers and control information about each event.
24 # It can also be used for fluent programming and create new events relatively to existing ones.
28 # The event queue is created empty, and can handle any kind of data.
31 # var eq = new EventQueue[String]
34 # To register an event, add it with a start time and a duration.
35 # Note that the time is relative to the current time frame in the queue.
38 # eq.add("1..2", 1.0, 1.0)
39 # eq.add("2..10", 2.0, 8.0)
42 # To register instantaneous event, use a 0.0 duration (or no duration)
48 # To get active events, use `update` with a time difference.
49 # This returns a sequence of currently active events.
52 # var es = eq.update(1.0) # What is active after 1 unit of time?
53 # assert es.length == 1 # only "1..2" is active
56 # Each `update` increments the time frame of the queue and returns an updated information about active events.
59 # es = eq.update(1.0) # What is active after an other unit of time?
60 # assert eq.time == 2.0
62 # assert es.length == 3 # there is now 3 active events
65 # Results of the `update` method contains a lot of information.
67 # Obviously the original events:
70 # assert es[0].event == "1..2"
71 # assert es[1].event == "1.5"
72 # assert es[2].event == "2..10"
75 # The time since the begin of the event:
78 # assert es[0].time == 1.0 # Started 1 unit of time ago
79 # assert es[1].time == 0.5
80 # assert es[2].time == 0.0 # Started just now
83 # The completion ratio of the event until its termination:
86 # assert es[0].completion == 1.0 # has just finished
87 # assert es[1].completion == inf # completion ratio does not make sense for instant events
88 # assert es[2].completion == 0.0 # has just started
91 # And a lot of other things, just look at `EventInfo`.
93 # ## Expiration and control
95 # When `update` returns events, `occurrences` count the number of time an
96 # event is returned by update. It can be used for instance to see if it
97 # is the first time that a specific event is active.
100 # assert es[0].occurrences == 2 # it is the second time we see it
101 # assert es[1].occurrences == 1 # instant one
102 # assert es[2].occurrences == 1 # first time we see it
105 # The duration is used to automatically manage the expiration of the event.
107 # Note that if a event expires during an `update`, then it is still returned by the function.
108 # This is the way to handle instant events and newly expired events.
110 # To distinguish them `has_expired` can be used.
113 # assert es[0].has_expired == true # just finished
114 # assert es[1].has_expired == true # instant one
115 # assert es[2].has_expired == false # sill active
118 # On the next `update`, the already expired events are not returned again.
121 # es = eq.update(1.0) # What is active after an other unit of time?
122 # assert eq.time == 3.0
123 # assert es.length == 1
124 # assert es.first.event == "2..10" # No more "1..2" or "1.5"
127 # The `expire` method can force the expiration of an event.
131 # es = eq.update(1.0)
132 # assert es.is_empty # Sorry, "2..10" was expired
135 # ## Fluent programming
137 # The `add` method (and its derivates) returns a `EventInfo` object that can be used to have
138 # information about the newly registered event but also to chain the creation of time-related events.
140 # For instance, the following example registers 4 events, each one relative to the previous one:
143 # eq = new EventQueue[String]
144 # eq.add("e1", 10.0, 5.0).
145 # add_after("e2", 2.0, 5.0).
146 # add_sync("e3", 2.0, 5.0).
147 # add_before("e4", 2.0, 5.0)
150 # This can be decomposed as:
153 # eq = new EventQueue[String]
154 # var e1 = eq.add("e1", 10.0, 5.0)
155 # assert e1.start == 10.0 # First event starts at 10
157 # var e2 = e1.add_after("e2", 2.0, 5.0) # starts 2 units of time after the end of e1
158 # assert e2.start == 17.0 # So starts at 10 + 5 + 2
160 # var e3 = e2.add_sync("e3", 2.0, 5.0) # starts 2 units of time after the begin of e2
161 # assert e3.start == 19.0 # So starts at 17 + 2
163 # var e4 = e3.add_before("e4", 2.0, 5.0) # ends 2 units of time before the start of e3
164 # assert e4.start == 12.0 # So starts at 19 - 2 - 5
168 # Queuing and management of arbitrary events in a timeline
170 # Comparator used by the queue
171 private var event_comparator
= new EventComparator
174 private var queue
= new MinHeap[EventInfo[E
]](event_comparator
)
176 # List of current active event
177 private var actives
= new Array[EventInfo[E
]]
179 # List of previously active event
180 private var old_actives
= new Array[EventInfo[E
]]
182 # Global time since the creation of the queue
185 # Nearest deadline, used to optimise queue access
187 # `inf` if no deadline is set
188 private var next
: Float = inf
190 # Register an `event` in the queue to be active in `delay` units of time.
192 # If `duration` is given, this is duration after what the event is automatically discarded.
193 # If `null`, 0.0 or not given, the event will be executed only once
194 # Use `inf` for an event with an infinite duration.
195 fun add
(event
: E
, delay
: Float, duration
: nullable Float): EventInfo[E
]
197 return add_at
(event
, time
+ delay
, duration
)
200 # Register an `event` in the queue executed at a specific time.
201 fun add_at
(event
: E
, start
: Float, duration
: nullable Float): EventInfo[E
]
203 if start
< next
then next
= start
204 var ei
= new EventInfo[E
](event
, self, start
, duration
or else 0.0)
210 # Add a given amount of time and return all the events that were active during the delay.
212 # Note that events that expired during the delay are marked `has_expired` and are still returned.
213 fun update
(dt
: Float): SequenceRead[EventInfo[E
]]
220 var tmp
= old_actives
221 old_actives
= actives
224 # Discard dead events
226 for ei
in old_actives
do
227 if not ei
.has_expired
then actives
.add ei
231 if time
>= next
then loop
232 if queue
.is_empty
then
237 if ei
.start
> time
then
242 if not ei
.has_expired
then
248 if actives
.is_empty
then return actives
250 # Update event information
251 for ei
in actives
do ei
.update
(time
, dt
)
257 # Information and management about a registered event
259 # It allows to retrieve static and dynamic information about an event.
260 # It also allows to register other time-related events with a fluent programming way.
262 # The registered event.
265 # The associated event queue.
267 # It is used internally for fluent programming.
268 var queue
: EventQueue[E
]
270 # Absolute start time for the registered event in the event queue time frame.
273 # Registered duration.
275 # Events with a 0.0 duration are called *instant events*.
278 # Time since the begin of the event, in units of time.
279 var time
: Float = nan
281 # Time since the last update (or the begin of the event if smaller)
283 # Note that if the event has expired during the last time lapse,
284 # then `dt` also counts the *expired* time between the expiration time
285 # and the update time.
288 # Ratio of completion
290 # Usually between 0.0 and 1.
291 # It might be > 1.0 if the event has expired during the last time lapse.
294 # Number of times that an event was returned by `update`.
296 # If the event just started during the last update, 1 is returned.
298 # If the event was not returned by `update` yet, 0 is returned.
301 # Has the event expired?
303 # Such an event will be not present in the next `update`.
305 # Note that an event can be `has_expired` and have `occurrences == 0` if it
306 # is entirely included in the last time lapse.
307 # It is especially the case for instant events.
308 var has_expired
= false
312 # Register an event that starts after the end of the current one.
314 # `delay` indicates the time between the end of the current event and the begin of the new one.
315 # Use 0.0 if both events should be contiguous and not overlap.
317 # Returns the new event information that can be used in fluent programming.
318 fun add_after
(event
: E
, delay
: Float, duration
: nullable Float): EventInfo[E
]
320 return queue
.add_at
(event
, start
+ self.duration
+ delay
, duration
)
323 # Register an event that starts with the current one.
325 # `delay` indicates the time between the begin of the current event and the begin of the new one.
326 # Use 0.0 if both events should start at the same time and overlaps.
328 # Returns the new event information that can be used in fluent programming.
329 fun add_sync
(event
: E
, delay
: Float, duration
: nullable Float): EventInfo[E
]
331 return queue
.add_at
(event
, start
+ delay
, duration
)
334 # Register an event that finishes before the begin of current one.
336 # `delay` indicates the time between the end of the new event and the begin of the current one.
337 # Use 0.0 if both event should be contiguous and not overlap.
339 # Returns the new event information that can be used in fluent programming.
340 fun add_before
(event
: E
, delay
: Float, duration
: nullable Float): EventInfo[E
]
342 duration
= duration
or else 0.0
343 return queue
.add_at
(event
, start
- delay
- duration
, duration
)
346 # Update attributes. Is called by `EventQueue::update`
347 private fun update
(queue_time
, queue_dt
: Float)
349 time
= queue_time
- start
350 if time
>= duration
then expire
351 dt
= queue_dt
.min
(time
)
352 completion
= time
/ duration
356 # Force the event to expire.
358 # The event can be active of not.
361 # var eq = new EventQueue[String]
362 # var e1 = eq.add("active", 0.0, 10.0)
363 # var e2 = eq.add("not active", 2.0, 10.0)
364 # var es = eq.update(1.0)
368 # es = eq.update(2.0)
372 # Note that when an event is forced to expire,
373 # it will not appears in the next `update`.
374 fun expire
do has_expired
= true
376 redef fun to_s
do return "{event or else "null"}@{start}+{duration}"
379 private class EventComparator
381 redef type COMPARED: EventInfo[nullable Object]
382 redef fun compare
(a
, b
) do return a
.start
<=> b
.start