← Back to branch summary

~slub.team/goobi-indexserver/3.x

« back to all changes in this revision

Viewing changes to lucene/backwards/src/test/org/apache/lucene/util/fst/TestFSTs.java

  • Committer: Sebastian Meyer
  • Date: 2012-08-03 09:12:40 UTC
  • Revision ID: sebastian.meyer@slub-dresden.de-20120803091240-x6861b0vabq1xror
https://launchpad.net/bugs/985487
Remove Lucene and Solr source code and add patches instead
Fix Bug #985487: Auto-suggestion for the search interface

Show diffs side-by-side

added added

removed removed

Lines of Context:
lucene/backwards/src/test/org/apache/lucene/util/fst/TestFSTs.java
1
 
package org.apache.lucene.util.fst;
2
 
 
3
 
/**
4
 
 * Licensed to the Apache Software Foundation (ASF) under one or more
5
 
 * contributor license agreements.  See the NOTICE file distributed with
6
 
 * this work for additional information regarding copyright ownership.
7
 
 * The ASF licenses this file to You under the Apache License, Version 2.0
8
 
 * (the "License"); you may not use this file except in compliance with
9
 
 * the License.  You may obtain a copy of the License at
10
 
 *
11
 
 *     http://www.apache.org/licenses/LICENSE-2.0
12
 
 *
13
 
 * Unless required by applicable law or agreed to in writing, software
14
 
 * distributed under the License is distributed on an "AS IS" BASIS,
15
 
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16
 
 * See the License for the specific language governing permissions and
17
 
 * limitations under the License.
18
 
 */
19
 
 
20
 
import java.io.BufferedReader;
21
 
import java.io.File;
22
 
import java.io.FileInputStream;
23
 
import java.io.FileOutputStream;
24
 
import java.io.IOException;
25
 
import java.io.InputStreamReader;
26
 
import java.io.OutputStreamWriter;
27
 
import java.io.Writer;
28
 
import java.util.*;
29
 
 
30
 
import org.apache.lucene.analysis.MockAnalyzer;
31
 
import org.apache.lucene.document.Document;
32
 
import org.apache.lucene.index.IndexReader;
33
 
import org.apache.lucene.index.IndexWriter;
34
 
import org.apache.lucene.index.IndexWriterConfig;
35
 
import org.apache.lucene.index.Term;
36
 
import org.apache.lucene.index.TermEnum;
37
 
import org.apache.lucene.store.Directory;
38
 
import org.apache.lucene.store.FSDirectory;
39
 
import org.apache.lucene.store.IndexInput;
40
 
import org.apache.lucene.store.IndexOutput;
41
 
import org.apache.lucene.store.MockDirectoryWrapper;
42
 
import org.apache.lucene.util.BytesRef;
43
 
import org.apache.lucene.util.IntsRef;
44
 
import org.apache.lucene.util.LineFileDocs;
45
 
import org.apache.lucene.util.LuceneTestCase;
46
 
import org.apache.lucene.util.UnicodeUtil;
47
 
import org.apache.lucene.util._TestUtil;
48
 
import org.apache.lucene.util.fst.FST.Arc;
49
 
 
50
 
public class TestFSTs extends LuceneTestCase {
51
 
 
52
 
  private MockDirectoryWrapper dir;
53
 
 
54
 
  @Override
55
 
  public void setUp() throws Exception {
56
 
    super.setUp();
57
 
    dir = newDirectory();
58
 
    dir.setPreventDoubleWrite(false);
59
 
  }
60
 
 
61
 
  @Override
62
 
  public void tearDown() throws Exception {
63
 
    dir.close();
64
 
    super.tearDown();
65
 
  }
66
 
 
67
 
  private static BytesRef toBytesRef(IntsRef ir) {
68
 
    BytesRef br = new BytesRef(ir.length);
69
 
    for(int i=0;i<ir.length;i++) {
70
 
      int x = ir.ints[ir.offset+i];
71
 
      assert x >= 0 && x <= 255;
72
 
      br.bytes[i] = (byte) x;
73
 
    }
74
 
    br.length = ir.length;
75
 
    return br;
76
 
  }
77
 
 
78
 
  private static IntsRef toIntsRef(String s, int inputMode) {
79
 
    return toIntsRef(s, inputMode, new IntsRef(10));
80
 
  }
81
 
 
82
 
  private static IntsRef toIntsRef(String s, int inputMode, IntsRef ir) {
83
 
    if (inputMode == 0) {
84
 
      // utf8
85
 
      return toIntsRef(new BytesRef(s), ir);
86
 
    } else {
87
 
      // utf32
88
 
      return toIntsRefUTF32(s, ir);
89
 
    }
90
 
  }
91
 
 
92
 
  private static IntsRef toIntsRefUTF32(String s, IntsRef ir) {
93
 
    final int charLength = s.length();
94
 
    int charIdx = 0;
95
 
    int intIdx = 0;
96
 
    while(charIdx < charLength) {
97
 
      if (intIdx == ir.ints.length) {
98
 
        ir.grow(intIdx+1);
99
 
      }
100
 
      final int utf32 = s.codePointAt(charIdx);
101
 
      ir.ints[intIdx] = utf32;
102
 
      charIdx += Character.charCount(utf32);
103
 
      intIdx++;
104
 
    }
105
 
    ir.length = intIdx;
106
 
    return ir;
107
 
  }
108
 
 
109
 
  private static IntsRef toIntsRef(BytesRef br, IntsRef ir) {
110
 
    if (br.length > ir.ints.length) {
111
 
      ir.grow(br.length);
112
 
    }
113
 
    for(int i=0;i<br.length;i++) {
114
 
      ir.ints[i] = br.bytes[br.offset+i]&0xFF;
115
 
    }
116
 
    ir.length = br.length;
117
 
    return ir;
118
 
  }
119
 
 
120
 
  public void testBasicFSA() throws IOException {
121
 
    String[] strings = new String[] {"station", "commotion", "elation", "elastic", "plastic", "stop", "ftop", "ftation", "stat"};
122
 
    String[] strings2 = new String[] {"station", "commotion", "elation", "elastic", "plastic", "stop", "ftop", "ftation"};
123
 
    IntsRef[] terms = new IntsRef[strings.length];
124
 
    IntsRef[] terms2 = new IntsRef[strings2.length];
125
 
    for(int inputMode=0;inputMode<2;inputMode++) {
126
 
      if (VERBOSE) {
127
 
        System.out.println("TEST: inputMode=" + inputModeToString(inputMode));
128
 
      }
129
 
 
130
 
      for(int idx=0;idx<strings.length;idx++) {
131
 
        terms[idx] = toIntsRef(strings[idx], inputMode);
132
 
      }
133
 
      for(int idx=0;idx<strings2.length;idx++) {
134
 
        terms2[idx] = toIntsRef(strings2[idx], inputMode);
135
 
      }
136
 
      Arrays.sort(terms2);
137
 
 
138
 
      doTest(inputMode, terms);
139
 
    
140
 
      // Test pre-determined FST sizes to make sure we haven't lost minimality (at least on this trivial set of terms):
141
 
 
142
 
      // FSA
143
 
      {
144
 
        final Outputs<Object> outputs = NoOutputs.getSingleton();
145
 
        final Object NO_OUTPUT = outputs.getNoOutput();      
146
 
        final List<FSTTester.InputOutput<Object>> pairs = new ArrayList<FSTTester.InputOutput<Object>>(terms2.length);
147
 
        for(IntsRef term : terms2) {
148
 
          pairs.add(new FSTTester.InputOutput<Object>(term, NO_OUTPUT));
149
 
        }
150
 
        FST<Object> fst = new FSTTester<Object>(random, dir, inputMode, pairs, outputs).doTest(0, 0, false);
151
 
        assertNotNull(fst);
152
 
        assertEquals(22, fst.getNodeCount());
153
 
        assertEquals(27, fst.getArcCount());
154
 
      }
155
 
 
156
 
      // FST ord pos int
157
 
      {
158
 
        final PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton(true);
159
 
        final List<FSTTester.InputOutput<Long>> pairs = new ArrayList<FSTTester.InputOutput<Long>>(terms2.length);
160
 
        for(int idx=0;idx<terms2.length;idx++) {
161
 
          pairs.add(new FSTTester.InputOutput<Long>(terms2[idx], outputs.get(idx)));
162
 
        }
163
 
        final FST<Long> fst = new FSTTester<Long>(random, dir, inputMode, pairs, outputs).doTest(0, 0, false);
164
 
        assertNotNull(fst);
165
 
        assertEquals(22, fst.getNodeCount());
166
 
        assertEquals(27, fst.getArcCount());
167
 
      }
168
 
 
169
 
      // FST byte sequence ord
170
 
      {
171
 
        final ByteSequenceOutputs outputs = ByteSequenceOutputs.getSingleton();
172
 
        final BytesRef NO_OUTPUT = outputs.getNoOutput();      
173
 
        final List<FSTTester.InputOutput<BytesRef>> pairs = new ArrayList<FSTTester.InputOutput<BytesRef>>(terms2.length);
174
 
        for(int idx=0;idx<terms2.length;idx++) {
175
 
          final BytesRef output = random.nextInt(30) == 17 ? NO_OUTPUT : new BytesRef(Integer.toString(idx));
176
 
          pairs.add(new FSTTester.InputOutput<BytesRef>(terms2[idx], output));
177
 
        }
178
 
        final FST<BytesRef> fst = new FSTTester<BytesRef>(random, dir, inputMode, pairs, outputs).doTest(0, 0, false);
179
 
        assertNotNull(fst);
180
 
        assertEquals(24, fst.getNodeCount());
181
 
        assertEquals(30, fst.getArcCount());
182
 
      }
183
 
    }
184
 
  }
185
 
 
186
 
