/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/**
 * Finite state transducers
 * <p>
 * This package implements <a href="http://en.wikipedia.org/wiki/Finite_state_transducer">
 * Finite State Transducers</a> with the following characteristics:
 * <ul>
 *    <li>Fast and low memory overhead construction of the minimal FST 
 *        (but inputs must be provided in sorted order)</li>
 *    <li>Low object overhead and quick deserialization (byte[] representation)</li>
 *    <li>{@link org.apache.lucene.util.fst.Util#getByOutput Lookup-by-output} when the 
 *        outputs are in sorted order (e.g., ordinals or file pointers)</li>
 *    <li>Pluggable {@link org.apache.lucene.util.fst.Outputs Outputs} representation</li>
 *    <li>{@link org.apache.lucene.util.fst.Util#shortestPaths N-shortest-paths} search by
 *        weight</li>
 *    <li>Enumerators ({@link org.apache.lucene.util.fst.IntsRefFSTEnum IntsRef} and {@link org.apache.lucene.util.fst.BytesRefFSTEnum BytesRef}) that behave like {@link java.util.SortedMap SortedMap} iterators
 * </ul>
 * <p>
 * FST Construction example:
 * <pre class="prettyprint">
 *     // Input values (keys). These must be provided to Builder in Unicode code point (UTF8 or UTF32) sorted order.
 *     // Note that sorting by Java's String.compareTo, which is UTF16 sorted order, is not correct and can lead to
 *     // exceptions while building the FST:
 *     String inputValues[] = {"cat", "dog", "dogs"};
 *     long outputValues[] = {5, 7, 12};
 *     
 *     PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton();
 *     Builder&lt;Long&gt; builder = new Builder&lt;Long&gt;(INPUT_TYPE.BYTE1, outputs);
 *     BytesRef scratchBytes = new BytesRef();
 *     IntsRefBuilder scratchInts = new IntsRefBuilder();
 *     for (int i = 0; i &lt; inputValues.length; i++) {
 *       scratchBytes.copyChars(inputValues[i]);
 *       builder.add(Util.toIntsRef(scratchBytes, scratchInts), outputValues[i]);
 *     }
 *     FST&lt;Long&gt; fst = builder.finish();
 * </pre>
 * Retrieval by key:
 * <pre class="prettyprint">
 *     Long value = Util.get(fst, new BytesRef("dog"));
 *     System.out.println(value); // 7
 * </pre>
 * Retrieval by value:
 * <pre class="prettyprint">
 *     // Only works because outputs are also in sorted order
 *     IntsRef key = Util.getByOutput(fst, 12);
 *     System.out.println(Util.toBytesRef(key, scratchBytes).utf8ToString()); // dogs
 * </pre>
 * Iterate over key-value pairs in sorted order:
 * <pre class="prettyprint">
 *     // Like TermsEnum, this also supports seeking (advance)
 *     BytesRefFSTEnum&lt;Long&gt; iterator = new BytesRefFSTEnum&lt;Long&gt;(fst);
 *     while (iterator.next() != null) {
 *       InputOutput&lt;Long&gt; mapEntry = iterator.current();
 *       System.out.println(mapEntry.input.utf8ToString());
 *       System.out.println(mapEntry.output);
 *     }
 * </pre>
 * N-shortest paths by weight:
 * <pre class="prettyprint">
 *     Comparator&lt;Long&gt; comparator = new Comparator&lt;Long&gt;() {
 *       public int compare(Long left, Long right) {
 *         return left.compareTo(right);
 *       }
 *     };
 *     Arc&lt;Long&gt; firstArc = fst.getFirstArc(new Arc&lt;Long&gt;());
 *     MinResult&lt;Long&gt; paths[] = Util.shortestPaths(fst, firstArc, comparator, 2);
 *     System.out.println(Util.toBytesRef(paths[0].input, scratchBytes).utf8ToString()); // cat
 *     System.out.println(paths[0].output); // 5
 *     System.out.println(Util.toBytesRef(paths[1].input, scratchBytes).utf8ToString()); // dog
 *     System.out.println(paths[1].output); // 7
 * </pre>
 */
package org.apache.lucene.util.fst;

@@ -2334,21 +2334,25 @@
 %0A *     
-Bu
+FSTComp
 il
-d
 er&lt;Lo
@@ -2358,21 +2358,25 @@
 ong&gt; 
-bu
+fstComp
 il
-d
 er = new
@@ -2376,21 +2376,25 @@
 r = new 
-Bu
+FSTComp
 il
-d
 er&lt;Lo
@@ -2443,16 +2443,23 @@
 BytesRef
+Builder
  scratch
@@ -2478,16 +2478,23 @@
 BytesRef
+Builder
 ();%0A *  
@@ -2662,21 +2662,25 @@
 *       
-bu
+fstComp
 il
-d
 er.add(U
@@ -2705,16 +2705,29 @@
 tchBytes
+.toBytesRef()
 , scratc
@@ -2794,22 +2794,27 @@
 t = 
-bu
+fstComp
 il
-d
 er.
-finish
+compile
 ();%0A
@@ -4025,17 +4025,23 @@
     
-Min
+Util.Top
 Result
+s
 &lt;
@@ -4054,18 +4054,16 @@
 t; paths
-%5B%5D
  = Util.
@@ -4090,16 +4090,43 @@
 irstArc,
+ fst.outputs.getNoOutput(),
  compara
@@ -4130,17 +4130,23 @@
 arator, 
-2
+3, true
 );%0A *   
@@ -4187,19 +4187,28 @@
 ef(paths
-%5B0%5D
+.topN.get(0)
 .input, 
@@ -4280,11 +4280,20 @@
 aths
-%5B0%5D
+.topN.get(0)
 .out
@@ -4350,19 +4350,28 @@
 ef(paths
-%5B1%5D
+.topN.get(1)
 .input, 
@@ -4443,11 +4443,20 @@
 aths
-%5B1%5D
+.topN.get(1)
 .out

update FST usage example