You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

array-set.js 3.1KB

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