  private static String simpleRandomString(Random r) {
187
 
    final int end = r.nextInt(10);
188
 
    if (end == 0) {
189
 
      // allow 0 length
190
 
      return "";
191
 
    }
192
 
    final char[] buffer = new char[end];
193
 
    for (int i = 0; i < end; i++) {
194
 
      buffer[i] = (char) _TestUtil.nextInt(r, 97, 102);
195
 
    }
196
 
    return new String(buffer, 0, end);
197
 
  }
198
 
 
199
 
  // given set of terms, test the different outputs for them
200
 
  private void doTest(int inputMode, IntsRef[] terms) throws IOException {
201
 
    Arrays.sort(terms);
202
 
 
203
 
    // NoOutputs (simple FSA)
204
 
    {
205
 
      final Outputs<Object> outputs = NoOutputs.getSingleton();
206
 
      final Object NO_OUTPUT = outputs.getNoOutput();      
207
 
      final List<FSTTester.InputOutput<Object>> pairs = new ArrayList<FSTTester.InputOutput<Object>>(terms.length);
208
 
      for(IntsRef term : terms) {
209
 
        pairs.add(new FSTTester.InputOutput<Object>(term, NO_OUTPUT));
210
 
      }
211
 
      new FSTTester<Object>(random, dir, inputMode, pairs, outputs).doTest();
212
 
    }
213
 
 
214
 
    // PositiveIntOutput (ord)
215
 
    {
216
 
      final PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton(true);
217
 
      final List<FSTTester.InputOutput<Long>> pairs = new ArrayList<FSTTester.InputOutput<Long>>(terms.length);
218
 
      for(int idx=0;idx<terms.length;idx++) {
219
 
        pairs.add(new FSTTester.InputOutput<Long>(terms[idx], outputs.get(idx)));
220
 
      }
221
 
      new FSTTester<Long>(random, dir, inputMode, pairs, outputs).doTest();
222
 
    }
223
 
 
224
 
    // PositiveIntOutput (random monotonically increasing positive number)
225
 
    {
226
 
      final PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton(random.nextBoolean());
227
 
      final List<FSTTester.InputOutput<Long>> pairs = new ArrayList<FSTTester.InputOutput<Long>>(terms.length);
228
 
      long lastOutput = 0;
229
 
      for(int idx=0;idx<terms.length;idx++) {
230
 
        final long value = lastOutput + _TestUtil.nextInt(random, 1, 1000);
231
 
        lastOutput = value;
232
 
        pairs.add(new FSTTester.InputOutput<Long>(terms[idx], outputs.get(value)));
233
 
      }
234
 
      new FSTTester<Long>(random, dir, inputMode, pairs, outputs).doTest();
235
 
    }
236
 
 
237
 
    // PositiveIntOutput (random positive number)
238
 
    {
239
 
      final PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton(random.nextBoolean());
240
 
      final List<FSTTester.InputOutput<Long>> pairs = new ArrayList<FSTTester.InputOutput<Long>>(terms.length);
241
 
      for(int idx=0;idx<terms.length;idx++) {
242
 
        pairs.add(new FSTTester.InputOutput<Long>(terms[idx], outputs.get(random.nextLong()) & Long.MAX_VALUE));
243
 
      }
244
 
      new FSTTester<Long>(random, dir, inputMode, pairs, outputs).doTest();
245
 
    }
246
 
 
247
 
    // Pair<ord, (random monotonically increasing positive number>
248
 
    {
249
 
      final PositiveIntOutputs o1 = PositiveIntOutputs.getSingleton(random.nextBoolean());
250
 
      final PositiveIntOutputs o2 = PositiveIntOutputs.getSingleton(random.nextBoolean());
251
 
      final PairOutputs<Long,Long> outputs = new PairOutputs<Long,Long>(o1, o2);
252
 
      final List<FSTTester.InputOutput<PairOutputs.Pair<Long,Long>>> pairs = new ArrayList<FSTTester.InputOutput<PairOutputs.Pair<Long,Long>>>(terms.length);
253
 
      long lastOutput = 0;
254
 
      for(int idx=0;idx<terms.length;idx++) {
255
 
        final long value = lastOutput + _TestUtil.nextInt(random, 1, 1000);
256
 
        lastOutput = value;
257
 
        pairs.add(new FSTTester.InputOutput<PairOutputs.Pair<Long,Long>>(terms[idx],
258
 
                                                                         outputs.get(o1.get(idx),
259
 
                                                                                     o2.get(value))));
260
 
      }
261
 
      new FSTTester<PairOutputs.Pair<Long,Long>>(random, dir, inputMode, pairs, outputs).doTest();
262
 
    }
263
 
 
264
 
    // Sequence-of-bytes
265
 
    {
266
 
      final ByteSequenceOutputs outputs = ByteSequenceOutputs.getSingleton();
267
 
      final BytesRef NO_OUTPUT = outputs.getNoOutput();      
268
 
      final List<FSTTester.InputOutput<BytesRef>> pairs = new ArrayList<FSTTester.InputOutput<BytesRef>>(terms.length);
269
 
      for(int idx=0;idx<terms.length;idx++) {
270
 
        final BytesRef output = random.nextInt(30) == 17 ? NO_OUTPUT : new BytesRef(Integer.toString(idx));
271
 
        pairs.add(new FSTTester.InputOutput<BytesRef>(terms[idx], output));
272
 
      }
273
 
      new FSTTester<BytesRef>(random, dir, inputMode, pairs, outputs).doTest();
274
 
    }
275
 
 
276
 
    // Sequence-of-ints
277
 
    {
278
 
      final IntSequenceOutputs outputs = IntSequenceOutputs.getSingleton();
279
 
      final List<FSTTester.InputOutput<IntsRef>> pairs = new ArrayList<FSTTester.InputOutput<IntsRef>>(terms.length);
280
 
      for(int idx=0;idx<terms.length;idx++) {
281
 
        final String s = Integer.toString(idx);
282
 
        final IntsRef output = new IntsRef(s.length());
283
 
        output.length = s.length();
284
 
        for(int idx2=0;idx2<output.length;idx2++) {
285
 
          output.ints[idx2] = s.charAt(idx2);
286
 
        }
287
 
        pairs.add(new FSTTester.InputOutput<IntsRef>(terms[idx], output));
288
 
      }
289
 
      new FSTTester<IntsRef>(random, dir, inputMode, pairs, outputs).doTest();
290
 
    }
291
 
 
292
 
    // Up to two positive ints, shared, generally but not
293
 
    // monotonically increasing
294
 
    {
295
 
      if (VERBOSE) {
296
 
        System.out.println("TEST: now test UpToTwoPositiveIntOutputs");
297
 
      }
298
 
      final UpToTwoPositiveIntOutputs outputs = UpToTwoPositiveIntOutputs.getSingleton(true);
299
 
      final List<FSTTester.InputOutput<Object>> pairs = new ArrayList<FSTTester.InputOutput<Object>>(terms.length);
300
 
      long lastOutput = 0;
301
 
      for(int idx=0;idx<terms.length;idx++) {
302
 
        // Sometimes go backwards
303
 
        long value = lastOutput + _TestUtil.nextInt(random, -100, 1000);
304
 
        while(value < 0) {
305
 
          value = lastOutput + _TestUtil.nextInt(random, -100, 1000);
306
 
        }
307
 
        final Object output;
308
 
        if (random.nextInt(5) == 3) {
309
 
          long value2 = lastOutput + _TestUtil.nextInt(random, -100, 1000);
310
 
          while(value2 < 0) {
311
 
            value2 = lastOutput + _TestUtil.nextInt(random, -100, 1000);
312
 
          }
313
 
          output = outputs.get(value, value2);
314
 
        } else {
315
 
          output = outputs.get(value);
316
 
        }
317
 
        pairs.add(new FSTTester.InputOutput<Object>(terms[idx], output));
318
 
      }
319
 
      new FSTTester<Object>(random, dir, inputMode, pairs, outputs).doTest();
320
 
    }
321
 
  }
322
 
 
323
 
  private static class FSTTester<T> {
324
 
 
325
 
    final Random random;
326
 
    final List<InputOutput<T>> pairs;
327
 
    final int inputMode;
328
 
    final Outputs<T> outputs;
329
 
    final Directory dir;
330
 
 
331
 
    public FSTTester(Random random, Directory dir, int inputMode, List<InputOutput<T>> pairs, Outputs<T> outputs) {
332
 
      this.random = random;
333
 
      this.dir = dir;
334
 
      this.inputMode = inputMode;
335
 
      this.pairs = pairs;
336
 
      this.outputs = outputs;
337
 
    }
338
 
 
339
 
    private static class InputOutput<T> implements Comparable<InputOutput<T>> {
340
 
      public final IntsRef input;
341
 
      public final T output;
342
 
 
343
 
      public InputOutput(IntsRef input, T output) {
344
 
        this.input = input;
345
 
        this.output = output;
346
 
      }
347
 
 
348
 
      public int compareTo(InputOutput<T> other) {
349
 
        if (other instanceof InputOutput) {
350
 
          return input.compareTo((other).input);
351
 
        } else {
352
 
          throw new IllegalArgumentException();
353
 
        }
354
 
      }
355
 
    }
356
 
 
357
 
    public void doTest() throws IOException {
358
 
      // no pruning
359
 
      doTest(0, 0, true);
360
 
 
361
 
      if (!(outputs instanceof UpToTwoPositiveIntOutputs)) {
362
 
        // simple pruning
363
 
        doTest(_TestUtil.nextInt(random, 1, 1+pairs.size()), 0, true);
364
 
        
365
 
        // leafy pruning
366
 
        doTest(0, _TestUtil.nextInt(random, 1, 1+pairs.size()), true);
367
 
      }
368
 
    }
369
 
 
370
 
