Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## avrora.sim.util
Class DeltaQueue

    java.lang.Object
      avrora.sim.util.DeltaQueue

public class DeltaQueue
extends java.lang.Object

The `DeltaQueue` class implements an amortized constant time delta-queue for processing of scheduled events. Events are put into the queue that will fire at a given number of cycles in the future. An internal delta list is maintained where each link in the list represents a set of triggers to be fired some number of clock cycles after the previous link.

Each delta between links is maintained to be non-zero. Thus, to insert a trigger X cycles in the future, at most X nodes will be skipped over. Therefore over X time steps, this cost is amortized to be constant.

For each clock cycle, only the first node in the list must be checked, leading to constant time work per clock cycle.

This class allows the clock to be advanced multiple ticks at a time.

Also, since this class is used heavily in the simulator, its performance is important and maintains an internal cache of objects. Thus, it does not create garbage over its execution and never uses more space than is required to store the maximum encountered simultaneous events. It does not use standard libraries, casts, virtual dispatch, etc.

Field Summary
`protected long` | `count`
`protected avrora.sim.util.DeltaQueue.Link` | `freeLinks`
`protected avrora.sim.util.DeltaQueue.TriggerLink` | `freeTriggerLinks`
`protected avrora.sim.util.DeltaQueue.Link` | `head`

Constructor Summary
`DeltaQueue()`

Method Summary
`void` | `add(Simulator.Trigger t, long cycles)` The `add` method adds a trigger to be executed in the future.
`void` | `advance(long cycles)` The `advance` method advances timesteps through the queue by the specified number of clock cycles, processing any triggers.
`long` | `getCount()` The `getCount()` gets the total cumulative count of all the `advance()` calls on this delta queue.
`long` | `getHeadDelta()` The `getHeadDelta()` method gets the number of clock cycles until the first event will fire.
`void` | `remove(Simulator.Trigger e)` The `remove` method removes all occurrences of the specified trigger within the delta queue.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Field Detail

### head

    protected avrora.sim.util.DeltaQueue.Link head

### freeLinks

    protected avrora.sim.util.DeltaQueue.Link freeLinks

### freeTriggerLinks

    protected avrora.sim.util.DeltaQueue.TriggerLink freeTriggerLinks

### count

    protected long count

Constructor Detail

### DeltaQueue

    public DeltaQueue()

Method Detail

### add

    public void add(Simulator.Trigger t,
                    long cycles)

  The `add` method adds a trigger to be executed in the future.

  Parameters:
    `t` - the trigger to fire
    `cycles` - the number of clock cycles in the future

### remove

    public void remove(Simulator.Trigger e)

  The `remove` method removes all occurrences of the specified trigger within the delta queue.

  Parameters:
    `e` - the trigger to remove

### advance

    public void advance(long cycles)

  The `advance` method advances timesteps through the queue by the specified number of clock cycles, processing any triggers.

  Parameters:
    `cycles` - the number of clock cycles to advance

### getHeadDelta

    public long getHeadDelta()

  The `getHeadDelta()` method gets the number of clock cycles until the first event will fire.

  Returns:
    the number of clock cycles until the first event will fire

### getCount

    public long getCount()

  The `getCount()` gets the total cumulative count of all the `advance()` calls on this delta queue.

  Returns:
    the total number of cycles this queue has been advanced

Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD