}
AStar search = new AStar(finalNodes, latticeLength * t.numStates());
List<SequencePairAlignment<Object,ViterbiNode>> outputs = new ArrayList<SequencePairAlignment<Object,ViterbiNode>>(n);
for (int i = 0; i < n && search.hasNext(); i++) {
// gsc: removing unnecessary cast
SearchNode ans = search.next();
double weight = -ans.getCost();
ViterbiNode[] seq = new ViterbiNode[latticeLength];
// Commented out so we get the start state ViterbiNode -akm 12/2007
//ans = ans.getParent(); // ans now corresponds to the Viterbi node after the first transition
for (int j = 0; j < latticeLength; j++) {
ViterbiNode v = (ViterbiNode)ans.getState();
assert(v.inputPosition == j); // was == j+1
seq[j] = v;
ans = ans.getParent();
}
outputs.add(new SequencePairAlignment<Object,ViterbiNode>(input, new ArraySequence<ViterbiNode>(seq), weight));
}
viterbiNodeAlignmentCache = outputs;
return outputs;