private void computeStateSuffixesTopological ( final int initialState , final int magicMarker ) { for ( Iterator < Integer > iterator = sortStatesTopological ( initialState ) . iterator ( ) ; iterator . hasNext ( ) ; ) { Integer currentState = iterator . next ( ) ; int currentSuffixes = d_stateNSuffixes . get ( currentState ) ; if ( currentSuffixes == magicMarker ) { // is not yet computed int trans = d_stateOffsets . get ( currentState ) ; int transUpperBound = transitionsUpperBound ( currentState ) ; if ( trans < transUpperBound ) { // has children int suffixes = d_finalStates . get ( currentState ) ? 1 : 0 ; // add one if current state is final for ( ; trans < transUpperBound ; ++ trans ) { // add known number of suffixes of children int childState = d_transitionTo . get ( trans ) ; assert d_stateNSuffixes . get ( childState ) != magicMarker : "suffxies should have been calculated for state " + childState ; suffixes += d_stateNSuffixes . get ( childState ) ; } d_stateNSuffixes . set ( currentState , suffixes ) ; } else { d_stateNSuffixes . set ( currentState , d_finalStates . get ( currentState ) ? 1 : 0 ) ; } } // else already computed from a different path in the DAG } }
Iteratively computes the number of suffixes by topological order