    // runs the term, returning the output, or null if term
371
 
    // isn't accepted.  if prefixLength is non-null it must be
372
 
    // length 1 int array; prefixLength[0] is set to the length
373
 
    // of the term prefix that matches
374
 
    private T run(FST<T> fst, IntsRef term, int[] prefixLength) throws IOException {
375
 
      assert prefixLength == null || prefixLength.length == 1;
376
 
      final FST.Arc<T> arc = fst.getFirstArc(new FST.Arc<T>());
377
 
      final T NO_OUTPUT = fst.outputs.getNoOutput();
378
 
      T output = NO_OUTPUT;
379
 
 
380
 
      for(int i=0;i<=term.length;i++) {
381
 
        final int label;
382
 
        if (i == term.length) {
383
 
          label = FST.END_LABEL;
384
 
        } else {
385
 
          label = term.ints[term.offset+i];
386
 
        }
387
 
        //System.out.println("   loop i=" + i + " label=" + label + " output=" + fst.outputs.outputToString(output) + " curArc: target=" + arc.target + " isFinal?=" + arc.isFinal());
388
 
        if (fst.findTargetArc(label, arc, arc) == null) {
389
 
          if (prefixLength != null) {
390
 
            prefixLength[0] = i;
391
 
            return output;
392
 
          } else {
393
 
            return null;
394
 
          }
395
 
        }
396
 
        output = fst.outputs.add(output, arc.output);
397
 
      }
398
 
 
399
 
      if (prefixLength != null) {
400
 
        prefixLength[0] = term.length;
401
 
      }
402
 
 
403
 
      return output;
404
 
    }
405
 
 
406
 
    private T randomAcceptedWord(FST<T> fst, IntsRef in) throws IOException {
407
 
      FST.Arc<T> arc = fst.getFirstArc(new FST.Arc<T>());
408
 
 
409
 
      final List<FST.Arc<T>> arcs = new ArrayList<FST.Arc<T>>();
410
 
      in.length = 0;
411
 
      in.offset = 0;
412
 
      final T NO_OUTPUT = fst.outputs.getNoOutput();
413
 
      T output = NO_OUTPUT;
414
 
 
415
 
      while(true) {
416
 
        // read all arcs:
417
 
        fst.readFirstTargetArc(arc, arc);
418
 
        arcs.add(new FST.Arc<T>().copyFrom(arc));
419
 
        while(!arc.isLast()) {
420
 
          fst.readNextArc(arc);
421
 
          arcs.add(new FST.Arc<T>().copyFrom(arc));
422
 
        }
423
 
      
424
 
        // pick one
425
 
        arc = arcs.get(random.nextInt(arcs.size()));
426
 
        arcs.clear();
427
 
 
428
 
        // accumulate output
429
 
        output = fst.outputs.add(output, arc.output);
430
 
 
431
 
        // append label
432
 
        if (arc.label == FST.END_LABEL) {
433
 
          break;
434
 
        }
435
 
 
436
 
        if (in.ints.length == in.length) {
437
 
          in.grow(1+in.length);
438
 
        }
439
 
        in.ints[in.length++] = arc.label;
440
 
      }
441
 
 
442
 
      return output;
443
 
    }
444
 
 
445
 
 
446
 
    FST<T> doTest(int prune1, int prune2, boolean allowRandomSuffixSharing) throws IOException {
447
 
      if (VERBOSE) {
448
 
        System.out.println("TEST: prune1=" + prune1 + " prune2=" + prune2);
449
 
      }
450
 
 
451
 
      final Builder<T> builder = new Builder<T>(inputMode == 0 ? FST.INPUT_TYPE.BYTE1 : FST.INPUT_TYPE.BYTE4,
452
 
                                                prune1, prune2,
453
 
                                                prune1==0 && prune2==0,
454
 
                                                allowRandomSuffixSharing ? random.nextBoolean() : true,
455
 
                                                allowRandomSuffixSharing ? _TestUtil.nextInt(random, 1, 10) : Integer.MAX_VALUE,
456
 
                                                outputs);
457
 
 
458
 
      for(InputOutput<T> pair : pairs) {
459
 
        if (pair.output instanceof UpToTwoPositiveIntOutputs.TwoLongs) {
460
 
          final UpToTwoPositiveIntOutputs _outputs = (UpToTwoPositiveIntOutputs) outputs;
461
 
          final UpToTwoPositiveIntOutputs.TwoLongs twoLongs = (UpToTwoPositiveIntOutputs.TwoLongs) pair.output;
462
 
          @SuppressWarnings("unchecked") final Builder<Object> builderObject = (Builder<Object>) builder;
463
 
          builderObject.add(pair.input, _outputs.get(twoLongs.first));
464
 
          builderObject.add(pair.input, _outputs.get(twoLongs.second));
465
 
        } else {
466
 
          builder.add(pair.input, pair.output);
467
 
        }
468
 
      }
469
 
      FST<T> fst = builder.finish();
470
 
 
471
 
      if (random.nextBoolean() && fst != null) {
472
 
        IndexOutput out = dir.createOutput("fst.bin");
473
 
        fst.save(out);
474
 
        out.close();
475
 
        IndexInput in = dir.openInput("fst.bin");
476
 
        try {
477
 
          fst = new FST<T>(in, outputs);
478
 
        } finally {
479
 
          in.close();
480
 
          dir.deleteFile("fst.bin");
481
 
        }
482
 
      }
483
 
 
484
 
      if (VERBOSE && pairs.size() <= 20 && fst != null) {
485
 
        Writer w = new OutputStreamWriter(new FileOutputStream("out.dot"), "UTF-8");
486
 
        Util.toDot(fst, w, false, false);
487
 
        w.close();
488
 
        System.out.println("SAVED out.dot");
489
 
      }
490
 
 
491
 
      if (VERBOSE) {
492
 
        if (fst == null) {
493
 
          System.out.println("  fst has 0 nodes (fully pruned)");
494
 
        } else {
495
 
          System.out.println("  fst has " + fst.getNodeCount() + " nodes and " + fst.getArcCount() + " arcs");
496
 
        }
497
 
      }
498
 
 
499
 
      if (prune1 == 0 && prune2 == 0) {
500
 
        verifyUnPruned(inputMode, fst);
501
 
      } else {
502
 
        verifyPruned(inputMode, fst, prune1, prune2);
503
 
      }
504
 
 
505
 
      return fst;
506
 
    }
507
 
 
508
 
    // FST is complete
509
 
