/* -*- Mode: js; js-indent-level: 2; -*- */ /* * Copyright 2011 Mozilla Foundation and contributors * Licensed under the New BSD license. See LICENSE or: * http://opensource.org/licenses/BSD-3-Clause */ if (typeof define !== 'function') { var define = require('amdefine')(module); } define(function (require, exports, module) { /** * A data structure which is a combination of an array and a set. Adding a new * member is O(1), testing for membership is O(1), and finding the index of an * element is O(1). Removing elements from the set is not supported. Only * strings are supported for membership. */ function ArraySet() { this._array = []; this._set = {}; } /** * Static method for creating ArraySet instances from an existing array. */ ArraySet.fromArray = function ArraySet_fromArray(aArray) { var set = new ArraySet(); for (var i = 0, len = aArray.length; i < len; i++) { set.add(aArray[i]); } return set; }; /** * Because behavior goes wacky when you set `__proto__` on `this._set`, we * have to prefix all the strings in our set with an arbitrary character. * * See https://github.com/mozilla/source-map/pull/31 and * https://github.com/mozilla/source-map/issues/30 * * @param String aStr */ ArraySet.prototype._toSetString = function ArraySet__toSetString (aStr) { return "$" + aStr; }; /** * Add the given string to this set. * * @param String aStr */ ArraySet.prototype.add = function ArraySet_add(aStr) { if (this.has(aStr)) { // Already a member; nothing to do. return; } var idx = this._array.length; this._array.push(aStr); this._set[this._toSetString(aStr)] = idx; }; /** * Is the given string a member of this set? * * @param String aStr */ ArraySet.prototype.has = function ArraySet_has(aStr) { return Object.prototype.hasOwnProperty.call(this._set, this._toSetString(aStr)); }; /** * What is the index of the given string in the array? * * @param String aStr */ ArraySet.prototype.indexOf = function ArraySet_indexOf(aStr) { if (this.has(aStr)) { return this._set[this._toSetString(aStr)]; } throw new Error('"' + aStr + '" is not in the set.'); }; /** * What is the element at the given index? * * @param Number aIdx */ ArraySet.prototype.at = function ArraySet_at(aIdx) { if (aIdx >= 0 && aIdx < this._array.length) { return this._array[aIdx]; } throw new Error('No element indexed by ' + aIdx); }; /** * Returns the array representation of this set (which has the proper indices * indicated by indexOf). Note that this is a copy of the internal array used * for storing the members so that no one can mess with internal state. */ ArraySet.prototype.toArray = function ArraySet_toArray() { return this._array.slice(); }; exports.ArraySet = ArraySet; });