/*
 * TokenNFA.cs
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either version 3
 * of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,
 * MA 02111-1307, USA.
 *
 * Copyright (c) 2009 Per Cederberg. All rights reserved.
 */

using System;

namespace PerCederberg.Grammatica.Runtime {

    /**
     * A non-deterministic finite state automaton (NFA) for matching
     * tokens. It supports both fixed strings and simple regular
     * expressions, but should perform similar to a DFA due to highly
     * optimized data structures and tuning. The memory footprint during
     * matching should be near zero, since no heap memory is allocated
     * unless the pre-allocated queues need to be enlarged. The NFA also
     * does not use recursion, but iterates in a loop instead.
     *
     * @author   Per Cederberg, <per at percederberg dot net>
     * @version  1.5
     * @since    1.5
     */
    internal class TokenNFA {

        /**
         * The initial state lookup table, indexed by the first ASCII
         * character. This array is used to for speed optimizing the
         * first step in the match, since the initial state would
         * otherwise have a long list of transitions to consider.
         */
        private NFAState[] initialChar = new NFAState[128];

        /**
         * The initial state. This state contains any transitions not
         * already stored in the initial text state array, i.e. non-ASCII
         * or complex transitions (such as regular expressions).
         */
        private NFAState initial = new NFAState();

        /**
         * The NFA state queue to use.
         */
        private NFAStateQueue queue = new NFAStateQueue();

        /**
         * Adds a string match to this automaton. New states and
         * transitions will be added to extend this automaton to support
         * the specified string.
         *
         * @param str            the string to match
         * @param ignoreCase     the case-insensitive match flag
         * @param value          the match value
         */
        public void AddTextMatch(string str, bool ignoreCase, TokenPattern value) {
            NFAState  state;
            char      ch = str[0];

            if (ch < 128 && !ignoreCase) {
                state = initialChar[ch];
                if (state == null) {
                    state = initialChar[ch] = new NFAState();
                }
            } else {
                state = initial.AddOut(ch, ignoreCase, null);
            }
            for (int i = 1; i < str.Length; i++) {
                state = state.AddOut(str[i], ignoreCase, null);
            }
            state.value = value;
        }

        /**
         * Adds a regular expression match to this automaton. New states
         * and transitions will be added to extend this automaton to
         * support the specified string. Note that this method only
         * supports a subset of the full regular expression syntax, so
         * a more complete regular expression library must also be
         * provided.
         *
         * @param pattern        the regular expression string
         * @param ignoreCase     the case-insensitive match flag
         * @param value          the match value
         *
         * @throws RegExpException if the regular expression parsing
         *             failed
         */
        public void AddRegExpMatch(string pattern,
                                   bool ignoreCase,
                                   TokenPattern value) {

            TokenRegExpParser  parser = new TokenRegExpParser(pattern, ignoreCase);
            string             debug = "DFA regexp; " + parser.GetDebugInfo();
            bool               isAscii;

            isAscii = parser.start.IsAsciiOutgoing();
            for (int i = 0; isAscii && i < 128; i++) {
                bool match = false;
                for (int j = 0; j < parser.start.outgoing.Length; j++) {
                    if (parser.start.outgoing[j].Match((char) i)) {
                        if (match) {
                            isAscii = false;
                            break;
                        }
                        match = true;
                    }
                }
                if (match && initialChar[i] != null) {
                    isAscii = false;
                }
            }
            if (parser.start.incoming.Length > 0) {
                initial.AddOut(new NFAEpsilonTransition(parser.start));
                debug += ", uses initial epsilon";
            } else if (isAscii && !ignoreCase) {
                for (int i = 0; isAscii && i < 128; i++) {
                    for (int j = 0; j < parser.start.outgoing.Length; j++) {
                        if (parser.start.outgoing[j].Match((char) i)) {
                            initialChar[i] = parser.start.outgoing[j].state;
                        }
                    }
                }
                debug += ", uses ASCII lookup";
            } else {
                parser.start.MergeInto(initial);
                debug += ", uses initial state";
            }
            parser.end.value = value;
            value.DebugInfo = debug;
        }

