code: package morfologik.fsa;
  
  import static morfologik.fsa.MatchResult.*;
  
  /**
   * This class implements some common matching and scanning operations on a
   * generic FSA.
   */
  public final class FSATraversal {
  	/**
  	 * Target automaton.
  	 */
  	private final FSA fsa;
  
  	/**
  	 * Traversals of the given FSA.
  	 * 
  	 * @param fsa The target automaton for traversals. 
  	 */
  	public FSATraversal(FSA fsa) {
  		this.fsa = fsa;
  	}
  
  	/**
  	 * Calculate perfect hash for a given input sequence of bytes. The perfect hash requires
  	 * that {@link FSA} is built with {@link FSAFlags#NUMBERS} and corresponds to the sequential
  	 * order of input sequences used at automaton construction time.
  
  	 * @param sequence The byte sequence to calculate perfect hash for. 
  	 * @param start Start index in the sequence array. 
  	 * @param length Length of the byte sequence, must be at least 1.
  	 * @param node The node to start traversal from, typically the {@linkplain FSA#getRootNode() root node}.
  	 * 
  	 * @return Returns a unique integer assigned to the input sequence in the automaton (reflecting
  	 * the number of that sequence in the input used to build the automaton). Returns a negative
  	 * integer if the input sequence was not part of the input from which the automaton was created.
  	 * The type of mismatch is a constant defined in {@link MatchResult}.
  	 */
  	public int perfectHash(byte[] sequence, int start, int length, int node) {
  		assert fsa.getFlags().contains(FSAFlags.NUMBERS) : "FSA not built with NUMBERS option.";
  		assert length > 0 : "Must be a non-empty sequence.";
  
  		int hash = 0;
  		final int end = start + length - 1;
  
  		int seqIndex = start;
  		byte label = sequence[seqIndex];
  
  		// Seek through the current node's labels, looking for 'label', update hash.
  		for (int arc = fsa.getFirstArc(node); arc != 0;) {
  			if (fsa.getArcLabel(arc) == label) {
  				if (fsa.isArcFinal(arc)) {
  					if (seqIndex == end) {
  						return hash;
  					}
  
  					hash++;
  				}
  
  				if (fsa.isArcTerminal(arc)) {
  					/* The automaton contains a prefix of the input sequence. */
  					return AUTOMATON_HAS_PREFIX;
  				}
  
  				// The sequence is a prefix of one of the sequences stored in the automaton.
  				if (seqIndex == end) {
  					return SEQUENCE_IS_A_PREFIX;
  				}
  
  				// Make a transition along the arc, go the target node's first arc.
  				arc = fsa.getFirstArc(fsa.getEndNode(arc));
  				label = sequence[++seqIndex];
  				continue;
  			} else {
  				if (fsa.isArcFinal(arc)) {
  					hash++;
  				}
  				if (!fsa.isArcTerminal(arc)) {
  					hash += fsa.getRightLanguageCount(fsa.getEndNode(arc));
  				}
  			}
  
  			arc = fsa.getNextArc(arc);
  		}
  
  		if (seqIndex > start) {
  		  return AUTOMATON_HAS_PREFIX;
  		} else {
    		// Labels of this node ended without a match on the sequence. 
    		// Perfect hash does not exist.
    		return NO_MATCH;
  		}
  	}
  	
  	/**
     * @param sequence The byte sequence to calculate perfect hash for. 
  	 * @see #perfectHash(byte[], int, int, int)  
     * @return Returns a unique integer assigned to the input sequence in the automaton (reflecting
     * the number of that sequence in the input used to build the automaton). Returns a negative
     * integer if the input sequence was not part of the input from which the automaton was created.
     * The type of mismatch is a constant defined in {@link MatchResult}.
  	 */
  	public int perfectHash(byte[] sequence) {
  		return perfectHash(sequence, 0, sequence.length, fsa.getRootNode());
  	}
  
  	/**
  	 * Same as {@link #match(byte[], int, int, int)}, but allows passing
  	 * a reusable {@link MatchResult} object so that no intermediate garbage is
  	 * produced.
  	 * 
  	 * @param reuse The {@link MatchResult} to reuse. 
  	 * @param sequence Input sequence to look for in the automaton.
     * @param start Start index in the sequence array. 
     * @param length Length of the byte sequence, must be at least 1.
  	 * @param node The node to start traversal from, typically the {@linkplain FSA#getRootNode() root node}.  
  	 * 
  	 * @return The same object as <code>reuse</code>, but with updated match {@link MatchResult#kind}
  	 *        and other relevant fields.
  	 */
  	public MatchResult match(MatchResult reuse, byte[] sequence, int start, int length, int node) {
  		if (node == 0) {
  		  reuse.reset(NO_MATCH, start, node);
  			return reuse;
  		}
  
  		final FSA fsa = this.fsa;
  		final int end = start + length;
  		for (int i = start; i < end; i++) {
  			final int arc = fsa.getArc(node, sequence[i]);
  			if (arc != 0) {
  				if (i + 1 == end && fsa.isArcFinal(arc)) {
  					/* The automaton has an exact match of the input sequence. */
  				  reuse.reset(EXACT_MATCH, i, node);
  					return reuse;
  				}
  
  				if (fsa.isArcTerminal(arc)) {
  					/* The automaton contains a prefix of the input sequence. */
  				  reuse.reset(AUTOMATON_HAS_PREFIX, i + 1, node);
  					return reuse;
  				}
  
  				// Make a transition along the arc.
  				node = fsa.getEndNode(arc);
  			} else {
  			  if (i > start) {
  			    reuse.reset(AUTOMATON_HAS_PREFIX, i, node);
  			  } else {
  	        reuse.reset(NO_MATCH, i, node);
  			  }
  				return reuse;
  			}
  		}
  
  		/* The sequence is a prefix of at least one sequence in the automaton. */
  		reuse.reset(SEQUENCE_IS_A_PREFIX, 0, node);
  		return reuse;
  	}
  
    /**
     * Finds a matching path in the dictionary for a given sequence of labels from
     * <code>sequence</code> and starting at node <code>node</code>.
     * 
     * @param sequence Input sequence to look for in the automaton.
     * @param start Start index in the sequence array. 
     * @param length Length of the byte sequence, must be at least 1.
     * @param node The node to start traversal from, typically the {@linkplain FSA#getRootNode() root node}.  
     * 
     * @see #match(byte [], int)
     * @return {@link MatchResult} with updated match {@link MatchResult#kind}.
     */
    public MatchResult match(byte[] sequence, int start, int length, int node) {
      return match(new MatchResult(), sequence, start, length, node);
    }
  
  	/**
     * @param sequence Input sequence to look for in the automaton.
     * @param node The node to start traversal from, typically the {@linkplain FSA#getRootNode() root node}.  
     * 
     * @see #match(byte [], int)
     * @return {@link MatchResult} with updated match {@link MatchResult#kind}.
  	 */
  	public MatchResult match(byte[] sequence, int node) {
  		return match(sequence, 0, sequence.length, node);
  	}
  
  	/**
     * @param sequence Input sequence to look for in the automaton.
     * 
     * @see #match(byte [], int)
     * @return {@link MatchResult} with updated match {@link MatchResult#kind}.
  	 */
  	public MatchResult match(byte[] sequence) {
  		return match(sequence, fsa.getRootNode());
  	}
  }