Class: DiscreteEvent::EventQueue

Inherits:
Object
  • Object
show all
Defined in:
lib/discrete_event/event_queue.rb

Overview

Queue of pending events; also keeps track of the clock (the current time).

There are two key terms:

  • action: any Ruby block

  • event: an action to be executed at some specified time in the future

Events are usually created using the #at and #after methods. The methods #at_each, #every and #recur_after make some important special cases more efficient.

See the README for an example.

Direct Known Subclasses

Simulation

Defined Under Namespace

Classes: Event

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(now = 0.0) ⇒ EventQueue

Returns a new instance of EventQueue.


35
36
37
38
39
 
# File 'lib/discrete_event/event_queue.rb', line 35

def initialize now=0.0
  @now = now
  @events = PQueue.new {|a,b| a.time < b.time}
  @recur_interval = nil
end

Instance Attribute Details

#events ⇒ PQueue (readonly)

Event queue.

Returns:

  • (PQueue) 

33
34
35
 
# File 'lib/discrete_event/event_queue.rb', line 33

def events
  @events
end

#now ⇒ Number (readonly)

Current time (taken from the currently executing event, if any). You can use floating point or integer time.

Returns:

  • (Number) 

26
27
28
 
# File 'lib/discrete_event/event_queue.rb', line 26

def now
  @now
end

Instance Method Details

#after(delay) { ... } ⇒ nil

Schedule action (a block) to run after the given delay (with respect to #now).

Parameters:

  • delay (Number) —

    after which action should run; non-negative

Yields:

  • action to be run after delay

Returns:

  • (nil) 

67
68
69
 
# File 'lib/discrete_event/event_queue.rb', line 67

def after delay, &action
  at(@now + delay, &action)
end

#at(time) { ... } ⇒ nil

Schedule action (a block) to run at the given time; time must not be in the past.

Parameters:

  • time (Number) —

    at which action should run; must be >= #now

Yields:

  • action to be run at time

Returns:

  • (nil) 

51
52
53
54
55
 
# File 'lib/discrete_event/event_queue.rb', line 51

def at time, &action
  raise "cannot schedule event in the past" if time < now
  @events.push(Event.new(time, action))
  nil
end

#at_each(elements, time = nil) {|element| ... } ⇒ nil

Schedule action (a block) to run for each element in the given list (possibly at different times).

This method may be of interest if you have a large number of events that occur at known times. You could use #at to add each one to the event queue at the start of the simulation, but this will make adding other events more expensive. Instead, this method adds them one at a time, so only the next event is stored in the event queue.

Examples:

Alert = Struct.new(:when, :message)
alerts = [Alert.new(12, "ha!"), Alert.new(42, "ah!")] # and many more
at_each alerts, :when do |alert|
  puts alert.message
end

Parameters:

  • elements (Enumerable) —

    to yield; must be in ascending order according to time; note that this method keeps a reference to this object and removes elements as they are executed, so you may want to pass a copy if you plan to change it after this call returns

  • time (Proc, Symbol, nil) (defaults to: nil) —

    used to determine when the action will run for a given element; if a Proc, the proc must return the appropriate time; if a Symbol, each element must respond to time; if nil, it is assumed that element.time returns the time

Yields:

  • (element)

Yield Parameters:

  • element (Object) —

    from elements

Returns:

  • (nil)

Raises:

  • (ArgumentError) 

106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/discrete_event/event_queue.rb', line 106

def at_each elements, time=nil, &action
  raise ArgumentError, 'no action given' unless block_given?

  unless elements.empty?
    element = elements.shift
    if time.nil?
      element_time = element.time
    elsif time.is_a? Proc
      element_time = time.call(element) 
    elsif time.is_a? Symbol
      element_time = element.send(time)
    else 
      raise ArgumentError, "bad time"
    end

    at element_time do
      yield element
      at_each elements, time, &action
    end
  end
  nil
end

#each {|now| ... } ⇒ self

Allow for the creation of a ruby Enumerator for the simulation. This yields for each event.

Examples:

TODO

eq = EventQueue.new
eq.at 13 do
  puts "hi"
end
eq.at 42 do
  puts "hello"
end
for t in eq.to_enum
  puts t
end

Yields:

  • (now) —

    called immediately after each event runs

Yield Parameters:

  • now (Number) —

    as #now

Returns:

  • (self) 

268
269
270
271
 
# File 'lib/discrete_event/event_queue.rb', line 268

def each
  yield now while run_next
  self
end

#every(interval, start = 0, &action) ⇒ nil

Schedule action (a block) to run periodically.

This is useful for statistics collection.

Note that if you specify one or more events of this kind, the simulation will never run out of events.

Examples:

every 5 do
  if now > 100
    # record stats
  end
  throw :stop if now > 1000
end

Parameters:

  • interval (Numeric) —

    non-negative

  • start (Numeric) (defaults to: 0) —

    block first runs at this time

Returns:

  • (nil) 

187
188
189
190
191
192
193
 
# File 'lib/discrete_event/event_queue.rb', line 187

def every interval, start=0, &action
  at start do
    yield
    recur_after interval
  end
  nil
end

#next_event_time ⇒ Number?

The time of the next queued event, or nil if there are no queued events.

If this method is called from within an action block, it returns #now (that is, the current event hasn’t finished yet, so it’s still in some sense the next event).

Returns:

  • (Number, nil) 

204
205
206
207
208
209
210
211
 
# File 'lib/discrete_event/event_queue.rb', line 204

def next_event_time
  event = @events.top
  if event
    event.time
  else
    nil
  end
end

#recur_after(interval) ⇒ nil

When called from within an action block, repeats the action block after the specified interval has elapsed.

Calling this method from outside an action block has no effect. You may call this method at most once in an action block.

Note that you can achieve the same effect using #at and #after and a named method, as in

def demo
  at 5 do
    puts "now: #{now}"
    after 10*rand do
      demo
    end
  end
end

but it is somewhat more efficient to call recur_after, and, if you do, the named method is not necessary.

Examples:

at 5 do
  puts "now: #{now}"
  recur_after 10*rand
end

Parameters:

  • interval (Number) —

    non-negative

Returns:

  • (nil) 

159
160
161
162
163
 
# File 'lib/discrete_event/event_queue.rb', line 159

def recur_after interval
  raise "cannot recur twice" if @recur_interval
  @recur_interval = interval
  nil
end

#reset(now = 0.0) ⇒ self

Clear any pending events in the event queue and reset #now.

Returns:

  • (self) 

278
279
280
281
282
 
# File 'lib/discrete_event/event_queue.rb', line 278

def reset now=0.0
  @now = now
  @events.clear
  self
end

#run_next ⇒ Boolean

Run the action for the next event in the queue.

Returns:

  • (Boolean) —

    false if there are no more events.


218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
 
# File 'lib/discrete_event/event_queue.rb', line 218

def run_next
  event = @events.top
  if event
    # run the action
    @now = event.time
    event.action.call

    # recurring events get special treatment: can avoid doing a push and a
    # pop by reusing the Event at the top of the heap, but with a new time
    #
    # NB: this assumes that the top element in the heap can't change due to
    # the event that we just ran, which is the case here, because we don't
    # allow events to be created in the past, and because of the internals
    # of the PQueue datastructure
    if @recur_interval
      event.time = @now + @recur_interval
      @events.replace_top(event)
      @recur_interval = nil
    else
      @events.pop
    end

    true
  else
    false
  end
end