        /**
         * Checks if this NFA matches the specified input text. The
         * matching will be performed from position zero (0) in the
         * buffer. This method will not read any characters from the
         * stream, just peek ahead.
         *
         * @param buffer         the input buffer to check
         * @param match          the token match to update
         *
         * @return the number of characters matched, or
         *         zero (0) if no match was found
         *
         * @throws IOException if an I/O error occurred
         */
        public int Match(ReaderBuffer buffer, TokenMatch match) {
            int       length = 0;
            int       pos = 1;
            int       peekChar;
            NFAState  state;

            // The first step of the match loop has been unrolled and
            // optimized for performance below.
            this.queue.Clear();
            peekChar = buffer.Peek(0);
            if (0 <= peekChar && peekChar < 128) {
                state = this.initialChar[peekChar];
                if (state != null) {
                    this.queue.AddLast(state);
                }
            }
            if (peekChar >= 0) {
                this.initial.MatchTransitions((char) peekChar, this.queue, true);
            }
            this.queue.MarkEnd();
            peekChar = buffer.Peek(1);

            // The remaining match loop processes all subsequent states
            while (!this.queue.Empty) {
                if (this.queue.Marked) {
                    pos++;
                    peekChar = buffer.Peek(pos);
                    this.queue.MarkEnd();
                }
                state = this.queue.RemoveFirst();
                if (state.value != null) {
                    match.Update(pos, state.value);
                }
                if (peekChar >= 0) {
                    state.MatchTransitions((char) peekChar, this.queue, false);
                }
            }
            return length;
        }
    }


    /**
     * An NFA state. The NFA consists of a series of states, each
     * having zero or more transitions to other states.
     */
    internal class NFAState {

        /**
        * The optional state value (if it is a final state).
         */
        internal TokenPattern value = null;

        /**
        * The incoming transitions to this state.
        */
        internal NFATransition[] incoming = new NFATransition[0];

        /**
        * The outgoing transitions from this state.
        */
        internal NFATransition[] outgoing = new NFATransition[0];

        /**
        * The outgoing epsilon transitions flag.
        */
        internal bool epsilonOut = false;

        /**
         * Checks if this state has any incoming or outgoing
         * transitions.
         *
         * @return true if this state has transitions, or
         *         false otherwise
         */
        public bool HasTransitions() {
            return incoming.Length > 0 || outgoing.Length > 0;
        }

        /**
         * Checks if all outgoing transitions only match ASCII
         * characters.
         *
         * @return true if all transitions are ASCII-only, or
         *         false otherwise
         */
        public bool IsAsciiOutgoing() {
            for (int i = 0; i < outgoing.Length; i++) {
                if (!outgoing[i].IsAscii()) {
                    return false;
                }
            }
            return true;
        }

        /**
         * Adds a new incoming transition.
         *
         * @param trans          the transition to add
         */
        public void AddIn(NFATransition trans) {
            Array.Resize(ref incoming, incoming.Length + 1);
            incoming[incoming.Length -1] = trans;
        }

        /**
         * Adds a new outgoing character transition. If the target
         * state specified was null and an identical transition
         * already exists, it will be reused and its target returned.
         *
         * @param ch             he character to match
         * @param ignoreCase     the case-insensitive flag
         * @param state          the target state, or null
         *
         * @return the transition target state
         */
        public NFAState AddOut(char ch, bool ignoreCase, NFAState state) {
            if (ignoreCase) {
                if (state == null) {
                    state = new NFAState();
                }
                AddOut(new NFACharTransition(Char.ToLower(ch), state));
                AddOut(new NFACharTransition(Char.ToUpper(ch), state));
                return state;
            } else {
                if (state == null) {
                    state = FindUniqueCharTransition(ch);
                    if (state != null) {
                        return state;
                    }
                    state = new NFAState();
                }
                return AddOut(new NFACharTransition(ch, state));
            }
        }

        /**
         * Adds a new outgoing transition.
         *
         * @param trans          the transition to add
         *
         * @return the transition target state
         */
        public NFAState AddOut(NFATransition trans) {
            Array.Resize(ref outgoing, outgoing.Length + 1);
            outgoing[outgoing.Length -1] = trans;
            if (trans is NFAEpsilonTransition) {
                epsilonOut = true;
            }
            return trans.state;
        }

