code: package morfologik.fsa;
  
  import java.io.DataInputStream;
  import java.io.IOException;
  import java.io.InputStream;
  import java.util.EnumSet;
  import java.util.Set;
  
  /**
   * CFSA (Compact Finite State Automaton) binary format implementation, version 2:
   * <ul>
   *  <li>{@link #BIT_TARGET_NEXT} applicable on all arcs, not necessarily the last one.</li>
   *  <li>v-coded goto field</li>
   *  <li>v-coded perfect hashing numbers, if any</li>
   *  <li>31 most frequent labels integrated with flags byte</li>
   * </ul>
   * 
   * <p>The encoding of automaton body is as follows.</p>
   * 
   * <pre>
   * ---- CFSA header
   * Byte                            Description 
   *       +-+-+-+-+-+-+-+-+\
   *     0 | | | | | | | | | +------ '\'
   *       +-+-+-+-+-+-+-+-+/
   *       +-+-+-+-+-+-+-+-+\
   *     1 | | | | | | | | | +------ 'f'
   *       +-+-+-+-+-+-+-+-+/
   *       +-+-+-+-+-+-+-+-+\
   *     2 | | | | | | | | | +------ 's'
   *       +-+-+-+-+-+-+-+-+/
   *       +-+-+-+-+-+-+-+-+\
   *     3 | | | | | | | | | +------ 'a'
   *       +-+-+-+-+-+-+-+-+/
   *       +-+-+-+-+-+-+-+-+\
   *     4 | | | | | | | | | +------ version (fixed 0xc6)
   *       +-+-+-+-+-+-+-+-+/
   *       +-+-+-+-+-+-+-+-+\
   *     5 | | | | | | | | | +----\
   *       +-+-+-+-+-+-+-+-+/      \ flags [MSB first]
   *       +-+-+-+-+-+-+-+-+\      /
   *     6 | | | | | | | | | +----/
   *       +-+-+-+-+-+-+-+-+/
   *       +-+-+-+-+-+-+-+-+\
   *     7 | | | | | | | | | +------ label lookup table size
   *       +-+-+-+-+-+-+-+-+/
   *       +-+-+-+-+-+-+-+-+\
   *  8-32 | | | | | | | | | +------ label value lookup table 
   *       : : : : : : : : : |
   *       +-+-+-+-+-+-+-+-+/
   * 
   * ---- Start of a node; only if automaton was compiled with NUMBERS option.
   * 
   * Byte
   *        +-+-+-+-+-+-+-+-+\
   *      0 | | | | | | | | | \  
   *        +-+-+-+-+-+-+-+-+  +
   *      1 | | | | | | | | |  |      number of strings recognized
   *        +-+-+-+-+-+-+-+-+  +----- by the automaton starting
   *        : : : : : : : : :  |      from this node. v-coding
   *        +-+-+-+-+-+-+-+-+  +
   *        | | | | | | | | | /  
   *        +-+-+-+-+-+-+-+-+/
   *
   * ---- A vector of this node's arcs. An arc's layout depends on the combination of flags.
   * 
   * 1) NEXT bit set, mapped arc label. 
   * 
   *        +----------------------- node pointed to is next
   *        | +--------------------- the last arc of the node
   *        | | +------------------- this arc leads to a final state (acceptor)
   *        | | |  _______+--------- arc's label; indexed if M &gt; 0, otherwise explicit label follows
   *        | | | / | | | |
   *       +-+-+-+-+-+-+-+-+\
   *     0 |N|L|F|M|M|M|M|M| +------ flags + (M) index of the mapped label.
   *       +-+-+-+-+-+-+-+-+/
   *       +-+-+-+-+-+-+-+-+\
   *     1 | | | | | | | | | +------ optional label if M == 0
   *       +-+-+-+-+-+-+-+-+/
   *       : : : : : : : : :
   *       +-+-+-+-+-+-+-+-+\
   *       |A|A|A|A|A|A|A|A| +------ v-coded goto address
   *       +-+-+-+-+-+-+-+-+/
   * </pre>
   */
  public final class CFSA2 extends FSA {
  	/**
  	 * Automaton header version value. 
  	 */
  	public static final byte VERSION = (byte) 0xc6;
  
    /**
     * The target node of this arc follows the last arc of the current state
     * (no goto field).
     */
    public static final int BIT_TARGET_NEXT = 1 << 7;
  
    /**
     * The arc is the last one from the current node's arcs list.
     */
    public static final int BIT_LAST_ARC = 1 << 6;
  
  	/**
  	 * The arc corresponds to the last character of a sequence 
  	 * available when building the automaton (acceptor transition).
  	 */
  	public static final int BIT_FINAL_ARC = 1 << 5;
  
  	/**
  	 * The count of bits assigned to storing an indexed label. 
  	 */
  	static final int LABEL_INDEX_BITS = 5;
  	
  	/**
  	 * Masks only the M bits of a flag byte.
  	 */
  	static final int LABEL_INDEX_MASK = (1 << LABEL_INDEX_BITS) - 1;
  
    /**
     * Maximum size of the labels index.
     */
    public static final int LABEL_INDEX_SIZE = (1 << LABEL_INDEX_BITS) - 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 byte[] arcs;
  
    /**
     * Flags for this automaton version.
     */
    private final EnumSet<FSAFlags> flags;
  
  	/**
  	 * Label mapping for M-indexed labels.
  	 */
  	public final byte[] labelMapping;
  	
  	/**
  	 * If <code>true</code> states are prepended with numbers.
  	 */
  	private final boolean hasNumbers;
  	
  	/**
  	 * Epsilon node's offset.
  	 */
  	private final int epsilon = 0;
  
  	/**
  	 * Reads an automaton from a byte stream.
  	 */
  	CFSA2(InputStream stream) throws IOException {
      DataInputStream in = new DataInputStream(stream);
  
  		// Read flags.
  		short flagBits = in.readShort();
  		flags = EnumSet.noneOf(FSAFlags.class);
  		for (FSAFlags f : FSAFlags.values()) {
  		    if (f.isSet(flagBits)) {
  		        flags.add(f);
  		    }
  		}
  
  		if (flagBits != FSAFlags.asShort(flags)) {
  		    throw new IOException("Unrecognized flags: 0x" + Integer.toHexString(flagBits));
  		}
  
  		this.hasNumbers = flags.contains(FSAFlags.NUMBERS);
  
  		/*
  		 * Read mapping dictionary.
  		 */
  		int labelMappingSize = in.readByte() & 0xff;
  		labelMapping = new byte[labelMappingSize];
  		in.readFully(labelMapping);
  
  		/*
  		 * Read arcs' data.
  		 */
  		arcs = readRemaining(in);		
  	}
  
    /**
     * {@inheritDoc}
     */
    @Override
    public int getRootNode() {
      // Skip dummy node marking terminating state.
      return getDestinationNodeOffset(getFirstArc(epsilon));
    }
  
    /**
     * {@inheritDoc}
     */
    @Override
    public final int getFirstArc(int node) {
      if (hasNumbers) {
        return skipVInt(node);
      } else {
        return 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 : "Can't follow a terminal arc: " + arc;
      assert nodeOffset < arcs.length : "Node out of bounds.";
      return nodeOffset;
    }
  
    /**
     * {@inheritDoc}
     */
    @Override
    public byte getArcLabel(int arc) {
      int index = arcs[arc] & LABEL_INDEX_MASK;
      if (index > 0) {
        return this.labelMapping[index];
      } else {
        return arcs[arc + 1];
      }
    }
  
    /**
     * {@inheritDoc}
     */
    @Override
    public int getRightLanguageCount(int node) {
      assert getFlags().contains(FSAFlags.NUMBERS) : "This FSA was not compiled with NUMBERS.";
      return readVInt(arcs, node);
    }
  
    /**
     * {@inheritDoc}
     */
    @Override
    public boolean isArcFinal(int arc) {
      return (arcs[arc] & BIT_FINAL_ARC) != 0;
    }
  
    /**
     * {@inheritDoc}
     */
    @Override
    public boolean isArcTerminal(int arc) {
      return (0 == getDestinationNodeOffset(arc));
    }
  
    /**
     * 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] & 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] & BIT_TARGET_NEXT) != 0;
    }
  
    /**
     * {@inheritDoc}
     */
    public Set<FSAFlags> getFlags() {
      return flags;
    }
  
    /**
     * Returns the address of the node pointed to by this arc.
     */
    final int getDestinationNodeOffset(int arc) {
      if (isNextSet(arc)) {
        /* Follow until the last arc of this state. */
        while (!isArcLast(arc)) {
          arc = getNextArc(arc);
        }
  
        /* And return the byte right after it. */
        return skipArc(arc);
      } else {
        /*
         * The destination node address is v-coded. v-code starts either
         * at the next byte (label indexed) or after the next byte (label explicit).
         */
        return readVInt(arcs, arc + ((arcs[arc] & LABEL_INDEX_MASK) == 0 ? 2 : 1));
      }
    }
  
    /**
     * Read the arc's layout and skip as many bytes, as needed, to skip it.
     */
    private int skipArc(int offset) {
      int flag = arcs[offset++];
  
      // Explicit label?
      if ((flag & LABEL_INDEX_MASK) == 0) {
        offset++;
      }
  
      // Explicit goto?
      if ((flag & BIT_TARGET_NEXT) == 0) {
        offset = skipVInt(offset);
      }
  
      assert offset < this.arcs.length;
      return offset;
    }
  
    /**
     * Read a v-int.
     */
    static int readVInt(byte[] array, int offset) {
      byte b = array[offset];
      int value = b & 0x7F;
  
      for (int shift = 7; b < 0; shift += 7) {
        b = array[++offset];
        value |= (b & 0x7F) << shift;
      }
  
      return value;
    }
  
    /**
     * Return the byte-length of a v-coded int.
     */
    static int vIntLength(int value) {
      assert value >= 0 : "Can't v-code negative ints.";
  
      int bytes;
      for (bytes = 1; value >= 0x80; bytes++) {
        value >>= 7;
      }
  
      return bytes;
    }
  
    /**
     * Skip a v-int.
     */
    private int skipVInt(int offset) {
      while (arcs[offset++] < 0) {
        // Do nothing.
      }
      return offset;
    }
  }