text:
package org.apache.lucene.util.fst;

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.apache.lucene.codecs.CodecUtil;
import org.apache.lucene.store.ByteArrayDataOutput;
import org.apache.lucene.store.DataInput;
import org.apache.lucene.store.DataOutput;
import org.apache.lucene.store.InputStreamDataInput;
import org.apache.lucene.store.OutputStreamDataOutput;
import org.apache.lucene.store.RAMOutputStream;
import org.apache.lucene.util.Accountable;
import org.apache.lucene.util.Accountables;
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.Constants;
import org.apache.lucene.util.PriorityQueue;
import org.apache.lucene.util.RamUsageEstimator;
import org.apache.lucene.util.fst.Builder.UnCompiledNode;
import org.apache.lucene.util.packed.GrowableWriter;
import org.apache.lucene.util.packed.PackedInts;

// TODO: break this into WritableFST and ReadOnlyFST.. then
// we can have subclasses of ReadOnlyFST to handle the
// different byte[] level encodings (packed or
// not)... and things like nodeCount, arcCount are read only

// 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 finite state machine (FST), using a
 *  compact byte[] format.
 *  <p> The format is similar to what's used by Morfologik
 *  (http://sourceforge.net/projects/morfologik).
 *
 *  <p> See the {@link org.apache.lucene.util.fst package
 *      documentation} for some simple examples.
 *
 * @lucene.experimental
 */
public final class FST<T> implements Accountable {

  private static final long BASE_RAM_BYTES_USED = RamUsageEstimator.shallowSizeOfInstance(FST.class);
  private static final long ARC_SHALLOW_RAM_BYTES_USED = RamUsageEstimator.shallowSizeOfInstance(Arc.class);

  /** Specifies allowed range of each int input label for
   *  this FST. */
  public static enum INPUT_TYPE {BYTE1, BYTE2, BYTE4};

  static final int BIT_FINAL_ARC = 1 << 0;
  static final int BIT_LAST_ARC = 1 << 1;
  static final int BIT_TARGET_NEXT = 1 << 2;

  // TODO: we can free up a bit if we can nuke this:
  static final int BIT_STOP_NODE = 1 << 3;

  /** This flag is set if the arc has an output. */
  public static final int BIT_ARC_HAS_OUTPUT = 1 << 4;

  static final 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:

  // If set, the target node is delta coded vs current
  // position:
  private static final int BIT_TARGET_DELTA = 1 << 6;

  // We use this as a marker (because this one flag is
  // illegal by itself ...):
  private static final byte ARCS_AS_FIXED_ARRAY = BIT_ARC_HAS_FINAL_OUTPUT;

  /**
   * @see #shouldExpand(UnCompiledNode)
   */
  static final int FIXED_ARRAY_SHALLOW_DISTANCE = 3; // 0 => only root node.

  /**
   * @see #shouldExpand(UnCompiledNode)
   */
  static final int FIXED_ARRAY_NUM_ARCS_SHALLOW = 5;

  /**
   * @see #shouldExpand(UnCompiledNode)
   */
  static final int FIXED_ARRAY_NUM_ARCS_DEEP = 10;

  // Reused temporarily while building the FST:
  private int[] reusedBytesPerArc = new int[0];

  // Increment version to change it
  private static final String FILE_FORMAT_NAME = "FST";
  private static final int VERSION_START = 0;

  /** Changed numBytesPerArc for array'd case from byte to int. */
  private static final int VERSION_INT_NUM_BYTES_PER_ARC = 1;

  /** Write BYTE2 labels as 2-byte short, not vInt. */
  private static final int VERSION_SHORT_BYTE2_LABELS = 2;

  /** Added optional packed format. */
  private static final int VERSION_PACKED = 3;

  /** Changed from int to vInt for encoding arc targets.
   *  Also changed maxBytesPerArc from int to vInt in the array case. */
  private static final int VERSION_VINT_TARGET = 4;

  private static final int VERSION_CURRENT = VERSION_VINT_TARGET;

  // Never serialized; just used to represent the virtual
  // final node w/ no arcs:
  private static final long FINAL_END_NODE = -1;

  // Never serialized; just used to represent the virtual
  // non-final node w/ no arcs:
  private static final long NON_FINAL_END_NODE = 0;

  /** If arc has this label then that arc is final/accepted */
  public static final int END_LABEL = -1;

  public final INPUT_TYPE inputType;

  // if non-null, this FST accepts the empty string and
  // produces this output
  T emptyOutput;

  final BytesStore bytes;

  private long startNode = -1;

  public final Outputs<T> outputs;

  // Used for the BIT_TARGET_NEXT optimization (whereby
  // instead of storing the address of the target node for
  // a given arc, we mark a single bit noting that the next
  // node in the byte[] is the target node):
  private long lastFrozenNode;

  private final T NO_OUTPUT;

  public long nodeCount;
  public long arcCount;
  public long arcWithOutputCount;

  private final boolean packed;
  private PackedInts.Reader nodeRefToAddress;

  private final boolean allowArrayArcs;

  private Arc<T> cachedRootArcs[];

  /** Represents a single arc. */
  public static final class Arc<T> {
    public int label;
    public T output;

    // From node (ord or address); currently only used when
    // building an FST w/ willPackFST=true:
    long node;

    /** To node (ord or address) */
    public long target;

    byte flags;
    public T nextFinalOutput;

    // address (into the byte[]), or ord/address if label == END_LABEL
    long nextArc;

    /** Where the first arc in the array starts; only valid if
     *  bytesPerArc != 0 */
    public long posArcsStart;

    /** Non-zero if this arc is part of an array, which means all
     *  arcs for the node are encoded with a fixed number of bytes so
     *  that we can random access by index.  We do when there are enough
     *  arcs leaving one node.  It wastes some bytes but gives faster
     *  lookups. */
    public int bytesPerArc;

    /** Where we are in the array; only valid if bytesPerArc != 0. */
    public int arcIdx;

    /** How many arcs in the array; only valid if bytesPerArc != 0. */
    public int numArcs;

    /** Returns this */
    public Arc<T> copyFrom(Arc<T> other) {
      node = other.node;
      label = other.label;
      target = other.target;
      flags = other.flags;
      output = other.output;
      nextFinalOutput = other.nextFinalOutput;
      nextArc = other.nextArc;
      bytesPerArc = other.bytesPerArc;
      if (bytesPerArc != 0) {
        posArcsStart = other.posArcsStart;
        arcIdx = other.arcIdx;
        numArcs = other.numArcs;
      }
      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);
    }

    @Override
    public String toString() {
      StringBuilder b = new StringBuilder();
      b.append("node=" + node);
      b.append(" target=" + target);
      b.append(" label=0x" + Integer.toHexString(label));
      if (flag(BIT_FINAL_ARC)) {
        b.append(" final");
      }
      if (flag(BIT_LAST_ARC)) {
        b.append(" last");
      }
      if (flag(BIT_TARGET_NEXT)) {
        b.append(" targetNext");
      }
      if (flag(BIT_STOP_NODE)) {
        b.append(" stop");
      }
      if (flag(BIT_ARC_HAS_OUTPUT)) {
        b.append(" output=" + output);
      }
      if (flag(BIT_ARC_HAS_FINAL_OUTPUT)) {
        b.append(" nextFinalOutput=" + nextFinalOutput);
      }
      if (bytesPerArc != 0) {
        b.append(" arcArray(idx=" + arcIdx + " of " + numArcs + ")");
      }
      return b.toString();
    }
  };

  private static boolean flag(int flags, int bit) {
    return (flags & bit) != 0;
  }

  private GrowableWriter nodeAddress;

  // TODO: we could be smarter here, and prune periodically
  // as we go; high in-count nodes will "usually" become
  // clear early on:
  private GrowableWriter inCounts;

  private final int version;

  // make a new empty FST, for building; Builder invokes
  // this ctor
  FST(INPUT_TYPE inputType, Outputs<T> outputs, boolean willPackFST, float acceptableOverheadRatio, boolean allowArrayArcs, int bytesPageBits) {
    this.inputType = inputType;
    this.outputs = outputs;
    this.allowArrayArcs = allowArrayArcs;
    version = VERSION_CURRENT;
    bytes = new BytesStore(bytesPageBits);
    // pad: ensure no node gets address 0 which is reserved to mean
    // the stop state w/ no arcs
    bytes.writeByte((byte) 0);
    NO_OUTPUT = outputs.getNoOutput();
    if (willPackFST) {
      nodeAddress = new GrowableWriter(15, 8, acceptableOverheadRatio);
      inCounts = new GrowableWriter(1, 8, acceptableOverheadRatio);
    } else {
      nodeAddress = null;
      inCounts = null;
    }

    emptyOutput = null;
    packed = false;
    nodeRefToAddress = null;
  }

  public static final int DEFAULT_MAX_BLOCK_BITS = Constants.JRE_IS_64BIT ? 30 : 28;

  /** Load a previously saved FST. */
  public FST(DataInput in, Outputs<T> outputs) throws IOException {
    this(in, outputs, DEFAULT_MAX_BLOCK_BITS);
  }

  /** Load a previously saved FST; maxBlockBits allows you to
   *  control the size of the byte[] pages used to hold the FST bytes. */
  public FST(DataInput in, Outputs<T> outputs, int maxBlockBits) throws IOException {
    this.outputs = outputs;

    if (maxBlockBits < 1 || maxBlockBits > 30) {
      throw new IllegalArgumentException("maxBlockBits should be 1 .. 30; got " + maxBlockBits);
    }

    // NOTE: only reads most recent format; we don't have
    // back-compat promise for FSTs (they are experimental):
    version = CodecUtil.checkHeader(in, FILE_FORMAT_NAME, VERSION_PACKED, VERSION_VINT_TARGET);
    packed = in.readByte() == 1;
    if (in.readByte() == 1) {
      // accepts empty string
      // 1 KB blocks:
      BytesStore emptyBytes = new BytesStore(10);
      int numBytes = in.readVInt();
      emptyBytes.copyBytes(in, numBytes);

      // De-serialize empty-string output:
      BytesReader reader;
      if (packed) {
        reader = emptyBytes.getForwardReader();
      } else {
        reader = emptyBytes.getReverseReader();
        // NoOutputs uses 0 bytes when writing its output,
        // so we have to check here else BytesStore gets
        // angry:
        if (numBytes > 0) {
          reader.setPosition(numBytes-1);
        }
      }
      emptyOutput = outputs.readFinalOutput(reader);
    } 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);
    }
    if (packed) {
      nodeRefToAddress = PackedInts.getReader(in);
    } else {
      nodeRefToAddress = null;
    }
    startNode = in.readVLong();
    nodeCount = in.readVLong();
    arcCount = in.readVLong();
    arcWithOutputCount = in.readVLong();

    long numBytes = in.readVLong();
    bytes = new BytesStore(in, numBytes, 1<<maxBlockBits);

    NO_OUTPUT = outputs.getNoOutput();

    cacheRootArcs();

    // NOTE: bogus because this is only used during
    // building; we need to break out mutable FST from
    // immutable
    allowArrayArcs = false;

    /*
    if (bytes.length == 665) {
      Writer w = new OutputStreamWriter(new FileOutputStream("out.dot"), StandardCharsets.UTF_8);
      Util.toDot(this, w, false, false);
      w.close();
      System.out.println("Wrote FST to out.dot");
    }
    */
  }

  public INPUT_TYPE getInputType() {
    return inputType;
  }

  private long ramBytesUsed(Arc<T>[] arcs) {
    long size = 0;
    if (arcs != null) {
      size += RamUsageEstimator.shallowSizeOf(arcs);
      for (Arc<T> arc : arcs) {
        if (arc != null) {
          size += ARC_SHALLOW_RAM_BYTES_USED;
          if (arc.output != null && arc.output != outputs.getNoOutput()) {
            size += outputs.ramBytesUsed(arc.output);
          }
          if (arc.nextFinalOutput != null && arc.nextFinalOutput != outputs.getNoOutput()) {
            size += outputs.ramBytesUsed(arc.nextFinalOutput);
          }
        }
      }
    }
    return size;
  }

  private int cachedArcsBytesUsed;

  @Override
  public long ramBytesUsed() {
    long size = BASE_RAM_BYTES_USED;
    size += bytes.ramBytesUsed();
    if (packed) {
      size += nodeRefToAddress.ramBytesUsed();
    } else if (nodeAddress != null) {
      size += nodeAddress.ramBytesUsed();
      size += inCounts.ramBytesUsed();
    }
    size += cachedArcsBytesUsed;
    size += RamUsageEstimator.sizeOf(reusedBytesPerArc);
    return size;
  }

  @Override
  public Collection<Accountable> getChildResources() {
    List<Accountable> resources = new ArrayList<>();
    if (packed) {
      resources.add(Accountables.namedAccountable("node ref to address", nodeRefToAddress));
    } else if (nodeAddress != null) {
      resources.add(Accountables.namedAccountable("node addresses", nodeAddress));
      resources.add(Accountables.namedAccountable("in counts", inCounts));
    }
    return resources;
  }

  @Override
  public String toString() {
    return getClass().getSimpleName() + "(input=" + inputType + ",output=" + outputs + ",packed=" + packed + ",nodes=" + nodeCount + ",arcs=" + arcCount + ")";
  }

  void finish(long newStartNode) throws IOException {
    if (startNode != -1) {
      throw new IllegalStateException("already finished");
    }
    if (newStartNode == FINAL_END_NODE && emptyOutput != null) {
      newStartNode = 0;
    }
    startNode = newStartNode;
    bytes.finish();

    cacheRootArcs();
  }

  private long getNodeAddress(long node) {
    if (nodeAddress != null) {
      // Deref
      return nodeAddress.get((int) node);
    } else {
      // Straight
      return node;
    }
  }

  // Optionally caches first 128 labels
  @SuppressWarnings({"rawtypes","unchecked"})
  private void cacheRootArcs() throws IOException {
    // We should only be called once per FST:
    assert cachedArcsBytesUsed == 0;

    final Arc<T> arc = new Arc<>();
    getFirstArc(arc);
    if (targetHasArcs(arc)) {
      final BytesReader in = getBytesReader();
      Arc<T>[] arcs = (Arc<T>[]) new Arc[0x80];
      readFirstRealTargetArc(arc.target, arc, in);
      int count = 0;
      while(true) {
        assert arc.label != END_LABEL;
        if (arc.label < arcs.length) {
          arcs[arc.label] = new Arc<T>().copyFrom(arc);
        } else {
          break;
        }
        if (arc.isLast()) {
          break;
        }
        readNextRealArc(arc, in);
        count++;
      }

      int cacheRAM = (int) ramBytesUsed(arcs);

      // Don't cache if there are only a few arcs or if the cache would use > 20% RAM of the FST itself:
      if (count >= FIXED_ARRAY_NUM_ARCS_SHALLOW && cacheRAM < ramBytesUsed()/5) {
        cachedRootArcs = arcs;
        cachedArcsBytesUsed = cacheRAM;
      }
    }
  }

  public T getEmptyOutput() {
    return emptyOutput;
  }

  void setEmptyOutput(T v) throws IOException {
    if (emptyOutput != null) {
      emptyOutput = outputs.merge(emptyOutput, v);
    } else {
      emptyOutput = v;
    }
  }

  public void save(DataOutput out) throws IOException {
    if (startNode == -1) {
      throw new IllegalStateException("call finish first");
    }
    if (nodeAddress != null) {
      throw new IllegalStateException("cannot save an FST pre-packed FST; it must first be packed");
    }
    if (packed && !(nodeRefToAddress instanceof PackedInts.Mutable)) {
      throw new IllegalStateException("cannot save a FST which has been loaded from disk ");
    }
    CodecUtil.writeHeader(out, FILE_FORMAT_NAME, VERSION_CURRENT);
    if (packed) {
      out.writeByte((byte) 1);
    } else {
      out.writeByte((byte) 0);
    }
    // TODO: really we should encode this as an arc, arriving
    // to the root node, instead of special casing here:
    if (emptyOutput != null) {
      // Accepts empty string
      out.writeByte((byte) 1);

      // Serialize empty-string output:
      RAMOutputStream ros = new RAMOutputStream();
      outputs.writeFinalOutput(emptyOutput, ros);

      byte[] emptyOutputBytes = new byte[(int) ros.getFilePointer()];
      ros.writeTo(emptyOutputBytes, 0);

      if (!packed) {
        // reverse
        final int stopAt = emptyOutputBytes.length/2;
        int upto = 0;
        while(upto < stopAt) {
          final byte b = emptyOutputBytes[upto];
          emptyOutputBytes[upto] = emptyOutputBytes[emptyOutputBytes.length-upto-1];
          emptyOutputBytes[emptyOutputBytes.length-upto-1] = b;
          upto++;
        }
      }
      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);
    if (packed) {
      ((PackedInts.Mutable) nodeRefToAddress).save(out);
    }
    out.writeVLong(startNode);
    out.writeVLong(nodeCount);
    out.writeVLong(arcCount);
    out.writeVLong(arcWithOutputCount);
    long numBytes = bytes.getPosition();
    out.writeVLong(numBytes);
    bytes.writeTo(out);
  }

  /**
   * Writes an automaton to a file.
   */
  public void save(final Path path) throws IOException {
    try (OutputStream os = new BufferedOutputStream(Files.newOutputStream(path))) {
      save(new OutputStreamDataOutput(os));
    }
  }

  /**
   * Reads an automaton from a file.
   */
  public static <T> FST<T> read(Path path, Outputs<T> outputs) throws IOException {
    try (InputStream is = Files.newInputStream(path)) {
      return new FST<>(new InputStreamDataInput(new BufferedInputStream(is)), outputs);
    }
  }

  private void writeLabel(DataOutput out, int v) throws IOException {
    assert v >= 0: "v=" + v;
    if (inputType == INPUT_TYPE.BYTE1) {
      assert v <= 255: "v=" + v;
      out.writeByte((byte) v);
    } else if (inputType == INPUT_TYPE.BYTE2) {
      assert v <= 65535: "v=" + v;
      out.writeShort((short) v);
    } else {
      out.writeVInt(v);
    }
  }

  /** Reads one BYTE1/2/4 label from the provided {@link DataInput}. */
  public int readLabel(DataInput in) throws IOException {
    final int v;
    if (inputType == INPUT_TYPE.BYTE1) {
      // Unsigned byte:
      v = in.readByte()&0xFF;
    } else if (inputType == INPUT_TYPE.BYTE2) {
      // Unsigned short:
      v = in.readShort()&0xFFFF;
    } else {
      v = in.readVInt();
    }
    return v;
  }

  /** returns true if the node at this address has any
   *  outgoing arcs */
  public static<T> boolean targetHasArcs(Arc<T> arc) {
    return arc.target > 0;
  }

  // serializes new node by appending its bytes to the end
  // of the current byte[]
  long addNode(Builder.UnCompiledNode<T> nodeIn) throws IOException {

    //System.out.println("FST.addNode pos=" + bytes.getPosition() + " numArcs=" + nodeIn.numArcs);
    if (nodeIn.numArcs == 0) {
      if (nodeIn.isFinal) {
        return FINAL_END_NODE;
      } else {
        return NON_FINAL_END_NODE;
      }
    }

    final long startAddress = bytes.getPosition();
    //System.out.println("  startAddr=" + startAddress);

    final boolean doFixedArray = shouldExpand(nodeIn);
    if (doFixedArray) {
      //System.out.println("  fixedArray");
      if (reusedBytesPerArc.length < nodeIn.numArcs) {
        reusedBytesPerArc = new int[ArrayUtil.oversize(nodeIn.numArcs, 1)];
      }
    }

    arcCount += nodeIn.numArcs;

    final int lastArc = nodeIn.numArcs-1;

    long lastArcStart = bytes.getPosition();
    int maxBytesPerArc = 0;
    for(int arcIdx=0;arcIdx<nodeIn.numArcs;arcIdx++) {
      final Builder.Arc<T> arc = nodeIn.arcs[arcIdx];
      final Builder.CompiledNode target = (Builder.CompiledNode) arc.target;
      int flags = 0;
      //System.out.println("  arc " + arcIdx + " label=" + arc.label + " -> target=" + target.node);

      if (arcIdx == lastArc) {
        flags += BIT_LAST_ARC;
      }

      if (lastFrozenNode == target.node && !doFixedArray) {
        // TODO: for better perf (but more RAM used) we
        // could avoid this except when arc is "near" the
        // last arc:
        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.node > 0;

      if (!targetHasArcs) {
        flags += BIT_STOP_NODE;
      } else if (inCounts != null) {
        inCounts.set((int) target.node, inCounts.get((int) target.node) + 1);
      }

      if (arc.output != NO_OUTPUT) {
        flags += BIT_ARC_HAS_OUTPUT;
      }

      bytes.writeByte((byte) flags);
      writeLabel(bytes, arc.label);

      // System.out.println("  write arc: label=" + (char) arc.label + " flags=" + flags + " target=" + target.node + " pos=" + bytes.getPosition() + " output=" + outputs.outputToString(arc.output));

      if (arc.output != NO_OUTPUT) {
        outputs.write(arc.output, bytes);
        //System.out.println("    write output");
        arcWithOutputCount++;
      }

      if (arc.nextFinalOutput != NO_OUTPUT) {
        //System.out.println("    write final output");
        outputs.writeFinalOutput(arc.nextFinalOutput, bytes);
      }

      if (targetHasArcs && (flags & BIT_TARGET_NEXT) == 0) {
        assert target.node > 0;
        //System.out.println("    write target");
        bytes.writeVLong(target.node);
      }

      // just write the arcs "like normal" on first pass,
      // but record how many bytes each one took, and max
      // byte size:
      if (doFixedArray) {
        reusedBytesPerArc[arcIdx] = (int) (bytes.getPosition() - lastArcStart);
        lastArcStart = bytes.getPosition();
        maxBytesPerArc = Math.max(maxBytesPerArc, reusedBytesPerArc[arcIdx]);
        //System.out.println("    bytes=" + reusedBytesPerArc[arcIdx]);
      }
    }

    // TODO: try to avoid wasteful cases: disable doFixedArray in that case
    /*
     *
     * LUCENE-4682: what is a fair heuristic here?
     * It could involve some of these:
     * 1. how "busy" the node is: nodeIn.inputCount relative to frontier[0].inputCount?
     * 2. how much binSearch saves over scan: nodeIn.numArcs
     * 3. waste: numBytes vs numBytesExpanded
     *
     * the one below just looks at #3
    if (doFixedArray) {
      // rough heuristic: make this 1.25 "waste factor" a parameter to the phd ctor????
      int numBytes = lastArcStart - startAddress;
      int numBytesExpanded = maxBytesPerArc * nodeIn.numArcs;
      if (numBytesExpanded > numBytes*1.25) {
        doFixedArray = false;
      }
    }
    */

    if (doFixedArray) {
      final int MAX_HEADER_SIZE = 11; // header(byte) + numArcs(vint) + numBytes(vint)
      assert maxBytesPerArc > 0;
      // 2nd pass just "expands" all arcs to take up a fixed
      // byte size

      //System.out.println("write int @pos=" + (fixedArrayStart-4) + " numArcs=" + nodeIn.numArcs);
      // create the header
      // TODO: clean this up: or just rewind+reuse and deal with it
      byte header[] = new byte[MAX_HEADER_SIZE];
      ByteArrayDataOutput bad = new ByteArrayDataOutput(header);
      // write a "false" first arc:
      bad.writeByte(ARCS_AS_FIXED_ARRAY);
      bad.writeVInt(nodeIn.numArcs);
      bad.writeVInt(maxBytesPerArc);
      int headerLen = bad.getPosition();

      final long fixedArrayStart = startAddress + headerLen;

      // expand the arcs in place, backwards
      long srcPos = bytes.getPosition();
      long destPos = fixedArrayStart + nodeIn.numArcs*maxBytesPerArc;
      assert destPos >= srcPos;
      if (destPos > srcPos) {
        bytes.skipBytes((int) (destPos - srcPos));
        for(int arcIdx=nodeIn.numArcs-1;arcIdx>=0;arcIdx--) {
          destPos -= maxBytesPerArc;
          srcPos -= reusedBytesPerArc[arcIdx];
          //System.out.println("  repack arcIdx=" + arcIdx + " srcPos=" + srcPos + " destPos=" + destPos);
          if (srcPos != destPos) {
            //System.out.println("  copy len=" + reusedBytesPerArc[arcIdx]);
            assert destPos > srcPos: "destPos=" + destPos + " srcPos=" + srcPos + " arcIdx=" + arcIdx + " maxBytesPerArc=" + maxBytesPerArc + " reusedBytesPerArc[arcIdx]=" + reusedBytesPerArc[arcIdx] + " nodeIn.numArcs=" + nodeIn.numArcs;
            bytes.copyBytes(srcPos, destPos, reusedBytesPerArc[arcIdx]);
          }
        }
      }

      // now write the header
      bytes.writeBytes(startAddress, header, 0, headerLen);
    }

    final long thisNodeAddress = bytes.getPosition()-1;

    bytes.reverse(startAddress, thisNodeAddress);

    // PackedInts uses int as the index, so we cannot handle
    // > 2.1B nodes when packing:
    if (nodeAddress != null && nodeCount == Integer.MAX_VALUE) {
      throw new IllegalStateException("cannot create a packed FST with more than 2.1 billion nodes");
    }

    nodeCount++;
    final long node;
    if (nodeAddress != null) {

      // Nodes are addressed by 1+ord:
      if ((int) nodeCount == nodeAddress.size()) {
        nodeAddress = nodeAddress.resize(ArrayUtil.oversize(nodeAddress.size() + 1, nodeAddress.getBitsPerValue()));
        inCounts = inCounts.resize(ArrayUtil.oversize(inCounts.size() + 1, inCounts.getBitsPerValue()));
      }
      nodeAddress.set((int) nodeCount, thisNodeAddress);
      // System.out.println("  write nodeAddress[" + nodeCount + "] = " + endAddress);
      node = nodeCount;
    } else {
      node = thisNodeAddress;
    }
    lastFrozenNode = node;

    //System.out.println("  ret node=" + node + " address=" + thisNodeAddress + " nodeAddress=" + nodeAddress);
    return node;
  }

  /** 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;
      if (emptyOutput != NO_OUTPUT) {
        arc.flags |= BIT_ARC_HAS_FINAL_OUTPUT;
      }
    } 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
    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, BytesReader in) throws IOException {
    //System.out.println("readLast");
    if (!targetHasArcs(follow)) {
      //System.out.println("  end node");
      assert follow.isFinal();
      arc.label = END_LABEL;
      arc.target = FINAL_END_NODE;
      arc.output = follow.nextFinalOutput;
      arc.flags = BIT_LAST_ARC;
      return arc;
    } else {
      in.setPosition(getNodeAddress(follow.target));
      arc.node = follow.target;
      final byte b = in.readByte();
      if (b == ARCS_AS_FIXED_ARRAY) {
        // array: jump straight to end
        arc.numArcs = in.readVInt();
        if (packed || version >= VERSION_VINT_TARGET) {
          arc.bytesPerArc = in.readVInt();
        } else {
          arc.bytesPerArc = in.readInt();
        }
        //System.out.println("  array numArcs=" + arc.numArcs + " bpa=" + arc.bytesPerArc);
        arc.posArcsStart = in.getPosition();
        arc.arcIdx = arc.numArcs - 2;
      } else {
        arc.flags = b;
        // 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.skipOutput(in);
          }
          if (arc.flag(BIT_ARC_HAS_FINAL_OUTPUT)) {
            outputs.skipFinalOutput(in);
          }
          if (arc.flag(BIT_STOP_NODE)) {
          } else if (arc.flag(BIT_TARGET_NEXT)) {
          } else if (packed) {
            in.readVLong();
          } else {
            readUnpackedNodeTarget(in);
          }
          arc.flags = in.readByte();
        }
        // Undo the byte flags we read:
        in.skipBytes(-1);
        arc.nextArc = in.getPosition();
      }
      readNextRealArc(arc, in);
      assert arc.isLast();
      return arc;
    }
  }

  private long readUnpackedNodeTarget(BytesReader in) throws IOException {
    long target;
    if (version < VERSION_VINT_TARGET) {
      target = in.readInt();
    } else {
      target = in.readVLong();
    }
    return target;
  }

  /**
   * 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, BytesReader in) 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;
      arc.flags = BIT_FINAL_ARC;
      if (follow.target <= 0) {
        arc.flags |= BIT_LAST_ARC;
      } else {
        arc.node = follow.target;
        // NOTE: nextArc is a node (not an address!) in this case:
        arc.nextArc = follow.target;
      }
      arc.target = FINAL_END_NODE;
      //System.out.println("    insert isFinal; nextArc=" + follow.target + " isLast=" + arc.isLast() + " output=" + outputs.outputToString(arc.output));
      return arc;
    } else {
      return readFirstRealTargetArc(follow.target, arc, in);
    }
  }

  public Arc<T> readFirstRealTargetArc(long node, Arc<T> arc, final BytesReader in) throws IOException {
    final long address = getNodeAddress(node);
    in.setPosition(address);
    //System.out.println("  readFirstRealTargtArc address="
    //+ address);
    //System.out.println("   flags=" + arc.flags);
    arc.node = node;

    if (in.readByte() == ARCS_AS_FIXED_ARRAY) {
      //System.out.println("  fixedArray");
      // this is first arc in a fixed-array
      arc.numArcs = in.readVInt();
      if (packed || version >= VERSION_VINT_TARGET) {
        arc.bytesPerArc = in.readVInt();
      } else {
        arc.bytesPerArc = in.readInt();
      }
      arc.arcIdx = -1;
      arc.nextArc = arc.posArcsStart = in.getPosition();
      //System.out.println("  bytesPer=" + arc.bytesPerArc + " numArcs=" + arc.numArcs + " arcsStart=" + pos);
    } else {
      //arc.flags = b;
      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, BytesReader in) throws IOException {
    if (!targetHasArcs(follow)) {
      return false;
    } else {
      in.setPosition(getNodeAddress(follow.target));
      return in.readByte() == ARCS_AS_FIXED_ARRAY;
    }
  }

  /** In-place read; returns the arc. */
  public Arc<T> readNextArc(Arc<T> arc, BytesReader in) throws IOException {
    if (arc.label == END_LABEL) {
      // This was a fake inserted "final" arc
      if (arc.nextArc <= 0) {
        throw new IllegalArgumentException("cannot readNextArc when arc.isLast()=true");
      }
      return readFirstRealTargetArc(arc.nextArc, arc, in);
    } else {
      return readNextRealArc(arc, in);
    }
  }

  /** Peeks at next arc's label; does not alter arc.  Do
   *  not call this if arc.isLast()! */
  public int readNextArcLabel(Arc<T> arc, BytesReader in) throws IOException {
    assert !arc.isLast();

    if (arc.label == END_LABEL) {
      //System.out.println("    nextArc fake " +
      //arc.nextArc);

      long pos = getNodeAddress(arc.nextArc);
      in.setPosition(pos);

      final byte b = in.readByte();
      if (b == ARCS_AS_FIXED_ARRAY) {
        //System.out.println("    nextArc fixed array");
        in.readVInt();

        // Skip bytesPerArc:
        if (packed || version >= VERSION_VINT_TARGET) {
          in.readVInt();
        } else {
          in.readInt();
        }
      } else {
        in.setPosition(pos);
      }
    } else {
      if (arc.bytesPerArc != 0) {
        //System.out.println("    nextArc real array");
        // arcs are at fixed entries
        in.setPosition(arc.posArcsStart);
        in.skipBytes((1+arc.arcIdx)*arc.bytesPerArc);
      } else {
        // arcs are packed
        //System.out.println("    nextArc real packed");
        in.setPosition(arc.nextArc);
      }
    }
    // skip flags
    in.readByte();
    return readLabel(in);
  }

  /** Never returns null, but you should never call this if
   *  arc.isLast() is true. */
  public Arc<T> readNextRealArc(Arc<T> arc, final BytesReader in) throws IOException {

    // TODO: can't assert this because we call from readFirstArc
    // assert !flag(arc.flags, BIT_LAST_ARC);

    // 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.setPosition(arc.posArcsStart);
      in.skipBytes(arc.arcIdx*arc.bytesPerArc);
    } else {
      // arcs are packed
      in.setPosition(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.readFinalOutput(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.getPosition();
    } else if (arc.flag(BIT_TARGET_NEXT)) {
      arc.nextArc = in.getPosition();
      // TODO: would be nice to make this lazy -- maybe
      // caller doesn't need the target and is scanning arcs...
      if (nodeAddress == null) {
        if (!arc.flag(BIT_LAST_ARC)) {
          if (arc.bytesPerArc == 0) {
            // must scan
            seekToNextNode(in);
          } else {
            in.setPosition(arc.posArcsStart);
            in.skipBytes(arc.bytesPerArc * arc.numArcs);
          }
        }
        arc.target = in.getPosition();
      } else {
        arc.target = arc.node - 1;
        assert arc.target > 0;
      }
    } else {
      if (packed) {
        final long pos = in.getPosition();
        final long code = in.readVLong();
        if (arc.flag(BIT_TARGET_DELTA)) {
          // Address is delta-coded from current address:
          arc.target = pos + code;
          //System.out.println("    delta pos=" + pos + " delta=" + code + " target=" + arc.target);
        } else if (code < nodeRefToAddress.size()) {
          // Deref
          arc.target = nodeRefToAddress.get((int) code);
          //System.out.println("    deref code=" + code + " target=" + arc.target);
        } else {
          // Absolute
          arc.target = code;
          //System.out.println("    abs code=" + code);
        }
      } else {
        arc.target = readUnpackedNodeTarget(in);
      }
      arc.nextArc = in.getPosition();
    }
    return arc;
  }

  // LUCENE-5152: called only from asserts, to validate that the
  // non-cached arc lookup would produce the same result, to
  // catch callers that illegally modify shared structures with
  // the result (we shallow-clone the Arc itself, but e.g. a BytesRef
  // output is still shared):
  private boolean assertRootCachedArc(int label, Arc<T> cachedArc) throws IOException {
    Arc<T> arc = new Arc<>();
    getFirstArc(arc);
    BytesReader in = getBytesReader();
    Arc<T> result = findTargetArc(label, arc, arc, in, false);
    if (result == null) {
      assert cachedArc == null;
    } else {
      assert cachedArc != null;
      assert cachedArc.arcIdx == result.arcIdx;
      assert cachedArc.bytesPerArc == result.bytesPerArc;
      assert cachedArc.flags == result.flags;
      assert cachedArc.label == result.label;
      assert cachedArc.nextArc == result.nextArc;
      assert cachedArc.nextFinalOutput.equals(result.nextFinalOutput);
      assert cachedArc.node == result.node;
      assert cachedArc.numArcs == result.numArcs;
      assert cachedArc.output.equals(result.output);
      assert cachedArc.posArcsStart == result.posArcsStart;
      assert cachedArc.target == result.target;
    }

    return true;
  }

  // TODO: could we somehow [partially] tableize arc lookups
  // like automaton?

  /** 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, BytesReader in) throws IOException {
    return findTargetArc(labelToMatch, follow, arc, in, true);
  }

  /** 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. */
  private Arc<T> findTargetArc(int labelToMatch, Arc<T> follow, Arc<T> arc, BytesReader in, boolean useRootArcCache) throws IOException {

    if (labelToMatch == END_LABEL) {
      if (follow.isFinal()) {
        if (follow.target <= 0) {
          arc.flags = BIT_LAST_ARC;
        } else {
          arc.flags = 0;
          // NOTE: nextArc is a node (not an address!) in this case:
          arc.nextArc = follow.target;
          arc.node = follow.target;
        }
        arc.output = follow.nextFinalOutput;
        arc.label = END_LABEL;
        return arc;
      } else {
        return null;
      }
    }

    // Short-circuit if this arc is in the root arc cache:
    if (useRootArcCache && cachedRootArcs != null && follow.target == startNode && labelToMatch < cachedRootArcs.length) {
      final Arc<T> result = cachedRootArcs[labelToMatch];

      // LUCENE-5152: detect tricky cases where caller
      // modified previously returned cached root-arcs:
      assert assertRootCachedArc(labelToMatch, result);

      if (result == null) {
        return null;
      } else {
        arc.copyFrom(result);
        return arc;
      }
    }

    if (!targetHasArcs(follow)) {
      return null;
    }

    in.setPosition(getNodeAddress(follow.target));

    arc.node = follow.target;

    // System.out.println("fta label=" + (char) labelToMatch);

    if (in.readByte() == ARCS_AS_FIXED_ARRAY) {
      // Arcs are full array; do binary search:
      arc.numArcs = in.readVInt();
      if (packed || version >= VERSION_VINT_TARGET) {
        arc.bytesPerArc = in.readVInt();
      } else {
        arc.bytesPerArc = in.readInt();
      }
      arc.posArcsStart = in.getPosition();
      int low = 0;
      int high = arc.numArcs-1;
      while (low <= high) {
        //System.out.println("    cycle");
        int mid = (low + high) >>> 1;
        in.setPosition(arc.posArcsStart);
        in.skipBytes(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
    readFirstRealTargetArc(follow.target, arc, in);

    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 {
        readNextRealArc(arc, in);
      }
    }
  }

  private void seekToNextNode(BytesReader in) throws IOException {

    while(true) {

      final int flags = in.readByte();
      readLabel(in);

      if (flag(flags, BIT_ARC_HAS_OUTPUT)) {
        outputs.skipOutput(in);
      }

      if (flag(flags, BIT_ARC_HAS_FINAL_OUTPUT)) {
        outputs.skipFinalOutput(in);
      }

      if (!flag(flags, BIT_STOP_NODE) && !flag(flags, BIT_TARGET_NEXT)) {
        if (packed) {
          in.readVLong();
        } else {
          readUnpackedNodeTarget(in);
        }
      }

      if (flag(flags, BIT_LAST_ARC)) {
        return;
      }
    }
  }

  public long getNodeCount() {
    // 1+ in order to count the -1 implicit final node
    return 1+nodeCount;
  }

  public long getArcCount() {
    return arcCount;
  }

  public long getArcWithOutputCount() {
    return arcWithOutputCount;
  }

  /**
   * Nodes will be expanded if their depth (distance from the root node) is
   * <= this value and their number of arcs is >=
   * {@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 allowArrayArcs &&
      ((node.depth <= FIXED_ARRAY_SHALLOW_DISTANCE && node.numArcs >= FIXED_ARRAY_NUM_ARCS_SHALLOW) ||
       node.numArcs >= FIXED_ARRAY_NUM_ARCS_DEEP);
  }

  /** Returns a {@link BytesReader} for this FST, positioned at
   *  position 0. */
  public BytesReader getBytesReader() {
    BytesReader in;
    if (packed) {
      in = bytes.getForwardReader();
    } else {
      in = bytes.getReverseReader();
    }
    return in;
  }

  /** Reads bytes stored in an FST. */
  public static abstract class BytesReader extends DataInput {
    /** Get current read position. */
    public abstract long getPosition();

    /** Set current read position. */
    public abstract void setPosition(long pos);

    /** Returns true if this reader uses reversed bytes
     *  under-the-hood. */
    public abstract boolean reversed();
  }

  /*
  public void countSingleChains() throws IOException {
    // TODO: must assert this FST was built with
    // "willRewrite"

    final List<ArcAndState<T>> queue = new ArrayList<>();

    // TODO: use bitset to not revisit nodes already
    // visited

    FixedBitSet seen = new FixedBitSet(1+nodeCount);
    int saved = 0;

    queue.add(new ArcAndState<T>(getFirstArc(new Arc<T>()), new IntsRef()));
    Arc<T> scratchArc = new Arc<>();
    while(queue.size() > 0) {
      //System.out.println("cycle size=" + queue.size());
      //for(ArcAndState<T> ent : queue) {
      //  System.out.println("  " + Util.toBytesRef(ent.chain, new BytesRef()));
      //  }
      final ArcAndState<T> arcAndState = queue.get(queue.size()-1);
      seen.set(arcAndState.arc.node);
      final BytesRef br = Util.toBytesRef(arcAndState.chain, new BytesRef());
      if (br.length > 0 && br.bytes[br.length-1] == -1) {
        br.length--;
      }
      //System.out.println("  top node=" + arcAndState.arc.target + " chain=" + br.utf8ToString());
      if (targetHasArcs(arcAndState.arc) && !seen.get(arcAndState.arc.target)) {
        // push
        readFirstTargetArc(arcAndState.arc, scratchArc);
        //System.out.println("  push label=" + (char) scratchArc.label);
        //System.out.println("    tonode=" + scratchArc.target + " last?=" + scratchArc.isLast());

        final IntsRef chain = IntsRef.deepCopyOf(arcAndState.chain);
        chain.grow(1+chain.length);
        // TODO
        //assert scratchArc.label != END_LABEL;
        chain.ints[chain.length] = scratchArc.label;
        chain.length++;

        if (scratchArc.isLast()) {
          if (scratchArc.target != -1 && inCounts[scratchArc.target] == 1) {
            //System.out.println("    append");
          } else {
            if (arcAndState.chain.length > 1) {
              saved += chain.length-2;
              try {
                System.out.println("chain: " + Util.toBytesRef(chain, new BytesRef()).utf8ToString());
              } catch (AssertionError ae) {
                System.out.println("chain: " + Util.toBytesRef(chain, new BytesRef()));
              }
            }
            chain.length = 0;
          }
        } else {
          //System.out.println("    reset");
          if (arcAndState.chain.length > 1) {
            saved += arcAndState.chain.length-2;
            try {
              System.out.println("chain: " + Util.toBytesRef(arcAndState.chain, new BytesRef()).utf8ToString());
            } catch (AssertionError ae) {
              System.out.println("chain: " + Util.toBytesRef(arcAndState.chain, new BytesRef()));
            }
          }
          if (scratchArc.target != -1 && inCounts[scratchArc.target] != 1) {
            chain.length = 0;
          } else {
            chain.ints[0] = scratchArc.label;
            chain.length = 1;
          }
        }
        // TODO: instead of new Arc() we can re-use from
        // a by-depth array
        queue.add(new ArcAndState<T>(new Arc<T>().copyFrom(scratchArc), chain));
      } else if (!arcAndState.arc.isLast()) {
        // next
        readNextArc(arcAndState.arc);
        //System.out.println("  next label=" + (char) arcAndState.arc.label + " len=" + arcAndState.chain.length);
        if (arcAndState.chain.length != 0) {
          arcAndState.chain.ints[arcAndState.chain.length-1] = arcAndState.arc.label;
        }
      } else {
        if (arcAndState.chain.length > 1) {
          saved += arcAndState.chain.length-2;
          System.out.println("chain: " + Util.toBytesRef(arcAndState.chain, new BytesRef()).utf8ToString());
        }
        // pop
        //System.out.println("  pop");
        queue.remove(queue.size()-1);
        while(queue.size() > 0 && queue.get(queue.size()-1).arc.isLast()) {
          queue.remove(queue.size()-1);
        }
        if (queue.size() > 0) {
          final ArcAndState<T> arcAndState2 = queue.get(queue.size()-1);
          readNextArc(arcAndState2.arc);
          //System.out.println("  read next=" + (char) arcAndState2.arc.label + " queue=" + queue.size());
          assert arcAndState2.arc.label != END_LABEL;
          if (arcAndState2.chain.length != 0) {
            arcAndState2.chain.ints[arcAndState2.chain.length-1] = arcAndState2.arc.label;
          }
        }
      }
    }

    System.out.println("TOT saved " + saved);
  }
 */

  // Creates a packed FST
  private FST(INPUT_TYPE inputType, Outputs<T> outputs, int bytesPageBits) {
    version = VERSION_CURRENT;
    packed = true;
    this.inputType = inputType;
    bytes = new BytesStore(bytesPageBits);
    this.outputs = outputs;
    NO_OUTPUT = outputs.getNoOutput();

    // NOTE: bogus because this is only used during
    // building; we need to break out mutable FST from
    // immutable
    allowArrayArcs = false;
  }

  /** Expert: creates an FST by packing this one.  This
   *  process requires substantial additional RAM (currently
   *  up to ~8 bytes per node depending on
   *  <code>acceptableOverheadRatio</code>), but then should
   *  produce a smaller FST.
   *
   *  <p>The implementation of this method uses ideas from
   *  <a target="_blank" href="http://www.cs.put.poznan.pl/dweiss/site/publications/download/fsacomp.pdf">Smaller Representation of Finite State Automata</a>,
   *  which describes techniques to reduce the size of a FST.
   *  However, this is not a strict implementation of the
   *  algorithms described in this paper.
   */
  FST<T> pack(int minInCountDeref, int maxDerefNodes, float acceptableOverheadRatio) throws IOException {

    // NOTE: maxDerefNodes is intentionally int: we cannot
    // support > 2.1B deref nodes

    // TODO: other things to try
    //   - renumber the nodes to get more next / better locality?
    //   - allow multiple input labels on an arc, so
    //     singular chain of inputs can take one arc (on
    //     wikipedia terms this could save another ~6%)
    //   - in the ord case, the output '1' is presumably
    //     very common (after NO_OUTPUT)... maybe use a bit
    //     for it..?
    //   - use spare bits in flags.... for top few labels /
    //     outputs / targets

    if (nodeAddress == null) {
      throw new IllegalArgumentException("this FST was not built with willPackFST=true");
    }

    Arc<T> arc = new Arc<>();

    final BytesReader r = getBytesReader();

    final int topN = Math.min(maxDerefNodes, inCounts.size());

    // Find top nodes with highest number of incoming arcs:
    NodeQueue q = new NodeQueue(topN);

    // TODO: we could use more RAM efficient selection algo here...
    NodeAndInCount bottom = null;
    for(int node=0; node<inCounts.size(); node++) {
      if (inCounts.get(node) >= minInCountDeref) {
        if (bottom == null) {
          q.add(new NodeAndInCount(node, (int) inCounts.get(node)));
          if (q.size() == topN) {
            bottom = q.top();
          }
        } else if (inCounts.get(node) > bottom.count) {
          q.insertWithOverflow(new NodeAndInCount(node, (int) inCounts.get(node)));
        }
      }
    }

    // Free up RAM:
    inCounts = null;

    final Map<Integer,Integer> topNodeMap = new HashMap<>();
    for(int downTo=q.size()-1;downTo>=0;downTo--) {
      NodeAndInCount n = q.pop();
      topNodeMap.put(n.node, downTo);
      //System.out.println("map node=" + n.node + " inCount=" + n.count + " to newID=" + downTo);
    }

    // +1 because node ords start at 1 (0 is reserved as stop node):
    final GrowableWriter newNodeAddress = new GrowableWriter(
                       PackedInts.bitsRequired(this.bytes.getPosition()), (int) (1 + nodeCount), acceptableOverheadRatio);

    // Fill initial coarse guess:
    for(int node=1;node<=nodeCount;node++) {
      newNodeAddress.set(node, 1 + this.bytes.getPosition() - nodeAddress.get(node));
    }

    int absCount;
    int deltaCount;
    int topCount;
    int nextCount;

    FST<T> fst;

    // Iterate until we converge:
    while(true) {

      //System.out.println("\nITER");
      boolean changed = false;

      // for assert:
      boolean negDelta = false;

      fst = new FST<>(inputType, outputs, bytes.getBlockBits());

      final BytesStore writer = fst.bytes;

      // Skip 0 byte since 0 is reserved target:
      writer.writeByte((byte) 0);

      fst.arcWithOutputCount = 0;
      fst.nodeCount = 0;
      fst.arcCount = 0;

      absCount = deltaCount = topCount = nextCount = 0;

      int changedCount = 0;

      long addressError = 0;

      //int totWasted = 0;

      // Since we re-reverse the bytes, we now write the
      // nodes backwards, so that BIT_TARGET_NEXT is
      // unchanged:
      for(int node=(int)nodeCount;node>=1;node--) {
        fst.nodeCount++;
        final long address = writer.getPosition();

        //System.out.println("  node: " + node + " address=" + address);
        if (address != newNodeAddress.get(node)) {
          addressError = address - newNodeAddress.get(node);
          //System.out.println("    change: " + (address - newNodeAddress[node]));
          changed = true;
          newNodeAddress.set(node, address);
          changedCount++;
        }

        int nodeArcCount = 0;
        int bytesPerArc = 0;

        boolean retry = false;

        // for assert:
        boolean anyNegDelta = false;

        // Retry loop: possibly iterate more than once, if
        // this is an array'd node and bytesPerArc changes:
        writeNode:
        while(true) { // retry writing this node

          //System.out.println("  cycle: retry");
          readFirstRealTargetArc(node, arc, r);

          final boolean useArcArray = arc.bytesPerArc != 0;
          if (useArcArray) {
            // Write false first arc:
            if (bytesPerArc == 0) {
              bytesPerArc = arc.bytesPerArc;
            }
            writer.writeByte(ARCS_AS_FIXED_ARRAY);
            writer.writeVInt(arc.numArcs);
            writer.writeVInt(bytesPerArc);
            //System.out.println("node " + node + ": " + arc.numArcs + " arcs");
          }

          int maxBytesPerArc = 0;
          //int wasted = 0;
          while(true) {  // iterate over all arcs for this node
            //System.out.println("    cycle next arc");

            final long arcStartPos = writer.getPosition();
            nodeArcCount++;

            byte flags = 0;

            if (arc.isLast()) {
              flags += BIT_LAST_ARC;
            }
            /*
            if (!useArcArray && nodeUpto < nodes.length-1 && arc.target == nodes[nodeUpto+1]) {
              flags += BIT_TARGET_NEXT;
            }
            */
            if (!useArcArray && node != 1 && arc.target == node-1) {
              flags += BIT_TARGET_NEXT;
              if (!retry) {
                nextCount++;
              }
            }
            if (arc.isFinal()) {
              flags += BIT_FINAL_ARC;
              if (arc.nextFinalOutput != NO_OUTPUT) {
                flags += BIT_ARC_HAS_FINAL_OUTPUT;
              }
            } else {
              assert arc.nextFinalOutput == NO_OUTPUT;
            }
            if (!targetHasArcs(arc)) {
              flags += BIT_STOP_NODE;
            }

            if (arc.output != NO_OUTPUT) {
              flags += BIT_ARC_HAS_OUTPUT;
            }

            final long absPtr;
            final boolean doWriteTarget = targetHasArcs(arc) && (flags & BIT_TARGET_NEXT) == 0;
            if (doWriteTarget) {

              final Integer ptr = topNodeMap.get(arc.target);
              if (ptr != null) {
                absPtr = ptr;
              } else {
                absPtr = topNodeMap.size() + newNodeAddress.get((int) arc.target) + addressError;
              }

              long delta = newNodeAddress.get((int) arc.target) + addressError - writer.getPosition() - 2;
              if (delta < 0) {
                //System.out.println("neg: " + delta);
                anyNegDelta = true;
                delta = 0;
              }

              if (delta < absPtr) {
                flags |= BIT_TARGET_DELTA;
              }
            } else {
              absPtr = 0;
            }

            assert flags != ARCS_AS_FIXED_ARRAY;
            writer.writeByte(flags);

            fst.writeLabel(writer, arc.label);

            if (arc.output != NO_OUTPUT) {
              outputs.write(arc.output, writer);
              if (!retry) {
                fst.arcWithOutputCount++;
              }
            }
            if (arc.nextFinalOutput != NO_OUTPUT) {
              outputs.writeFinalOutput(arc.nextFinalOutput, writer);
            }

            if (doWriteTarget) {

              long delta = newNodeAddress.get((int) arc.target) + addressError - writer.getPosition();
              if (delta < 0) {
                anyNegDelta = true;
                //System.out.println("neg: " + delta);
                delta = 0;
              }

              if (flag(flags, BIT_TARGET_DELTA)) {
                //System.out.println("        delta");
                writer.writeVLong(delta);
                if (!retry) {
                  deltaCount++;
                }
              } else {
                /*
                if (ptr != null) {
                  System.out.println("        deref");
                } else {
                  System.out.println("        abs");
                }
                */
                writer.writeVLong(absPtr);
                if (!retry) {
                  if (absPtr >= topNodeMap.size()) {
                    absCount++;
                  } else {
                    topCount++;
                  }
                }
              }
            }

            if (useArcArray) {
              final int arcBytes = (int) (writer.getPosition() - arcStartPos);
              //System.out.println("  " + arcBytes + " bytes");
              maxBytesPerArc = Math.max(maxBytesPerArc, arcBytes);
              // NOTE: this may in fact go "backwards", if
              // somehow (rarely, possibly never) we use
              // more bytesPerArc in this rewrite than the
              // incoming FST did... but in this case we
              // will retry (below) so it's OK to ovewrite
              // bytes:
              //wasted += bytesPerArc - arcBytes;
              writer.skipBytes((int) (arcStartPos + bytesPerArc - writer.getPosition()));
            }

            if (arc.isLast()) {
              break;
            }

            readNextRealArc(arc, r);
          }

          if (useArcArray) {
            if (maxBytesPerArc == bytesPerArc || (retry && maxBytesPerArc <= bytesPerArc)) {
              // converged
              //System.out.println("  bba=" + bytesPerArc + " wasted=" + wasted);
              //totWasted += wasted;
              break;
            }
          } else {
            break;
          }

          //System.out.println("  retry this node maxBytesPerArc=" + maxBytesPerArc + " vs " + bytesPerArc);

          // Retry:
          bytesPerArc = maxBytesPerArc;
          writer.truncate(address);
          nodeArcCount = 0;
          retry = true;
          anyNegDelta = false;
        }

        negDelta |= anyNegDelta;

        fst.arcCount += nodeArcCount;
      }

      if (!changed) {
        // We don't renumber the nodes (just reverse their
        // order) so nodes should only point forward to
        // other nodes because we only produce acyclic FSTs
        // w/ nodes only pointing "forwards":
        assert !negDelta;
        //System.out.println("TOT wasted=" + totWasted);
        // Converged!
        break;
      }
      //System.out.println("  " + changedCount + " of " + fst.nodeCount + " changed; retry");
    }

    long maxAddress = 0;
    for (long key : topNodeMap.keySet()) {
      maxAddress = Math.max(maxAddress, newNodeAddress.get((int) key));
    }

    PackedInts.Mutable nodeRefToAddressIn = PackedInts.getMutable(topNodeMap.size(),
        PackedInts.bitsRequired(maxAddress), acceptableOverheadRatio);
    for(Map.Entry<Integer,Integer> ent : topNodeMap.entrySet()) {
      nodeRefToAddressIn.set(ent.getValue(), newNodeAddress.get(ent.getKey()));
    }
    fst.nodeRefToAddress = nodeRefToAddressIn;

    fst.startNode = newNodeAddress.get((int) startNode);
    //System.out.println("new startNode=" + fst.startNode + " old startNode=" + startNode);

    if (emptyOutput != null) {
      fst.setEmptyOutput(emptyOutput);
    }

    assert fst.nodeCount == nodeCount: "fst.nodeCount=" + fst.nodeCount + " nodeCount=" + nodeCount;
    assert fst.arcCount == arcCount;
    assert fst.arcWithOutputCount == arcWithOutputCount: "fst.arcWithOutputCount=" + fst.arcWithOutputCount + " arcWithOutputCount=" + arcWithOutputCount;

    fst.bytes.finish();
    fst.cacheRootArcs();

    //final int size = fst.sizeInBytes();
    //System.out.println("nextCount=" + nextCount + " topCount=" + topCount + " deltaCount=" + deltaCount + " absCount=" + absCount);

    return fst;
  }

  private static class NodeAndInCount implements Comparable<NodeAndInCount> {
    final int node;
    final int count;

    public NodeAndInCount(int node, int count) {
      this.node = node;
      this.count = count;
    }

    @Override
    public int compareTo(NodeAndInCount other) {
      if (count > other.count) {
        return 1;
      } else if (count < other.count) {
        return -1;
      } else {
        // Tie-break: smaller node compares as greater than
        return other.node - node;
      }
    }
  }

  private static class NodeQueue extends PriorityQueue<NodeAndInCount> {
    public NodeQueue(int topN) {
      super(topN, false);
    }

    @Override
    public boolean lessThan(NodeAndInCount a, NodeAndInCount b) {
      final int cmp = a.compareTo(b);
      assert cmp != 0;
      return cmp < 0;
    }
  }
}


text:
<!DOCTYPE html>

  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
  <title>The source code</title>
  <link href="../resources/prettify/prettify.css" type="text/css" rel="stylesheet" />

/**
 * Layout class for {@link Ext.form.field.ComboBox} fields. Handles sizing the input field.
 * @private
 */
Ext.define('Ext.layout.component.field.ComboBox', {
    extend: 'Ext.layout.component.field.Trigger',
    alias: 'layout.combobox',
    requires: ['Ext.util.TextMetrics'],

    type: 'combobox',

    startingWidth: null,

    getTextWidth: function () {
        var me = this,
            owner = me.owner,
            store = owner.store,
            field = owner.displayField,
            storeLn = store.data.length,
            value = '',
            i = 0, n = 0, ln, item, width;

        for (; i < storeLn; i++) {
            item = store.getAt(i).data[field];
            ln = item.length;
            // compare the current item's length with the current longest length and store the value
            if (ln > n) {
                n = ln;
                value = item;
            }
        }

        width = Math.max(me.callParent(arguments), owner.inputEl.getTextWidth(value + owner.growAppend));

        // it's important to know the starting width else the inputEl could be resized smaller than the boundlist
        // NOTE that when removing items from the store that the startingWidth needs to be recalculated
        if (!me.startingWidth || owner.removingRecords) {
            me.startingWidth = width;

            // also, if the width is less than growMin reset the default boundlist width
            // or it will appear wider than the component if the trigger is clicked
            if (width < owner.growMin) {
                owner.defaultListConfig.minWidth = owner.growMin;
            }

            owner.removingRecords = false;
        }

        // only resize if the new width is greater than the starting width
        return (width < me.startingWidth) ? me.startingWidth : width;
    }
});

redpajama_set_name: RedPajamaGithub


text:
package com.morzeux.bioseclogger.logic;

import java.io.File;
import java.io.IOException;

import android.content.Context;
import android.os.Environment;
import android.util.Log;
import biosecLogger.core.StorageHandler;
import biosecLogger.core.UserLoggerManager;

/**
 * Extends StorageHandler from biosecLogger.core to be usable in different
 * packages. I do not want to have original StorageHandler as public.
 *
 * @author Stefan Smihla
 * @see StorageHandler class
 */
public class ExtendedStorageHandler extends StorageHandler {

	/**
	 * Save file to storage.
	 *
	 * @param filename
	 *            new file name
	 * @param content
	 *            content of file
	 * @param ctx
	 *            if activity context is set, file is saved to internal storage,
	 *            otherwise to external storage
	 * @param b64encode
	 *            if true, content of file is base64 encoded
	 * @return true if file is saved
	 * @throws IOException
	 *             raises when file could not be saved
	 */
	public static boolean saveFile(String filename, String content,
			Context ctx, boolean b64encode) {
		try {
			return StorageHandler.saveFile(filename, content, ctx, b64encode);
		} catch (IOException e) {
			Log.e(UserLoggerManager.LOGNAME, e.getMessage(), e);
			return false;
		}
	}

	/**
	 * Checks if file exists.
	 *
	 * @param path
	 *            path to file
	 * @return true if exists else false
	 */
	public static Boolean checkFile(String path) {
		return new File(getExternalPath(path)).exists() ? true : false;
	}

	/**
	 * Returns absolute path to provided file or directory name.
	 *
	 * @param fileName
	 *            name of file or directory
	 * @return absolute path to file or directory
	 */
	public static final String getExternalPath(String fileName) {
		return Environment.getExternalStorageDirectory().toString() + "/"
				+ fileName;
	}
}


text:
/*!
** @file LED_DOWN.h
** @version 01.03
** @brief
**         The HAL BitIO component provides a low level API for unified
**         access to general purpose digital input/output pins across
**         various device designs.
**
**         RTOS drivers using HAL BitIO API are simpler and more
**         portable to various microprocessors.
*/
/*!
**  @addtogroup LED_DOWN_module LED_DOWN module documentation
**  @{
*/

#ifndef __LED_DOWN_H
#define __LED_DOWN_H

/* MODULE LED_DOWN. */

/* Include shared modules, which are used for whole project */
#include "PE_Types.h"
#include "PE_Error.h"
#include "PE_Const.h"
#include "IO_Map.h"
/* Include inherited beans */
#include "IO_Map.h"
#include "GPIO_PDD.h"

#include "Cpu.h"

#ifdef __cplusplus
extern "C" {
#endif

/*! Peripheral base address of a device allocated by the component. This constant can be used directly in PDD macros. */
#define LED_DOWN_PRPH_BASE_ADDRESS  0x400FF0C0U

/*! Device data structure pointer used when auto initialization property is enabled. This constant can be passed as a first parameter to all component's methods. */
#define LED_DOWN_DeviceData  ((LDD_TDeviceData *)PE_LDD_GetDeviceStructure(PE_LDD_COMPONENT_LED_DOWN_ID))

/* Methods configuration constants - generated for all enabled component's methods */
#define LED_DOWN_Init_METHOD_ENABLED   /*!< Init method of the component LED_DOWN is enabled (generated) */
#define LED_DOWN_GetVal_METHOD_ENABLED /*!< GetVal method of the component LED_DOWN is enabled (generated) */
#define LED_DOWN_PutVal_METHOD_ENABLED /*!< PutVal method of the component LED_DOWN is enabled (generated) */
#define LED_DOWN_ClrVal_METHOD_ENABLED /*!< ClrVal method of the component LED_DOWN is enabled (generated) */
#define LED_DOWN_SetVal_METHOD_ENABLED /*!< SetVal method of the component LED_DOWN is enabled (generated) */

/* Definition of implementation constants */
#define LED_DOWN_MODULE_BASE_ADDRESS PTD_BASE_PTR /*!< Name of macro used as the base address */
#define LED_DOWN_PORTCONTROL_BASE_ADDRESS PORTD_BASE_PTR /*!< Name of macro used as the base address */
#define LED_DOWN_PORT_MASK 0x80U       /*!< Mask of the allocated pin from the port */

/*
** ===================================================================
**     Method      :  LED_DOWN_Init (component BitIO_LDD)
*/
/*!
**     @brief
**         Initializes the device. Allocates memory for the device data
**         structure, allocates interrupt vectors and sets interrupt
**         priority, sets pin routing, sets timing, etc. If the "Enable
**         in init. code" is set to "yes" value then the device is also
**         enabled(see the description of the Enable() method). In this
**         case the Enable() method is not necessary and needn't to be
**         generated.
**     @param
**         UserDataPtr     - Pointer to the user or
**                           RTOS specific data. This pointer will be
**                           passed as an event or callback parameter.
**     @return
**                         - Pointer to the dynamically allocated private
**                           structure or NULL if there was an error.
*/
/* ===================================================================*/
LDD_TDeviceData* LED_DOWN_Init(LDD_TUserData *UserDataPtr);

/*
** ===================================================================
**     Method      :  LED_DOWN_GetVal (component BitIO_LDD)
*/
/*!
**     @brief
**         Returns the input/output value. If the direction is [input]
**         then the input value of the pin is read and returned. If the
**         direction is [output] then the last written value is read
**         and returned (see <Safe mode> property for limitations).
**         This method cannot be disabled if direction is [input].
**     @param
**         DeviceDataPtr   - Device data structure
**                           pointer returned by <Init> method.
**     @return
**                         - Input or output value. Possible values:
**                           <false> - logical "0" (Low level)
**                           <true> - logical "1" (High level)
*/
/* ===================================================================*/
bool LED_DOWN_GetVal(LDD_TDeviceData *DeviceDataPtr);

/*
** ===================================================================
**     Method      :  LED_DOWN_PutVal (component BitIO_LDD)
*/
/*!
**     @brief
**         The specified output value is set. If the direction is
**         input, the component saves the value to a memory or a
**         register and this value will be written to the pin after
**         switching to the output mode (using <tt>SetDir(TRUE)</tt>;
**         see Safe mode
**         property for limitations). If the direction is output,
**         it writes the value to the pin. (Method is available only if
**         the direction = <tt>output</tt> or <tt>
**         input/output</tt>).
**     @param
**         DeviceDataPtr   - Device data structure
**                           pointer returned by <Init> method.
**     @param
**         Val             - Output value. Possible values:
**                           <false> - logical "0" (Low level)
**                           <true> - logical "1" (High level)
*/
/* ===================================================================*/
void LED_DOWN_PutVal(LDD_TDeviceData *DeviceDataPtr, bool Val);

/*
** ===================================================================
**     Method      :  LED_DOWN_ClrVal (component BitIO_LDD)
*/
/*!
**     @brief
**         Clears (set to zero) the output value. It is equivalent to
**         the [PutVal(FALSE)]. This method is available only if the
**         direction = _[output]_ or _[input/output]_.
**     @param
**         DeviceDataPtr   - Pointer to device data
**                           structure returned by <Init> method.
*/
/* ===================================================================*/
void LED_DOWN_ClrVal(LDD_TDeviceData *DeviceDataPtr);

/*
** ===================================================================
**     Method      :  LED_DOWN_SetVal (component BitIO_LDD)
*/
/*!
**     @brief
**         Sets (to one) the output value. It is equivalent to the
**         [PutVal(TRUE)]. This method is available only if the
**         direction = _[output]_ or _[input/output]_.
**     @param
**         DeviceDataPtr   - Pointer to device data
**                           structure returned by <Init> method.
*/
/* ===================================================================*/
void LED_DOWN_SetVal(LDD_TDeviceData *DeviceDataPtr);

/* END LED_DOWN. */

#ifdef __cplusplus
}  /* extern "C" */
#endif

#endif
/* ifndef __LED_DOWN_H */
/*!
** @}
*/
/*
** ###################################################################
**
**     This file was created by Processor Expert 10.5 [05.21]
**     for the Freescale Kinetis series of microcontrollers.
**
** ###################################################################
*/


text:
<?xml version="1.0" encoding="utf-8"?>
<ScrollView xmlns:android="http://schemas.android.com/apk/res/android"
    android:id="@+id/mainScrollView"
    android:layout_width="match_parent"
    android:layout_height="wrap_content" >

    <LinearLayout
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        android:layout_margin="20dp"
        android:orientation="vertical" >

        <TextView
            android:id="@+id/textView1"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:text="@string/popview_name"
            android:textColor="@color/gray"
            android:textSize="16sp"/>
    </LinearLayout>

</ScrollView>


text:
#ifndef WF_CUBE_SIMPLE_BACKGROUND_HPP
#define WF_CUBE_SIMPLE_BACKGROUND_HPP

#include "cube-background.hpp"

class wf_cube_simple_background : public wf_cube_background_base
{
    wf::option_wrapper_t<wf::color_t> background_color{"cube/background"};

  public:
    wf_cube_simple_background();
    virtual void render_frame(const wf::framebuffer_t& fb,
        wf_cube_animation_attribs& attribs) override;
};

#endif /* end of include guard: WF_CUBE_SIMPLE_BACKGROUND_HPP */


text:
module.exports = {
	root: true,
	plugins: ["node"],
	extends: ["../.eslintrc.js", "plugin:node/recommended"],
	env: {
		node: true,
		es6: true,
		jest: true
	},
	parserOptions: { ecmaVersion: 2017, sourceType: "module" },
	rules: {
		"node/no-unsupported-features": ["error", { version: 6 }],
		"node/no-deprecated-api": "error",
		"node/no-missing-import": "error",
		"node/no-missing-require": [
			"error",
			{
				resolvePaths: ["./packages"],
				allowModules: [
					"webpack",
					"@webpack-cli/generators",
					"@webpack-cli/init",
					"@webpack-cli/migrate",
					"@webpack-cli/utils",
					"@webpack-cli/generate-loader",
					"@webpack-cli/generate-plugin",
					"@webpack-cli/webpack-scaffold"
				]
			}
		],
		"node/no-unpublished-bin": "error",
		"node/no-unpublished-require": [
			"error",
			{
				allowModules: [
					"webpack",
					"webpack-dev-server",
					"@webpack-cli/generators",
					"@webpack-cli/init",
					"@webpack-cli/migrate",
					"@webpack-cli/utils",
					"@webpack-cli/generate-loader",
					"@webpack-cli/generate-plugin",
					"@webpack-cli/webpack-scaffold"
				]
			}
		],
		"node/no-extraneous-require": [
			"error",
			{
				allowModules: [
					"@webpack-cli/migrate",
					"@webpack-cli/generators",
					"@webpack-cli/utils",
					"@webpack-cli/generate-loader",
					"@webpack-cli/generate-plugin",
					"@webpack-cli/webpack-scaffold"
				]
			}
		],
		"node/process-exit-as-throw": "error"
	}
};


text:
import sys
_b=sys.version_info[0]<3 and (lambda x:x) or (lambda x:x.encode('latin1'))
from google.protobuf.internal import enum_type_wrapper
from google.protobuf import descriptor as _descriptor
from google.protobuf import message as _message
from google.protobuf import reflection as _reflection
from google.protobuf import symbol_database as _symbol_database
from google.protobuf import descriptor_pb2
# @@protoc_insertion_point(imports)

_sym_db = _symbol_database.Default()

DESCRIPTOR = _descriptor.FileDescriptor(
  name='POGOProtos/Networking/Platform/PlatformRequestType.proto',
  package='POGOProtos.Networking.Platform',
  syntax='proto3',
  serialized_pb=_b('\n:POGOProtos/Networking/Platform/PlatformRequestType.proto\x12\x1ePOGOProtos.Networking.Platform*\xaa\x01\n\x13PlatformRequestType\x12\x10\n\x0cMETHOD_UNSET\x10\x00\x12\x16\n\x12\x42UY_ITEM_POKECOINS\x10\x02\x12\x14\n\x10\x42UY_ITEM_ANDROID\x10\x03\x12\x10\n\x0c\x42UY_ITEM_IOS\x10\x04\x12\x13\n\x0fGET_STORE_ITEMS\x10\x05\x12\x1c\n\x18SEND_ENCRYPTED_SIGNATURE\x10\x06\x12\x0e\n\nPLAT_EIGHT\x10\x08\x62\x06proto3')
)
_sym_db.RegisterFileDescriptor(DESCRIPTOR)

_PLATFORMREQUESTTYPE = _descriptor.EnumDescriptor(
  name='PlatformRequestType',
  full_name='POGOProtos.Networking.Platform.PlatformRequestType',
  filename=None,
  file=DESCRIPTOR,
  values=[
    _descriptor.EnumValueDescriptor(
      name='METHOD_UNSET', index=0, number=0,
      options=None,
      type=None),
    _descriptor.EnumValueDescriptor(
      name='BUY_ITEM_POKECOINS', index=1, number=2,
      options=None,
      type=None),
    _descriptor.EnumValueDescriptor(
      name='BUY_ITEM_ANDROID', index=2, number=3,
      options=None,
      type=None),
    _descriptor.EnumValueDescriptor(
      name='BUY_ITEM_IOS', index=3, number=4,
      options=None,
      type=None),
    _descriptor.EnumValueDescriptor(
      name='GET_STORE_ITEMS', index=4, number=5,
      options=None,
      type=None),
    _descriptor.EnumValueDescriptor(
      name='SEND_ENCRYPTED_SIGNATURE', index=5, number=6,
      options=None,
      type=None),
    _descriptor.EnumValueDescriptor(
      name='PLAT_EIGHT', index=6, number=8,
      options=None,
      type=None),
  ],
  containing_type=None,
  options=None,
  serialized_start=93,
  serialized_end=247,
)
_sym_db.RegisterEnumDescriptor(_PLATFORMREQUESTTYPE)

PlatformRequestType = enum_type_wrapper.EnumTypeWrapper(_PLATFORMREQUESTTYPE)
METHOD_UNSET = 0
BUY_ITEM_POKECOINS = 2
BUY_ITEM_ANDROID = 3
BUY_ITEM_IOS = 4
GET_STORE_ITEMS = 5
SEND_ENCRYPTED_SIGNATURE = 6

DESCRIPTOR.enum_types_by_name['PlatformRequestType'] = _PLATFORMREQUESTTYPE

# @@protoc_insertion_point(module_scope)


text:
import { BypassPipe } from './bypass.pipe';
import { BypassService } from './bypass.service';

describe('BypassPipe', () => {

    let pipe: BypassPipe;

    const value = '
bob
';
    let bypass: BypassService;

    beforeEach(() => {

        bypass = jasmine.createSpyObj<BypassService>('BypassService', ['map']);

        pipe = new BypassPipe(bypass);
    });

    it('create an instance', () => {
        expect(pipe).toBeTruthy();
    });

    it('should call map', () => {
        pipe.transform(value);
        expect(bypass.map).toHaveBeenCalledWith(value, undefined);
    });
});


text:
#pragma once
#include <aws/ram/RAM_EXPORTS.h>
#include <aws/ram/RAMRequest.h>
#include <aws/core/utils/memory/stl/AWSString.h>
#include <utility>

namespace Aws
{
namespace RAM
{
namespace Model
{

  /**
   */
  class AWS_RAM_API RejectResourceShareInvitationRequest : public RAMRequest
  {
  public:
    RejectResourceShareInvitationRequest();

    // Service request name is the Operation name which will send this request out,
    // each operation should has unique request name, so that we can get operation's name from this request.
    // Note: this is not true for response, multiple operations may have the same response name,
    // so we can not get operation's name from response.
    inline virtual const char* GetServiceRequestName() const override { return "RejectResourceShareInvitation"; }

    Aws::String SerializePayload() const override;

    /**
     *
The Amazon Resource Name (ARN) of the invitation.

     */
    inline const Aws::String& GetResourceShareInvitationArn() const{ return m_resourceShareInvitationArn; }

    /**
     *
The Amazon Resource Name (ARN) of the invitation.

     */
    inline bool ResourceShareInvitationArnHasBeenSet() const { return m_resourceShareInvitationArnHasBeenSet; }

    /**
     *
The Amazon Resource Name (ARN) of the invitation.

     */
    inline void SetResourceShareInvitationArn(const Aws::String& value) { m_resourceShareInvitationArnHasBeenSet = true; m_resourceShareInvitationArn = value; }

    /**
     *
The Amazon Resource Name (ARN) of the invitation.

     */
    inline void SetResourceShareInvitationArn(Aws::String&& value) { m_resourceShareInvitationArnHasBeenSet = true; m_resourceShareInvitationArn = std::move(value); }

    /**
     *
The Amazon Resource Name (ARN) of the invitation.

     */
    inline void SetResourceShareInvitationArn(const char* value) { m_resourceShareInvitationArnHasBeenSet = true; m_resourceShareInvitationArn.assign(value); }

    /**
     *
The Amazon Resource Name (ARN) of the invitation.

     */
    inline RejectResourceShareInvitationRequest& WithResourceShareInvitationArn(const Aws::String& value) { SetResourceShareInvitationArn(value); return *this;}

    /**
     *
The Amazon Resource Name (ARN) of the invitation.

     */
    inline RejectResourceShareInvitationRequest& WithResourceShareInvitationArn(Aws::String&& value) { SetResourceShareInvitationArn(std::move(value)); return *this;}

    /**
     *
The Amazon Resource Name (ARN) of the invitation.

     */
    inline RejectResourceShareInvitationRequest& WithResourceShareInvitationArn(const char* value) { SetResourceShareInvitationArn(value); return *this;}

    /**
     *
A unique, case-sensitive identifier that you provide to ensure the
     * idempotency of the request.

     */
    inline const Aws::String& GetClientToken() const{ return m_clientToken; }

    /**
     *
A unique, case-sensitive identifier that you provide to ensure the
     * idempotency of the request.

     */
    inline bool ClientTokenHasBeenSet() const { return m_clientTokenHasBeenSet; }

    /**
     *
A unique, case-sensitive identifier that you provide to ensure the
     * idempotency of the request.

     */
    inline void SetClientToken(const Aws::String& value) { m_clientTokenHasBeenSet = true; m_clientToken = value; }

    /**
     *
A unique, case-sensitive identifier that you provide to ensure the
     * idempotency of the request.

     */
    inline void SetClientToken(Aws::String&& value) { m_clientTokenHasBeenSet = true; m_clientToken = std::move(value); }

    /**
     *
A unique, case-sensitive identifier that you provide to ensure the
     * idempotency of the request.

     */
    inline void SetClientToken(const char* value) { m_clientTokenHasBeenSet = true; m_clientToken.assign(value); }

    /**
     *
A unique, case-sensitive identifier that you provide to ensure the
     * idempotency of the request.

     */
    inline RejectResourceShareInvitationRequest& WithClientToken(const Aws::String& value) { SetClientToken(value); return *this;}

    /**
     *
A unique, case-sensitive identifier that you provide to ensure the
     * idempotency of the request.

     */
    inline RejectResourceShareInvitationRequest& WithClientToken(Aws::String&& value) { SetClientToken(std::move(value)); return *this;}

    /**
     *
A unique, case-sensitive identifier that you provide to ensure the
     * idempotency of the request.

     */
    inline RejectResourceShareInvitationRequest& WithClientToken(const char* value) { SetClientToken(value); return *this;}

  private:

    Aws::String m_resourceShareInvitationArn;
    bool m_resourceShareInvitationArnHasBeenSet;

    Aws::String m_clientToken;
    bool m_clientTokenHasBeenSet;
  };

} // namespace Model
} // namespace RAM
} // namespace Aws


text:
const triggerMap = {
  // www.artinstitutes.edu
  'artinstitutes': 'optimizely.story',
  // www.southuniversity.edu, visit.southuniversity.edu
  'southuniversity': 'optimizely.story',
  // www.bludot.com
  'bludot': 'ch.event',
};

const sites = Object.keys(triggerMap);

export default function getTrigger() {
  const host = window.location.hostname;

  for (let i = 0; i < sites.length; i++) {
    const site = sites[i];
    if ((new RegExp(site)).test(host)) return triggerMap[site];
  }

  return 'clearhead.goal';
}


text:
/**
 *
 */
package org.connectbot.keyboard;

import org.connectbot.service.TerminalKeyListener;

import android.view.KeyEvent;
import android.view.View;

/**
 * @author James
 *
 */
public interface IKeyboard {
	/**
	 * Receives a key press and sends it to the SSH session.
	 * @param listener The terminal key listener than owns this keyboard.
	 * @param v The view the key press occurred in.
	 * @param keyCode The key code that was pressed.
	 * @param event The key event information.
	 * @return Whether the key press was handled.
	 */
	public boolean onKey(TerminalKeyListener listener, View v, int keyCode, KeyEvent event);

	/**
	 * Returns whether or not this keyboard permits the on-screen
	 * touch display to appear.
	 * @return Whether the on-screen touch display should appear.
	 */
	public boolean permitsTouch();
}


text:
import logging
from urllib import urlencode
import json
from dateutil import parser
from datetime import datetime

from google.appengine.ext.deferred import deferred  # pylint: disable=no-name-in-module, import-error
from google.appengine.ext import ndb  # pylint: disable=no-name-in-module, import-error
from google.appengine.api import urlfetch  # pylint: disable=no-name-in-module, import-error

from Square import Order
from Config import get_config

def rec():
    # Get list of entities from Datastore and post to task queue
    query = Order.query(ancestor=ndb.Key('Orders', 'Orders'))
    if query.count() > 0:
        orders = query.fetch()
        for o in orders:
            deferred.defer(process_entity, o)
    else:
        raise Exception('No orders found')

    return 'OK'

def process_entity(order):
    msg = 'Processing order {} for {}'.format(
        order.created_at.date(), order.email)
    logging.info(msg)
    config = get_config()

    # Lookup user by email or create
    id = None
    try:
        id = get_crm_id_from_email(config, order)
        logging.info('Found user ID {} from CiviCRM'.format(id))
    except Exception:
        logging.info(
            'User ID not found in CiviCRM for {}, creating'.format(order.email))
        status, id = create_id_from_order(config, order)
        if not status:
            logging.info("Insufficient user info provided in order, skipping")
            return 'OK'

        logging.info('Created ID {}'.format(id))

    # Only compare memberships if order contains a membership type
    membership_type = False
    for l in order.order.line_items:
        if 'Membership' in l.name:
            membership_type = True

    if membership_type:
        # Get user memberships
        memberships = get_crm_memberships(config, id)

        # Compare
        match = False
        for m in memberships:
            # compare join_date with order.created_at
            logging.info('Looking at membership {}'.format(m['join_date']))
            join_date = parser.parse(m['join_date']).date()
            if join_date == order.created_at.date():
                logging.info('Order {} found in CiviCRM'.format(
                    order.created_at.date()))
                match = True

        # Create if necessary
        if match == False:
            logging.info(
                'Order was not found in CiviCRM, persisting membership')
            for item in order.order.line_items:
                logging.info(
                    'About to create membership of type {}'.format(item.name))
                create_membership(config, item.name, id, order.created_at)

    return 'OK'

def get_crm_id_from_email(config, order):
    res = generic_civicrm_call(config, 'Email', 'get', {
        'sequential': 1,
        'return': 'contact_id',
        'email': order.email
    })
    if 'id' in res:
        return res['id']
    else:
        raise Exception('Email not found in CiviCRM')

def create_id_from_order(config, order):
    # Ensure one identifying field is populated
    if not (order.first_name or order.last_name or order.email):
        return False, None

    # Handle two different models for street address
    street_address = ""
    if order.address:
        street_address = order.address

    if (order.address1 and order.address2):
        street_address = ', '.join([order.address1, order.address2])

    res = generic_civicrm_call(config, 'Contact', 'create', {
        'contact_type': 'Individual',
        'first_name': order.first_name,
        'last_name': order.last_name,
        'email': order.email,
        'phone': order.phone,
        'current_employer': order.employer,
        'job_title': order.occupation,
        'street_address': street_address,
        'city': order.towncity,
        'state_province': order.state,
        'postal_code': order.zip,
        'source': 'hkdems-shop online store'
    })
    if 'id' in res:
        return True, res['id']
    else:
        raise Exception(
            'Failed trying to create ID for {}'.format(order.email))

def get_crm_memberships(config, id):
    logging.info('About to get_crm_memberships for id {}'.format(id))
    res = generic_civicrm_call(config, 'Membership', 'get', {
        'sequential': 1,
        'return': 'join_date,start_date,end_date,id,membership_type_id',
        'contact_id': id
    })
    if 'values' in res:
        return res['values']
    else:
        return []

def create_membership(config, membership_type, contact_id, order_date):
    # If purchased after November 1, accrue to following year
    start_date = order_date
    if (start_date.month >= 11):
        start_date = datetime(start_date.year + 1, 2, 1)

    if (start_date.month == 1):
        start_date = datetime(start_date.year, 2, 1)

    res = generic_civicrm_call(config, 'Membership', 'create', {
        'membership_type_id': membership_type,
        'contact_id': contact_id,
        'source': 'hkdems-shop online store',
        'join_date': order_date.date().isoformat(),
        'start_date': start_date.date().isoformat(),
        'status_id': 'New',
        'is_override': 1,
        'status_override_end_date': start_date.date().isoformat()
    })
    if res['is_error']:
        raise Exception('Failed to create new membership: {}'.format(res))

def generic_civicrm_call(config, entity, action, blob):
    params = {
        'entity': entity,
        'action': action,
        'api_key': config.civicrm_api_key,
        'key': config.civicrm_site_key,
        'json': json.dumps(blob)
    }
    url = config.civicrm_base_url + '?' + urlencode(params)
    method = urlfetch.POST if action == 'create' else urlfetch.GET
    result = urlfetch.fetch(
        url=url,
        method=method)
    logging.info('Received response from CiviCRM: {}'.format(result.content))
    if (result.status_code == 200):
        return json.loads(result.content)
    else:
        raise Exception('CiviCRM call failed')


text:
#!/usr/bin/env node

var fs = require('fs');
var path = require('path');
var browserify = require('browserify');
var through = require('through');
var _ = require('underscore');
var uglify = require('uglify-js');
var bundleTransform = require('./bundle-transform');
var bundleHelpers = require('./bundle-helpers');

var version = JSON.parse(fs.readFileSync('package.json')).version;
var licenseHeader = [
  '// AWS SDK for JavaScript v' + version,
  '// ' + fs.readFileSync(bundleHelpers.mainFile).toString().
          match(/(Copyright\s+.+?Amazon.+?)\n/)[1],
  '// License at https://sdk.amazonaws.com/js/BUNDLE_LICENSE.txt'
].join('\n') + '\n';

function defaultOptions() {
  return {
    minify: false,
    minifyOptions: { compress: false },
    stream: process.stdout
  };
}

function minifyStream(options) {
  options = options || {};
  options.fromString = true;
  var buffer = [];

  function write(data) { buffer.push(data); }
  function end() {
    var min = uglify.minify(buffer.join(''), options);
    this.queue(licenseHeader); // put license back
    this.queue(min.code);
    this.queue(null);
    buffer = null;
  }

  return through(write, end);
}

function stripCommentStream() {
  var buffer = [];

  function write(data) { buffer.push(data); }
  function end() {
    var lines = buffer.join('').split(/\r?\n/);
    var multiLine = false;
    lines = lines.map(function (line) {
      rLine = line;
      if (line.match(/^\s*\/\//)) {
        rLine = null;
      } else if (line.match(/^\s*\/\*/)) {
        multiLine = true;
        rLine = null;
      }

      if (multiLine) {
        var multiLineEnd = line.match(/\*\/(.*)/);
        if (multiLineEnd) {
          multiLine = false;
          rLine = multiLineEnd[1];
        } else {
          rLine = null;
        }
      }

      return rLine;
    }).filter(function(l) { return l != null; });
    var code = lines.join('\n');
    code = code.replace(/\/\*\*[\s\S]+?Copyright\s+.+?Amazon[\s\S]+?\*\//g, '');
    this.queue(licenseHeader); // put license back
    this.queue(code);
    this.queue(null);
    buffer = null;
  }

  return through(write, end);
}

function build(services, options, callback) {
  options = _.defaults(options || {}, defaultOptions());

  bundleTransform(services, true, function (err, transform) {
    if (err) {
      if (callback) return callback(err);
      else throw err;
    }

    var stream = browserify(bundleHelpers.mainFile).
                 transform(transform).
                 ignore('domain').
                 bundle();
    var b = stream;

    if (options.minify) {
      var newStream = minifyStream(options.minifyOptions);
      stream.on('error', newStream.emit.bind(newStream, 'error'));
      stream = stream.pipe(newStream);
    } else {
      var newStream = stripCommentStream();
      stream.on('error', newStream.emit.bind(newStream, 'error'));
      stream = stream.pipe(newStream);
    }
    if (options.stream) {
      stream.on('error', options.stream.emit.bind(options.stream, 'error'));
      stream = stream.pipe(options.stream);
    }

    if (callback) callback(err, stream);
  });
}

module.exports = build;

// run if we called this tool directly
if (require.main === module) {
  var options = { minify: process.env.MINIFY ? true : false };
  module.exports(process.argv[2] || process.env.SERVICES, options);
}


text:
package concurrency.thread;

import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class WaitNotify {

	// 对象监视器锁
	private static Object lock = new Object();

	static final int size = 6;
	private static Queue<Integer> queue = new ArrayBlockingQueue<Integer>(size);

	private static int producerCount=1;

	public static void main(String[] args){
		Consumer consumer = new Consumer();
		Producer producer = new Producer();
		Thread cThread = new Thread(consumer, "consumer");
		Thread pThread = new Thread(producer, "producer1");
		Thread p2Thread = new Thread(producer, "producer2");

		cThread.start();
		p2Thread.start();
		pThread.start();
	}

	static class Consumer implements Runnable {
		public void run() {
			while(true){
				try {
					Thread.sleep(10);
					synchronized (lock) {
						//循环条件等待
						while (queue.isEmpty()) {
							//条件不满足释放锁,挂起阻塞?
							//直到有线程在同一个监视器锁对象上发起notify才会唤醒,但是唤醒的线程需要再次获取这个对象监视器锁
							//此时此线程没有运行了
							System.out.println("empty ,call wait " +Thread.currentThread().getName());
							lock.wait();
							System.out.println("notified:  "+Thread.currentThread().getName());
						}
						//
						Integer i = queue.poll();
						//不知道谁会获取到锁,所以只能全部唤醒
						lock.notifyAll();
						System.out.println("get "+i.intValue());
					}
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
		}
	}

	static class Producer implements Runnable {
		public void run() {
			while(true){
				try {
					Thread.sleep(100);
					synchronized (lock) {
						//循环条件等待
						while (queue.size()>=size) {
							//条件不满足释放锁,挂起阻塞?
							//直到有线程在同一个监视器锁对象上发起notify才会唤醒
							//此时此线程没有运行了,
							System.out.println("full ,call wait " +Thread.currentThread().getName());
							lock.wait();
							System.out.println("state:  " + Thread.currentThread().getState());
							System.out.println("notified:  "+Thread.currentThread().getName());
						}
						//
						for(int i=0;i<6;i++){
							producerCount++;
							boolean ok = queue.offer(Integer.valueOf(producerCount));
							System.out.println("offer add  "+ ok);
						}
						//不知道谁会获取到锁,所以只能全部唤醒,全部唤醒的线程将会竞争锁,不会被挂起,进入等待锁状态【会一直等待下去嘛?】
						lock.notifyAll();
					}
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
		}
	}

}