1  /* -*- Mode: js; js-indent-level: 2; -*- */
  2  /*
  3   * Copyright 2011 Mozilla Foundation and contributors
  4   * Licensed under the New BSD license. See LICENSE or:
  5   * http://opensource.org/licenses/BSD-3-Clause
  6   */
  7  
  8  var util = require('./util');
  9  var has = Object.prototype.hasOwnProperty;
 10  var hasNativeMap = typeof Map !== "undefined";
 11  
 12  /**
 13   * A data structure which is a combination of an array and a set. Adding a new
 14   * member is O(1), testing for membership is O(1), and finding the index of an
 15   * element is O(1). Removing elements from the set is not supported. Only
 16   * strings are supported for membership.
 17   */
 18  function ArraySet() {
 19    this._array = [];
 20    this._set = hasNativeMap ? new Map() : Object.create(null);
 21  }
 22  
 23  /**
 24   * Static method for creating ArraySet instances from an existing array.
 25   */
 26  ArraySet.fromArray = function ArraySet_fromArray(aArray, aAllowDuplicates) {
 27    var set = new ArraySet();
 28    for (var i = 0, len = aArray.length; i < len; i++) {
 29      set.add(aArray[i], aAllowDuplicates);
 30    }
 31    return set;
 32  };
 33  
 34  /**
 35   * Return how many unique items are in this ArraySet. If duplicates have been
 36   * added, than those do not count towards the size.
 37   *
 38   * @returns Number
 39   */
 40  ArraySet.prototype.size = function ArraySet_size() {
 41    return hasNativeMap ? this._set.size : Object.getOwnPropertyNames(this._set).length;
 42  };
 43  
 44  /**
 45   * Add the given string to this set.
 46   *
 47   * @param String aStr
 48   */
 49  ArraySet.prototype.add = function ArraySet_add(aStr, aAllowDuplicates) {
 50    var sStr = hasNativeMap ? aStr : util.toSetString(aStr);
 51    var isDuplicate = hasNativeMap ? this.has(aStr) : has.call(this._set, sStr);
 52    var idx = this._array.length;
 53    if (!isDuplicate || aAllowDuplicates) {
 54      this._array.push(aStr);
 55    }
 56    if (!isDuplicate) {
 57      if (hasNativeMap) {
 58        this._set.set(aStr, idx);
 59      } else {
 60        this._set[sStr] = idx;
 61      }
 62    }
 63  };
 64  
 65  /**
 66   * Is the given string a member of this set?
 67   *
 68   * @param String aStr
 69   */
 70  ArraySet.prototype.has = function ArraySet_has(aStr) {
 71    if (hasNativeMap) {
 72      return this._set.has(aStr);
 73    } else {
 74      var sStr = util.toSetString(aStr);
 75      return has.call(this._set, sStr);
 76    }
 77  };
 78  
 79  /**
 80   * What is the index of the given string in the array?
 81   *
 82   * @param String aStr
 83   */
 84  ArraySet.prototype.indexOf = function ArraySet_indexOf(aStr) {
 85    if (hasNativeMap) {
 86      var idx = this._set.get(aStr);
 87      if (idx >= 0) {
 88          return idx;
 89      }
 90    } else {
 91      var sStr = util.toSetString(aStr);
 92      if (has.call(this._set, sStr)) {
 93        return this._set[sStr];
 94      }
 95    }
 96  
 97    throw new Error('"' + aStr + '" is not in the set.');
 98  };
 99  
100  /**
101   * What is the element at the given index?
102   *
103   * @param Number aIdx
104   */
105  ArraySet.prototype.at = function ArraySet_at(aIdx) {
106    if (aIdx >= 0 && aIdx < this._array.length) {
107      return this._array[aIdx];
108    }
109    throw new Error('No element indexed by ' + aIdx);
110  };
111  
112  /**
113   * Returns the array representation of this set (which has the proper indices
114   * indicated by indexOf). Note that this is a copy of the internal array used
115   * for storing the members so that no one can mess with internal state.
116   */
117  ArraySet.prototype.toArray = function ArraySet_toArray() {
118    return this._array.slice();
119  };
120  
121  exports.ArraySet = ArraySet;