# 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