        /**
         * Merges all the transitions in this state into another
         * state.
         *
         * @param state      the state to merge into
         */
        public void MergeInto(NFAState state) {
            for (int i = 0; i < incoming.Length; i++) {
                state.AddIn(incoming[i]);
                incoming[i].state = state;
            }
            incoming = null;
            for (int i = 0; i < outgoing.Length; i++) {
                state.AddOut(outgoing[i]);
            }
            outgoing = null;
        }

        /**
         * Finds a unique character transition if one exists. The
         * transition must be the only matching single character
         * transition and no other transitions may reach the same
         * state.
         *
         * @param ch             the character to search for
         *
         * @return the unique transition state found, or
         *         null if not found
         */
        private NFAState FindUniqueCharTransition(char ch) {
            NFATransition  res = null;
            NFATransition  trans;

            for (int i = 0; i < outgoing.Length; i++) {
                trans = outgoing[i];
                if (trans.Match(ch) && trans is NFACharTransition) {
                    if (res != null) {
                        return null;
                    }
                    res = trans;
                }
            }
            for (int i = 0; res != null && i < outgoing.Length; i++) {
                trans = outgoing[i];
                if (trans != res && trans.state == res.state) {
                    return null;
                }
            }
            return (res == null) ? null : res.state;
        }

        /**
         * Attempts a match on each of the transitions leading from
         * this state. If a match is found, its state will be added
         * to the queue. If the initial match flag is set, epsilon
         * transitions will also be matched (and their targets called
         * recursively).
         *
         * @param ch         the character to match
         * @param queue      the state queue
         * @param initial    the initial match flag
         */
        public void MatchTransitions(char ch, NFAStateQueue queue, bool initial) {
            NFATransition  trans;
            NFAState       target;

            for (int i = 0; i < outgoing.Length; i++) {
                trans = outgoing[i];
                target = trans.state;
                if (initial && trans is NFAEpsilonTransition) {
                    target.MatchTransitions(ch, queue, true);
                } else if (trans.Match(ch)) {
                    queue.AddLast(target);
                    if (target.epsilonOut) {
                        target.MatchEmpty(queue);
                    }
                }
            }
        }

        /**
         * Adds all the epsilon transition targets to the specified
         * queue.
         *
         * @param queue      the state queue
         */
        public void MatchEmpty(NFAStateQueue queue) {
            NFATransition  trans;
            NFAState       target;

            for (int i = 0; i < outgoing.Length; i++) {
                trans = outgoing[i];
                if (trans is NFAEpsilonTransition) {
                    target = trans.state;
                    queue.AddLast(target);
                    if (target.epsilonOut) {
                        target.MatchEmpty(queue);
                    }
                }
            }
        }
    }


    /**
     * An NFA state transition. A transition checks a single
     * character of input an determines if it is a match. If a match
     * is encountered, the NFA should move forward to the transition
     * state.
     */
    internal abstract class NFATransition {

        /**
         * The target state of the transition.
         */
        internal NFAState state;

        /**
         * Creates a new state transition.
         *
         * @param state          the target state
         */
        public NFATransition(NFAState state) {
            this.state = state;
            this.state.AddIn(this);
        }

        /**
         * Checks if this transition only matches ASCII characters.
         * I.e. characters with numeric values between 0 and 127.
         *
         * @return true if this transition only matches ASCII, or
         *         false otherwise
         */
        public abstract bool IsAscii();

        /**
         * Checks if the specified character matches the transition.
         *
         * @param ch             the character to check
         *
         * @return true if the character matches, or
         *         false otherwise
         */
        public abstract bool Match(char ch);

        /**
         * Creates a copy of this transition but with another target
         * state.
         *
         * @param state          the new target state
         *
         * @return an identical copy of this transition
         */
        public abstract NFATransition Copy(NFAState state);
    }


    /**
     * The special epsilon transition. This transition matches the
     * empty input, i.e. it is an automatic transition that doesn't
     * read any input. As such, it returns false in the match method
     * and is handled specially everywhere.
     */
    internal class NFAEpsilonTransition : NFATransition {

        /**
         * Creates a new epsilon transition.
         *
         * @param state          the target state
         */
        public NFAEpsilonTransition(NFAState state) : base(state) {
        }