    private void verifyUnPruned(int inputMode, FST<T> fst) throws IOException {
510
 
 
511
 
      if (pairs.size() == 0) {
512
 
        assertNull(fst);
513
 
        return;
514
 
      }
515
 
 
516
 
      if (VERBOSE) {
517
 
        System.out.println("TEST: now verify " + pairs.size() + " terms");
518
 
        for(InputOutput<T> pair : pairs) {
519
 
          assertNotNull(pair);
520
 
          assertNotNull(pair.input);
521
 
          assertNotNull(pair.output);
522
 
          System.out.println("  " + inputToString(inputMode, pair.input) + ": " + outputs.outputToString(pair.output));
523
 
        }
524
 
      }
525
 
 
526
 
      assertNotNull(fst);
527
 
 
528
 
      // visit valid paris in order -- make sure all words
529
 
      // are accepted, and FSTEnum's next() steps through
530
 
      // them correctly
531
 
      if (VERBOSE) {
532
 
        System.out.println("TEST: check valid terms/next()");
533
 
      }
534
 
      {
535
 
        IntsRefFSTEnum<T> fstEnum = new IntsRefFSTEnum<T>(fst);
536
 
        for(InputOutput<T> pair : pairs) {
537
 
          IntsRef term = pair.input;
538
 
          if (VERBOSE) {
539
 
            System.out.println("TEST: check term=" + inputToString(inputMode, term) + " output=" + fst.outputs.outputToString(pair.output));
540
 
          }
541
 
          Object output = run(fst, term, null);
542
 
 
543
 
          assertNotNull("term " + inputToString(inputMode, term) + " is not accepted", output);
544
 
          assertEquals(pair.output, output);
545
 
 
546
 
          // verify enum's next
547
 
          IntsRefFSTEnum.InputOutput<T> t = fstEnum.next();
548
 
          assertNotNull(t);
549
 
          assertEquals("expected input=" + inputToString(inputMode, term) + " but fstEnum returned " + inputToString(inputMode, t.input), term, t.input);
550
 
          assertEquals(pair.output, t.output);
551
 
        }
552
 
        assertNull(fstEnum.next());
553
 
      }
554
 
 
555
 
      final Map<IntsRef,T> termsMap = new HashMap<IntsRef,T>();
556
 
      for(InputOutput<T> pair : pairs) {
557
 
        termsMap.put(pair.input, pair.output);
558
 
      }
559
 
 
560
 
      // find random matching word and make sure it's valid
561
 
      if (VERBOSE) {
562
 
        System.out.println("TEST: verify random accepted terms");
563
 
      }
564
 
      final IntsRef scratch = new IntsRef(10);
565
 
      int num = atLeast(500);
566
 
      for(int iter=0;iter<num;iter++) {
567
 
        T output = randomAcceptedWord(fst, scratch);
568
 
        assertTrue("accepted word " + inputToString(inputMode, scratch) + " is not valid", termsMap.containsKey(scratch));
569
 
        assertEquals(termsMap.get(scratch), output);
570
 
      }
571
 
    
572
 
      // test IntsRefFSTEnum.seek:
573
 
      if (VERBOSE) {
574
 
        System.out.println("TEST: verify seek");
575
 
      }
576
 
      IntsRefFSTEnum<T> fstEnum = new IntsRefFSTEnum<T>(fst);
577
 
      num = atLeast(100);
578
 
      for(int iter=0;iter<num;iter++) {
579
 
        if (VERBOSE) {
580
 
          System.out.println("TEST: iter=" + iter);
581
 
        }
582
 
        if (random.nextBoolean()) {
583
 
          // seek to term that doesn't exist:
584
 
          while(true) {
585
 
            final IntsRef term = toIntsRef(getRandomString(), inputMode);
586
 
            int pos = Collections.binarySearch(pairs, new InputOutput<T>(term, null));
587
 
            if (pos < 0) {
588
 
              pos = -(pos+1);
589
 
              // ok doesn't exist
590
 
              //System.out.println("  seek " + inputToString(inputMode, term));
591
 
              final IntsRefFSTEnum.InputOutput<T> seekResult;
592
 
              if (random.nextBoolean()) {
593
 
                if (VERBOSE) {
594
 
                  System.out.println("  do non-exist seekFloor term=" + inputToString(inputMode, term));
595
 
                }
596
 
                seekResult = fstEnum.seekFloor(term);
597
 
                pos--;
598
 
              } else {
599
 
                if (VERBOSE) {
600
 
                  System.out.println("  do non-exist seekCeil term=" + inputToString(inputMode, term));
601
 
                }
602
 
                seekResult = fstEnum.seekCeil(term);
603
 
              }
604
 
 
605
 
              if (pos != -1 && pos < pairs.size()) {
606
 
                //System.out.println("    got " + inputToString(inputMode,seekResult.input) + " output=" + fst.outputs.outputToString(seekResult.output));
607
 
                assertNotNull("got null but expected term=" + inputToString(inputMode, pairs.get(pos).input), seekResult);
608
 
                if (VERBOSE) {
609
 
                  System.out.println("    got " + inputToString(inputMode, seekResult.input));
610
 
                }
611
 
                assertEquals("expected " + inputToString(inputMode, pairs.get(pos).input) + " but got " + inputToString(inputMode, seekResult.input), pairs.get(pos).input, seekResult.input);
612
 
                assertEquals(pairs.get(pos).output, seekResult.output);
613
 
              } else {
614
 
                // seeked before start or beyond end
615
 
                //System.out.println("seek=" + seekTerm);
616
 
                assertNull("expected null but got " + (seekResult==null ? "null" : inputToString(inputMode, seekResult.input)), seekResult);
617
 
                if (VERBOSE) {
618
 
                  System.out.println("    got null");
619
 
                }
620
 
              }
621
 
 
622
 
              break;
623
 
            }
624
 
          }
625
 
        } else {
626
 
          // seek to term that does exist:
627
 
          InputOutput<T> pair = pairs.get(random.nextInt(pairs.size()));
628
 
          final IntsRefFSTEnum.InputOutput<T> seekResult;
629
 
          if (random.nextBoolean()) {
630
 
            if (VERBOSE) {
631
 
              System.out.println("  do exists seekFloor " + inputToString(inputMode, pair.input));
632
 
            }
633
 
            seekResult = fstEnum.seekFloor(pair.input);
634
 
          } else {
635
 
            if (VERBOSE) {
636
 
              System.out.println("  do exists seekCeil " + inputToString(inputMode, pair.input));
637
 
            }
638
 
            seekResult = fstEnum.seekCeil(pair.input);
639
 
          }
640
 
          assertNotNull(seekResult);
641
 
          assertEquals("got " + inputToString(inputMode, seekResult.input) + " but expected " + inputToString(inputMode, pair.input), pair.input, seekResult.input);
642
 
          assertEquals(pair.output, seekResult.output);
643
 
        }
644
 
      }
645
 
 
646
 
      if (VERBOSE) {
647
 
        System.out.println("TEST: mixed next/seek");
648
 
      }
649
 
 
650
 
      // test mixed next/seek
651
 
      num = atLeast(100);
652
 
      for(int iter=0;iter<num;iter++) {
653
 
        if (VERBOSE) {
654
 
          System.out.println("TEST: iter " + iter);
655
 
        }
656
 
        // reset:
657
 
        fstEnum = new IntsRefFSTEnum<T>(fst);
658
 
        int upto = -1;
659
 
        while(true) {
660
 
          boolean isDone = false;
661
 
          if (upto == pairs.size()-1 || random.nextBoolean()) {
662
 
            // next
663
 
            upto++;
664
 
            if (VERBOSE) {
665
 
              System.out.println("  do next");
666
 
            }
667
 
            isDone = fstEnum.next() == null;
668
 
          } else if (upto != -1 && upto < 0.75 * pairs.size() && random.nextBoolean()) {
669
 
            int attempt = 0;
670
 
            for(;attempt<10;attempt++) {
671
 
              IntsRef term = toIntsRef(getRandomString(), inputMode);
672
 
              if (!termsMap.containsKey(term) && term.compareTo(pairs.get(upto).input) > 0) {
673
 
                int pos = Collections.binarySearch(pairs, new InputOutput<T>(term, null));
674
 
                assert pos < 0;
675
 
                upto = -(pos+1);
676
 
 
677
 
                if (random.nextBoolean()) {
678
 
                  upto--;
679
 
                  assertTrue(upto != -1);
680
 
                  if (VERBOSE) {
681
 
                    System.out.println("  do non-exist seekFloor(" + inputToString(inputMode, term) + ")");
682
 
                  }
683
 
                  isDone = fstEnum.seekFloor(term) == null;
684
 
                } else {
685
 
                  if (VERBOSE) {
686
 
                    System.out.println("  do non-exist seekCeil(" + inputToString(inputMode, term) + ")");
687
 
                  }
688
 
                  isDone = fstEnum.seekCeil(term) == null;
689
 
                }
690
 
 
691
 
                break;
692
 
              }
693
 
            }
694
 
            if (attempt == 10) {
695
 
              continue;
696
 
            }
697
 
            
698
 
          } else {
699
 
            final int inc = random.nextInt(pairs.size() - upto - 1);
700
 
            upto += inc;
701
 
            if (upto == -1) {
702
 
              upto = 0;
703
 
            }
704
 
 
705
 
            if (random.nextBoolean()) {
706
 
              if (VERBOSE) {
707
 
                System.out.println("  do advanceCeil(" + inputToString(inputMode, pairs.get(upto).input) + ")");
708
 
              }
709
 
              isDone = fstEnum.seekCeil(pairs.get(upto).input) == null;
710
 
            } else {
711
 
              if (VERBOSE) {
712
 
                System.out.println("  do advanceFloor(" + inputToString(inputMode, pairs.get(upto).input) + ")");
713
 
              }
714
 
              isDone = fstEnum.seekFloor(pairs.get(upto).input) == null;
715
 
            }
716
 
          }
717
 
          if (VERBOSE) {
718
 
            if (!isDone) {
719
 
              System.out.println("    got " + inputToString(inputMode, fstEnum.current().input));
720
 
            } else {
721
 
              System.out.println("    got null");
722
 
            }
723
 
          }
724
 
 
725
 
          if (upto == pairs.size()) {
726
 
            assertTrue(isDone);
727
 
            break;
728
 
          } else {
729
 
            assertFalse(isDone);
730
 
            assertEquals(pairs.get(upto).input, fstEnum.current().input);
731
 
            assertEquals(pairs.get(upto).output, fstEnum.current().output);
732
 
 
733
 
            /*
734
 
            if (upto < pairs.size()-1) {
735
 
              int tryCount = 0;
736
 
              while(tryCount < 10) {
737
 
                final IntsRef t = toIntsRef(getRandomString(), inputMode);
738
 
                if (pairs.get(upto).input.compareTo(t) < 0) {
739
 
                  final boolean expected = t.compareTo(pairs.get(upto+1).input) < 0;
740
 
                  if (VERBOSE) {
741
 
                    System.out.println("TEST: call beforeNext(" + inputToString(inputMode, t) + "); current=" + inputToString(inputMode, pairs.get(upto).input) + " next=" + inputToString(inputMode, pairs.get(upto+1).input) + " expected=" + expected);
742
 
                  }
743
 
                  assertEquals(expected, fstEnum.beforeNext(t));
744
 
                  break;
745
 
                }
746
 
                tryCount++;
747
 
              }
748
 
            }
749
 
            */
750
 
          }
751
 
        }
752
 
      }
753
 
    }
754
 
 
755
 
    private static class CountMinOutput<T> {
756
 
      int count;
757
 
      T output;
758
 
      T finalOutput;
759
 
      boolean isLeaf = true;
760
 
      boolean isFinal;
761
 
    }
762
 
 
763
 
    // FST is pruned
764
 
