code: package morfologik.fsa;
  
  import static morfologik.fsa.FSAFlags.*;
  
  import java.io.DataInputStream;
  import java.io.IOException;
  import java.io.InputStream;
  import java.util.Collections;
  import java.util.EnumSet;
  import java.util.Set;
  
  /**
   * FSA binary format implementation for version 5.
   * 
   * <p>
   * Version 5 indicates the dictionary was built with these flags:
   * {@link FSAFlags#FLEXIBLE}, {@link FSAFlags#STOPBIT} and
   * {@link FSAFlags#NEXTBIT}. The internal representation of the FSA must
   * therefore follow this description (please note this format describes only a
   * single transition (arc), not the entire dictionary file).
   * 
   * <pre>
   * ---- this node header present only if automaton was compiled with NUMBERS option.
   * Byte
   *        +-+-+-+-+-+-+-+-+\
   *      0 | | | | | | | | | \  LSB
   *        +-+-+-+-+-+-+-+-+  +
   *      1 | | | | | | | | |  |      number of strings recognized
   *        +-+-+-+-+-+-+-+-+  +----- by the automaton starting
   *        : : : : : : : : :  |      from this node.
   *        +-+-+-+-+-+-+-+-+  +
   *  ctl-1 | | | | | | | | | /  MSB
   *        +-+-+-+-+-+-+-+-+/
   *        
   * ---- remaining part of the node
   * 
   * Byte
   *       +-+-+-+-+-+-+-+-+\
   *     0 | | | | | | | | | +------ label
   *       +-+-+-+-+-+-+-+-+/
   * 
   *                  +------------- node pointed to is next
   *                  | +----------- the last arc of the node
   *                  | | +--------- the arc is final
   *                  | | |
   *             +-----------+
   *             |    | | |  |
   *         ___+___  | | |  |
   *        /       \ | | |  |
   *       MSB           LSB |
   *        7 6 5 4 3 2 1 0  |
   *       +-+-+-+-+-+-+-+-+ |
   *     1 | | | | | | | | | \ \
   *       +-+-+-+-+-+-+-+-+  \ \  LSB
   *       +-+-+-+-+-+-+-+-+     +
   *     2 | | | | | | | | |     |
   *       +-+-+-+-+-+-+-+-+     |
   *     3 | | | | | | | | |     +----- target node address (in bytes)
   *       +-+-+-+-+-+-+-+-+     |      (not present except for the byte
   *       : : : : : : : : :     |       with flags if the node pointed to
   *       +-+-+-+-+-+-+-+-+     +       is next)
   *   gtl | | | | | | | | |    /  MSB
   *       +-+-+-+-+-+-+-+-+   /
   * gtl+1                           (gtl = gotoLength)
   * </pre>
   */
  public final class FSA5 extends FSA {
    /**
     * Default filler byte.
     */
    public final static byte DEFAULT_FILLER = '_';
  
    /**
     * Default annotation byte.
     */
    public final static byte DEFAULT_ANNOTATION = '+';
  
    /**
     * Automaton version as in the file header.
     */
    public static final byte VERSION = 5;
  
    /**
     * Bit indicating that an arc corresponds to the last character of a sequence
     * available when building the automaton.
     */
    public static final int BIT_FINAL_ARC = 1 << 0;
  
    /**
     * Bit indicating that an arc is the last one of the node's list and the
     * following one belongs to another node.
     */
    public static final int BIT_LAST_ARC = 1 << 1;
  
    /**
     * Bit indicating that the target node of this arc follows it in the
     * compressed automaton structure (no goto field).
     */
    public static final int BIT_TARGET_NEXT = 1 << 2;
  
    /**
     * An offset in the arc structure, where the address and flags field begins.
     * In version 5 of FSA automata, this value is constant (1, skip label).
     */
    public final static int ADDRESS_OFFSET = 1;
  
    /**
     * An array of bytes with the internal representation of the automaton. Please
     * see the documentation of this class for more information on how this
     * structure is organized.
     */
    public final byte[] arcs;
  
    /**
     * The length of the node header structure (if the automaton was compiled with
     * <code>NUMBERS</code> option). Otherwise zero.
     */
    public final int nodeDataLength;
  
    /**
     * Flags for this automaton version.
     */
    private Set<FSAFlags> flags;
  
    /**
     * Number of bytes each address takes in full, expanded form (goto length).
     */
    public final int gtl;
  
    /** Filler character. */
    public final byte filler;
  
    /** Annotation character. */
    public final byte annotation;
  
    /**
     * Read and wrap a binary automaton in FSA version 5.
     */
    FSA5(InputStream stream) throws IOException {
      DataInputStream in = new DataInputStream(stream);
  
      this.filler = in.readByte();
      this.annotation = in.readByte();
      final byte hgtl = in.readByte();
  
      /*
       * Determine if the automaton was compiled with NUMBERS. If so, modify
       * ctl and goto fields accordingly.
       */
      flags = EnumSet.of(FLEXIBLE, STOPBIT, NEXTBIT);
      if ((hgtl & 0xf0) != 0) {
        flags.add(NUMBERS);
      }
  
      flags = Collections.unmodifiableSet(flags);
  
      this.nodeDataLength = (hgtl >>> 4) & 0x0f;
      this.gtl = hgtl & 0x0f;
  
      arcs = readRemaining(in);
    }
  
    /**
     * Returns the start node of this automaton.
     */
    @Override
    public int getRootNode() {
      // Skip dummy node marking terminating state.
      final int epsilonNode = skipArc(getFirstArc(0));
  
      // And follow the epsilon node's first (and only) arc.
      return getDestinationNodeOffset(getFirstArc(epsilonNode));
    }
  
    /**
     * {@inheritDoc}
     */
    @Override
    public final int getFirstArc(int node) {
      return nodeDataLength + node;
    }
  
    /**
     * {@inheritDoc}
     */
    @Override
    public final int getNextArc(int arc) {
      if (isArcLast(arc))
        return 0;
      else
        return skipArc(arc);
    }
  
    /**
     * {@inheritDoc}
     */
    @Override
    public int getArc(int node, byte label) {
      for (int arc = getFirstArc(node); arc != 0; arc = getNextArc(arc)) {
        if (getArcLabel(arc) == label)
          return arc;
      }
  
      // An arc labeled with "label" not found.
      return 0;
    }
  
    /**
     * {@inheritDoc}
     */
    @Override
    public int getEndNode(int arc) {
      final int nodeOffset = getDestinationNodeOffset(arc);
      assert nodeOffset != 0 : "No target node for terminal arcs.";
      return nodeOffset;
    }
  
    /**
     * {@inheritDoc}
     */
    @Override
    public byte getArcLabel(int arc) {
      return arcs[arc];
    }
  
    /**
     * {@inheritDoc}
     */
    @Override
    public boolean isArcFinal(int arc) {
      return (arcs[arc + ADDRESS_OFFSET] & BIT_FINAL_ARC) != 0;
    }
  
    /**
     * {@inheritDoc}
     */
    @Override
    public boolean isArcTerminal(int arc) {
      return (0 == getDestinationNodeOffset(arc));
    }
  
    /**
     * Returns the number encoded at the given node. The number equals the count
     * of the set of suffixes reachable from <code>node</code> (called its right
     * language).
     */
    @Override
    public int getRightLanguageCount(int node) {
      assert getFlags().contains(FSAFlags.NUMBERS) : "This FSA was not compiled with NUMBERS.";
      return decodeFromBytes(arcs, node, nodeDataLength);
    }
  
    /**
     * {@inheritDoc}
     * 
     * <p>
     * For this automaton version, an additional {@link FSAFlags#NUMBERS} flag may
     * be set to indicate the automaton contains extra fields for each node.
     * </p>
     */
    @Override
    public Set<FSAFlags> getFlags() {
      return flags;
    }
  
    /**
     * Returns <code>true</code> if this arc has <code>NEXT</code> bit set.
     * 
     * @see #BIT_LAST_ARC
     * @param arc The node's arc identifier.
     * @return Returns true if the argument is the last arc of a node.
     */
    public boolean isArcLast(int arc) {
      return (arcs[arc + ADDRESS_OFFSET] & BIT_LAST_ARC) != 0;
    }
  
    /**
     * @see #BIT_TARGET_NEXT
     * @param arc The node's arc identifier.
     * @return Returns true if {@link #BIT_TARGET_NEXT} is set for this arc.
     */
    public boolean isNextSet(int arc) {
      return (arcs[arc + ADDRESS_OFFSET] & BIT_TARGET_NEXT) != 0;
    }
  
    /**
     * Returns an n-byte integer encoded in byte-packed representation.
     */
    static final int decodeFromBytes(final byte[] arcs, final int start, final int n) {
      int r = 0;
      for (int i = n; --i >= 0;) {
        r = r << 8 | (arcs[start + i] & 0xff);
      }
      return r;
    }
  
    /**
     * Returns the address of the node pointed to by this arc.
     */
    final int getDestinationNodeOffset(int arc) {
      if (isNextSet(arc)) {
        /* The destination node follows this arc in the array. */
        return skipArc(arc);
      } else {
        /*
         * The destination node address has to be extracted from the arc's
         * goto field.
         */
        return decodeFromBytes(arcs, arc + ADDRESS_OFFSET, gtl) >>> 3;
      }
    }
  
    /**
     * Read the arc's layout and skip as many bytes, as needed.
     */
    private int skipArc(int offset) {
      return offset + 
          (isNextSet(offset) 
              ? 1 + 1   /* label + flags */ 
              : 1 + gtl /* label + flags/address */);
    }
  }