        /**
         * Checks if this transition only matches ASCII characters.
         * I.e. characters with numeric values between 0 and 127.
         *
         * @return true if this transition only matches ASCII, or
         *         false otherwise
         */
        public override bool IsAscii() {
            return false;
        }

        /**
         * Checks if the specified character matches the transition.
         *
         * @param ch             the character to check
         *
         * @return true if the character matches, or
         *         false otherwise
         */
        public override bool Match(char ch) {
            return false;
        }

        /**
         * Creates a copy of this transition but with another target
         * state.
         *
         * @param state          the new target state
         *
         * @return an identical copy of this transition
         */
        public override NFATransition Copy(NFAState state) {
            return new NFAEpsilonTransition(state);
        }
    }


    /**
     * A single character match transition.
     */
    internal class NFACharTransition : NFATransition {

        /**
         * The character to match.
         */
        protected char match;

        /**
         * Creates a new character transition.
         *
         * @param match          the character to match
         * @param state          the target state
         */
        public NFACharTransition(char match, NFAState state) : base(state) {
            this.match = match;
        }

        /**
         * Checks if this transition only matches ASCII characters.
         * I.e. characters with numeric values between 0 and 127.
         *
         * @return true if this transition only matches ASCII, or
         *         false otherwise
         */
        public override bool IsAscii() {
            return 0 <= match && match < 128;
        }

        /**
         * Checks if the specified character matches the transition.
         *
         * @param ch             the character to check
         *
         * @return true if the character matches, or
         *         false otherwise
         */
        public override bool Match(char ch) {
            return this.match == ch;
        }

        /**
         * Creates a copy of this transition but with another target
         * state.
         *
         * @param state          the new target state
         *
         * @return an identical copy of this transition
         */
        public override NFATransition Copy(NFAState state) {
            return new NFACharTransition(match, state);
        }
    }


    /**
     * A character range match transition. Used for user-defined
     * character sets in regular expressions.
     */
    internal class NFACharRangeTransition : NFATransition {

        /**
         * The inverse match flag.
         */
        protected bool inverse;

        /**
         * The case-insensitive match flag.
         */
        protected bool ignoreCase;

        /**
         * The character set content. This array may contain either
         * range objects or Character objects.
         */
        private object[] contents = new object[0];

        /**
         * Creates a new character range transition.
         *
         * @param inverse        the inverse match flag
         * @param ignoreCase     the case-insensitive match flag
         * @param state          the target state
         */
        public NFACharRangeTransition(bool inverse,
                                      bool ignoreCase,
                                      NFAState state) : base(state) {
            this.inverse = inverse;
            this.ignoreCase = ignoreCase;
        }

        /**
         * Checks if this transition only matches ASCII characters.
         * I.e. characters with numeric values between 0 and 127.
         *
         * @return true if this transition only matches ASCII, or
         *         false otherwise
         */
        public override bool IsAscii() {
            object  obj;
            char    c;

            if (inverse) {
                return false;
            }
            for (int i = 0; i < contents.Length; i++) {
                obj = contents[i];
                if (obj is char) {
                    c = (char) obj;
                    if (c < 0 || 128 <= c) {
                        return false;
                    }
                } else if (obj is Range) {
                    if (!((Range) obj).IsAscii()) {
                        return false;
                    }
                }
            }
            return true;
        }

        /**
         * Adds a single character to this character set.
         *
         * @param c              the character to add
         */
        public void AddCharacter(char c) {
            if (ignoreCase) {
                c = Char.ToLower(c);
            }
            AddContent(c);
        }

        /**
         * Adds a character range to this character set.
         *
         * @param min            the minimum character value
         * @param max            the maximum character value
         */
        public void AddRange(char min, char max) {
            if (ignoreCase) {
                min = Char.ToLower(min);
                max = Char.ToLower(max);
            }
            AddContent(new Range(min, max));
        }

        /**
         * Adds an object to the character set content array.
         *
         * @param obj            the object to add
         */
        private void AddContent(Object obj) {
            Array.Resize(ref contents, contents.Length + 1);
            contents[contents.Length -1] = obj;
        }

