/** A DFA implemented as a set of transition tables.
 *
 *  Any state that has a semantic predicate edge is special; those states
 *  are generated with if-then-else structures in a specialStateTransition()
 *  which is generated by cyclicDFA template.
 *
 *  There are at most 32767 states (16-bit signed short).
 *  Could get away with byte sometimes but would have to generate different
 *  types and the simulation code too.  For a point of reference, the Java
 *  lexer's Tokens rule DFA has 326 states roughly.
 */
org.antlr.runtime.DFA = function() {};

org.antlr.runtime.DFA.prototype = {
    /** From the input stream, predict what alternative will succeed
     *  using this DFA (representing the covering regular approximation
     *  to the underlying CFL).  Return an alternative number 1..n.  Throw
     *  an exception upon error.
     */
    predict: function(input) {
        var mark = input.mark(), // remember where decision started in input
            s = 0, // we always start at s0
            specialState,
            c,
            snext;

        try {
            while ( true ) {
                specialState = this.special[s];
                if ( specialState>=0 ) {
                    s = this.specialStateTransition(specialState,input);
                    if (s===-1) {
                        this.noViableAlt(s, input);
                        return 0;
                    }
                    input.consume();
                    continue;
                }
                if ( this.accept[s] >= 1 ) {
                    return this.accept[s];
                }
                // look for a normal char transition
                c = input.LA(1); // -1 == \uFFFF, all tokens fit in 65000 space

                if (c===org.antlr.runtime.Token.EOF) {
                    c = -1;
                } else if (org.antlr.lang.isString(c)) {
                    c = c.charCodeAt(0);
                }

                if (c>=this.min[s] && c<=this.max[s]) {
                    snext = this.transition[s][c-this.min[s]]; // move to next state
                    if ( snext < 0 ) {
                        // was in range but not a normal transition
                        // must check EOT, which is like the else clause.
                        // eot[s]>=0 indicates that an EOT edge goes to another
                        // state.
                        if ( this.eot[s]>=0 ) {  // EOT Transition to accept state?
                            s = this.eot[s];
                            input.consume();
                            // TODO: I had this as return accept[eot[s]]
                            // which assumed here that the EOT edge always
                            // went to an accept...faster to do this, but
                            // what about predicated edges coming from EOT
                            // target?
                            continue;
                        }
                        this.noViableAlt(s,input);
                        return 0;
                    }
                    s = snext;
                    input.consume();
                    continue;
                }
                if ( this.eot[s]>=0 ) {  // EOT Transition?
                    s = this.eot[s];
                    input.consume();
                    continue;
                }
                if ( c==org.antlr.runtime.Token.EOF && this.eof[s]>=0 ) {  // EOF Transition to accept state?
                    return this.accept[this.eof[s]];
                }
                // not in range and not EOF/EOT, must be invalid symbol
                this.noViableAlt(s,input);
                return 0;
            }
        }
        finally {
            input.rewind(mark);
        }
    },

    noViableAlt: function(s, input) {
        if (this.recognizer.state.backtracking>0) {
            this.recognizer.state.failed=true;
            return;
        }
        var nvae =
            new org.antlr.runtime.NoViableAltException(this.getDescription(),
                                     this.decisionNumber,
                                     s,
                                     input);
        this.error(nvae);
        throw nvae;
    },

    /** A hook for debugging interface */
    error: function(nvae) { },

    specialStateTransition: function(s, input) {
        return -1;
    },

    getDescription: function() {
        return "n/a";
    }
};

org.antlr.lang.augmentObject(org.antlr.runtime.DFA, {
    /** Given a String that has a run-length-encoding of some unsigned shorts
     *  like "\1\2\3\9", convert to short[] {2,9,9,9}.
     */
    unpackEncodedString: function(encodedString) {
        // walk first to find how big it is.
        var i,
            data = [],
            di = 0,
            n,
            v,
            j;
        for (i=0; i<encodedString.length; i+=2) {
            n = encodedString.charCodeAt(i);
            v = encodedString.charCodeAt(i+1);
            if (v===0xffff) {
                v = -1; // overflow at 16 bits
            }
            // add v n times to data
            for (j=1; j<=n; j++) {
                data[di++] = v;
            }
        }
        return data;
    },

    // alias
    unpackEncodedStringToUnsignedChars: function(encodedString) {
        return org.antlr.runtime.DFA.unpackEncodedString(encodedString);
    }
});