    private void verifyPruned(int inputMode, FST<T> fst, int prune1, int prune2) throws IOException {
765
 
 
766
 
      if (VERBOSE) {
767
 
        System.out.println("TEST: now verify pruned " + pairs.size() + " terms; outputs=" + outputs);
768
 
        for(InputOutput<T> pair : pairs) {
769
 
          System.out.println("  " + inputToString(inputMode, pair.input) + ": " + outputs.outputToString(pair.output));
770
 
        }
771
 
      }
772
 
 
773
 
      // To validate the FST, we brute-force compute all prefixes
774
 
      // in the terms, matched to their "common" outputs, prune that
775
 
      // set according to the prune thresholds, then assert the FST
776
 
      // matches that same set.
777
 
 
778
 
      // NOTE: Crazy RAM intensive!!
779
 
 
780
 
      //System.out.println("TEST: tally prefixes");
781
 
 
782
 
      // build all prefixes
783
 
      final Map<IntsRef,CountMinOutput<T>> prefixes = new HashMap<IntsRef,CountMinOutput<T>>();
784
 
      final IntsRef scratch = new IntsRef(10);
785
 
      for(InputOutput<T> pair: pairs) {
786
 
        scratch.copy(pair.input);
787
 
        for(int idx=0;idx<=pair.input.length;idx++) {
788
 
          scratch.length = idx;
789
 
          CountMinOutput<T> cmo = prefixes.get(scratch);
790
 
          if (cmo == null) {
791
 
            cmo = new CountMinOutput<T>();
792
 
            cmo.count = 1;
793
 
            cmo.output = pair.output;
794
 
            prefixes.put(new IntsRef(scratch), cmo);
795
 
          } else {
796
 
            cmo.count++;
797
 
            cmo.output = outputs.common(cmo.output, pair.output);
798
 
          }
799
 
          if (idx == pair.input.length) {
800
 
            cmo.isFinal = true;
801
 
            cmo.finalOutput = cmo.output;
802
 
          }
803
 
        }
804
 
      }
805
 
 
806
 
      if (VERBOSE) {
807
 
        System.out.println("TEST: now prune");
808
 
      }
809
 
 
810
 
      // prune 'em
811
 
      final Iterator<Map.Entry<IntsRef,CountMinOutput<T>>> it = prefixes.entrySet().iterator();
812
 
      while(it.hasNext()) {
813
 
        Map.Entry<IntsRef,CountMinOutput<T>> ent = it.next();
814
 
        final IntsRef prefix = ent.getKey();
815
 
        final CountMinOutput<T> cmo = ent.getValue();
816
 
        if (VERBOSE) {
817
 
          System.out.println("  term prefix=" + inputToString(inputMode, prefix, false) + " count=" + cmo.count + " isLeaf=" + cmo.isLeaf + " output=" + outputs.outputToString(cmo.output) + " isFinal=" + cmo.isFinal);
818
 
        }
819
 
        final boolean keep;
820
 
        if (prune1 > 0) {
821
 
          keep = cmo.count >= prune1;
822
 
        } else {
823
 
          assert prune2 > 0;
824
 
          if (prune2 > 1 && cmo.count >= prune2) {
825
 
            keep = true;
826
 
          } else if (prefix.length > 0) {
827
 
            // consult our parent
828
 
            scratch.length = prefix.length-1;
829
 
            System.arraycopy(prefix.ints, prefix.offset, scratch.ints, 0, scratch.length);
830
 
            final CountMinOutput<T> cmo2 = prefixes.get(scratch);
831
 
            //System.out.println("    parent count = " + (cmo2 == null ? -1 : cmo2.count));
832
 
            keep = cmo2 != null && ((prune2 > 1 && cmo2.count >= prune2) || (prune2 == 1 && (cmo2.count >= 2 || prefix.length <= 1)));
833
 
          } else if (cmo.count >= prune2) {
834
 
            keep = true;
835
 
          } else {
836
 
            keep = false;
837
 
          }
838
 
        }
839
 
 
840
 
        if (!keep) {
841
 
          it.remove();
842
 
          //System.out.println("    remove");
843
 
        } else {
844
 
          // clear isLeaf for all ancestors
845
 
          //System.out.println("    keep");
846
 
          scratch.copy(prefix);
847
 
          scratch.length--;
848
 
          while(scratch.length >= 0) {
849
 
            final CountMinOutput<T> cmo2 = prefixes.get(scratch);
850
 
            if (cmo2 != null) {
851
 
              //System.out.println("    clear isLeaf " + inputToString(inputMode, scratch));
852
 
              cmo2.isLeaf = false;
853
 
            }
854
 
            scratch.length--;
855
 
          }
856
 
        }
857
 
      }
858
 
 
859
 
      //System.out.println("TEST: after prune");
860
 
      /*
861
 
        for(Map.Entry<BytesRef,CountMinOutput> ent : prefixes.entrySet()) {
862
 
        System.out.println("  " + inputToString(inputMode, ent.getKey()) + ": isLeaf=" + ent.getValue().isLeaf + " isFinal=" + ent.getValue().isFinal);
863
 
        if (ent.getValue().isFinal) {
864
 
        System.out.println("    finalOutput=" + outputs.outputToString(ent.getValue().finalOutput));
865
 
        }
866
 
        }
867
 
      */
868
 
 
869
 
      if (prefixes.size() <= 1) {
870
 
        assertNull(fst);
871
 
        return;
872
 
      }
873
 
 
874
 
      assertNotNull(fst);
875
 
 
876
 
      // make sure FST only enums valid prefixes
877
 
      if (VERBOSE) {
878
 
        System.out.println("TEST: check pruned enum");
879
 
      }
880
 
      IntsRefFSTEnum<T> fstEnum = new IntsRefFSTEnum<T>(fst);
881
 
      IntsRefFSTEnum.InputOutput<T> current;
882
 
      while((current = fstEnum.next()) != null) {
883
 
        if (VERBOSE) {
884
 
          System.out.println("  fstEnum.next prefix=" + inputToString(inputMode, current.input, false) + " output=" + outputs.outputToString(current.output));
885
 
        }
886
 
        final CountMinOutput cmo = prefixes.get(current.input);
887
 
        assertNotNull(cmo);
888
 
        assertTrue(cmo.isLeaf || cmo.isFinal);
889
 
        //if (cmo.isFinal && !cmo.isLeaf) {
890
 
        if (cmo.isFinal) {
891
 
          assertEquals(cmo.finalOutput, current.output);
892
 
        } else {
893
 
          assertEquals(cmo.output, current.output);
894
 
        }
895
 
      }
896
 
 
897
 
      // make sure all non-pruned prefixes are present in the FST
898
 
      if (VERBOSE) {
899
 
        System.out.println("TEST: verify all prefixes");
900
 
      }
901
 
      final int[] stopNode = new int[1];
902
 
      for(Map.Entry<IntsRef,CountMinOutput<T>> ent : prefixes.entrySet()) {
903
 
        if (ent.getKey().length > 0) {
904
 
          final CountMinOutput<T> cmo = ent.getValue();
905
 
          final T output = run(fst, ent.getKey(), stopNode);
906
 
          if (VERBOSE) {
907
 
            System.out.println("TEST: verify prefix=" + inputToString(inputMode, ent.getKey(), false) + " output=" + outputs.outputToString(cmo.output));
908
 
          }
909
 
          // if (cmo.isFinal && !cmo.isLeaf) {
910
 
          if (cmo.isFinal) {
911
 
            assertEquals(cmo.finalOutput, output);
912
 
          } else {
913
 
            assertEquals(cmo.output, output);
914
 
          }
915
 
          assertEquals(ent.getKey().length, stopNode[0]);
916
 
        }
917
 
      }
918
 
    }
919
 
  }
920
 
 
921
 
  public void testRandomWords() throws IOException {
922
 
    testRandomWords(1000, atLeast(2));
923
 
    //testRandomWords(20, 100);
924
 
  }
925
 
 
926
 
  private String inputModeToString(int mode) {
927
 
    if (mode == 0) {
928
 
      return "utf8";
929
 
    } else {
930
 
      return "utf32";
931
 
    }
932
 
  }
933
 
 
934
 
  private void testRandomWords(int maxNumWords, int numIter) throws IOException {
935
 
    for(int iter=0;iter<numIter;iter++) {
936
 
      if (VERBOSE) {
937
 
        System.out.println("\nTEST: iter " + iter);
938
 
      }
939
 
      for(int inputMode=0;inputMode<2;inputMode++) {
940
 
        final int numWords = random.nextInt(maxNumWords+1);
941
 
        Set<IntsRef> termsSet = new HashSet<IntsRef>();
942
 
        IntsRef[] terms = new IntsRef[numWords];
943
 
        while(termsSet.size() < numWords) {
944
 
          final String term = getRandomString();
945
 
          termsSet.add(toIntsRef(term, inputMode));
946
 
        }
947
 
        doTest(inputMode, termsSet.toArray(new IntsRef[termsSet.size()]));
948
 
      }
949
 
    }
950
 
  }
951
 
 
952
 
  static String getRandomString() {
953
 
    final String term;
954
 
    if (random.nextBoolean()) {
955
 
      term = _TestUtil.randomRealisticUnicodeString(random);
956
 
    } else {
957
 
      // we want to mix in limited-alphabet symbols so
958
 
      // we get more sharing of the nodes given how few
959
 
      // terms we are testing...
960
 
      term = simpleRandomString(random);
961
 
    }
962
 
    return term;
963
 
  }
964
 
 
965
 
  @Nightly
966
 
  public void testBigSet() throws IOException {
967
 
    testRandomWords(_TestUtil.nextInt(random, 50000, 60000), 1);
968
 
  }
969
 
  
970
 
  private static String inputToString(int inputMode, IntsRef term) {
971
 
    return inputToString(inputMode, term, true);
972
 
  }
973
 
 
974
 
  private static String inputToString(int inputMode, IntsRef term, boolean isValidUnicode) {
975
 
    if (!isValidUnicode) {
976
 
      return term.toString();
977
 
    } else if (inputMode == 0) {
978
 
      // utf8
979
 
      return toBytesRef(term).utf8ToString() + " " + term;
980
 
    } else {
981
 
      // utf32
982
 
      return UnicodeUtil.newString(term.ints, term.offset, term.length) + " " + term;
983
 
    }
984
 
  }
985
 
 
986
 
  private static IntsRef toIntsRef(String s) {
987
 
    final int charCount = s.length();
988
 
    IntsRef ir = new IntsRef(charCount);
989
 
    for(int charIDX=0;charIDX<charCount;charIDX++) {
990
 
      ir.ints[charIDX] = s.charAt(charIDX);
991
 
    }
992
 
    ir.length = charCount;
993
 
    return ir;
994
 
  }
995
 
 
996
 
