git.r.bdr.sh - rbdr/dotfiles/blob

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