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 events 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 an event X cycles in the future, at most X nodes will be skipped over. Therefore, when the list is advanced 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` The `count` field stores the total number of cycles that this queue has been advanced, i.e.
`protected avrora.sim.util.DeltaQueue.EventList` | `freeEventLists` The `freeEventLists` field stores a reference to any free event links that have become unused during the processing of events.
`protected avrora.sim.util.DeltaQueue.Link` | `freeLinks` The `freeLinks` field stores a reference to any free links that have become unused during the processing of events.
`protected avrora.sim.util.DeltaQueue.Link` | `head` The `head` field stores a reference to the head of the delta queue, which represents the event that is nearest in the future.

Constructor Summary
`DeltaQueue()`

Method Summary
`void` | `add(Simulator.Event t, long cycles)` The `add` method adds an event 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 events.
`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.Event e)` The `remove` method removes all occurrences of the specified event 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

  The `head` field stores a reference to the head of the delta queue, which represents the event that is nearest in the future.

### freeLinks

    protected avrora.sim.util.DeltaQueue.Link freeLinks

  The `freeLinks` field stores a reference to any free links that have become unused during the processing of events. A free list is used to prevent garbage from accumulating.

### freeEventLists

    protected avrora.sim.util.DeltaQueue.EventList freeEventLists

  The `freeEventLists` field stores a reference to any free event links that have become unused during the processing of events. A free list is used to prevent garbage from accumulating.

### count

    protected long count

  The `count` field stores the total number of cycles that this queue has been advanced, i.e. the sum of all `advance()` calls.

Constructor Detail

### DeltaQueue

    public DeltaQueue()

Method Detail

### add

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

  The `add` method adds an event to be executed in the future.

  Parameters:
    `t` - the event to add
    `cycles` - the number of clock cycles in the future

### remove

    public void remove(Simulator.Event e)

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

  Parameters:
    `e` - the event 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 events.

  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