void FsmAp::notFinalFromStateAction( int ordering, Action *action )
{
	for ( StateList::Iter state = stateList; state.lte(); state++ ) {
		if ( ! state->isFinState() )
			state->fromStateActionTable.setAction( ordering, action );
	}
}

void FsmAp::notFinalErrorAction( int ordering, Action *action, int transferPoint )
{
	for ( StateList::Iter state = stateList; state.lte(); state++ ) {
		if ( ! state->isFinState() )
			state->errActionTable.setAction( ordering, action, transferPoint );
	}
}

/**
 * \brief Minimize by partitioning version 2 (best alg).
 *
 * Repeatedly tries to split partitions that may splittable until there are no
 * more partitions that might possibly need splitting. Runs faster than
 * version 1. Produces the most minimal fsm possible.
 */
void FsmAp::minimizePartition2()
{
	/* Need a mergesort and an initial partition compare. */
	MergeSort<StateAp*, InitPartitionCompare> mergeSort;
	InitPartitionCompare initPartCompare;

	/* Nothing to do if there are no states. */
	if ( stateList.length() == 0 )
		return;

	/* 
	 * First thing is to partition the states by final state status and
	 * transition functions. This gives us an initial partitioning to work
	 * with.
	 */

	/* Make a array of pointers to states. */
	int numStates = stateList.length();
	StateAp** statePtrs = new StateAp*[numStates];

	/* Fill up an array of pointers to the states for easy sorting. */
	StateList::Iter state = stateList;
	for ( int s = 0; state.lte(); state++, s++ )
		statePtrs[s] = state;
		
	/* Sort the states using the array of states. */
	mergeSort.sort( statePtrs, numStates );

	/* An array of lists of states is used to partition the states. */
	MinPartition *parts = new MinPartition[numStates];

	/* Assign the states into partitions. */
	int destPart = 0;
	for ( int s = 0; s < numStates; s++ ) {
		/* If this state differs from the last then move to the next partition. */
		if ( s > 0 && initPartCompare.compare( statePtrs[s-1], statePtrs[s] ) < 0 ) {
			/* Move to the next partition. */
			destPart += 1;
		}

		/* Put the state into its partition. */
		statePtrs[s]->alg.partition = &parts[destPart];
		parts[destPart].list.append( statePtrs[s] );
	}

	/* We just moved all the states from the main list into partitions without
	 * taking them off the main list. So clean up the main list now. */
	stateList.abandon();

	/* Split partitions. */
	int numParts = splitCandidates( statePtrs, parts, destPart+1 );

	/* Fuse states in the same partition. The states will end up back on the
	 * main list. */
	fusePartitions( parts, numParts );

	/* Cleanup. */
	delete[] statePtrs;
	delete[] parts;
}

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++;
			}
		}
	}
}

void FsmAp::notStartFromStateAction( int ordering, Action *action )
{
	for ( StateList::Iter state = stateList; state.lte(); state++ ) {
		if ( state != startState )
			state->fromStateActionTable.setAction( ordering, action );
	}
}

void FsmAp::notStartErrorAction( int ordering, Action *action, int transferPoint )
{
	for ( StateList::Iter state = stateList; state.lte(); state++ ) {
		if ( state != startState )
			state->errActionTable.setAction( ordering, action, transferPoint );
	}
}

void FsmAp::middleFromStateAction( int ordering, Action *action )
{
	/* Set the action in all states that are not the start state and not final. */
	for ( StateList::Iter state = stateList; state.lte(); state++ ) {
		if ( state != startState && ! state->isFinState() )
			state->fromStateActionTable.setAction( ordering, action );
	}
}

/* Set error actions in the states that have transitions into a final state. */
void FsmAp::middleErrorAction( int ordering, Action *action, int transferPoint )
{
	/* Isolate the start state in case it is reachable from in inside the
	 * machine, in which case we don't want it set. */
	for ( StateList::Iter state = stateList; state.lte(); state++ ) {
		if ( state != startState && ! state->isFinState() )
			state->errActionTable.setAction( ordering, action, transferPoint );
	}
}

/* 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 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 );
		}
	}
}

/* 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();
	}
}

/* Walk the list of states and verify that non final states do not have out
 * data, that all stateBits are cleared, and that there are no states with
 * zero foreign in transitions. */
void FsmAp::verifyStates()
{
	for ( StateList::Iter state = stateList; state.lte(); state++ ) {
		/* Non final states should not have leaving data. */
		if ( ! (state->stateBits & SB_ISFINAL) ) {
			assert( state->outActionTable.length() == 0 );
			assert( state->outCondSet.length() == 0 );
			assert( state->outPriorTable.length() == 0 );
		}

		/* Data used in algorithms should be cleared. */
		assert( (state->stateBits & SB_BOTH) == 0 );
		assert( state->foreignInTrans > 0 );
	}
}

