File Explorer

1/**2 * Mnemonist SparseSet3 * ====================4 *5 * JavaScript sparse set implemented on top of byte arrays.6 *7 * [Reference]: https://research.swtch.com/sparse8 */9var Iterator = require('obliterator/iterator'),10    getPointerArray = require('./utils/typed-arrays.js').getPointerArray;11 12/**13 * SparseSet.14 *15 * @constructor16 */17function SparseSet(length) {18 19  var ByteArray = getPointerArray(length);20 21  // Properties22  this.size = 0;23  this.length = length;24  this.dense = new ByteArray(length);25  this.sparse = new ByteArray(length);26}27 28/**29 * Method used to clear the structure.30 *31 * @return {undefined}32 */33SparseSet.prototype.clear = function() {34  this.size = 0;35};36 37/**38 * Method used to check the existence of a member in the set.39 *40 * @param  {number} member - Member to test.41 * @return {SparseSet}42 */43SparseSet.prototype.has = function(member) {44  var index = this.sparse[member];45 46  return (47    index < this.size &&48    this.dense[index] === member49  );50};51 52/**53 * Method used to add a member to the set.54 *55 * @param  {number} member - Member to add.56 * @return {SparseSet}57 */58SparseSet.prototype.add = function(member) {59  var index = this.sparse[member];60 61  if (index < this.size && this.dense[index] === member)62    return this;63 64  this.dense[this.size] = member;65  this.sparse[member] = this.size;66  this.size++;67 68  return this;69};70 71/**72 * Method used to remove a member from the set.73 *74 * @param  {number} member - Member to delete.75 * @return {boolean}76 */77SparseSet.prototype.delete = function(member) {78  var index = this.sparse[member];79 80  if (index >= this.size || this.dense[index] !== member)81    return false;82 83  index = this.dense[this.size - 1];84  this.dense[this.sparse[member]] = index;85  this.sparse[index] = this.sparse[member];86  this.size--;87 88  return true;89};90 91/**92 * Method used to iterate over the set's values.93 *94 * @param  {function}  callback - Function to call for each item.95 * @param  {object}    scope    - Optional scope.96 * @return {undefined}97 */98SparseSet.prototype.forEach = function(callback, scope) {99  scope = arguments.length > 1 ? scope : this;100 101  var item;102 103  for (var i = 0; i < this.size; i++) {104    item = this.dense[i];105 106    callback.call(scope, item, item);107  }108};109 110/**111 * Method used to create an iterator over a set's values.112 *113 * @return {Iterator}114 */115SparseSet.prototype.values = function() {116  var size = this.size,117      dense = this.dense,118      i = 0;119 120  return new Iterator(function() {121    if (i < size) {122      var item = dense[i];123      i++;124 125      return {126        value: item127      };128    }129 130    return {131      done: true132    };133  });134};135 136/**137 * Attaching the #.values method to Symbol.iterator if possible.138 */139if (typeof Symbol !== 'undefined')140  SparseSet.prototype[Symbol.iterator] = SparseSet.prototype.values;141 142/**143 * Convenience known methods.144 */145SparseSet.prototype.inspect = function() {146  var proxy = new Set();147 148  for (var i = 0; i < this.size; i++)149    proxy.add(this.dense[i]);150 151  // Trick so that node displays the name of the constructor152  Object.defineProperty(proxy, 'constructor', {153    value: SparseSet,154    enumerable: false155  });156 157  proxy.length = this.length;158 159  return proxy;160};161 162if (typeof Symbol !== 'undefined')163  SparseSet.prototype[Symbol.for('nodejs.util.inspect.custom')] = SparseSet.prototype.inspect;164 165/**166 * Exporting.167 */168module.exports = SparseSet;169