        /**
         * Checks if the specified character matches the transition.
         *
         * @param ch             the character to check
         *
         * @return true if the character matches, or
         *         false otherwise
         */
        public override bool Match(char ch) {
            object  obj;
            char    c;
            Range   r;

            if (ignoreCase) {
                ch = Char.ToLower(ch);
            }
            for (int i = 0; i < contents.Length; i++) {
                obj = contents[i];
                if (obj is char) {
                    c = (char) obj;
                    if (c == ch) {
                        return !inverse;
                    }
                } else if (obj is Range) {
                    r = (Range) obj;
                    if (r.Inside(ch)) {
                        return !inverse;
                    }
                }
            }
            return inverse;
        }

        /**
         * Creates a copy of this transition but with another target
         * state.
         *
         * @param state          the new target state
         *
         * @return an identical copy of this transition
         */
        public override NFATransition Copy(NFAState state) {
            NFACharRangeTransition  copy;

            copy = new NFACharRangeTransition(inverse, ignoreCase, state);
            copy.contents = contents;
            return copy;
        }

        /**
         * A character range class.
         */
        private class Range {

            /**
             * The minimum character value.
             */
            private char min;

            /**
             * The maximum character value.
             */
            private char max;

            /**
             * Creates a new character range.
             *
             * @param min        the minimum character value
             * @param max        the maximum character value
             */
            public Range(char min, char max) {
                this.min = min;
                this.max = max;
            }

            /**
             * Checks if this range only matches ASCII characters
             *
             * @return true if this range only matches ASCII, or
             *         false otherwise
             */
            public bool IsAscii() {
                return 0 <= min && min < 128 &&
                       0 <= max && max < 128;
            }

            /**
             * Checks if the specified character is inside the range.
             *
             * @param c          the character to check
             *
             * @return true if the character is in the range, or
             *         false otherwise
             */
            public bool Inside(char c) {
                return min <= c && c <= max;
            }
        }
    }


    /**
     * The dot ('.') character set transition. This transition
     * matches a single character that is not equal to a newline
     * character.
     */
    internal class NFADotTransition : NFATransition {

        /**
         * Creates a new dot character set transition.
         *
         * @param state          the target state
         */
        public NFADotTransition(NFAState state) : base(state) {
        }

        /**
         * Checks if this transition only matches ASCII characters.
         * I.e. characters with numeric values between 0 and 127.
         *
         * @return true if this transition only matches ASCII, or
         *         false otherwise
         */
        public override bool IsAscii() {
            return false;
        }

        /**
         * Checks if the specified character matches the transition.
         *
         * @param ch             the character to check
         *
         * @return true if the character matches, or
         *         false otherwise
         */
        public override bool Match(char ch) {
            switch (ch) {
            case '\n':
            case '\r':
            case '\u0085':
            case '\u2028':
            case '\u2029':
                return false;
            default:
                return true;
            }
        }

        /**
         * Creates a copy of this transition but with another target
         * state.
         *
         * @param state          the new target state
         *
         * @return an identical copy of this transition
         */
        public override NFATransition Copy(NFAState state) {
            return new NFADotTransition(state);
        }
    }


    /**
     * The digit character set transition. This transition matches a
     * single numeric character.
     */
    internal class NFADigitTransition : NFATransition {

        /**
         * Creates a new digit character set transition.
         *
         * @param state          the target state
         */
        public NFADigitTransition(NFAState state) : base(state) {
        }

        /**
         * Checks if this transition only matches ASCII characters.
         * I.e. characters with numeric values between 0 and 127.
         *
         * @return true if this transition only matches ASCII, or
         *         false otherwise
         */
        public override bool IsAscii() {
            return true;
        }

        /**
         * Checks if the specified character matches the transition.
         *
         * @param ch             the character to check
         *
         * @return true if the character matches, or
         *         false otherwise
         */
        public override bool Match(char ch) {
            return '0' <= ch && ch <= '9';
        }

        /**
         * Creates a copy of this transition but with another target
         * state.
         *
         * @param state          the new target state
         *
         * @return an identical copy of this transition
         */
        public override NFATransition Copy(NFAState state) {
            return new NFADigitTransition(state);
        }
    }