  private static String toString(IntsRef ints) {
997
 
    char[] chars = new char[ints.length];
998
 
    for(int charIDX=0;charIDX<ints.length;charIDX++) {
999
 
      final int ch = ints.ints[ints.offset+charIDX];
1000
 
      assertTrue(ch >= 0 && ch < 65536);
1001
 
      chars[charIDX] = (char) ch;
1002
 
    }
1003
 
    return new String(chars);
1004
 
  }
1005
 
 
1006
 
  // Build FST for all unique terms in the test line docs
1007
 
  // file, up until a time limit
1008
 
  public void testRealTerms() throws Exception {
1009
 
 
1010
 
    /*
1011
 
    if (CodecProvider.getDefault().getDefaultFieldCodec().equals("SimpleText")) {
1012
 
      // no
1013
 
      CodecProvider.getDefault().setDefaultFieldCodec("Standard");
1014
 
    }
1015
 
    */
1016
 
 
1017
 
    final LineFileDocs docs = new LineFileDocs(random);
1018
 
    final int RUN_TIME_MSEC = atLeast(500);
1019
 
    final IndexWriterConfig conf = newIndexWriterConfig(TEST_VERSION_CURRENT, new MockAnalyzer(random)).setMaxBufferedDocs(-1).setRAMBufferSizeMB(64);
1020
 
    final File tempDir = _TestUtil.getTempDir("fstlines");
1021
 
    final MockDirectoryWrapper dir = newFSDirectory(tempDir);
1022
 
    final IndexWriter writer = new IndexWriter(dir, conf);
1023
 
    writer.setInfoStream(VERBOSE ? System.out : null);
1024
 
    final long stopTime = System.currentTimeMillis() + RUN_TIME_MSEC;
1025
 
    Document doc;
1026
 
    int docCount = 0;
1027
 
    while((doc = docs.nextDoc()) != null && System.currentTimeMillis() < stopTime) {
1028
 
      writer.addDocument(doc);
1029
 
      docCount++;
1030
 
    }
1031
 
    IndexReader r = IndexReader.open(writer, true);
1032
 
    writer.close();
1033
 
    final PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton(random.nextBoolean());
1034
 
    Builder<Long> builder = new Builder<Long>(FST.INPUT_TYPE.BYTE2, outputs);
1035
 
 
1036
 
    boolean storeOrd = false;
1037
 
    if (VERBOSE) {
1038
 
      if (storeOrd) {
1039
 
        System.out.println("FST stores ord");
1040
 
      } else {
1041
 
        System.out.println("FST stores docFreq");
1042
 
      }
1043
 
    }
1044
 
    TermEnum termEnum = r.terms(new Term("body", ""));
1045
 
    if (VERBOSE) {
1046
 
      System.out.println("TEST: got termEnum=" + termEnum);
1047
 
    }
1048
 
    int ord = 0;
1049
 
    while(true) {
1050
 
      final Term term = termEnum.term();
1051
 
      if (term == null || !"body".equals(term.field())) {
1052
 
        break;
1053
 
      }
1054
 
 
1055
 
      // No ord in 3.x:
1056
 
      /*
1057
 
      if (ord == 0) {
1058
 
        try {
1059
 
          termsEnum.ord();
1060
 
        } catch (UnsupportedOperationException uoe) {
1061
 
          if (VERBOSE) {
1062
 
            System.out.println("TEST: codec doesn't support ord; FST stores docFreq");
1063
 
          }
1064
 
          storeOrd = false;
1065
 
        }
1066
 
      }
1067
 
      */
1068
 
      final int output;
1069
 
      if (storeOrd) {
1070
 
        output = ord;
1071
 
      } else {
1072
 
        output = termEnum.docFreq();
1073
 
      }
1074
 
      //System.out.println("ADD: " + term.text() + " ch[0]=" + (term.text().length() == 0 ? -1 : term.text().charAt(0)));
1075
 
      builder.add(toIntsRef(term.text()), outputs.get(output));
1076
 
      ord++;
1077
 
      if (VERBOSE && ord % 100000 == 0 && LuceneTestCase.TEST_NIGHTLY) {
1078
 
        System.out.println(ord + " terms...");
1079
 
      }
1080
 
      termEnum.next();
1081
 
    }
1082
 
    final FST<Long> fst = builder.finish();
1083
 
    if (VERBOSE) {
1084
 
      System.out.println("FST: " + docCount + " docs; " + ord + " terms; " + fst.getNodeCount() + " nodes; " + fst.getArcCount() + " arcs;" + " " + fst.sizeInBytes() + " bytes");
1085
 
    }
1086
 
 
1087
 
    if (ord > 0) {
1088
 
      // Now confirm BytesRefFSTEnum and TermEnum act the
1089
 
      // same:
1090
 
      final IntsRefFSTEnum<Long> fstEnum = new IntsRefFSTEnum<Long>(fst);
1091
 
      int num = atLeast(1000);
1092
 
      for(int iter=0;iter<num;iter++) {
1093
 
        final String randomTerm = getRandomString();
1094
 
 
1095
 
        if (VERBOSE) {
1096
 
          System.out.println("TEST: seek " + randomTerm + " ch[0]=" + (randomTerm.length() == 0 ? -1 : randomTerm.charAt(0)));
1097
 
        }
1098
 
 
1099
 
        termEnum = r.terms(new Term("body", randomTerm));
1100
 
        final IntsRefFSTEnum.InputOutput fstSeekResult = fstEnum.seekCeil(toIntsRef(randomTerm));
1101
 
 
1102
 
        if (termEnum.term() == null || !"body".equals(termEnum.term().field())) {
1103
 
          assertNull("got " + (fstSeekResult == null ? "null" : toString(fstSeekResult.input) + " but expected null"), fstSeekResult);
1104
 
        } else {
1105
 
          assertSame(termEnum, fstEnum, storeOrd);
1106
 
          for(int nextIter=0;nextIter<10;nextIter++) {
1107
 
            if (VERBOSE) {
1108
 
              System.out.println("TEST: next");
1109
 
              //if (storeOrd) {
1110
 
              //System.out.println("  ord=" + termEnum.ord());
1111
 
              //}
1112
 
            }
1113
 
            termEnum.next();
1114
 
            if (termEnum.term() != null && "body".equals(termEnum.term().field())) {
1115
 
              if (VERBOSE) {
1116
 
                System.out.println("  term=" + termEnum.term());
1117
 
              }
1118
 
              assertNotNull(fstEnum.next());
1119
 
              assertSame(termEnum, fstEnum, storeOrd);
1120
 
            } else {
1121
 
              if (VERBOSE) {
1122
 
                System.out.println("  end!");
1123
 
              }
1124
 
              IntsRefFSTEnum.InputOutput<Long> nextResult = fstEnum.next();
1125
 
              if (nextResult != null) {
1126
 
                System.out.println("expected null but got: input=" + toString(nextResult.input) + " output=" + outputs.outputToString(nextResult.output));
1127
 
                fail();
1128
 
              }
1129
 
              break;
1130
 
            }
1131
 
          }
1132
 
        }
1133
 
      }
1134
 
    }
1135
 
 
1136
 
    r.close();
1137
 
    dir.close();
1138
 
  }
1139
 
 
1140
 
  private void assertSame(TermEnum termEnum, IntsRefFSTEnum fstEnum, boolean storeOrd) throws Exception {
1141
 
    if (termEnum.term() == null || !"body".equals(termEnum.term().field())) {
1142
 
      if (fstEnum.current() != null) {
1143
 
        fail("fstEnum.current().input=" + toString(fstEnum.current().input));
1144
 
      }
1145
 
    } else {
1146
 
      assertNotNull(fstEnum.current());
1147
 
      assertEquals(termEnum.term() + " != " + toString(fstEnum.current().input), termEnum.term().text(), toString(fstEnum.current().input));
1148
 
      if (storeOrd) {
1149
 
        // fst stored the ord
1150
 
        // No ord in 3.x
1151
 
        // assertEquals(termEnum.ord(), ((Long) fstEnum.current().output).longValue());
1152
 
      } else {
1153
 
        // fst stored the docFreq
1154
 
        assertEquals(termEnum.docFreq(), (int) (((Long) fstEnum.current().output).longValue()));
1155
 
      }
1156
 
    }
1157
 
  }
1158
 
 
1159
 
  private static abstract class VisitTerms<T> {
1160
 
    private final String dirOut;
1161
 
    private final String wordsFileIn;
1162
 
    private int inputMode;
1163
 
    private final Outputs<T> outputs;
1164
 
    private final Builder<T> builder;
1165
 
 
1166
 
    public VisitTerms(String dirOut, String wordsFileIn, int inputMode, int prune, Outputs<T> outputs) {
1167
 
      this.dirOut = dirOut;
1168
 
      this.wordsFileIn = wordsFileIn;
1169
 
      this.inputMode = inputMode;
1170
 
      this.outputs = outputs;
1171
 
      
1172
 
      builder = new Builder<T>(inputMode == 0 ? FST.INPUT_TYPE.BYTE1 : FST.INPUT_TYPE.BYTE4, 0, prune, prune == 0, true, Integer.MAX_VALUE, outputs);
1173
 
    }
1174
 
 
1175
 
    protected abstract T getOutput(IntsRef input, int ord) throws IOException;
1176
 
 
1177
 
