Class StateTable

java.lang.Object
  StateTable

public class StateTable
extends java.lang.Object

Class StateTable gives a representation of the set of reachable states with a given history length.

Nested Class Summary

class

StateTable.Element Class Element represents a node in a linked list of states; two links are provided, queueLink and hashLink, so that the node can be used both in the representation of the BFS queue and in the representation of a chain in the hash table.

Field Summary

static java.lang.String	DATADIRECTORY The path to the directory in which the transition table is to be stored.
(package private) int	h The value of the history parameter.
(package private) StateTable.Element[]	hashTable A hash table of states.
(package private) static int	hashTableSize The number of slots in the hash table.
(package private) int	numberOfAcceptingStates The number of distinct reachable accepting states found so far.
(package private) StateTable.Element	queueHead The head of the queue.
(package private) StateTable.Element	queueTail The tail of the queue.
(package private) State[]	sortedStates A call to sortStates will set this to an array containing state number i in sortedStates[i]; position 0 in the array is unused.
(package private) static boolean	verbose Set this to true for verbose output.

Constructor Summary

StateTable()
Create and initialize a new StateTable class.

Method Summary

void	addSuccessors(State s, int c) Find all states that can be reached from this state by reading a single minimal match pair of the form Tc,pad, for -h<pad<h, and write the transitions to the file.
void	build(int h) Build the state table for history h, and write it to the file.
StateTable.Element	dequeue() Remove and return the next element from the queue.
void	enqueue(StateTable.Element e) Append e to the queue.
int	findOrAdd(State s) Search for state s; if not found insert into the hash table and append it to the queue; in any case return its state number.
static void	main(java.lang.String[] args) Build and write out the table of transitions and states.
void	sortStates() Set sortedStates to an array in which the element indexed by i is state number i; the 0th array position is unused.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

hashTableSize

static final int hashTableSize

The number of slots in the hash table.

See Also:

Constant Field Values

DATADIRECTORY

public static final java.lang.String DATADIRECTORY

The path to the directory in which the transition table is to be stored.

See Also:

Constant Field Values

verbose

static boolean verbose

Set this to true for verbose output.

sortedStates

State[] sortedStates

A call to sortStates will set this to an array containing state number i in sortedStates[i]; position 0 in the array is unused.

h

int h

The value of the history parameter.

numberOfAcceptingStates

int numberOfAcceptingStates

The number of distinct reachable accepting states found so far.

hashTable

StateTable.Element[] hashTable

A hash table of states.

queueHead

StateTable.Element queueHead

The head of the queue.

queueTail

StateTable.Element queueTail

The tail of the queue.

Constructor Detail

StateTable

public StateTable()

Create and initialize a new StateTable class. Create an empty hash table and an empty queue, and set numberOfAcceptingStates to 0.

Method Detail

enqueue

public void enqueue(StateTable.Element e)

Append e to the queue.

dequeue

public StateTable.Element dequeue()

Remove and return the next element from the queue.

build

public void build(int h)
           throws java.io.IOException

Build the state table for history h, and write it to the file.

Throws:

java.io.IOException

addSuccessors

public void addSuccessors(State s,
                          int c)
                   throws java.io.IOException

Find all states that can be reached from this state by reading a single minimal match pair of the form T_c,pad, for -h<pad<h, and write the transitions to the file.

Throws:

java.io.IOException

findOrAdd

public int findOrAdd(State s)

Search for state s; if not found insert into the hash table and append it to the queue; in any case return its state number.

sortStates

public void sortStates()

Set sortedStates to an array in which the element indexed by i is state number i; the 0th array position is unused.

main

public static void main(java.lang.String[] args)
                 throws java.io.IOException

Build and write out the table of transitions and states. The program is used with the command
java StateTable <history>

Throws:

java.io.IOException