    /**
     * The non-digit character set transition. This transition
     * matches a single non-numeric character.
     */
    internal class NFANonDigitTransition : NFATransition {

        /**
         * Creates a new non-digit character set transition.
         *
         * @param state          the target state
         */
        public NFANonDigitTransition(NFAState state) : base(state) {
        }

        /**
         * Checks if this transition only matches ASCII characters.
         * I.e. characters with numeric values between 0 and 127.
         *
         * @return true if this transition only matches ASCII, or
         *         false otherwise
         */
        public override bool IsAscii() {
            return false;
        }

        /**
         * Checks if the specified character matches the transition.
         *
         * @param ch             the character to check
         *
         * @return true if the character matches, or
         *         false otherwise
         */
        public override bool Match(char ch) {
            return ch < '0' || '9' < ch;
        }

        /**
         * Creates a copy of this transition but with another target
         * state.
         *
         * @param state          the new target state
         *
         * @return an identical copy of this transition
         */
        public override NFATransition Copy(NFAState state) {
            return new NFANonDigitTransition(state);
        }
    }


    /**
     * The whitespace character set transition. This transition
     * matches a single whitespace character.
     */
    internal class NFAWhitespaceTransition : NFATransition {

        /**
         * Creates a new whitespace character set transition.
         *
         * @param state          the target state
         */
        public NFAWhitespaceTransition(NFAState state) : base(state) {
        }

        /**
         * Checks if this transition only matches ASCII characters.
         * I.e. characters with numeric values between 0 and 127.
         *
         * @return true if this transition only matches ASCII, or
         *         false otherwise
         */
        public override bool IsAscii() {
            return true;
        }

        /**
         * Checks if the specified character matches the transition.
         *
         * @param ch             the character to check
         *
         * @return true if the character matches, or
         *         false otherwise
         */
        public override bool Match(char ch) {
            switch (ch) {
            case ' ':
            case '\t':
            case '\n':
            case '\f':
            case '\r':
            case (char) 11:
                return true;
            default:
                return false;
            }
        }

        /**
         * Creates a copy of this transition but with another target
         * state.
         *
         * @param state          the new target state
         *
         * @return an identical copy of this transition
         */
        public override NFATransition Copy(NFAState state) {
            return new NFAWhitespaceTransition(state);
        }
    }


    /**
     * The non-whitespace character set transition. This transition
     * matches a single non-whitespace character.
     */
    internal class NFANonWhitespaceTransition : NFATransition {

        /**
         * Creates a new non-whitespace character set transition.
         *
         * @param state          the target state
         */
        public NFANonWhitespaceTransition(NFAState state) : base(state) {
        }

        /**
         * Checks if this transition only matches ASCII characters.
         * I.e. characters with numeric values between 0 and 127.
         *
         * @return true if this transition only matches ASCII, or
         *         false otherwise
         */
        public override bool IsAscii() {
            return false;
        }

        /**
         * Checks if the specified character matches the transition.
         *
         * @param ch             the character to check
         *
         * @return true if the character matches, or
         *         false otherwise
         */
        public override bool Match(char ch) {
            switch (ch) {
            case ' ':
            case '\t':
            case '\n':
            case '\f':
            case '\r':
            case (char) 11:
                return false;
            default:
                return true;
            }
        }

        /**
         * Creates a copy of this transition but with another target
         * state.
         *
         * @param state          the new target state
         *
         * @return an identical copy of this transition
         */
        public override NFATransition Copy(NFAState state) {
            return new NFANonWhitespaceTransition(state);
        }
    }


    /**
     * The word character set transition. This transition matches a
     * single word character.
     */
    internal class NFAWordTransition : NFATransition {

        /**
         * Creates a new word character set transition.
         *
         * @param state          the target state
         */
        public NFAWordTransition(NFAState state) : base(state) {
        }

        /**
         * Checks if this transition only matches ASCII characters.
         * I.e. characters with numeric values between 0 and 127.
         *
         * @return true if this transition only matches ASCII, or
         *         false otherwise
         */
        public override bool IsAscii() {
            return true;
        }

