//
// [The "BSD license"]
//  Copyright (c) 2012 Terence Parr
//  Copyright (c) 2012 Sam Harwell
//  Copyright (c) 2014 Eric Vergnaud
//  All rights reserved.
//
//  Redistribution and use in source and binary forms, with or without
//  modification, are permitted provided that the following conditions
//  are met:
//
//  1. Redistributions of source code must retain the above copyright
//     notice, this list of conditions and the following disclaimer.
//  2. Redistributions in binary form must reproduce the above copyright
//     notice, this list of conditions and the following disclaimer in the
//     documentation and/or other materials provided with the distribution.
//  3. The name of the author may not be used to endorse or promote products
//     derived from this software without specific prior written permission.
//
//  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
//  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
//  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
//  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
//  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
//  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
//  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
//  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
//  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
//  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

//
// Specialized {@link Set}{@code <}{@link ATNConfig}{@code >} that can track
// info about the set, with support for combining similar configurations using a
// graph-structured stack.
///

var ATN = require('./ATN').ATN;
var Utils = require('./../Utils');
var Set = Utils.Set;
var SemanticContext = require('./SemanticContext').SemanticContext;
var merge = require('./../PredictionContext').merge;

function hashATNConfig(c) {
    return c.shortHashString();
}

function equalATNConfigs(a, b) {
    if (a === b) {
        return true;
    }
    if (a === null || b === null) {
        return false;
    }
    return a.state.stateNumber === b.state.stateNumber &&
        a.alt === b.alt && a.semanticContext.equals(b.semanticContext);
}


function ATNConfigSet(fullCtx) {
    //
    // The reason that we need this is because we don't want the hash map to use
    // the standard hash code and equals. We need all configurations with the
    // same
    // {@code (s,i,_,semctx)} to be equal. Unfortunately, this key effectively
    // doubles
    // the number of objects associated with ATNConfigs. The other solution is
    // to
    // use a hash table that lets us specify the equals/hashcode operation.
    // All configs but hashed by (s, i, _, pi) not including context. Wiped out
    // when we go readonly as this set becomes a DFA state.
    this.configLookup = new Set(hashATNConfig, equalATNConfigs);
    // Indicates that this configuration set is part of a full context
    // LL prediction. It will be used to determine how to merge $. With SLL
    // it's a wildcard whereas it is not for LL context merge.
    this.fullCtx = fullCtx === undefined ? true : fullCtx;
    // Indicates that the set of configurations is read-only. Do not
    // allow any code to manipulate the set; DFA states will point at
    // the sets and they must not change. This does not protect the other
    // fields; in particular, conflictingAlts is set after
    // we've made this readonly.
    this.readOnly = false;
    // Track the elements as they are added to the set; supports get(i)///
    this.configs = [];

    // TODO: these fields make me pretty uncomfortable but nice to pack up info
    // together, saves recomputation
    // TODO: can we track conflicts as they are added to save scanning configs
    // later?
    this.uniqueAlt = 0;
    this.conflictingAlts = null;

    // Used in parser and lexer. In lexer, it indicates we hit a pred
    // while computing a closure operation. Don't make a DFA state from this.
    this.hasSemanticContext = false;
    this.dipsIntoOuterContext = false;

    this.cachedHashString = "-1";

    return this;
}

// Adding a new config means merging contexts with existing configs for
// {@code (s, i, pi, _)}, where {@code s} is the
// {@link ATNConfig//state}, {@code i} is the {@link ATNConfig//alt}, and
// {@code pi} is the {@link ATNConfig//semanticContext}. We use
// {@code (s,i,pi)} as key.
//
// <p>This method updates {@link //dipsIntoOuterContext} and
// {@link //hasSemanticContext} when necessary.</p>
// /
ATNConfigSet.prototype.add = function (config, mergeCache) {
    if (mergeCache === undefined) {
        mergeCache = null;
    }
    if (this.readOnly) {
        throw "This set is readonly";
    }
    if (config.semanticContext !== SemanticContext.NONE) {
        this.hasSemanticContext = true;
    }
    if (config.reachesIntoOuterContext > 0) {
        this.dipsIntoOuterContext = true;
    }
    var existing = this.configLookup.add(config);
    if (existing === config) {
        this.cachedHashString = "-1";
        this.configs.push(config); // track order here
        return true;
    }
    // a previous (s,i,pi,_), merge with it and save result
    var rootIsWildcard = !this.fullCtx;
    var merged = merge(existing.context, config.context, rootIsWildcard, mergeCache);
    // no need to check for existing.context, config.context in cache
    // since only way to create new graphs is "call rule" and here. We
    // cache at both places.
    existing.reachesIntoOuterContext = Math.max(existing.reachesIntoOuterContext, config.reachesIntoOuterContext);
    // make sure to preserve the precedence filter suppression during the merge
    if (config.precedenceFilterSuppressed) {
        existing.precedenceFilterSuppressed = true;
    }
    existing.context = merged; // replace context; no need to alt mapping
    return true;
};

