/**
 * This class provides an **unordered** collection similar to `Ext.util.Collection`. The
 * removal of order maintenance provides a significant performance increase. Further, this
 * class does not provide events or other high-level features. It maintains an array of
 * `items` and a map to quickly find items by their `id`.
 *
 * @private
 * @since 5.1.1
 */
Ext.define('Ext.util.Bag', {
    isBag: true,

    constructor: function() {
        /**
         * @property {Object[]} items
         * An array containing the items.
         * @private
         * @since 5.1.1
         */
        this.items = [];

        /**
         * @property {Object} map
         * An object used as a map to find items based on their key.
         * @private
         * @since 5.1.1
         */
        this.map = {};
    },

    /**
     * @property {Number} generation
     * Mutation counter which is incremented when the collection changes.
     * @readonly
     * @since 5.1.1
     */
    generation: 0,

    /**
     * @property {Number} length
     * The count of items in the collection.
     * @readonly
     * @since 5.1.1
     */
    length: 0,

    beginUpdate: Ext.emptyFn,

    endUpdate: Ext.emptyFn,

    add: function(item) {
        var me = this,
            items = me.items,
            map = me.map,
            n = 1,
            old, i, idx, id, it, ret, was;

        if (Ext.isArray(item)) {
            old = ret = [];
            n = item.length;
        }

        for (i = 0; i < n; i++) {
            id = me.getKey(it = old ? item[i] : item);
            idx = map[id];

            if (idx === undefined) {
                items.push(it);
                map[id] = me.length++;

                if (old) {
                    old.push(it);
                }
                else {
                    ret = it;
                }
            }
            else {
                was = items[idx];

                if (old) {
                    old.push(was);
                }
                else {
                    ret = was;
                }

                items[idx] = it;
            }
        }

        ++me.generation;

        return ret;
    },

    clear: function() {
        var me = this,
            needsClear = me.generation || me.length,
            ret = needsClear ? me.items : [];

        if (needsClear) {
            me.items = [];
            me.length = 0;
            me.map = {};
            ++me.generation;
        }

        return ret;
    },

    clone: function() {
        var me = this,
            ret = new me.self(),
            len = me.length;

        if (len) {
            Ext.apply(ret.map, me.map);
            ret.items = me.items.slice();
            ret.length = me.length;
        }

        return ret;
    },

    contains: function(item) {
        var ret = false,
            map = this.map,
            key;

        if (item != null) {
            key = this.getKey(item);

            if (key in map) {
                ret = this.items[map[key]] === item;
            }
        }

        return ret;
    },

    containsKey: function(key) {
        return key in this.map;
    },

    destroy: function() {
        this.items = this.map = null;
        this.callParent();
    },

    each: function(fn, scope) {
        var items = this.items,
            len = items.length,
            i, ret;

        if (len) {
            scope = scope || this;
            items = items.slice(0); // safe for re-entrant calls

            for (i = 0; i < len; i++) {
                ret = fn.call(scope, items[i], i, len);

                if (ret === false) {
                    break;
                }
            }
        }

        return ret;
    },

    getAt: function(index) {
        var out = null;

        if (index < this.length) {
            out = this.items[index];
        }

        return out;
    },

    get: function(key) {
        return this.getByKey(key);
    },

    getByKey: function(key) {
        var map = this.map,
            ret = (key in map) ? this.items[map[key]] : null;

        return ret;
    },

    indexOfKey: function(key) {
        var map = this.map,
            ret = (key in map) ? map[key] : -1;

        return ret;
    },

    last: function() {
        return this.items[this.length - 1];
    },

    updateKey: function(item, oldKey) {
        var me = this,
            map = me.map,
            newKey;

        if (!item || !oldKey) {
            return;
        }

        if ((newKey = me.getKey(item)) !== oldKey) {
            if (me.getAt(map[oldKey]) === item && !(newKey in map)) {
                me.generation++;
                map[newKey] = map[oldKey];
                delete map[oldKey];
            }
        }
        //<debug>
        else {
            // It may be that the item is (somehow) already in the map using the
            // newKey or that there is no item in the map with the oldKey. These
            // are not errors.

            if (newKey in map && me.getAt(map[newKey]) !== item) {
                // There is a different item in the map with the newKey which is an
                // error. To properly handle this, add the item instead.
                Ext.raise('Duplicate newKey "' + newKey +
                                '" for item with oldKey "' + oldKey + '"');
            }

            if (oldKey in map && me.getAt(map[oldKey]) !== item) {
                // There is a different item in the map with the oldKey which is also
                // an error. Do not call this method for items that are not part of
                // the collection.
                Ext.raise('Incorrect oldKey "' + oldKey +
                                '" for item with newKey "' + newKey + '"');
            }
        }
        //</debug>
    },

    getCount: function() {
        return this.length;
    },

    getKey: function(item) {
        return item.id || item.getId();
    },

    getRange: function(begin, end) {
        var items = this.items,
            length = items.length,
            range;

        if (!length) {
            range = [];
        }
        else {
            range = Ext.Number.clipIndices(length, [begin, end]);
            range = items.slice(range[0], range[1]);
        }

        return range;
    },

    remove: function(item) {
        var me = this,
            map = me.map,
            items = me.items,
            ret = null,
            n = 1,
            changed, old, i, idx, id, last, was;

        if (Ext.isArray(item)) {
            n = item.length;
            old = ret = [];
        }

        if (me.length) {
            for (i = 0; i < n; i++) {
                idx = map[id = me.getKey(old ? item[i] : item)];

                if (idx !== undefined) {
                    delete map[id];
                    was = items[idx];

                    if (old) {
                        old.push(was);
                    }
                    else {
                        ret = was;
                    }

                    last = items.pop();

                    if (idx < --me.length) {
                        items[idx] = last;
                        map[me.getKey(last)] = idx;
                    }

                    changed = true;
                }
            }

            if (changed) {
                ++me.generation;
            }
        }

        return ret;
    },

    removeByKey: function(key) {
        var item = this.getByKey(key);

        if (item) {
            this.remove(item);
        }

        return item || null;
    },

    replace: function(item) {
        this.add(item);

        return item;
    },

    sort: function(fn) {
        var me = this,
            items = me.items,
            n = items.length,
            item;

        if (n) {
            Ext.Array.sort(items, fn);

            me.map = {};

            while (n-- > 0) {
                item = items[n];
                me.map[me.getKey(item)] = n;
            }

            ++me.generation;
        }
    }
});