        /**
         * Checks if the specified character matches the transition.
         *
         * @param ch             the character to check
         *
         * @return true if the character matches, or
         *         false otherwise
         */
        public override bool Match(char ch) {
            return ('a' <= ch && ch <= 'z')
                || ('A' <= ch && ch <= 'Z')
                || ('0' <= ch && ch <= '9')
                || ch == '_';
        }

        /**
         * Creates a copy of this transition but with another target
         * state.
         *
         * @param state          the new target state
         *
         * @return an identical copy of this transition
         */
        public override NFATransition Copy(NFAState state) {
            return new NFAWordTransition(state);
        }
    }


    /**
     * The non-word character set transition. This transition matches
     * a single non-word character.
     */
    internal class NFANonWordTransition : NFATransition {

        /**
         * Creates a new non-word character set transition.
         *
         * @param state          the target state
         */
        public NFANonWordTransition(NFAState state) : base(state) {
        }

        /**
         * Checks if this transition only matches ASCII characters.
         * I.e. characters with numeric values between 0 and 127.
         *
         * @return true if this transition only matches ASCII, or
         *         false otherwise
         */
        public override bool IsAscii() {
            return false;
        }

        /**
         * Checks if the specified character matches the transition.
         *
         * @param ch             the character to check
         *
         * @return true if the character matches, or
         *         false otherwise
         */
        public override bool Match(char ch) {
            bool word = ('a' <= ch && ch <= 'z')
                     || ('A' <= ch && ch <= 'Z')
                     || ('0' <= ch && ch <= '9')
                     || ch == '_';
            return !word;
        }

        /**
         * Creates a copy of this transition but with another target
         * state.
         *
         * @param state          the new target state
         *
         * @return an identical copy of this transition
         */
        public override NFATransition Copy(NFAState state) {
            return new NFANonWordTransition(state);
        }
    }


    /**
     * An NFA state queue. This queue is used during processing to
     * keep track of the current and subsequent NFA states. The
     * current state is read from the beginning of the queue, and new
     * states are added at the end. A marker index is used to
     * separate the current from the subsequent states.<p>
     *
     * The queue implementation is optimized for quick removal at the
     * beginning and addition at the end. It will attempt to use a
     * fixed-size array to store the whole queue, and moves the data
     * in this array only when absolutely needed. The array is also
     * enlarged automatically if too many states are being processed
     * at a single time.
     */
    internal class NFAStateQueue {

        /**
        * The state queue array. Will be enlarged as needed.
        */
        private NFAState[] queue = new NFAState[2048];

        /**
        * The position of the first entry in the queue (inclusive).
        */
        private int first = 0;

        /**
        * The position just after the last entry in the queue
        * (exclusive).
        */
        private int last = 0;

        /**
        * The current queue mark position.
        */
        private int mark = 0;

        /**
         * The empty queue property (read-only).
         */
        public bool Empty {
            get {
                return (last <= first);
            }
        }

        /**
         * The marked first entry property (read-only). This is set
         * to true if the first entry in the queue has been marked.
         */
        public bool Marked {
            get {
                return first == mark;
            }
        }

        /**
         * Clears this queue. This operation is fast, as it just
         * resets the queue position indices.
         */
        public void Clear() {
            first = 0;
            last = 0;
            mark = 0;
        }

        /**
         * Marks the end of the queue. This means that the next entry
         * added to the queue will be marked (when it becomes the
         * first in the queue). This operation is fast.
         */
        public void MarkEnd() {
            mark = last;
        }

        /**
         * Removes and returns the first entry in the queue. This
         * operation is fast, since it will only update the index of
         * the first entry in the queue.
         *
         * @return the previous first entry in the queue
         */
        public NFAState RemoveFirst() {
            if (first < last) {
                first++;
                return queue[first -1];
            } else {
                return null;
            }
        }

        /**
         * Adds a new entry at the end of the queue. This operation
         * is mostly fast, unless all the allocated queue space has
         * already been used.
         *
         * @param state          the state to add
         */
        public void AddLast(NFAState state) {
            if (last >= queue.Length) {
                if (first <= 0) {
                    Array.Resize(ref queue, queue.Length * 2);
                } else {
                    Array.Copy(queue, first, queue, 0, last -first);
                    last -= first;
                    mark -= first;
                    first = 0;
                }
            }
            queue[last++] = state;
        }
    }
}