ATNConfigSet.prototype.getStates = function () {
    var states = new Set();
    for (var i = 0; i < this.configs.length; i++) {
        states.add(this.configs[i].state);
    }
    return states;
};

ATNConfigSet.prototype.getPredicates = function () {
    var preds = [];
    for (var i = 0; i < this.configs.length; i++) {
        var c = this.configs[i].semanticContext;
        if (c !== SemanticContext.NONE) {
            preds.push(c.semanticContext);
        }
    }
    return preds;
};

Object.defineProperty(ATNConfigSet.prototype, "items", {
    get: function () {
        return this.configs;
    }
});

ATNConfigSet.prototype.optimizeConfigs = function (interpreter) {
    if (this.readOnly) {
        throw "This set is readonly";
    }
    if (this.configLookup.length === 0) {
        return;
    }
    for (var i = 0; i < this.configs.length; i++) {
        var config = this.configs[i];
        config.context = interpreter.getCachedContext(config.context);
    }
};

ATNConfigSet.prototype.addAll = function (coll) {
    for (var i = 0; i < coll.length; i++) {
        this.add(coll[i]);
    }
    return false;
};

ATNConfigSet.prototype.equals = function (other) {
    if (this === other) {
        return true;
    } else if (!(other instanceof ATNConfigSet)) {
        return false;
    }
    return this.configs !== null && this.configs.equals(other.configs) &&
        this.fullCtx === other.fullCtx &&
        this.uniqueAlt === other.uniqueAlt &&
        this.conflictingAlts === other.conflictingAlts &&
        this.hasSemanticContext === other.hasSemanticContext &&
        this.dipsIntoOuterContext === other.dipsIntoOuterContext;
};

ATNConfigSet.prototype.hashString = function () {
    if (this.readOnly) {
        if (this.cachedHashString === "-1") {
            this.cachedHashString = this.hashConfigs();
        }
        return this.cachedHashString;
    } else {
        return this.hashConfigs();
    }
};

ATNConfigSet.prototype.hashConfigs = function () {
    var s = "";
    this.configs.map(function (c) {
        s += c.toString();
    });
    return s;
};

Object.defineProperty(ATNConfigSet.prototype, "length", {
    get: function () {
        return this.configs.length;
    }
});

ATNConfigSet.prototype.isEmpty = function () {
    return this.configs.length === 0;
};

ATNConfigSet.prototype.contains = function (item) {
    if (this.configLookup === null) {
        throw "This method is not implemented for readonly sets.";
    }
    return this.configLookup.contains(item);
};

ATNConfigSet.prototype.containsFast = function (item) {
    if (this.configLookup === null) {
        throw "This method is not implemented for readonly sets.";
    }
    return this.configLookup.containsFast(item);
};

ATNConfigSet.prototype.clear = function () {
    if (this.readOnly) {
        throw "This set is readonly";
    }
    this.configs = [];
    this.cachedHashString = "-1";
    this.configLookup = new Set();
};

ATNConfigSet.prototype.setReadonly = function (readOnly) {
    this.readOnly = readOnly;
    if (readOnly) {
        this.configLookup = null; // can't mod, no need for lookup cache
    }
};

ATNConfigSet.prototype.toString = function () {
    return Utils.arrayToString(this.configs) +
        (this.hasSemanticContext ? ",hasSemanticContext=" + this.hasSemanticContext : "") +
        (this.uniqueAlt !== ATN.INVALID_ALT_NUMBER ? ",uniqueAlt=" + this.uniqueAlt : "") +
        (this.conflictingAlts !== null ? ",conflictingAlts=" + this.conflictingAlts : "") +
        (this.dipsIntoOuterContext ? ",dipsIntoOuterContext" : "");
};

function OrderedATNConfigSet() {
    ATNConfigSet.call(this);
    this.configLookup = new Set();
    return this;
}

OrderedATNConfigSet.prototype = Object.create(ATNConfigSet.prototype);
OrderedATNConfigSet.prototype.constructor = OrderedATNConfigSet;

exports.ATNConfigSet = ATNConfigSet;
exports.OrderedATNConfigSet = OrderedATNConfigSet;