    public void run(int limit, boolean verify) throws IOException {
1178
 
      BufferedReader is = new BufferedReader(new InputStreamReader(new FileInputStream(wordsFileIn), "UTF-8"), 65536);
1179
 
      try {
1180
 
        final IntsRef intsRef = new IntsRef(10);
1181
 
        long tStart = System.currentTimeMillis();
1182
 
        int ord = 0;
1183
 
        while(true) {
1184
 
          String w = is.readLine();
1185
 
          if (w == null) {
1186
 
            break;
1187
 
          }
1188
 
          toIntsRef(w, inputMode, intsRef);
1189
 
          builder.add(intsRef,
1190
 
                      getOutput(intsRef, ord));
1191
 
 
1192
 
          ord++;
1193
 
          if (ord % 500000 == 0) {
1194
 
            System.out.println(
1195
 
                String.format(Locale.ENGLISH, 
1196
 
                    "%6.2fs: %9d...", ((System.currentTimeMillis() - tStart) / 1000.0), ord));
1197
 
          }
1198
 
          if (ord >= limit) {
1199
 
            break;
1200
 
          }
1201
 
        }
1202
 
 
1203
 
        assert builder.getTermCount() == ord;
1204
 
        final FST<T> fst = builder.finish();
1205
 
        if (fst == null) {
1206
 
          System.out.println("FST was fully pruned!");
1207
 
          System.exit(0);
1208
 
        }
1209
 
 
1210
 
        if (dirOut == null)
1211
 
          return;
1212
 
 
1213
 
        System.out.println(ord + " terms; " + fst.getNodeCount() + " nodes; " + fst.getArcCount() + " arcs; " + fst.getArcWithOutputCount() + " arcs w/ output; tot size " + fst.sizeInBytes());
1214
 
        if (fst.getNodeCount() < 100) {
1215
 
          Writer w = new OutputStreamWriter(new FileOutputStream("out.dot"), "UTF-8");
1216
 
          Util.toDot(fst, w, false, false);
1217
 
          w.close();
1218
 
          System.out.println("Wrote FST to out.dot");
1219
 
        }
1220
 
 
1221
 
        Directory dir = FSDirectory.open(new File(dirOut));
1222
 
        IndexOutput out = dir.createOutput("fst.bin");
1223
 
        fst.save(out);
1224
 
        out.close();
1225
 
 
1226
 
        System.out.println("Saved FST to fst.bin.");
1227
 
 
1228
 
        if (!verify) {
1229
 
          return;
1230
 
        }
1231
 
 
1232
 
        System.out.println("\nNow verify...");
1233
 
 
1234
 
        is.close();
1235
 
        is = new BufferedReader(new InputStreamReader(new FileInputStream(wordsFileIn), "UTF-8"), 65536);
1236
 
 
1237
 
        ord = 0;
1238
 
        tStart = System.currentTimeMillis();
1239
 
        while(true) {
1240
 
          String w = is.readLine();
1241
 
          if (w == null) {
1242
 
            break;
1243
 
          }
1244
 
          toIntsRef(w, inputMode, intsRef);
1245
 
          T expected = getOutput(intsRef, ord);
1246
 
          T actual = Util.get(fst, intsRef);
1247
 
          if (actual == null) {
1248
 
            throw new RuntimeException("unexpected null output on input=" + w);
1249
 
          }
1250
 
          if (!actual.equals(expected)) {
1251
 
            throw new RuntimeException("wrong output (got " + outputs.outputToString(actual) + " but expected " + outputs.outputToString(expected) + ") on input=" + w);
1252
 
          }
1253
 
 
1254
 
          ord++;
1255
 
          if (ord % 500000 == 0) {
1256
 
            System.out.println(((System.currentTimeMillis()-tStart)/1000.0) + "s: " + ord + "...");
1257
 
          }
1258
 
          if (ord >= limit) {
1259
 
            break;
1260
 
          }
1261
 
        }
1262
 
 
1263
 
        double totSec = ((System.currentTimeMillis() - tStart)/1000.0);
1264
 
        System.out.println("Verify took " + totSec + " sec + (" + (int) ((totSec*1000000000/ord)) + " nsec per lookup)");
1265
 
 
1266
 
      } finally {
1267
 
        is.close();
1268
 
      }
1269
 
    }
1270
 
  }
1271
 
 
1272
 
  // java -cp build/classes/test:build/classes/java:build/classes/test-framework:lib/junit-4.7.jar org.apache.lucene.util.fst.TestFSTs /x/tmp/allTerms3.txt out
1273
 
  public static void main(String[] args) throws IOException {
1274
 
    int prune = 0;
1275
 
    int limit = Integer.MAX_VALUE;
1276
 
    int inputMode = 0;                             // utf8
1277
 
    boolean storeOrds = false;
1278
 
    boolean storeDocFreqs = false;
1279
 
    boolean verify = true;
1280
 
    
1281
 
    String wordsFileIn = null;
1282
 
    String dirOut = null;
1283
 
 
1284
 
    int idx = 0;
1285
 
    while (idx < args.length) {
1286
 
      if (args[idx].equals("-prune")) {
1287
 
        prune = Integer.valueOf(args[1 + idx]);
1288
 
        idx++;
1289
 
      } else if (args[idx].equals("-limit")) {
1290
 
        limit = Integer.valueOf(args[1 + idx]);
1291
 
        idx++;
1292
 
      } else if (args[idx].equals("-utf8")) {
1293
 
        inputMode = 0;
1294
 
      } else if (args[idx].equals("-utf32")) {
1295
 
        inputMode = 1;
1296
 
      } else if (args[idx].equals("-docFreq")) {
1297
 
        storeDocFreqs = true;
1298
 
      } else if (args[idx].equals("-ords")) {
1299
 
        storeOrds = true;
1300
 
      } else if (args[idx].equals("-noverify")) {
1301
 
        verify = false;
1302
 
      } else if (args[idx].startsWith("-")) {
1303
 
        System.err.println("Unrecognized option: " + args[idx]);
1304
 
        System.exit(-1);
1305
 
      } else {
1306
 
        if (wordsFileIn == null) {
1307
 
          wordsFileIn = args[idx];
1308
 
        } else if (dirOut == null) {
1309
 
          dirOut = args[idx];
1310
 
        } else {
1311
 
          System.err.println("Too many arguments, expected: input [output]");
1312
 
          System.exit(-1);
1313
 
        }
1314
 
      }
1315
 
      idx++;
1316
 
    }
1317
 
    
1318
 
    if (wordsFileIn == null) {
1319
 
      System.err.println("No input file.");
1320
 
      System.exit(-1);
1321
 
    }
1322
 
 
1323
 
    // ord benefits from share, docFreqs don't:
1324
 
 
1325
 
    if (storeOrds && storeDocFreqs) {
1326
 
      // Store both ord & docFreq:
1327
 
      final PositiveIntOutputs o1 = PositiveIntOutputs.getSingleton(true);
1328
 
      final PositiveIntOutputs o2 = PositiveIntOutputs.getSingleton(false);
1329
 
      final PairOutputs<Long,Long> outputs = new PairOutputs<Long,Long>(o1, o2);
1330
 
      new VisitTerms<PairOutputs.Pair<Long,Long>>(dirOut, wordsFileIn, inputMode, prune, outputs) {
1331
 
        Random rand;
1332
 
        @Override
1333
 
        public PairOutputs.Pair<Long,Long> getOutput(IntsRef input, int ord) {
1334
 
          if (ord == 0) {
1335
 
            rand = new Random(17);
1336
 
          }
1337
 
          return new PairOutputs.Pair<Long,Long>(o1.get(ord),
1338
 
                                                 o2.get(_TestUtil.nextInt(rand, 1, 5000)));
1339
 
        }
1340
 
      }.run(limit, verify);
1341
 
    } else if (storeOrds) {
1342
 
      // Store only ords
1343
 
      final PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton(true);
1344
 
      new VisitTerms<Long>(dirOut, wordsFileIn, inputMode, prune, outputs) {
1345
 
        @Override
1346
 
        public Long getOutput(IntsRef input, int ord) {
1347
 
          return outputs.get(ord);
1348
 
        }
1349
 
      }.run(limit, verify);
1350
 
    } else if (storeDocFreqs) {
1351
 
      // Store only docFreq
1352
 
      final PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton(false);
1353
 
      new VisitTerms<Long>(dirOut, wordsFileIn, inputMode, prune, outputs) {
1354
 
        Random rand;
1355
 
        @Override
1356
 
        public Long getOutput(IntsRef input, int ord) {
1357
 
          if (ord == 0) {
1358
 
            rand = new Random(17);
1359
 
          }
1360
 
          return outputs.get(_TestUtil.nextInt(rand, 1, 5000));
1361
 
        }
1362
 
      }.run(limit, verify);
1363
 
    } else {
1364
 
      // Store nothing
1365
 
      final NoOutputs outputs = NoOutputs.getSingleton();
1366
 
      final Object NO_OUTPUT = outputs.getNoOutput();
1367
 
      new VisitTerms<Object>(dirOut, wordsFileIn, inputMode, prune, outputs) {
1368
 
        @Override
1369
 
        public Object getOutput(IntsRef input, int ord) {
1370
 
          return NO_OUTPUT;
1371
 
        }
1372
 
      }.run(limit, verify);
1373
 
    }
1374
 
  }
1375
 
 
1376
 
  public void testSingleString() throws Exception {
1377
 
    final Outputs<Object> outputs = NoOutputs.getSingleton();
1378
 
    final Builder<Object> b = new Builder<Object>(FST.INPUT_TYPE.BYTE1, outputs);
1379
 
    b.add(new BytesRef("foobar"), outputs.getNoOutput());
1380
 
    final BytesRefFSTEnum<Object> fstEnum = new BytesRefFSTEnum<Object>(b.finish());
1381
 
    assertNull(fstEnum.seekFloor(new BytesRef("foo")));
1382
 
    assertNull(fstEnum.seekCeil(new BytesRef("foobaz")));
1383
 
  }
1384
 
 
1385
 