int FsmAp::partitionRound( StateAp **statePtrs, MinPartition *parts, int numParts )
{
	/* Need a mergesort object and a single partition compare. */
	MergeSort<StateAp*, PartitionCompare> mergeSort;
	PartitionCompare partCompare;

	/* For each partition. */
	for ( int p = 0; p < numParts; p++ ) {
		/* Fill the pointer array with the states in the partition. */
		StateList::Iter state = parts[p].list;
		for ( int s = 0; state.lte(); state++, s++ )
			statePtrs[s] = state;

		/* Sort the states using the partitioning compare. */
		int numStates = parts[p].list.length();
		mergeSort.sort( statePtrs, numStates );

		/* Assign the states into partitions based on the results of the sort. */
		int destPart = p, firstNewPart = numParts;
		for ( int s = 1; s < numStates; s++ ) {
			/* If this state differs from the last then move to the next partition. */
			if ( partCompare.compare( statePtrs[s-1], statePtrs[s] ) < 0 ) {
				/* The new partition is the next avail spot. */
				destPart = numParts;
				numParts += 1;
			}

			/* If the state is not staying in the first partition, then
			 * transfer it to its destination partition. */
			if ( destPart != p ) {
				StateAp *state = parts[p].list.detach( statePtrs[s] );
				parts[destPart].list.append( state );
			}
		}

		/* Fix the partition pointer for all the states that got moved to a new
		 * partition. This must be done after the states are transfered so the
		 * result of the sort is not altered. */
		for ( int newPart = firstNewPart; newPart < numParts; newPart++ ) {
			StateList::Iter state = parts[newPart].list;
			for ( ; state.lte(); state++ )
				state->alg.partition = &parts[newPart];
		}
	}

	return numParts;
}

bool FsmAp::minimizeRound()
{
	/* Nothing to do if there are no states. */
	if ( stateList.length() == 0 )
		return false;

	/* Need a mergesort on approx compare and an approx compare. */
	MergeSort<StateAp*, ApproxCompare> mergeSort;
	ApproxCompare approxCompare;

	/* Fill up an array of pointers to the states. */
	StateAp **statePtrs = new StateAp*[stateList.length()];
	StateList::Iter state = stateList;
	for ( int s = 0; state.lte(); state++, s++ )
		statePtrs[s] = state;

	bool modified = false;

	/* Sort The list. */
	mergeSort.sort( statePtrs, stateList.length() );

	/* Walk the list looking for duplicates next to each other, 
	 * merge in any duplicates. */
	StateAp **pLast = statePtrs;
	StateAp **pState = statePtrs + 1;
	for ( int i = 1; i < stateList.length(); i++, pState++ ) {
		if ( approxCompare.compare( *pLast, *pState ) == 0 ) {
			/* Last and pState are the same, so fuse together. Move forward
			 * with pState but not with pLast. If any more are identical, we
			 * must */
			fuseEquivStates( *pLast, *pState );
			modified = true;
		}
		else {
			/* Last and this are different, do not set to merge them. Move
			 * pLast to the current (it may be way behind from merging many
			 * states) and pState forward one to consider the next pair. */
			pLast = pState;
		}
	}
	delete[] statePtrs;
	return modified;
}

/* 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;
	}
}

void BackendGen::makeStateList()
{
	/* Write the list of states. */
	long length = fsm->stateList.length();
	cgd->initStateList( length );
	curState = 0;
	for ( StateList::Iter st = fsm->stateList; st.lte(); st++ ) {
		makeStateActions( st );
		makeEofTrans( st );
		makeStateConditions( st );
		makeTransList( st );

		long id = st->alg.stateNum;
		cgd->setId( curState, id );

		if ( st->isFinState() )
			cgd->setFinal( curState );

		curState += 1;
	}
}

void XMLCodeGen::writeStateList()
{
	/* Write the list of states. */
	out << "    <state_list length=\"" << fsm->stateList.length() << "\">\n";
	for ( StateList::Iter st = fsm->stateList; st.lte(); st++ ) {
		out << "      <state id=\"" << st->alg.stateNum << "\"";
		if ( st->isFinState() )
			out << " final=\"t\"";
		out << ">\n";

		writeStateActions( st );
		writeEofTrans( st );
		writeStateConditions( st );
		writeTransList( st );

		out << "      </state>\n";

		if ( !st.last() )
			out << "\n";
	}
	out << "    </state_list>\n";
}

/* 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();
				}
			}
		}
	}
}

/* Set error actions in all states where there is a transition out. */
void FsmAp::allErrorAction( int ordering, Action *action, int transferPoint )
{
	/* Insert actions in the error action table of all states. */
	for ( StateList::Iter state = stateList; state.lte(); state++ )
		state->errActionTable.setAction( ordering, action, transferPoint );
}

/* Set EOF actions in all states where there is a transition out. */
void FsmAp::allEOFAction( int ordering, Action *action )
{
	/* Insert actions in the EOF action table of all states. */
	for ( StateList::Iter state = stateList; state.lte(); state++ )
		state->eofActionTable.setAction( ordering, action );
}