+++ /dev/null
-# This file is part of NIT ( http://www.nitlanguage.org ).
-#
-# Licensed under the Apache License, Version 2.0 (the "License");
-# you may not use this file except in compliance with the License.
-# You may obtain a copy of the License at
-#
-# http://www.apache.org/licenses/LICENSE-2.0
-#
-# Unless required by applicable law or agreed to in writing, software
-# distributed under the License is distributed on an "AS IS" BASIS,
-# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-# See the License for the specific language governing permissions and
-# limitations under the License.
-
-# Register, update and discard events in a timeline.
-#
-# A queue of event is used to register objects associated with a start time and
-# a duration and to return them when they are active.
-#
-# The main class is `EventQueue`. It controls a timeline and register events.
-# Event can be any kind of object, usually specific time-related domain objects should be used.
-#
-# The auxiliary class `EventInfo` registers and control information about each event.
-# It can also be used for fluent programming and create new events relatively to existing ones.
-#
-# ## Basic usage
-#
-# The event queue is created empty, and can handle any kind of data.
-#
-# ~~~
-# var eq = new EventQueue[String]
-# ~~~
-#
-# To register an event, add it with a start time and a duration.
-# Note that the time is relative to the current time frame in the queue.
-#
-# ~~~
-# eq.add("1..2", 1.0, 1.0)
-# eq.add("2..10", 2.0, 8.0)
-# ~~~
-#
-# To register instantaneous event, use a 0.0 duration (or no duration)
-#
-# ~~~
-# eq.add("1.5", 1.5)
-# ~~~
-#
-# To get active events, use `update` with a time difference.
-# This returns a sequence of currently active events.
-#
-# ~~~
-# var es = eq.update(1.0) # What is active after 1 unit of time?
-# assert es.length == 1 # only "1..2" is active
-# ~~~
-#
-# Each `update` increments the time frame of the queue and returns an updated information about active events.
-#
-# ~~~
-# es = eq.update(1.0) # What is active after an other unit of time?
-# assert eq.time == 2.0
-#
-# assert es.length == 3 # there is now 3 active events
-# ~~~
-#
-# Results of the `update` method contains a lot of information.
-#
-# Obviously the original events:
-#
-# ~~~
-# assert es[0].event == "1..2"
-# assert es[1].event == "1.5"
-# assert es[2].event == "2..10"
-# ~~~
-#
-# The time since the begin of the event:
-#
-# ~~~
-# assert es[0].time == 1.0 # Started 1 unit of time ago
-# assert es[1].time == 0.5
-# assert es[2].time == 0.0 # Started just now
-# ~~~
-#
-# The completion ratio of the event until its termination:
-#
-# ~~~
-# assert es[0].completion == 1.0 # has just finished
-# assert es[1].completion == inf # completion ratio does not make sense for instant events
-# assert es[2].completion == 0.0 # has just started
-# ~~~
-#
-# And a lot of other things, just look at `EventInfo`.
-#
-# ## Expiration and control
-#
-# When `update` returns events, `occurrences` count the number of time an
-# event is returned by update. It can be used for instance to see if it
-# is the first time that a specific event is active.
-#
-# ~~~
-# assert es[0].occurrences == 2 # it is the second time we see it
-# assert es[1].occurrences == 1 # instant one
-# assert es[2].occurrences == 1 # first time we see it
-# ~~~
-#
-# The duration is used to automatically manage the expiration of the event.
-#
-# Note that if a event expires during an `update`, then it is still returned by the function.
-# This is the way to handle instant events and newly expired events.
-#
-# To distinguish them `has_expired` can be used.
-#
-# ~~~
-# assert es[0].has_expired == true # just finished
-# assert es[1].has_expired == true # instant one
-# assert es[2].has_expired == false # sill active
-# ~~~
-#
-# On the next `update`, the already expired events are not returned again.
-#
-# ~~~
-# es = eq.update(1.0) # What is active after an other unit of time?
-# assert eq.time == 3.0
-# assert es.length == 1
-# assert es.first.event == "2..10" # No more "1..2" or "1.5"
-# ~~~
-#
-# The `expire` method can force the expiration of an event.
-#
-# ~~~
-# es.first.expire
-# es = eq.update(1.0)
-# assert es.is_empty # Sorry, "2..10" was expired
-# ~~~
-#
-# ## Fluent programming
-#
-# The `add` method (and its derivates) returns a `EventInfo` object that can be used to have
-# information about the newly registered event but also to chain the creation of time-related events.
-#
-# For instance, the following example registers 4 events, each one relative to the previous one:
-#
-# ~~~
-# eq = new EventQueue[String]
-# eq.add("e1", 10.0, 5.0).
-# add_after("e2", 2.0, 5.0).
-# add_sync("e3", 2.0, 5.0).
-# add_before("e4", 2.0, 5.0)
-# ~~~
-#
-# This can be decomposed as:
-#
-# ~~~
-# eq = new EventQueue[String]
-# var e1 = eq.add("e1", 10.0, 5.0)
-# assert e1.start == 10.0 # First event starts at 10
-#
-# var e2 = e1.add_after("e2", 2.0, 5.0) # starts 2 units of time after the end of e1
-# assert e2.start == 17.0 # So starts at 10 + 5 + 2
-#
-# var e3 = e2.add_sync("e3", 2.0, 5.0) # starts 2 units of time after the begin of e2
-# assert e3.start == 19.0 # So starts at 17 + 2
-#
-# var e4 = e3.add_before("e4", 2.0, 5.0) # ends 2 units of time before the start of e3
-# assert e4.start == 12.0 # So starts at 19 - 2 - 5
-# ~~~
-module event_queue
-
-# Queuing and management of arbitrary events in a timeline
-class EventQueue[E]
- # Comparator used by the queue
- private var event_comparator = new EventComparator
-
- # Efficient queue
- private var queue = new MinHeap[EventInfo[E]](event_comparator)
-
- # List of current active event
- private var actives = new Array[EventInfo[E]]
-
- # List of previously active event
- private var old_actives = new Array[EventInfo[E]]
-
- # Global time since the creation of the queue
- var time = 0.0
-
- # Nearest deadline, used to optimise queue access
- #
- # `inf` if no deadline is set
- private var next: Float = inf
-
- # Register an `event` in the queue to be active in `delay` units of time.
- #
- # If `duration` is given, this is duration after what the event is automatically discarded.
- # If `null`, 0.0 or not given, the event will be executed only once
- # Use `inf` for an event with an infinite duration.
- fun add(event: E, delay: Float, duration: nullable Float): EventInfo[E]
- do
- return add_at(event, time + delay, duration)
- end
-
- # Register an `event` in the queue executed at a specific time.
- fun add_at(event: E, start: Float, duration: nullable Float): EventInfo[E]
- do
- if start < next then next = start
- var ei = new EventInfo[E](event, self, start, duration or else 0.0)
- queue.add ei
-
- return ei
- end
-
- # Add a given amount of time and return all the events that were active during the delay.
- #
- # Note that events that expired during the delay are marked `has_expired` and are still returned.
- fun update(dt: Float): SequenceRead[EventInfo[E]]
- do
- var time = self.time
- time += dt
- self.time = time
-
- # Switch things
- var tmp = old_actives
- old_actives = actives
- actives = tmp
-
- # Discard dead events
- actives.clear
- for ei in old_actives do
- if not ei.has_expired then actives.add ei
- end
-
- # Start new events
- if time >= next then loop
- if queue.is_empty then
- next = inf
- break
- end
- var ei = queue.peek
- if ei.start > time then
- next = ei.start
- break
- end
- ei = queue.take
- if not ei.has_expired then
- actives.add ei
- ei.occurrences = 0
- end
- end
-
- if actives.is_empty then return actives
-
- # Update event information
- for ei in actives do ei.update(time, dt)
-
- return actives
- end
-end
-
-# Information and management about a registered event
-#
-# It allows to retrieve static and dynamic information about an event.
-# It also allows to register other time-related events with a fluent programming way.
-class EventInfo[E]
- # The registered event.
- var event: E
-
- # The associated event queue.
- #
- # It is used internally for fluent programming.
- var queue: EventQueue[E]
-
- # Absolute start time for the registered event in the event queue time frame.
- var start: Float
-
- # Registered duration.
- #
- # Events with a 0.0 duration are called *instant events*.
- var duration: Float
-
- # Time since the begin of the event, in units of time.
- var time: Float = nan
-
- # Time since the last update (or the begin of the event if smaller)
- #
- # Note that if the event has expired during the last time lapse,
- # then `dt` also counts the *expired* time between the expiration time
- # and the update time.
- var dt: Float = nan
-
- # Ratio of completion
- #
- # Usually between 0.0 and 1.
- # It might be > 1.0 if the event has expired during the last time lapse.
- var completion = 0.0
-
- # Number of times that an event was returned by `update`.
- #
- # If the event just started during the last update, 1 is returned.
- #
- # If the event was not returned by `update` yet, 0 is returned.
- var occurrences = 0
-
- # Has the event expired?
- #
- # Such an event will be not present in the next `update`.
- #
- # Note that an event can be `has_expired` and have `occurrences == 0` if it
- # is entirely included in the last time lapse.
- # It is especially the case for instant events.
- var has_expired = false
-
- ## Fluent methods
-
- # Register an event that starts after the end of the current one.
- #
- # `delay` indicates the time between the end of the current event and the begin of the new one.
- # Use 0.0 if both events should be contiguous and not overlap.
- #
- # Returns the new event information that can be used in fluent programming.
- fun add_after(event: E, delay: Float, duration: nullable Float): EventInfo[E]
- do
- return queue.add_at(event, start + self.duration + delay, duration)
- end
-
- # Register an event that starts with the current one.
- #
- # `delay` indicates the time between the begin of the current event and the begin of the new one.
- # Use 0.0 if both events should start at the same time and overlaps.
- #
- # Returns the new event information that can be used in fluent programming.
- fun add_sync(event: E, delay: Float, duration: nullable Float): EventInfo[E]
- do
- return queue.add_at(event, start + delay, duration)
- end
-
- # Register an event that finishes before the begin of current one.
- #
- # `delay` indicates the time between the end of the new event and the begin of the current one.
- # Use 0.0 if both event should be contiguous and not overlap.
- #
- # Returns the new event information that can be used in fluent programming.
- fun add_before(event: E, delay: Float, duration: nullable Float): EventInfo[E]
- do
- duration = duration or else 0.0
- return queue.add_at(event, start - delay - duration, duration)
- end
-
- # Update attributes. Is called by `EventQueue::update`
- private fun update(queue_time, queue_dt: Float)
- do
- time = queue_time - start
- if time >= duration then expire
- dt = queue_dt.min(time)
- completion = time / duration
- occurrences += 1
- end
-
- # Force the event to expire.
- #
- # The event can be active of not.
- #
- # ~~~
- # var eq = new EventQueue[String]
- # var e1 = eq.add("active", 0.0, 10.0)
- # var e2 = eq.add("not active", 2.0, 10.0)
- # var es = eq.update(1.0)
- # assert es == [e1]
- # e1.expire
- # e2.expire
- # es = eq.update(2.0)
- # assert es.is_empty
- # ~~~
- #
- # Note that when an event is forced to expire,
- # it will not appears in the next `update`.
- fun expire do has_expired = true
-
- redef fun to_s do return "{event or else "null"}@{start}+{duration}"
-end
-
-private class EventComparator
- super Comparator
- redef type COMPARED: EventInfo[nullable Object]
- redef fun compare(a, b) do return a.start <=> b.start
-end