PerCederberg.Grammatica.Runtime
Class NFAStateQueue

System.Object
   |
   +--NFAStateQueue

internal class NFAStateQueue

extends System.Object

An NFA state queue. This queue is used during processing to keep track of the current and subsequent NFA states. The current state is read from the beginning of the queue, and new states are added at the end. A marker index is used to separate the current from the subsequent states.

The queue implementation is optimized for quick removal at the beginning and addition at the end. It will attempt to use a fixed-size array to store the whole queue, and moves the data in this array only when absolutely needed. The array is also enlarged automatically if too many states are being processed at a single time.

Empty

public bool Empty;

The empty queue property (read-only).

Marked

public bool Marked;

The marked first entry property (read-only). This is set to true if the first entry in the queue has been marked.

AddLast

public void AddLast( NFAState state );

Adds a new entry at the end of the queue. This operation is mostly fast, unless all the allocated queue space has already been used.

Parameters:

state - the state to add

Clear

public void Clear();

Clears this queue. This operation is fast, as it just resets the queue position indices.

MarkEnd

public void MarkEnd();

Marks the end of the queue. This means that the next entry added to the queue will be marked (when it becomes the first in the queue). This operation is fast.

RemoveFirst

public NFAState RemoveFirst();

Removes and returns the first entry in the queue. This operation is fast, since it will only update the index of the first entry in the queue.

Returns:

the previous first entry in the queue