using Lucene.Net.Store;
using Lucene.Net.Support;
using Lucene.Net.Util.Packed;
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using Console = Lucene.Net.Support.SystemConsole;
using Debug = Lucene.Net.Diagnostics.Debug; // LUCENENET NOTE: We cannot use System.Diagnostics.Debug because those calls will be optimized out of the release!
using Assert = Lucene.Net.TestFramework.Assert;
using Directory = Lucene.Net.Store.Directory;

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

    /// <summary>
    /// Holds one input/output pair. </summary>
    public class InputOutput<T> : IComparable<InputOutput<T>>
    {
        public Int32sRef Input { get; private set; }
        public T Output { get; private set; }

        public InputOutput(Int32sRef input, T output)
        {
            this.Input = input;
            this.Output = output;
        }

        public virtual int CompareTo(InputOutput<T> other)
        {
            return this.Input.CompareTo(other.Input);
        }
    }

    /// <summary>
    /// Helper class to test FSTs. </summary>
    public class FSTTester<T>
    {
        internal readonly Random random;
        internal readonly IList<InputOutput<T>> pairs;
        internal readonly int inputMode;
        internal readonly Outputs<T> outputs;
        internal readonly Directory dir;
        internal readonly bool doReverseLookup;

        public FSTTester(Random random, Directory dir, int inputMode, IList<InputOutput<T>> pairs, Outputs<T> outputs, bool doReverseLookup)
        {
            this.random = random;
            this.dir = dir;
            this.inputMode = inputMode;
            this.pairs = pairs;
            this.outputs = outputs;
            this.doReverseLookup = doReverseLookup;
        }

        internal static string InputToString(int inputMode, Int32sRef term)
        {
            return InputToString(inputMode, term, true);
        }

        internal static string InputToString(int inputMode, Int32sRef term, bool isValidUnicode)
        {
            if (!isValidUnicode)
            {
                return term.ToString();
            }
            else if (inputMode == 0)
            {
                // utf8
                return ToBytesRef(term).Utf8ToString() + " " + term;
            }
            else
            {
                // utf32
                return UnicodeUtil.NewString(term.Int32s, term.Offset, term.Length) + " " + term;
            }
        }

        private static BytesRef ToBytesRef(Int32sRef ir)
        {
            BytesRef br = new BytesRef(ir.Length);
            for (int i = 0; i < ir.Length; i++)
            {
                int x = ir.Int32s[ir.Offset + i];
                Debug.Assert(x >= 0 && x <= 255);
                br.Bytes[i] = (byte)x;
            }
            br.Length = ir.Length;
            return br;
        }

        internal static string GetRandomString(Random random)
        {
            string term;
            if (random.NextBoolean())
            {
                term = TestUtil.RandomRealisticUnicodeString(random);
            }
            else
            {
                // we want to mix in limited-alphabet symbols so
                // we get more sharing of the nodes given how few
                // terms we are testing...
                term = SimpleRandomString(random);
            }
            return term;
        }

        internal static string SimpleRandomString(Random r)
        {
            int end = r.Next(10);
            if (end == 0)
            {
                // allow 0 length
                return "";
            }
            char[] buffer = new char[end];
            for (int i = 0; i < end; i++)
            {
                buffer[i] = (char)TestUtil.NextInt32(r, 97, 102);
            }
            return new string(buffer, 0, end);
        }

        internal static Int32sRef ToInt32sRef(string s, int inputMode)
        {
            return ToInt32sRef(s, inputMode, new Int32sRef(10));
        }

        internal static Int32sRef ToInt32sRef(string s, int inputMode, Int32sRef ir)
        {
            if (inputMode == 0)
            {
                // utf8
                return ToInt32sRef(new BytesRef(s), ir);
            }
            else
            {
                // utf32
                return ToInt32sRefUTF32(s, ir);
            }
        }

        internal static Int32sRef ToInt32sRefUTF32(string s, Int32sRef ir)
        {
            int charLength = s.Length;
            int charIdx = 0;
            int intIdx = 0;
            while (charIdx < charLength)
            {
                if (intIdx == ir.Int32s.Length)
                {
                    ir.Grow(intIdx + 1);
                }
                int utf32 = Character.CodePointAt(s, charIdx);
                ir.Int32s[intIdx] = utf32;
                charIdx += Character.CharCount(utf32);
                intIdx++;
            }
            ir.Length = intIdx;
            return ir;
        }

        internal static Int32sRef ToInt32sRef(BytesRef br, Int32sRef ir)
        {
            if (br.Length > ir.Int32s.Length)
            {
                ir.Grow(br.Length);
            }
            for (int i = 0; i < br.Length; i++)
            {
                ir.Int32s[i] = br.Bytes[br.Offset + i] & 0xFF;
            }
            ir.Length = br.Length;
            return ir;
        }

        // LUCENENET specific - de-nested InputOutput<T>

        public virtual void DoTest(bool testPruning)
        {
            // no pruning
            DoTest(0, 0, true);

            if (testPruning)
            {
                // simple pruning
                DoTest(TestUtil.NextInt32(random, 1, 1 + pairs.Count), 0, true);

                // leafy pruning
                DoTest(0, TestUtil.NextInt32(random, 1, 1 + pairs.Count), true);
            }
        }

        // runs the term, returning the output, or null if term
        // isn't accepted.  if prefixLength is non-null it must be
        // length 1 int array; prefixLength[0] is set to the length
        // of the term prefix that matches
        private T Run(FST<T> fst, Int32sRef term, int[] prefixLength)
        {
            Debug.Assert(prefixLength == null || prefixLength.Length == 1);
            FST.Arc<T> arc = fst.GetFirstArc(new FST.Arc<T>());
            T NO_OUTPUT = fst.Outputs.NoOutput;
            T output = NO_OUTPUT;
            FST.BytesReader fstReader = fst.GetBytesReader();

            for (int i = 0; i <= term.Length; i++)
            {
                int label;
                if (i == term.Length)
                {
                    label = FST.END_LABEL;
                }
                else
                {
                    label = term.Int32s[term.Offset + i];
                }
                // System.out.println("   loop i=" + i + " label=" + label + " output=" + fst.Outputs.outputToString(output) + " curArc: target=" + arc.target + " isFinal?=" + arc.isFinal());
                if (fst.FindTargetArc(label, arc, arc, fstReader) == null)
                {
                    // System.out.println("    not found");
                    if (prefixLength != null)
                    {
                        prefixLength[0] = i;
                        return output;
                    }
                    else
                    {
                        return default(T);
                    }
                }
                output = fst.Outputs.Add(output, arc.Output);
            }

            if (prefixLength != null)
            {
                prefixLength[0] = term.Length;
            }

            return output;
        }

        private T RandomAcceptedWord(FST<T> fst, Int32sRef @in)
        {
            FST.Arc<T> arc = fst.GetFirstArc(new FST.Arc<T>());

            IList<FST.Arc<T>> arcs = new List<FST.Arc<T>>();
            @in.Length = 0;
            @in.Offset = 0;
            T NO_OUTPUT = fst.Outputs.NoOutput;
            T output = NO_OUTPUT;
            FST.BytesReader fstReader = fst.GetBytesReader();

            while (true)
            {
                // read all arcs:
                fst.ReadFirstTargetArc(arc, arc, fstReader);
                arcs.Add((new FST.Arc<T>()).CopyFrom(arc));
                while (!arc.IsLast)
                {
                    fst.ReadNextArc(arc, fstReader);
                    arcs.Add((new FST.Arc<T>()).CopyFrom(arc));
                }

                // pick one
                arc = arcs[random.Next(arcs.Count)];
                arcs.Clear();

                // accumulate output
                output = fst.Outputs.Add(output, arc.Output);

                // append label
                if (arc.Label == FST.END_LABEL)
                {
                    break;
                }

                if (@in.Int32s.Length == @in.Length)
                {
                    @in.Grow(1 + @in.Length);
                }
                @in.Int32s[@in.Length++] = arc.Label;
            }

            return output;
        }

        internal virtual FST<T> DoTest(int prune1, int prune2, bool allowRandomSuffixSharing)
        {
            if (LuceneTestCase.VERBOSE)
            {
                Console.WriteLine("\nTEST: prune1=" + prune1 + " prune2=" + prune2);
            }

            bool willRewrite = random.NextBoolean();

            Builder<T> builder = new Builder<T>(inputMode == 0 ? FST.INPUT_TYPE.BYTE1 : FST.INPUT_TYPE.BYTE4, 
                                                prune1, prune2, 
                                                prune1 == 0 && prune2 == 0, 
                                                allowRandomSuffixSharing ? random.NextBoolean() : true, 
                                                allowRandomSuffixSharing ? TestUtil.NextInt32(random, 1, 10) : int.MaxValue, 
                                                outputs, 
                                                null, 
                                                willRewrite, 
                                                PackedInt32s.DEFAULT, 
                                                true, 
                                                15);
            if (LuceneTestCase.VERBOSE)
            {
                if (willRewrite)
                {
                    Console.WriteLine("TEST: packed FST");
                }
                else
                {
                    Console.WriteLine("TEST: non-packed FST");
                }
            }

            foreach (InputOutput<T> pair in pairs)
            {
                if (pair.Output is IEnumerable)
                {
                    Builder<object> builderObject = builder as Builder<object>;
                    var values = pair.Output as IEnumerable;
                    foreach (object value in values)
                    {
                        builderObject.Add(pair.Input, value);
                    }
                }
                else
                {
                    builder.Add(pair.Input, pair.Output);
                }
            }
            FST<T> fst = builder.Finish();

            if (random.NextBoolean() && fst != null && !willRewrite)
            {
                IOContext context = LuceneTestCase.NewIOContext(random);
                using (IndexOutput @out = dir.CreateOutput("fst.bin", context))
                {
                    fst.Save(@out);
                }
                IndexInput @in = dir.OpenInput("fst.bin", context);
                try
                {
                    fst = new FST<T>(@in, outputs);
                }
                finally
                {
                    @in.Dispose();
                    dir.DeleteFile("fst.bin");
                }
            }

            if (LuceneTestCase.VERBOSE && pairs.Count <= 20 && fst != null)
            {
                using (TextWriter w = new StreamWriter(new FileStream("out.dot", FileMode.OpenOrCreate), Encoding.UTF8))
                {
                    Util.ToDot(fst, w, false, false);
                }
                Console.WriteLine("SAVED out.dot");
            }

            if (LuceneTestCase.VERBOSE)
            {
                if (fst == null)
                {
                    Console.WriteLine("  fst has 0 nodes (fully pruned)");
                }
                else
                {
                    Console.WriteLine("  fst has " + fst.NodeCount + " nodes and " + fst.ArcCount + " arcs");
                }
            }

            if (prune1 == 0 && prune2 == 0)
            {
                VerifyUnPruned(inputMode, fst);
            }
            else
            {
                VerifyPruned(inputMode, fst, prune1, prune2);
            }

            return fst;
        }

        protected virtual bool OutputsEqual(T a, T b)
        {
            // LUCENENET: In .NET, IEnumerables do not automatically test to ensure
            // their values are equal, so we need to do that manually.
            // Note that we are testing the values without regard to whether
            // the enumerable type is nullable.
            return Collections.Equals(a, b);
        }

        // FST is complete
        private void VerifyUnPruned(int inputMode, FST<T> fst)
        {
            FST<long?> fstLong;
            ISet<long?> validOutputs;
            long minLong = long.MaxValue;
            long maxLong = long.MinValue;

            if (doReverseLookup)
            {
                FST<long?> fstLong0 = fst as FST<long?>;
                fstLong = fstLong0;
                validOutputs = new HashSet<long?>();
                foreach (InputOutput<T> pair in pairs)
                {
                    long? output = pair.Output as long?;
                    maxLong = Math.Max(maxLong, output.Value);
                    minLong = Math.Min(minLong, output.Value);
                    validOutputs.Add(output.Value);
                }
            }
            else
            {
                fstLong = null;
                validOutputs = null;
            }

            if (pairs.Count == 0)
            {
                Assert.IsNull(fst);
                return;
            }

            if (LuceneTestCase.VERBOSE)
            {
                Console.WriteLine("TEST: now verify " + pairs.Count + " terms");
                foreach (InputOutput<T> pair in pairs)
                {
                    Assert.IsNotNull(pair);
                    Assert.IsNotNull(pair.Input);
                    Assert.IsNotNull(pair.Output);
                    Console.WriteLine("  " + InputToString(inputMode, pair.Input) + ": " + outputs.OutputToString(pair.Output));
                }
            }

            Assert.IsNotNull(fst);

            // visit valid pairs in order -- make sure all words
            // are accepted, and FSTEnum's next() steps through
            // them correctly
            if (LuceneTestCase.VERBOSE)
            {
                Console.WriteLine("TEST: check valid terms/next()");
            }
            {
                Int32sRefFSTEnum<T> fstEnum = new Int32sRefFSTEnum<T>(fst);
                foreach (InputOutput<T> pair in pairs)
                {
                    Int32sRef term = pair.Input;
                    if (LuceneTestCase.VERBOSE)
                    {
                        Console.WriteLine("TEST: check term=" + InputToString(inputMode, term) + " output=" + fst.Outputs.OutputToString(pair.Output));
                    }
                    T output = Run(fst, term, null);
                    Assert.IsNotNull(output, "term " + InputToString(inputMode, term) + " is not accepted");
                    Assert.IsTrue(OutputsEqual(pair.Output, output));

                    // verify enum's next
                    Int32sRefFSTEnum.InputOutput<T> t = fstEnum.Next();
                    Assert.IsNotNull(t);
                    Assert.AreEqual(term, t.Input, "expected input=" + InputToString(inputMode, term) + " but fstEnum returned " + InputToString(inputMode, t.Input));
                    Assert.IsTrue(OutputsEqual(pair.Output, t.Output));
                }
                Assert.IsNull(fstEnum.Next());
            }

            IDictionary<Int32sRef, T> termsMap = new Dictionary<Int32sRef, T>();
            foreach (InputOutput<T> pair in pairs)
            {
                termsMap[pair.Input] = pair.Output;
            }

            if (doReverseLookup && maxLong > minLong)
            {
                // Do random lookups so we test null (output doesn't
                // exist) case:
                Assert.IsNull(Util.GetByOutput(fstLong, minLong - 7));
                Assert.IsNull(Util.GetByOutput(fstLong, maxLong + 7));

                int num = LuceneTestCase.AtLeast(random, 100);
                for (int iter = 0; iter < num; iter++)
                {
                    long v = TestUtil.NextInt64(random, minLong, maxLong);
                    Int32sRef input = Util.GetByOutput(fstLong, v);
                    Assert.IsTrue(validOutputs.Contains(v) || input == null);
                }
            }

            // find random matching word and make sure it's valid
            if (LuceneTestCase.VERBOSE)
            {
                Console.WriteLine("TEST: verify random accepted terms");
            }
            Int32sRef scratch = new Int32sRef(10);
            int num_ = LuceneTestCase.AtLeast(random, 500);
            for (int iter = 0; iter < num_; iter++)
            {
                T output = RandomAcceptedWord(fst, scratch);
                Assert.IsTrue(termsMap.ContainsKey(scratch), "accepted word " + InputToString(inputMode, scratch) + " is not valid");
                Assert.IsTrue(OutputsEqual(termsMap[scratch], output));

                if (doReverseLookup)
                {
                    //System.out.println("lookup output=" + output + " outs=" + fst.Outputs);
                    Int32sRef input = Util.GetByOutput(fstLong, (output as long?).Value);
                    Assert.IsNotNull(input);
                    //System.out.println("  got " + Util.toBytesRef(input, new BytesRef()).utf8ToString());
                    Assert.AreEqual(scratch, input);
                }
            }

            // test IntsRefFSTEnum.Seek:
            if (LuceneTestCase.VERBOSE)
            {
                Console.WriteLine("TEST: verify seek");
            }
            Int32sRefFSTEnum<T> fstEnum_ = new Int32sRefFSTEnum<T>(fst);
            num_ = LuceneTestCase.AtLeast(random, 100);
            for (int iter = 0; iter < num_; iter++)
            {
                if (LuceneTestCase.VERBOSE)
                {
                    Console.WriteLine("  iter=" + iter);
                }
                if (random.NextBoolean())
                {
                    // seek to term that doesn't exist:
                    while (true)
                    {
                        Int32sRef term = ToInt32sRef(GetRandomString(random), inputMode);
                        int pos = pairs.BinarySearch(new InputOutput<T>(term, default(T)));
                        if (pos < 0)
                        {
                            pos = -(pos + 1);
                            // ok doesn't exist
                            //System.out.println("  seek " + inputToString(inputMode, term));
                            Int32sRefFSTEnum.InputOutput<T> seekResult;
                            if (random.Next(3) == 0)
                            {
                                if (LuceneTestCase.VERBOSE)
                                {
                                    Console.WriteLine("  do non-exist seekExact term=" + InputToString(inputMode, term));
                                }
                                seekResult = fstEnum_.SeekExact(term);
                                pos = -1;
                            }
                            else if (random.NextBoolean())
                            {
                                if (LuceneTestCase.VERBOSE)
                                {
                                    Console.WriteLine("  do non-exist seekFloor term=" + InputToString(inputMode, term));
                                }
                                seekResult = fstEnum_.SeekFloor(term);
                                pos--;
                            }
                            else
                            {
                                if (LuceneTestCase.VERBOSE)
                                {
                                    Console.WriteLine("  do non-exist seekCeil term=" + InputToString(inputMode, term));
                                }
                                seekResult = fstEnum_.SeekCeil(term);
                            }

                            if (pos != -1 && pos < pairs.Count)
                            {
                                //System.out.println("    got " + inputToString(inputMode,seekResult.input) + " output=" + fst.Outputs.outputToString(seekResult.Output));
                                Assert.IsNotNull(seekResult, "got null but expected term=" + InputToString(inputMode, pairs[pos].Input));
                                if (LuceneTestCase.VERBOSE)
                                {
                                    Console.WriteLine("    got " + InputToString(inputMode, seekResult.Input));
                                }
                                Assert.AreEqual(pairs[pos].Input, seekResult.Input, "expected " + InputToString(inputMode, pairs[pos].Input) + " but got " + InputToString(inputMode, seekResult.Input));
                                Assert.IsTrue(OutputsEqual(pairs[pos].Output, seekResult.Output));
                            }
                            else
                            {
                                // seeked before start or beyond end
                                //System.out.println("seek=" + seekTerm);
                                Assert.IsNull(seekResult, "expected null but got " + (seekResult == null ? "null" : InputToString(inputMode, seekResult.Input)));
                                if (LuceneTestCase.VERBOSE)
                                {
                                    Console.WriteLine("    got null");
                                }
                            }

                            break;
                        }
                    }
                }
                else
                {
                    // seek to term that does exist:
                    InputOutput<T> pair = pairs[random.Next(pairs.Count)];
                    Int32sRefFSTEnum.InputOutput<T> seekResult;
                    if (random.Next(3) == 2)
                    {
                        if (LuceneTestCase.VERBOSE)
                        {
                            Console.WriteLine("  do exists seekExact term=" + InputToString(inputMode, pair.Input));
                        }
                        seekResult = fstEnum_.SeekExact(pair.Input);
                    }
                    else if (random.NextBoolean())
                    {
                        if (LuceneTestCase.VERBOSE)
                        {
                            Console.WriteLine("  do exists seekFloor " + InputToString(inputMode, pair.Input));
                        }
                        seekResult = fstEnum_.SeekFloor(pair.Input);
                    }
                    else
                    {
                        if (LuceneTestCase.VERBOSE)
                        {
                            Console.WriteLine("  do exists seekCeil " + InputToString(inputMode, pair.Input));
                        }
                        seekResult = fstEnum_.SeekCeil(pair.Input);
                    }
                    Assert.IsNotNull(seekResult);
                    Assert.AreEqual(pair.Input, seekResult.Input, "got " + InputToString(inputMode, seekResult.Input) + " but expected " + InputToString(inputMode, pair.Input));
                    Assert.IsTrue(OutputsEqual(pair.Output, seekResult.Output));
                }
            }

            if (LuceneTestCase.VERBOSE)
            {
                Console.WriteLine("TEST: mixed next/seek");
            }

            // test mixed next/seek
            num_ = LuceneTestCase.AtLeast(random, 100);
            for (int iter = 0; iter < num_; iter++)
            {
                if (LuceneTestCase.VERBOSE)
                {
                    Console.WriteLine("TEST: iter " + iter);
                }
                // reset:
                fstEnum_ = new Int32sRefFSTEnum<T>(fst);
                int upto = -1;
                while (true)
                {
                    bool isDone = false;
                    if (upto == pairs.Count - 1 || random.NextBoolean())
                    {
                        // next
                        upto++;
                        if (LuceneTestCase.VERBOSE)
                        {
                            Console.WriteLine("  do next");
                        }
                        isDone = fstEnum_.Next() == null;
                    }
                    else if (upto != -1 && upto < 0.75 * pairs.Count && random.NextBoolean())
                    {
                        int attempt = 0;
                        for (; attempt < 10; attempt++)
                        {
                            Int32sRef term = ToInt32sRef(GetRandomString(random), inputMode);
                            if (!termsMap.ContainsKey(term) && term.CompareTo(pairs[upto].Input) > 0)
                            {
                                int pos = pairs.BinarySearch(new InputOutput<T>(term, default(T)));
                                Debug.Assert(pos < 0);
                                upto = -(pos + 1);

                                if (random.NextBoolean())
                                {
                                    upto--;
                                    Assert.IsTrue(upto != -1);
                                    if (LuceneTestCase.VERBOSE)
                                    {
                                        Console.WriteLine("  do non-exist seekFloor(" + InputToString(inputMode, term) + ")");
                                    }
                                    isDone = fstEnum_.SeekFloor(term) == null;
                                }
                                else
                                {
                                    if (LuceneTestCase.VERBOSE)
                                    {
                                        Console.WriteLine("  do non-exist seekCeil(" + InputToString(inputMode, term) + ")");
                                    }
                                    isDone = fstEnum_.SeekCeil(term) == null;
                                }

                                break;
                            }
                        }
                        if (attempt == 10)
                        {
                            continue;
                        }
                    }
                    else
                    {
                        int inc = random.Next(pairs.Count - upto - 1);
                        upto += inc;
                        if (upto == -1)
                        {
                            upto = 0;
                        }

                        if (random.NextBoolean())
                        {
                            if (LuceneTestCase.VERBOSE)
                            {
                                Console.WriteLine("  do seekCeil(" + InputToString(inputMode, pairs[upto].Input) + ")");
                            }
                            isDone = fstEnum_.SeekCeil(pairs[upto].Input) == null;
                        }
                        else
                        {
                            if (LuceneTestCase.VERBOSE)
                            {
                                Console.WriteLine("  do seekFloor(" + InputToString(inputMode, pairs[upto].Input) + ")");
                            }
                            isDone = fstEnum_.SeekFloor(pairs[upto].Input) == null;
                        }
                    }
                    if (LuceneTestCase.VERBOSE)
                    {
                        if (!isDone)
                        {
                            Console.WriteLine("    got " + InputToString(inputMode, fstEnum_.Current.Input));
                        }
                        else
                        {
                            Console.WriteLine("    got null");
                        }
                    }

                    if (upto == pairs.Count)
                    {
                        Assert.IsTrue(isDone);
                        break;
                    }
                    else
                    {
                        Assert.IsFalse(isDone);
                        Assert.AreEqual(pairs[upto].Input, fstEnum_.Current.Input);
                        Assert.IsTrue(OutputsEqual(pairs[upto].Output, fstEnum_.Current.Output));

                        /*
                          if (upto < pairs.size()-1) {
                          int tryCount = 0;
                          while(tryCount < 10) {
                          final IntsRef t = toIntsRef(getRandomString(), inputMode);
                          if (pairs.get(upto).input.compareTo(t) < 0) {
                          final boolean expected = t.compareTo(pairs.get(upto+1).input) < 0;
                          if (LuceneTestCase.VERBOSE) {
                          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);
                          }
                          Assert.AreEqual(expected, fstEnum.beforeNext(t));
                          break;
                          }
                          tryCount++;
                          }
                          }
                        */
                    }
                }
            }
        }

        private class CountMinOutput<S>
        {
            internal int Count { get; set; }
            internal S Output { get; set; }
            internal S FinalOutput { get; set; }
            internal bool IsLeaf { get; set; } = true;
            internal bool IsFinal { get; set; }
        }

        // FST is pruned
        private void VerifyPruned(int inputMode, FST<T> fst, int prune1, int prune2)
        {
            if (LuceneTestCase.VERBOSE)
            {
                Console.WriteLine("TEST: now verify pruned " + pairs.Count + " terms; outputs=" + outputs);
                foreach (InputOutput<T> pair in pairs)
                {
                    Console.WriteLine("  " + InputToString(inputMode, pair.Input) + ": " + outputs.OutputToString(pair.Output));
                }
            }

            // To validate the FST, we brute-force compute all prefixes
            // in the terms, matched to their "common" outputs, prune that
            // set according to the prune thresholds, then assert the FST
            // matches that same set.

            // NOTE: Crazy RAM intensive!!

            //System.out.println("TEST: tally prefixes");

            // build all prefixes
            IDictionary<Int32sRef, CountMinOutput<T>> prefixes = new HashMap<Int32sRef, CountMinOutput<T>>();
            Int32sRef scratch = new Int32sRef(10);
            foreach (InputOutput<T> pair in pairs)
            {
                scratch.CopyInt32s(pair.Input);
                for (int idx = 0; idx <= pair.Input.Length; idx++)
                {
                    scratch.Length = idx;
                    CountMinOutput<T> cmo = prefixes.ContainsKey(scratch) ? prefixes[scratch] : null;
                    if (cmo == null)
                    {
                        cmo = new CountMinOutput<T>();
                        cmo.Count = 1;
                        cmo.Output = pair.Output;
                        prefixes[Int32sRef.DeepCopyOf(scratch)] = cmo;
                    }
                    else
                    {
                        cmo.Count++;
                        T output1 = cmo.Output;
                        if (output1.Equals(outputs.NoOutput))
                        {
                            output1 = outputs.NoOutput;
                        }
                        T output2 = pair.Output;
                        if (output2.Equals(outputs.NoOutput))
                        {
                            output2 = outputs.NoOutput;
                        }
                        cmo.Output = outputs.Common(output1, output2);
                    }
                    if (idx == pair.Input.Length)
                    {
                        cmo.IsFinal = true;
                        cmo.FinalOutput = cmo.Output;
                    }
                }
            }

            if (LuceneTestCase.VERBOSE)
            {
                Console.WriteLine("TEST: now prune");
            }


            // prune 'em
            // LUCENENET NOTE: Altered this a bit to go in reverse rather than use an enumerator since
            // in .NET you cannot delete records while enumerating forward through a dictionary.
            for (int i = prefixes.Count - 1; i >= 0; i--)
            {
                KeyValuePair<Int32sRef, CountMinOutput<T>> ent = prefixes.ElementAt(i);
                Int32sRef prefix = ent.Key;
                CountMinOutput<T> cmo = ent.Value;
                if (LuceneTestCase.VERBOSE)
                {
                    Console.WriteLine("  term prefix=" + InputToString(inputMode, prefix, false) + " count=" + cmo.Count + " isLeaf=" + cmo.IsLeaf + " output=" + outputs.OutputToString(cmo.Output) + " isFinal=" + cmo.IsFinal);
                }
                bool keep;
                if (prune1 > 0)
                {
                    keep = cmo.Count >= prune1;
                }
                else
                {
                    Debug.Assert(prune2 > 0);
                    if (prune2 > 1 && cmo.Count >= prune2)
                    {
                        keep = true;
                    }
                    else if (prefix.Length > 0)
                    {
                        // consult our parent
                        scratch.Length = prefix.Length - 1;
                        Array.Copy(prefix.Int32s, prefix.Offset, scratch.Int32s, 0, scratch.Length);
                        CountMinOutput<T> cmo2 = prefixes.ContainsKey(scratch) ? prefixes[scratch] : null;
                        //System.out.println("    parent count = " + (cmo2 == null ? -1 : cmo2.count));
                        keep = cmo2 != null && ((prune2 > 1 && cmo2.Count >= prune2) || (prune2 == 1 && (cmo2.Count >= 2 || prefix.Length <= 1)));
                    }
                    else if (cmo.Count >= prune2)
                    {
                        keep = true;
                    }
                    else
                    {
                        keep = false;
                    }
                }

                if (!keep)
                {
                    prefixes.Remove(prefix);
                    //System.out.println("    remove");
                }
                else
                {
                    // clear isLeaf for all ancestors
                    //System.out.println("    keep");
                    scratch.CopyInt32s(prefix);
                    scratch.Length--;
                    while (scratch.Length >= 0)
                    {
                        CountMinOutput<T> cmo2 = prefixes.ContainsKey(scratch) ? prefixes[scratch] : null;
                        if (cmo2 != null)
                        {
                            //System.out.println("    clear isLeaf " + inputToString(inputMode, scratch));
                            cmo2.IsLeaf = false;
                        }
                        scratch.Length--;
                    }
                }
            }

            if (LuceneTestCase.VERBOSE)
            {
                Console.WriteLine("TEST: after prune");
                foreach (KeyValuePair<Int32sRef, CountMinOutput<T>> ent in prefixes)
                {
                    Console.WriteLine("  " + InputToString(inputMode, ent.Key, false) + ": isLeaf=" + ent.Value.IsLeaf + " isFinal=" + ent.Value.IsFinal);
                    if (ent.Value.IsFinal)
                    {
                        Console.WriteLine("    finalOutput=" + outputs.OutputToString(ent.Value.FinalOutput));
                    }
                }
            }

            if (prefixes.Count <= 1)
            {
                Assert.IsNull(fst);
                return;
            }

            Assert.IsNotNull(fst);

            // make sure FST only enums valid prefixes
            if (LuceneTestCase.VERBOSE)
            {
                Console.WriteLine("TEST: check pruned enum");
            }
            Int32sRefFSTEnum<T> fstEnum = new Int32sRefFSTEnum<T>(fst);
            Int32sRefFSTEnum.InputOutput<T> current;
            while ((current = fstEnum.Next()) != null)
            {
                if (LuceneTestCase.VERBOSE)
                {
                    Console.WriteLine("  fstEnum.next prefix=" + InputToString(inputMode, current.Input, false) + " output=" + outputs.OutputToString(current.Output));
                }
                CountMinOutput<T> cmo = prefixes.ContainsKey(current.Input) ? prefixes[current.Input] : null;
                Assert.IsNotNull(cmo);
                Assert.IsTrue(cmo.IsLeaf || cmo.IsFinal);
                //if (cmo.isFinal && !cmo.isLeaf) {
                if (cmo.IsFinal)
                {
                    Assert.AreEqual(cmo.FinalOutput, current.Output);
                }
                else
                {
                    Assert.AreEqual(cmo.Output, current.Output);
                }
            }

            // make sure all non-pruned prefixes are present in the FST
            if (LuceneTestCase.VERBOSE)
            {
                Console.WriteLine("TEST: verify all prefixes");
            }
            int[] stopNode = new int[1];
            foreach (KeyValuePair<Int32sRef, CountMinOutput<T>> ent in prefixes)
            {
                if (ent.Key.Length > 0)
                {
                    CountMinOutput<T> cmo = ent.Value;
                    T output = Run(fst, ent.Key, stopNode);
                    if (LuceneTestCase.VERBOSE)
                    {
                        Console.WriteLine("TEST: verify prefix=" + InputToString(inputMode, ent.Key, false) + " output=" + outputs.OutputToString(cmo.Output));
                    }
                    // if (cmo.isFinal && !cmo.isLeaf) {
                    if (cmo.IsFinal)
                    {
                        Assert.AreEqual(cmo.FinalOutput, output);
                    }
                    else
                    {
                        Assert.AreEqual(cmo.Output, output);
                    }
                    Assert.AreEqual(ent.Key.Length, stopNode[0]);
                }
            }
        }
    }
}