www.aleph1.co.uk Git - yaffs-website/blob - node_modules/source-map/lib/array-set.js

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