void GenBase::reduceActionTables()
{
	/* Reduce the actions tables to a set. */
	for ( StateList::Iter st = fsm->stateList; st.lte(); st++ ) {
		RedActionTable *actionTable = 0;

		/* Reduce To State Actions. */
		if ( st->toStateActionTable.length() > 0 ) {
			if ( actionTableMap.insert( st->toStateActionTable, &actionTable ) )
				actionTable->id = nextActionTableId++;
		}

		/* Reduce From State Actions. */
		if ( st->fromStateActionTable.length() > 0 ) {
			if ( actionTableMap.insert( st->fromStateActionTable, &actionTable ) )
				actionTable->id = nextActionTableId++;
		}

		/* Reduce EOF actions. */
		if ( st->eofActionTable.length() > 0 ) {
			if ( actionTableMap.insert( st->eofActionTable, &actionTable ) )
				actionTable->id = nextActionTableId++;
		}

		/* Loop the transitions and reduce their actions. */
		for ( TransList::Iter trans = st->outList; trans.lte(); trans++ ) {
			if ( trans->actionTable.length() > 0 ) {
				if ( actionTableMap.insert( trans->actionTable, &actionTable ) )
					actionTable->id = nextActionTableId++;
			}
		}
	}
}

bool FsmAp::outListCovers( StateAp *state )
{
	/* Must be at least one range to cover. */
	if ( state->outList.length() == 0 )
		return false;
	
	/* The first must start at the lower bound. */
	TransList::Iter trans = state->outList.first();
	if ( keyOps->minKey < trans->lowKey )
		return false;

	/* Loop starts at second el. */
	trans.increment();

	/* Loop checks lower against prev upper. */
	for ( ; trans.lte(); trans++ ) {
		/* Lower end of the trans must be one greater than the
		 * previous' high end. */
		Key lowKey = trans->lowKey;
		lowKey.decrement();
		if ( trans->prev->highKey < lowKey )
			return false;
	}

	/* Require that the last range extends to the upper bound. */
	trans = state->outList.last();
	if ( trans->highKey < keyOps->maxKey )
		return false;

	return true;
}

/* Detach a state from the graph. Detaches and deletes transitions in and out
 * of the state. Empties inList and outList. Removes the state from the final
 * state set. A detached state becomes useless and should be deleted. */
void FsmAp::detachState( StateAp *state )
{
	/* Detach the in transitions from the inList list of transitions. */
	while ( state->inList.head != 0 ) {
		/* Get pointers to the trans and the state. */
		TransAp *trans = state->inList.head;
		StateAp *fromState = trans->fromState;

		/* Detach the transitions from the source state. */
		detachTrans( fromState, state, trans );

		/* Ok to delete the transition. */
		fromState->outList.detach( trans );
		delete trans;
	}

	/* Remove the entry points in on the machine. */
	while ( state->entryIds.length() > 0 )
		unsetEntry( state->entryIds[0], state );

	/* Detach out range transitions. */
	for ( TransList::Iter trans = state->outList; trans.lte(); ) {
		TransList::Iter next = trans.next();
		detachTrans( state, trans->toState, trans );
		delete trans;
		trans = next;
	}

	/* Delete all of the out range pointers. */
	state->outList.abandon();

	/* Unset final stateness before detaching from graph. */
	if ( state->stateBits & SB_ISFINAL )
		finStateSet.remove( state );
}

void FsmAp::fillGaps( StateAp *state )
{
	if ( state->outList.length() == 0 ) {
		/* Add the range on the lower and upper bound. */
		attachNewTrans( state, 0, keyOps->minKey, keyOps->maxKey );
	}
	else {
		TransList srcList;
		srcList.transfer( state->outList );

		/* Check for a gap at the beginning. */
		TransList::Iter trans = srcList, next;
		if ( keyOps->minKey < trans->lowKey ) {
			/* Make the high key and append. */
			Key highKey = trans->lowKey;
			highKey.decrement();

			attachNewTrans( state, 0, keyOps->minKey, highKey );
		}

		/* Write the transition. */
		next = trans.next();
		state->outList.append( trans );

		/* Keep the last high end. */
		Key lastHigh = trans->highKey;

		/* Loop each source range. */
		for ( trans = next; trans.lte(); trans = next ) {
			/* Make the next key following the last range. */
			Key nextKey = lastHigh;
			nextKey.increment();

			/* Check for a gap from last up to here. */
			if ( nextKey < trans->lowKey ) {
				/* Make the high end of the range that fills the gap. */
				Key highKey = trans->lowKey;
				highKey.decrement();

				attachNewTrans( state, 0, nextKey, highKey );
			}

			/* Reduce the transition. If it reduced to anything then add it. */
			next = trans.next();
			state->outList.append( trans );

			/* Keep the last high end. */
			lastHigh = trans->highKey;
		}

		/* Now check for a gap on the end to fill. */
		if ( lastHigh < keyOps->maxKey ) {
			/* Get a copy of the default. */
			lastHigh.increment();

			attachNewTrans( state, 0, lastHigh, keyOps->maxKey );
		}
	}
}

