content: package org.apache.lucene.util.fst;
  
  /**
   * Licensed to the Apache Software Foundation (ASF) under one or more
   * contributor license agreements.  See the NOTICE file distributed with
   * this work for additional information regarding copyright ownership.
   * The ASF licenses this file to You under the Apache License, Version 2.0
   * (the "License"); you may not use this file except in compliance with
   * the License.  You may obtain a copy of the License at
   *
   *     http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  import java.io.IOException;
  
  import org.apache.lucene.store.DataInput;
  import org.apache.lucene.store.DataOutput;
  import org.apache.lucene.util.ArrayUtil;
  import org.apache.lucene.util.CodecUtil;
  import org.apache.lucene.util.fst.Builder.UnCompiledNode;
  
  // TODO: if FST is pure prefix trie we can do a more compact
  // job, ie, once we are at a 'suffix only', just store the
  // completion labels as a string not as a series of arcs.
  
  // NOTE: while the FST is able to represent a non-final
  // dead-end state (NON_FINAL_END_NODE=0), the layers above
  // (FSTEnum, Util) have problems with this!!
  
  /** Represents an FST using a compact byte[] format.
   *  <p> The format is similar to what's used by Morfologik
   *  (http://sourceforge.net/projects/morfologik).
   *
   *  <p><b>NOTE</b>: the FST cannot be larger than ~2.1 GB
   *  because it uses int to address the byte[].
   *
   * @lucene.experimental
   */
  public class FST<T> {
    public static enum INPUT_TYPE {BYTE1, BYTE2, BYTE4};
    public final INPUT_TYPE inputType;
  
    private final static int BIT_FINAL_ARC = 1 << 0;
    private final static int BIT_LAST_ARC = 1 << 1;
    private final static int BIT_TARGET_NEXT = 1 << 2;
    private final static int BIT_STOP_NODE = 1 << 3;
    private final static int BIT_ARC_HAS_OUTPUT = 1 << 4;
    private final static int BIT_ARC_HAS_FINAL_OUTPUT = 1 << 5;
  
    // Arcs are stored as fixed-size (per entry) array, so
    // that we can find an arc using binary search.  We do
    // this when number of arcs is > NUM_ARCS_ARRAY:
    private final static int BIT_ARCS_AS_FIXED_ARRAY = 1 << 6;
  
    /**
     * @see #shouldExpand(UnCompiledNode)
     */
    final static int FIXED_ARRAY_SHALLOW_DISTANCE = 3; // 0 => only root node.
  
    /**
     * @see #shouldExpand(UnCompiledNode)
     */
    final static int FIXED_ARRAY_NUM_ARCS_SHALLOW = 5;
  
    /**
     * @see #shouldExpand(UnCompiledNode)
     */
    final static int FIXED_ARRAY_NUM_ARCS_DEEP = 10;
  
    private int[] bytesPerArc = new int[0];
  
    // Increment version to change it
    private final static String FILE_FORMAT_NAME = "FST";
    private final static int VERSION_START = 0;
  
    /** Changed numBytesPerArc for array'd case from byte to int. */
    private final static int VERSION_INT_NUM_BYTES_PER_ARC = 1;
  
    private final static int VERSION_CURRENT = VERSION_INT_NUM_BYTES_PER_ARC;
  
    // Never serialized; just used to represent the virtual
    // final node w/ no arcs:
    private final static int FINAL_END_NODE = -1;
  
    // Never serialized; just used to represent the virtual
    // non-final node w/ no arcs:
    private final static int NON_FINAL_END_NODE = 0;
  
    // if non-null, this FST accepts the empty string and
    // produces this output
    T emptyOutput;
    private byte[] emptyOutputBytes;
  
    private byte[] bytes;
    int byteUpto = 0;
  
    private int startNode = -1;
  
    public final Outputs<T> outputs;
  
    private int lastFrozenNode;
  
    private final T NO_OUTPUT;
  
    public int nodeCount;
    public int arcCount;
    public int arcWithOutputCount;
  
    // If arc has this label then that arc is final/accepted
    public static final int END_LABEL = -1;
  
    private Arc<T> cachedRootArcs[];
  
    public final static class Arc<T> {
      public int label;
      public T output;
  
      int target;
  
      byte flags;
      public T nextFinalOutput;
      int nextArc;
  
      // This is non-zero if current arcs are fixed array:
      int posArcsStart;
      int bytesPerArc;
      int arcIdx;
      int numArcs;
  
      /** Returns this */
      public Arc<T> copyFrom(Arc<T> other) {
        label = other.label;
        target = other.target;
        flags = other.flags;
        output = other.output;
        nextFinalOutput = other.nextFinalOutput;
        nextArc = other.nextArc;
        if (other.bytesPerArc != 0) {
          bytesPerArc = other.bytesPerArc;
          posArcsStart = other.posArcsStart;
          arcIdx = other.arcIdx;
          numArcs = other.numArcs;
        } else {
          bytesPerArc = 0;
        }
        return this;
      }
  
      boolean flag(int flag) {
        return FST.flag(flags, flag);
      }
  
      public boolean isLast() {
        return flag(BIT_LAST_ARC);
      }
  
      public boolean isFinal() {
        return flag(BIT_FINAL_ARC);
      }
    };
  
    static boolean flag(int flags, int bit) {
      return (flags & bit) != 0;
    }
  
    private final BytesWriter writer;
  
    // make a new empty FST, for building
    public FST(INPUT_TYPE inputType, Outputs<T> outputs) {
      this.inputType = inputType;
      this.outputs = outputs;
      bytes = new byte[128];
      NO_OUTPUT = outputs.getNoOutput();
      
      writer = new BytesWriter();
  
      emptyOutput = null;
    }
  
    // create an existing FST
    public FST(DataInput in, Outputs<T> outputs) throws IOException {
      this.outputs = outputs;
      writer = null;
      CodecUtil.checkHeader(in, FILE_FORMAT_NAME, VERSION_INT_NUM_BYTES_PER_ARC, VERSION_INT_NUM_BYTES_PER_ARC);
      if (in.readByte() == 1) {
        // accepts empty string
        int numBytes = in.readVInt();
        // messy
        bytes = new byte[numBytes];
        in.readBytes(bytes, 0, numBytes);
        emptyOutput = outputs.read(getBytesReader(numBytes-1));
      } else {
        emptyOutput = null;
      }
      final byte t = in.readByte();
      switch(t) {
        case 0:
          inputType = INPUT_TYPE.BYTE1;
          break;
        case 1:
          inputType = INPUT_TYPE.BYTE2;
          break;
        case 2:
          inputType = INPUT_TYPE.BYTE4;
          break;
      default:
        throw new IllegalStateException("invalid input type " + t);
      }
      startNode = in.readVInt();
      nodeCount = in.readVInt();
      arcCount = in.readVInt();
      arcWithOutputCount = in.readVInt();
  
      bytes = new byte[in.readVInt()];
      in.readBytes(bytes, 0, bytes.length);
      NO_OUTPUT = outputs.getNoOutput();
  
      cacheRootArcs();
    }
  
    public INPUT_TYPE getInputType() {
      return inputType;
    }
  
    /** Returns bytes used to represent the FST */
    public int sizeInBytes() {
      return bytes.length;
    }
  
    void finish(int startNode) throws IOException {
      if (startNode == FINAL_END_NODE && emptyOutput != null) {
        startNode = 0;
      }
      if (this.startNode != -1) {
        throw new IllegalStateException("already finished");
      }
      byte[] finalBytes = new byte[writer.posWrite];
      System.arraycopy(bytes, 0, finalBytes, 0, writer.posWrite);
      bytes = finalBytes;
      this.startNode = startNode;
  
      cacheRootArcs();
    }
  
    // Caches first 128 labels
    @SuppressWarnings("unchecked")
    private void cacheRootArcs() throws IOException {
      cachedRootArcs = (FST.Arc<T>[]) new FST.Arc[0x80];
      final FST.Arc<T> arc = new FST.Arc<T>();
      getFirstArc(arc);
      final BytesReader in = getBytesReader(0);
      if (targetHasArcs(arc)) {
        readFirstRealArc(arc.target, arc);
        while(true) {
          assert arc.label != END_LABEL;
          if (arc.label < cachedRootArcs.length) {
            cachedRootArcs[arc.label] = new Arc<T>().copyFrom(arc);
          } else {
            break;
          }
          if (arc.isLast()) {
            break;
          }
          readNextRealArc(arc, in);
        }
      }
    }
  
    void setEmptyOutput(T v) throws IOException {
      if (emptyOutput != null) {
        emptyOutput = outputs.merge(emptyOutput, v);
      } else {
        emptyOutput = v;
      }
  
      // TODO: this is messy -- replace with sillyBytesWriter; maybe make
      // bytes private
      final int posSave = writer.posWrite;
      outputs.write(emptyOutput, writer);
      emptyOutputBytes = new byte[writer.posWrite-posSave];
  
      // reverse
      final int stopAt = (writer.posWrite - posSave)/2;
      int upto = 0;
      while(upto < stopAt) {
        final byte b = bytes[posSave + upto];
        bytes[posSave+upto] = bytes[writer.posWrite-upto-1];
        bytes[writer.posWrite-upto-1] = b;
        upto++;
      }
      System.arraycopy(bytes, posSave, emptyOutputBytes, 0, writer.posWrite-posSave);
      writer.posWrite = posSave;
    }
  
    public void save(DataOutput out) throws IOException {
      if (startNode == -1) {
        throw new IllegalStateException("call finish first");
      }
      CodecUtil.writeHeader(out, FILE_FORMAT_NAME, VERSION_CURRENT);
      // TODO: really we should encode this as an arc, arriving
      // to the root node, instead of special casing here:
      if (emptyOutput != null) {
        out.writeByte((byte) 1);
        out.writeVInt(emptyOutputBytes.length);
        out.writeBytes(emptyOutputBytes, 0, emptyOutputBytes.length);
      } else {
        out.writeByte((byte) 0);
      }
      final byte t;
      if (inputType == INPUT_TYPE.BYTE1) {
        t = 0;
      } else if (inputType == INPUT_TYPE.BYTE2) {
        t = 1;
      } else {
        t = 2;
      }
      out.writeByte(t);
      out.writeVInt(startNode);
      out.writeVInt(nodeCount);
      out.writeVInt(arcCount);
      out.writeVInt(arcWithOutputCount);
      out.writeVInt(bytes.length);
      out.writeBytes(bytes, 0, bytes.length);
    }
  
    private void writeLabel(int v) throws IOException {
      assert v >= 0: "v=" + v;
      if (inputType == INPUT_TYPE.BYTE1) {
        assert v <= 255: "v=" + v;
        writer.writeByte((byte) v);
      } else if (inputType == INPUT_TYPE.BYTE2) {
        assert v <= 65535: "v=" + v;
        writer.writeVInt(v);
      } else {
        //writeInt(v);
        writer.writeVInt(v);
      }
    }
  
    int readLabel(DataInput in) throws IOException {
      final int v;
      if (inputType == INPUT_TYPE.BYTE1) {
        v = in.readByte()&0xFF;
      } else { 
        v = in.readVInt();
      }
      return v;
    }
  
    // returns true if the node at this address has any
    // outgoing arcs
    public boolean targetHasArcs(Arc<T> arc) {
      return arc.target > 0;
    }
  
    // serializes new node by appending its bytes to the end
    // of the current byte[]
    int addNode(Builder.UnCompiledNode<T> node) throws IOException {
      //System.out.println("FST.addNode pos=" + posWrite + " numArcs=" + node.numArcs);
      if (node.numArcs == 0) {
        if (node.isFinal) {
          return FINAL_END_NODE;
        } else {
          return NON_FINAL_END_NODE;
        }
      }
  
      int startAddress = writer.posWrite;
      //System.out.println("  startAddr=" + startAddress);
  
      final boolean doFixedArray = shouldExpand(node);
      final int fixedArrayStart;
      if (doFixedArray) {
        if (bytesPerArc.length < node.numArcs) {
          bytesPerArc = new int[ArrayUtil.oversize(node.numArcs, 1)];
        }
        // write a "false" first arc:
        writer.writeByte((byte) BIT_ARCS_AS_FIXED_ARRAY);
        writer.writeVInt(node.numArcs);
        // placeholder -- we'll come back and write the number
        // of bytes per arc (int) here:
        // TODO: we could make this a vInt instead
        writer.writeInt(0);
        fixedArrayStart = writer.posWrite;
        //System.out.println("  do fixed arcs array arcsStart=" + fixedArrayStart);
      } else {
        fixedArrayStart = 0;
      }
  
      nodeCount++;
      arcCount += node.numArcs;
      
      final int lastArc = node.numArcs-1;
  
      int lastArcStart = writer.posWrite;
      int maxBytesPerArc = 0;
      for(int arcIdx=0;arcIdx<node.numArcs;arcIdx++) {
        final Builder.Arc<T> arc = node.arcs[arcIdx];
        final Builder.CompiledNode target = (Builder.CompiledNode) arc.target;
        int flags = 0;
  
        if (arcIdx == lastArc) {
          flags += BIT_LAST_ARC;
        }
  
        if (lastFrozenNode == target.address && !doFixedArray) {
          flags += BIT_TARGET_NEXT;
        }
  
        if (arc.isFinal) {
          flags += BIT_FINAL_ARC;
          if (arc.nextFinalOutput != NO_OUTPUT) {
            flags += BIT_ARC_HAS_FINAL_OUTPUT;
          }
        } else {
          assert arc.nextFinalOutput == NO_OUTPUT;
        }
  
        boolean targetHasArcs = target.address > 0;
  
        if (!targetHasArcs) {
          flags += BIT_STOP_NODE;
        }
  
        if (arc.output != NO_OUTPUT) {
          flags += BIT_ARC_HAS_OUTPUT;
        }
  
        writer.writeByte((byte) flags);
        writeLabel(arc.label);
  
        //System.out.println("  write arc: label=" + arc.label + " flags=" + flags);
  
        if (arc.output != NO_OUTPUT) {
          outputs.write(arc.output, writer);
          arcWithOutputCount++;
        }
        if (arc.nextFinalOutput != NO_OUTPUT) {
          outputs.write(arc.nextFinalOutput, writer);
        }
  
        if (targetHasArcs && (doFixedArray || lastFrozenNode != target.address)) {
          assert target.address > 0;
          writer.writeInt(target.address);
        }
  
        // just write the arcs "like normal" on first pass,
        // but record how many bytes each one took, and max
        // byte size:
        if (doFixedArray) {
          bytesPerArc[arcIdx] = writer.posWrite - lastArcStart;
          lastArcStart = writer.posWrite;
          maxBytesPerArc = Math.max(maxBytesPerArc, bytesPerArc[arcIdx]);
          //System.out.println("    bytes=" + bytesPerArc[arcIdx]);
        }
      }
  
      // TODO: if arc'd arrays will be "too wasteful" by some
      // measure, eg if arcs have vastly different sized
      // outputs, then we should selectively disable array for
      // such cases
  
      if (doFixedArray) {
        assert maxBytesPerArc > 0;
        // 2nd pass just "expands" all arcs to take up a fixed
        // byte size
        final int sizeNeeded = fixedArrayStart + node.numArcs * maxBytesPerArc;
        bytes = ArrayUtil.grow(bytes, sizeNeeded);
        // TODO: we could make this a vInt instead
        bytes[fixedArrayStart-4] = (byte) (maxBytesPerArc >> 24);
        bytes[fixedArrayStart-3] = (byte) (maxBytesPerArc >> 16);
        bytes[fixedArrayStart-2] = (byte) (maxBytesPerArc >> 8);
        bytes[fixedArrayStart-1] = (byte) maxBytesPerArc;
  
        // expand the arcs in place, backwards
        int srcPos = writer.posWrite;
        int destPos = fixedArrayStart + node.numArcs*maxBytesPerArc;
        writer.posWrite = destPos;
        for(int arcIdx=node.numArcs-1;arcIdx>=0;arcIdx--) {
          //System.out.println("  repack arcIdx=" + arcIdx + " srcPos=" + srcPos + " destPos=" + destPos);
          destPos -= maxBytesPerArc;
          srcPos -= bytesPerArc[arcIdx];
          if (srcPos != destPos) {
            assert destPos > srcPos;
            System.arraycopy(bytes, srcPos, bytes, destPos, bytesPerArc[arcIdx]);
          }
        }
      }
  
      // reverse bytes in-place; we do this so that the
      // "BIT_TARGET_NEXT" opto can work, ie, it reads the
      // node just before the current one
      final int endAddress = lastFrozenNode = writer.posWrite - 1;
  
      int left = startAddress;
      int right = endAddress;
      while (left < right) {
        final byte b = bytes[left];
        bytes[left++] = bytes[right];
        bytes[right--] = b;
      }
  
      return endAddress;
    }
  
    /** Fills virtual 'start' arc, ie, an empty incoming arc to
     *  the FST's start node */
    public Arc<T> getFirstArc(Arc<T> arc) {
      if (emptyOutput != null) {
        arc.flags = BIT_FINAL_ARC | BIT_LAST_ARC;
        arc.nextFinalOutput = emptyOutput;
      } else {
        arc.flags = BIT_LAST_ARC;
        arc.nextFinalOutput = NO_OUTPUT;
      }
      arc.output = NO_OUTPUT;
  
      // If there are no nodes, ie, the FST only accepts the
      // empty string, then startNode is 0, and then readFirstTargetArc
      arc.target = startNode;
      return arc;
    }
  
    /** Follows the <code>follow</code> arc and reads the last
     *  arc of its target; this changes the provided
     *  <code>arc</code> (2nd arg) in-place and returns it.
     * 
     * @return Returns the second argument
     * (<code>arc</code>). */
    public Arc<T> readLastTargetArc(Arc<T> follow, Arc<T> arc) throws IOException {
      //System.out.println("readLast");
      if (!targetHasArcs(follow)) {
        //System.out.println("  end node");
        assert follow.isFinal();
        arc.label = END_LABEL;
        arc.output = follow.nextFinalOutput;
        arc.flags = BIT_LAST_ARC;
        return arc;
      } else {
        final BytesReader in = getBytesReader(follow.target);
        arc.flags = in.readByte();
        if (arc.flag(BIT_ARCS_AS_FIXED_ARRAY)) {
          // array: jump straight to end
          arc.numArcs = in.readVInt();
          arc.bytesPerArc = in.readInt();
          //System.out.println("  array numArcs=" + arc.numArcs + " bpa=" + arc.bytesPerArc);
          arc.posArcsStart = in.pos;
          arc.arcIdx = arc.numArcs - 2;
        } else {
          // non-array: linear scan
          arc.bytesPerArc = 0;
          //System.out.println("  scan");
          while(!arc.isLast()) {
            // skip this arc:
            readLabel(in);
            if (arc.flag(BIT_ARC_HAS_OUTPUT)) {
              outputs.read(in);
            }
            if (arc.flag(BIT_ARC_HAS_FINAL_OUTPUT)) {
              outputs.read(in);
            }
            if (arc.flag(BIT_STOP_NODE)) {
            } else if (arc.flag(BIT_TARGET_NEXT)) {
            } else {
              in.pos -= 4;
            }
            arc.flags = in.readByte();
          }
          arc.nextArc = in.pos+1;
        }
        readNextRealArc(arc, in);
        assert arc.isLast();
        return arc;
      }
    }
  
    /**
     * Follow the <code>follow</code> arc and read the first arc of its target;
     * this changes the provided <code>arc</code> (2nd arg) in-place and returns
     * it.
     * 
     * @return Returns the second argument (<code>arc</code>).
     */
    public Arc<T> readFirstTargetArc(Arc<T> follow, Arc<T> arc) throws IOException {
      //int pos = address;
      //System.out.println("    readFirstTarget follow.target=" + follow.target + " isFinal=" + follow.isFinal());
      if (follow.isFinal()) {
        // Insert "fake" final first arc:
        arc.label = END_LABEL;
        arc.output = follow.nextFinalOutput;
        if (follow.target <= 0) {
          arc.flags = BIT_LAST_ARC;
        } else {
          arc.flags = 0;
          arc.nextArc = follow.target;
        }
        //System.out.println("    insert isFinal; nextArc=" + follow.target + " isLast=" + arc.isLast() + " output=" + outputs.outputToString(arc.output));
        return arc;
      } else {
        return readFirstRealArc(follow.target, arc);
      }
    }
  
    // Not private because NodeHash needs access:
    Arc<T> readFirstRealArc(int address, Arc<T> arc) throws IOException {
  
      final BytesReader in = getBytesReader(address);
  
      arc.flags = in.readByte();
  
      if (arc.flag(BIT_ARCS_AS_FIXED_ARRAY)) {
        //System.out.println("  fixedArray");
        // this is first arc in a fixed-array
        arc.numArcs = in.readVInt();
        arc.bytesPerArc = in.readInt();
        arc.arcIdx = -1;
        arc.nextArc = arc.posArcsStart = in.pos;
        //System.out.println("  bytesPer=" + arc.bytesPerArc + " numArcs=" + arc.numArcs + " arcsStart=" + pos);
      } else {
        arc.nextArc = address;
        arc.bytesPerArc = 0;
      }
      return readNextRealArc(arc, in);
    }
  
    /**
     * Checks if <code>arc</code>'s target state is in expanded (or vector) format. 
     * 
     * @return Returns <code>true</code> if <code>arc</code> points to a state in an
     * expanded array format.
     */
    boolean isExpandedTarget(Arc<T> follow) throws IOException {
      if (!targetHasArcs(follow)) {
        return false;
      } else {
        final BytesReader in = getBytesReader(follow.target);
        final byte b = in.readByte();
        return (b & BIT_ARCS_AS_FIXED_ARRAY) != 0;
      }
    }
  
    /** In-place read; returns the arc. */
    public Arc<T> readNextArc(Arc<T> arc) throws IOException {
      if (arc.label == END_LABEL) {
        // This was a fake inserted "final" arc
        if (arc.nextArc <= 0) {
          // This arc went to virtual final node, ie has no outgoing arcs
          return null;
        }
        return readFirstRealArc(arc.nextArc, arc);
      } else {
        return readNextRealArc(arc, getBytesReader(0));
      }
    }
  
    /** Peeks at next arc's label; does not alter arc.  Do
     *  not call this if arc.isLast()! */
    public int readNextArcLabel(Arc<T> arc) throws IOException {
      assert !arc.isLast();
  
      final BytesReader in;
      if (arc.label == END_LABEL) {
        //System.out.println("    nextArc fake " + arc.nextArc);
        in = getBytesReader(arc.nextArc);
        byte flags = bytes[in.pos];
        if (flag(flags, BIT_ARCS_AS_FIXED_ARRAY)) {
          //System.out.println("    nextArc fake array");
          in.pos--;
          in.readVInt();
          in.readInt();
        }
      } else {
        if (arc.bytesPerArc != 0) {
          //System.out.println("    nextArc real array");
          // arcs are at fixed entries
          in = getBytesReader(arc.posArcsStart - (1+arc.arcIdx)*arc.bytesPerArc);
        } else {
          // arcs are packed
          //System.out.println("    nextArc real packed");
          in = getBytesReader(arc.nextArc);
        }
      }
      // skip flags
      in.readByte();
      return readLabel(in);
    }
  
    Arc<T> readNextRealArc(Arc<T> arc, final BytesReader in) throws IOException {
      // this is a continuing arc in a fixed array
      if (arc.bytesPerArc != 0) {
        // arcs are at fixed entries
        arc.arcIdx++;
        assert arc.arcIdx < arc.numArcs;
        in.pos = arc.posArcsStart - arc.arcIdx*arc.bytesPerArc;
      } else {
        // arcs are packed
        in.pos = arc.nextArc;
      }
      arc.flags = in.readByte();
      arc.label = readLabel(in);
  
      if (arc.flag(BIT_ARC_HAS_OUTPUT)) {
        arc.output = outputs.read(in);
      } else {
        arc.output = outputs.getNoOutput();
      }
  
      if (arc.flag(BIT_ARC_HAS_FINAL_OUTPUT)) {
        arc.nextFinalOutput = outputs.read(in);
      } else {
        arc.nextFinalOutput = outputs.getNoOutput();
      }
  
      if (arc.flag(BIT_STOP_NODE)) {
        if (arc.flag(BIT_FINAL_ARC)) {
          arc.target = FINAL_END_NODE;
        } else {
          arc.target = NON_FINAL_END_NODE;
        }
        arc.nextArc = in.pos;
      } else if (arc.flag(BIT_TARGET_NEXT)) {
        arc.nextArc = in.pos;
        if (!arc.flag(BIT_LAST_ARC)) {
          if (arc.bytesPerArc == 0) {
            // must scan
            seekToNextNode(in);
          } else {
            in.pos = arc.posArcsStart - arc.bytesPerArc * arc.numArcs;
          }
        }
        arc.target = in.pos;
      } else {
        arc.target = in.readInt();
        arc.nextArc = in.pos;
      }
  
      return arc;
    }
  
    /** Finds an arc leaving the incoming arc, replacing the arc in place.
     *  This returns null if the arc was not found, else the incoming arc. */
    public Arc<T> findTargetArc(int labelToMatch, Arc<T> follow, Arc<T> arc) throws IOException {
      assert cachedRootArcs != null;
      // Short-circuit if this arc is in the root arc cache:
      if (follow.target == startNode && labelToMatch != END_LABEL && labelToMatch < cachedRootArcs.length) {
        final Arc<T> result = cachedRootArcs[labelToMatch];
        if (result == null) {
          return result;
        } else {
          arc.copyFrom(result);
          return arc;
        }
      }
   
      if (labelToMatch == END_LABEL) {
        if (follow.isFinal()) {
          arc.output = follow.nextFinalOutput;
          arc.label = END_LABEL;
          return arc;
        } else {
          return null;
        }
      }
  
      if (!targetHasArcs(follow)) {
        return null;
      }
  
      // TODO: maybe make an explicit thread state that holds
      // reusable stuff eg BytesReader:
      final BytesReader in = getBytesReader(follow.target);
  
      // System.out.println("fta label=" + (char) labelToMatch);
  
      if ((in.readByte() & BIT_ARCS_AS_FIXED_ARRAY) != 0) {
        // Arcs are full array; do binary search:
        arc.numArcs = in.readVInt();
        //System.out.println("  bs " + arc.numArcs);
        arc.bytesPerArc = in.readInt();
        arc.posArcsStart = in.pos;
        int low = 0;
        int high = arc.numArcs-1;
        while (low <= high) {
          //System.out.println("    cycle");
          int mid = (low + high) >>> 1;
          in.pos = arc.posArcsStart - arc.bytesPerArc*mid - 1;
          int midLabel = readLabel(in);
          final int cmp = midLabel - labelToMatch;
          if (cmp < 0)
            low = mid + 1;
          else if (cmp > 0)
            high = mid - 1;
          else {
            arc.arcIdx = mid-1;
            //System.out.println("    found!");
            return readNextRealArc(arc, in);
          }
        }
  
        return null;
      }
  
      // Linear scan
      readFirstTargetArc(follow, arc);
      while(true) {
        //System.out.println("  non-bs cycle");
        // TODO: we should fix this code to not have to create
        // object for the output of every arc we scan... only
        // for the matching arc, if found
        if (arc.label == labelToMatch) {
          //System.out.println("    found!");
          return arc;
        } else if (arc.label > labelToMatch) {
          return null;
        } else if (arc.isLast()) {
          return null;
        } else {
          readNextArc(arc);
        }
      }
    }
  
    private void seekToNextNode(BytesReader in) throws IOException {
  
      while(true) {
  
        final int flags = in.readByte();
        readLabel(in);
  
        if (flag(flags, BIT_ARC_HAS_OUTPUT)) {
          outputs.read(in);
        }
  
        if (flag(flags, BIT_ARC_HAS_FINAL_OUTPUT)) {
          outputs.read(in);
        }
  
        if (!flag(flags, BIT_STOP_NODE) && !flag(flags, BIT_TARGET_NEXT)) {
          in.readInt();
        }
  
        if (flag(flags, BIT_LAST_ARC)) {
          return;
        }
      }
    }
  
    public int getNodeCount() {
      // 1+ in order to count the -1 implicit final node
      return 1+nodeCount;
    }
    
    public int getArcCount() {
      return arcCount;
    }
  
    public int getArcWithOutputCount() {
      return arcWithOutputCount;
    }
    
    /**
     * Nodes will be expanded if their depth (distance from the root node) is
     * &lt;= this value and their number of arcs is &gt;=
     * {@link #FIXED_ARRAY_NUM_ARCS_SHALLOW}.
     * 
     * <p>
     * Fixed array consumes more RAM but enables binary search on the arcs
     * (instead of a linear scan) on lookup by arc label.
     * 
     * @return <code>true</code> if <code>node</code> should be stored in an
     *         expanded (array) form.
     * 
     * @see #FIXED_ARRAY_NUM_ARCS_DEEP
     * @see Builder.UnCompiledNode#depth
     */
    private boolean shouldExpand(UnCompiledNode<T> node) {
      return (node.depth <= FIXED_ARRAY_SHALLOW_DISTANCE && node.numArcs >= FIXED_ARRAY_NUM_ARCS_SHALLOW) || 
              node.numArcs >= FIXED_ARRAY_NUM_ARCS_DEEP;
    }
  
    // Non-static: writes to FST's byte[]
    class BytesWriter extends DataOutput {
      int posWrite;
  
      public BytesWriter() {
        // pad: ensure no node gets address 0 which is reserved to mean
        // the stop state w/ no arcs
        posWrite = 1;
      }
  
      @Override
      public void writeByte(byte b) {
        if (bytes.length == posWrite) {
          bytes = ArrayUtil.grow(bytes);
        }
        assert posWrite < bytes.length: "posWrite=" + posWrite + " bytes.length=" + bytes.length;
        bytes[posWrite++] = b;
      }
  
      @Override
      public void writeBytes(byte[] b, int offset, int length) {
        final int size = posWrite + length;
        bytes = ArrayUtil.grow(bytes, size);
        System.arraycopy(b, offset, bytes, posWrite, length);
        posWrite += length;
      }
    }
  
    final BytesReader getBytesReader(int pos) {
      // TODO: maybe re-use via ThreadLocal?
      return new BytesReader(pos);
    }
  
    // Non-static: reads byte[] from FST
    final class BytesReader extends DataInput {
      int pos;
  
      public BytesReader(int pos) {
        this.pos = pos;
      }
  
      @Override
      public byte readByte() {
        return bytes[pos--];
      }
  
      @Override
      public void readBytes(byte[] b, int offset, int len) {
        for(int i=0;i<len;i++) {
          b[offset+i] = bytes[pos--];
        }
      }
    }
  }
  