  public void testSimple() throws Exception {
1386
 
 
1387
 
    // Get outputs -- passing true means FST will share
1388
 
    // (delta code) the outputs.  This should result in
1389
 
    // smaller FST if the outputs grow monotonically.  But
1390
 
    // if numbers are "random", false should give smaller
1391
 
    // final size:
1392
 
    final PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton(true);
1393
 
 
1394
 
    // Build an FST mapping BytesRef -> Long
1395
 
    final Builder<Long> builder = new Builder<Long>(FST.INPUT_TYPE.BYTE1, outputs);
1396
 
 
1397
 
    final BytesRef a = new BytesRef("a");
1398
 
    final BytesRef b = new BytesRef("b");
1399
 
    final BytesRef c = new BytesRef("c");
1400
 
 
1401
 
    builder.add(a, outputs.get(17));
1402
 
    builder.add(b, outputs.get(42));
1403
 
    builder.add(c, outputs.get(13824324872317238L));
1404
 
 
1405
 
    final FST<Long> fst = builder.finish();
1406
 
 
1407
 
    assertEquals(13824324872317238L, (long) Util.get(fst, c));
1408
 
    assertEquals(42, (long) Util.get(fst, b));
1409
 
    assertEquals(17, (long) Util.get(fst, a));
1410
 
 
1411
 
    BytesRefFSTEnum<Long> fstEnum = new BytesRefFSTEnum<Long>(fst);
1412
 
    BytesRefFSTEnum.InputOutput<Long> seekResult;
1413
 
    seekResult = fstEnum.seekFloor(a);
1414
 
    assertNotNull(seekResult);
1415
 
    assertEquals(17, (long) seekResult.output);
1416
 
 
1417
 
    // goes to a
1418
 
    seekResult = fstEnum.seekFloor(new BytesRef("aa"));
1419
 
    assertNotNull(seekResult);
1420
 
    assertEquals(17, (long) seekResult.output);
1421
 
 
1422
 
    // goes to b
1423
 
    seekResult = fstEnum.seekCeil(new BytesRef("aa"));
1424
 
    assertNotNull(seekResult);
1425
 
    assertEquals(b, seekResult.input);
1426
 
    assertEquals(42, (long) seekResult.output);
1427
 
  }
1428
 
 
1429
 
  /**
1430
 
   * Test state expansion (array format) on close-to-root states. Creates
1431
 
   * synthetic input that has one expanded state on each level.
1432
 
   * 
1433
 
   * @see "https://issues.apache.org/jira/browse/LUCENE-2933" 
1434
 
   */
1435
 
  public void testExpandedCloseToRoot() throws Exception {
1436
 
    class SyntheticData {
1437
 
      FST<Object> compile(String[] lines) throws IOException {
1438
 
        final NoOutputs outputs = NoOutputs.getSingleton();
1439
 
        final Object nothing = outputs.getNoOutput();
1440
 
        final Builder<Object> b = new Builder<Object>(FST.INPUT_TYPE.BYTE1, outputs);
1441
 
 
1442
 
        int line = 0;
1443
 
        final BytesRef term = new BytesRef();
1444
 
        while (line < lines.length) {
1445
 
          String w = lines[line++];
1446
 
          if (w == null) {
1447
 
            break;
1448
 
          }
1449
 
          term.copy(w);
1450
 
          b.add(term, nothing);
1451
 
        }
1452
 
        
1453
 
        return b.finish();
1454
 
      }
1455
 
      
1456
 
      void generate(ArrayList<String> out, StringBuilder b, char from, char to,
1457
 
          int depth) {
1458
 
        if (depth == 0 || from == to) {
1459
 
          String seq = b.toString() + "_" + out.size() + "_end";
1460
 
          out.add(seq);
1461
 
        } else {
1462
 
          for (char c = from; c <= to; c++) {
1463
 
            b.append(c);
1464
 
            generate(out, b, from, c == to ? to : from, depth - 1);
1465
 
            b.deleteCharAt(b.length() - 1);
1466
 
          }
1467
 
        }
1468
 
      }
1469
 
 
1470
 
      public int verifyStateAndBelow(FST<Object> fst, Arc<Object> arc, int depth) 
1471
 
        throws IOException {
1472
 
        if (fst.targetHasArcs(arc)) {
1473
 
          int childCount = 0;
1474
 
          for (arc = fst.readFirstTargetArc(arc, arc);; 
1475
 
               arc = fst.readNextArc(arc), childCount++)
1476
 
          {
1477
 
            boolean expanded = fst.isExpandedTarget(arc);
1478
 
            int children = verifyStateAndBelow(fst, new FST.Arc<Object>().copyFrom(arc), depth + 1);
1479
 
 
1480
 
            assertEquals(
1481
 
                expanded,
1482
 
                (depth <= FST.FIXED_ARRAY_SHALLOW_DISTANCE && 
1483
 
                    children >= FST.FIXED_ARRAY_NUM_ARCS_SHALLOW) ||
1484
 
                 children >= FST.FIXED_ARRAY_NUM_ARCS_DEEP);
1485
 
            if (arc.isLast()) break;
1486
 
          }
1487
 
 
1488
 
          return childCount;
1489
 
        }
1490
 
        return 0;
1491
 
      }
1492
 
    }
1493
 
 
1494
 
    // Sanity check.
1495
 
    assertTrue(FST.FIXED_ARRAY_NUM_ARCS_SHALLOW < FST.FIXED_ARRAY_NUM_ARCS_DEEP);
1496
 
    assertTrue(FST.FIXED_ARRAY_SHALLOW_DISTANCE >= 0);
1497
 
 
1498
 
    SyntheticData s = new SyntheticData();
1499
 
 
1500
 
    ArrayList<String> out = new ArrayList<String>();
1501
 
    StringBuilder b = new StringBuilder();
1502
 
    s.generate(out, b, 'a', 'i', 10);
1503
 
    String[] input = out.toArray(new String[out.size()]);
1504
 
    Arrays.sort(input);
1505
 
    FST<Object> fst = s.compile(input);
1506
 
    FST.Arc<Object> arc = fst.getFirstArc(new FST.Arc<Object>());
1507
 
    s.verifyStateAndBelow(fst, arc, 1);
1508
 
  }
1509
 
 
1510
 
  // Make sure raw FST can differentiate between final vs
1511
 
  // non-final end nodes
1512
 
  public void testNonFinalStopNodes() throws Exception {
1513
 
    final PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton(true);
1514
 
    final Long nothing = outputs.getNoOutput();
1515
 
    final Builder<Long> b = new Builder<Long>(FST.INPUT_TYPE.BYTE1, outputs);
1516
 
 
1517
 
    final FST<Long> fst = new FST<Long>(FST.INPUT_TYPE.BYTE1, outputs);
1518
 
 
1519
 
    final Builder.UnCompiledNode<Long> rootNode = new Builder.UnCompiledNode<Long>(b, 0);
1520
 
 
1521
 
    // Add final stop node
1522
 
    {
1523
 
      final Builder.UnCompiledNode<Long> node = new Builder.UnCompiledNode<Long>(b, 0);
1524
 
      node.isFinal = true;
1525
 
      rootNode.addArc('a', node);
1526
 
      final Builder.CompiledNode frozen = new Builder.CompiledNode();
1527
 
      frozen.address = fst.addNode(node);
1528
 
      rootNode.arcs[0].nextFinalOutput = outputs.get(17);
1529
 
      rootNode.arcs[0].isFinal = true;
1530
 
      rootNode.arcs[0].output = nothing;
1531
 
      rootNode.arcs[0].target = frozen;
1532
 
    }
1533
 
 
1534
 
    // Add non-final stop node
1535
 
    {
1536
 
      final Builder.UnCompiledNode<Long> node = new Builder.UnCompiledNode<Long>(b, 0);
1537
 
      rootNode.addArc('b', node);
1538
 
      final Builder.CompiledNode frozen = new Builder.CompiledNode();
1539
 
      frozen.address = fst.addNode(node);
1540
 
      rootNode.arcs[1].nextFinalOutput = nothing;
1541
 
      rootNode.arcs[1].output = outputs.get(42);
1542
 
      rootNode.arcs[1].target = frozen;
1543
 
    }
1544
 
 
1545
 
    fst.finish(fst.addNode(rootNode));
1546
 
    
1547
 
    checkStopNodes(fst, outputs);
1548
 
 
1549
 
    // Make sure it still works after save/load:
1550
 
    Directory dir = newDirectory();
1551
 
    IndexOutput out = dir.createOutput("fst");
1552
 
    fst.save(out);
1553
 
    out.close();
1554
 
 
1555
 
    IndexInput in = dir.openInput("fst");
1556
 
    final FST<Long> fst2 = new FST<Long>(in, outputs);
1557
 
    checkStopNodes(fst2, outputs);
1558
 
    in.close();
1559
 
    dir.close();
1560
 
  }
1561
 
 
1562
 
  private void checkStopNodes(FST<Long> fst, PositiveIntOutputs outputs) throws Exception {
1563
 
    final Long nothing = outputs.getNoOutput();
1564
 
    FST.Arc<Long> startArc = fst.getFirstArc(new FST.Arc<Long>());
1565
 
    assertEquals(nothing, startArc.output);
1566
 
    assertEquals(nothing, startArc.nextFinalOutput);
1567
 
 
1568
 
    FST.Arc<Long> arc = fst.readFirstTargetArc(startArc, new FST.Arc<Long>());
1569
 
    assertEquals('a', arc.label);
1570
 
    assertEquals(17, arc.nextFinalOutput.longValue());
1571
 
    assertTrue(arc.isFinal());
1572
 
 
1573
 
    arc = fst.readNextArc(arc);
1574
 
    assertEquals('b', arc.label);
1575
 
    assertFalse(arc.isFinal());
1576
 
    assertEquals(42, arc.output.longValue());
1577
 
  }
1578
 
}