/* Remove all priorities. */
void FsmAp::clearAllPriorities()
{
	for ( StateList::Iter state = stateList; state.lte(); state++ ) {
		/* Clear out priority data. */
		state->outPriorTable.empty();

		/* Clear transition data from the out transitions. */
		for ( TransList::Iter trans = state->outList; trans.lte(); trans++ )
			trans->priorTable.empty();
	}
}

void FsmAp::setErrorAction( StateAp *state, int ordering, Action *action )
{
	/* Fill any gaps in the out list with an error transition. */
	fillGaps( state );

	/* Set error transitions in the transitions that go to error. */
	for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
		if ( trans->toState == 0 )
			trans->actionTable.setAction( ordering, action );
	}
}

/* Set functions to execute on all transitions. Walks the out lists of all
 * states. */
void FsmAp::allTransAction( int ordering, Action *action )
{
	/* Walk all states. */
	for ( StateList::Iter state = stateList; state.lte(); state++ ) {
		/* Walk the out list of the state. */
		for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
			if ( trans->toState != 0 )
				trans->actionTable.setAction( ordering, action );
		}
	}
}

/* Set actions to execute on starting transitions. Isolates the start state
 * so it has no other entry points, then adds to the transition functions
 * of all the transitions out of the start state. If the start state is final,
 * then the func is also added to the start state's out func list. The idea is
 * that a machine that accepts the null string can execute a start func when it
 * matches the null word, which can only be done when leaving the start/final
 * state. */
void FsmAp::startFsmAction( int ordering, Action *action )
{
	/* Make sure the start state has no other entry points. */
	isolateStartState();

	/* Walk the start state's transitions, setting functions. */
	for ( TransList::Iter trans = startState->outList; trans.lte(); trans++ ) {
		if ( trans->toState != 0 )
			trans->actionTable.setAction( ordering, action );
	}
}

/* Set the priority of all transitions in a graph. Walks all transition lists
 * and all def transitions. */
void FsmAp::allTransPrior( int ordering, PriorDesc *prior )
{
	/* Walk the list of all states. */
	for ( StateList::Iter state = stateList; state.lte(); state++ ) {
		/* Walk the out list of the state. */
		for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
			if ( trans->toState != 0 )
				trans->priorTable.setPrior( ordering, prior );
		}
	}
}

/* Set the priority of starting transitions. Isolates the start state so it has
 * no other entry points, then sets the priorities of all the transitions out
 * of the start state. If the start state is final, then the outPrior of the
 * start state is also set. The idea is that a machine that accepts the null
 * string can still specify the starting trans prior for when it accepts the
 * null word. */
void FsmAp::startFsmPrior( int ordering, PriorDesc *prior )
{
	/* Make sure the start state has no other entry points. */
	isolateStartState();

	/* Walk all transitions out of the start state. */
	for ( TransList::Iter trans = startState->outList; trans.lte(); trans++ ) {
		if ( trans->toState != 0 )
			trans->priorTable.setPrior( ordering, prior );
	}
}

/* Give a target state for error transitions. */
void FsmAp::setErrorTarget( StateAp *state, StateAp *target, int *orderings, 
			Action **actions, int nActs )
{
	/* Fill any gaps in the out list with an error transition. */
	fillGaps( state );

	/* Set error target in the transitions that go to error. */
	for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
		if ( trans->toState == 0 ) {
			/* The trans goes to error, redirect it. */
			redirectErrorTrans( trans->fromState, target, trans );
			trans->actionTable.setActions( orderings, actions, nActs );
		}
	}
}

void XMLCodeGen::writeTransList( StateAp *state )
{
	TransListVect outList;

	/* If there is only are no ranges the task is simple. */
	if ( state->outList.length() > 0 ) {
		/* Loop each source range. */
		for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
			/* Reduce the transition. If it reduced to anything then add it. */
			appendTrans( outList, trans->lowKey, trans->highKey, trans );
		}
	}

	out << "      <trans_list length=\"" << outList.length() << "\">\n";
	for ( TransListVect::Iter tvi = outList; tvi.lte(); tvi++ )
		writeTrans( tvi->lowKey, tvi->highKey, tvi->value );
	out << "      </trans_list>\n";
}

/* Zeros out the function ordering keys. This may be called before minimization
 * when it is known that no more fsm operations are going to be done.  This
 * will achieve greater reduction as states will not be separated on the basis
 * of function ordering. */
void FsmAp::nullActionKeys( )
{
	/* For each state... */
	for ( StateList::Iter state = stateList; state.lte(); state++ ) {
		/* Walk the transitions for the state. */
		for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
			/* Walk the action table for the transition. */
			for ( ActionTable::Iter action = trans->actionTable;
					action.lte(); action++ )
				action->key = 0;

			/* Walk the action table for the transition. */
			for ( LmActionTable::Iter action = trans->lmActionTable;
					action.lte(); action++ )
				action->key = 0;
		}

		/* Null the action keys of the to state action table. */
		for ( ActionTable::Iter action = state->toStateActionTable;
				action.lte(); action++ )
			action->key = 0;

		/* Null the action keys of the from state action table. */
		for ( ActionTable::Iter action = state->fromStateActionTable;
				action.lte(); action++ )
			action->key = 0;

		/* Null the action keys of the out transtions. */
		for ( ActionTable::Iter action = state->outActionTable;
				action.lte(); action++ )
			action->key = 0;

		/* Null the action keys of the error action table. */
		for ( ErrActionTable::Iter action = state->errActionTable;
				action.lte(); action++ )
			action->ordering = 0;

		/* Null the action keys eof action table. */
		for ( ActionTable::Iter action = state->eofActionTable;
				action.lte(); action++ )
			action->key = 0;
	}
}

/* Shift the function ordering of the start transitions to start
 * at fromOrder and increase in units of 1. Useful before staring.
 * Returns the maximum number of order numbers used. */
int FsmAp::shiftStartActionOrder( int fromOrder )
{
	int maxUsed = 0;

	/* Walk the start state's transitions, shifting function ordering. */
	for ( TransList::Iter trans = startState->outList; trans.lte(); trans++ ) {
		/* Walk the function data for the transition and set the keys to
		 * increasing values starting at fromOrder. */
		int curFromOrder = fromOrder;
		ActionTable::Iter action = trans->actionTable;
		for ( ; action.lte(); action++ ) 
			action->key = curFromOrder++;
	
		/* Keep track of the max number of orders used. */
		if ( curFromOrder - fromOrder > maxUsed )
			maxUsed = curFromOrder - fromOrder;
	}
	
	return maxUsed;
}

void BackendGen::makeTransList( StateAp *state )
{
	TransListVect outList;

	/* If there is only are no ranges the task is simple. */
	if ( state->outList.length() > 0 ) {
		/* Loop each source range. */
		for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
			/* Reduce the transition. If it reduced to anything then add it. */
			appendTrans( outList, trans->lowKey, trans->highKey, trans );
		}
	}

	cgd->initTransList( curState, outList.length() );
	curTrans = 0;

	for ( TransListVect::Iter tvi = outList; tvi.lte(); tvi++ )
		makeTrans( tvi->lowKey, tvi->highKey, tvi->value );

	cgd->finishTransList( curState );
}

/* Merge neighboring transitions go to the same state and have the same
 * transitions data. */
void FsmAp::compressTransitions()
{
	for ( StateList::Iter st = stateList; st.lte(); st++ ) {
		if ( st->outList.length() > 1 ) {
			for ( TransList::Iter trans = st->outList, next = trans.next(); next.lte();  ) {
				Key nextLow = next->lowKey;
				nextLow.decrement();
				if ( trans->highKey == nextLow && trans->toState == next->toState &&
					CmpActionTable::compare( trans->actionTable, next->actionTable ) == 0 )
				{
					trans->highKey = next->highKey;
					st->outList.detach( next );
					detachTrans( next->fromState, next->toState, next );
					delete next;
					next = trans.next();
				}
				else {
					trans.increment();
					next.increment();
				}
			}
		}
	}
}