File Explorer

1/**2 * Mnemonist SparseQueueSet3 * =========================4 *5 * JavaScript sparse queue 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 * SparseQueueSet.14 *15 * @constructor16 */17function SparseQueueSet(capacity) {18 19  var ByteArray = getPointerArray(capacity);20 21  // Properties22  this.start = 0;23  this.size = 0;24  this.capacity = capacity;25  this.dense = new ByteArray(capacity);26  this.sparse = new ByteArray(capacity);27}28 29/**30 * Method used to clear the structure.31 *32 * @return {undefined}33 */34SparseQueueSet.prototype.clear = function() {35  this.start = 0;36  this.size = 0;37};38 39/**40 * Method used to check the existence of a member in the queue.41 *42 * @param  {number} member - Member to test.43 * @return {SparseQueueSet}44 */45SparseQueueSet.prototype.has = function(member) {46  if (this.size === 0)47    return false;48 49  var index = this.sparse[member];50 51  var inBounds = (52    index < this.capacity &&53    (54      index >= this.start &&55      index < this.start + this.size56    ) ||57    (58      index < ((this.start + this.size) % this.capacity)59    )60  );61 62  return (63    inBounds &&64    this.dense[index] === member65  );66};67 68/**69 * Method used to add a member to the queue.70 *71 * @param  {number} member - Member to add.72 * @return {SparseQueueSet}73 */74SparseQueueSet.prototype.enqueue = function(member) {75  var index = this.sparse[member];76 77  if (this.size !== 0) {78    var inBounds = (79      index < this.capacity &&80      (81        index >= this.start &&82        index < this.start + this.size83      ) ||84      (85        index < ((this.start + this.size) % this.capacity)86      )87    );88 89    if (inBounds && this.dense[index] === member)90      return this;91  }92 93  index = (this.start + this.size) % this.capacity;94 95  this.dense[index] = member;96  this.sparse[member] = index;97  this.size++;98 99  return this;100};101 102/**103 * Method used to remove the next member from the queue.104 *105 * @param  {number} member - Member to delete.106 * @return {boolean}107 */108SparseQueueSet.prototype.dequeue = function() {109  if (this.size === 0)110    return;111 112  var index = this.start;113 114  this.size--;115  this.start++;116 117  if (this.start === this.capacity)118    this.start = 0;119 120  var member = this.dense[index];121 122  this.sparse[member] = this.capacity;123 124  return member;125};126 127/**128 * Method used to iterate over the queue's values.129 *130 * @param  {function}  callback - Function to call for each item.131 * @param  {object}    scope    - Optional scope.132 * @return {undefined}133 */134SparseQueueSet.prototype.forEach = function(callback, scope) {135  scope = arguments.length > 1 ? scope : this;136 137  var c = this.capacity,138      l = this.size,139      i = this.start,140      j = 0;141 142  while (j < l) {143    callback.call(scope, this.dense[i], j, this);144    i++;145    j++;146 147    if (i === c)148      i = 0;149  }150};151 152/**153 * Method used to create an iterator over a set's values.154 *155 * @return {Iterator}156 */157SparseQueueSet.prototype.values = function() {158  var dense = this.dense,159      c = this.capacity,160      l = this.size,161      i = this.start,162      j = 0;163 164  return new Iterator(function() {165    if (j >= l)166      return {167        done: true168      };169 170    var value = dense[i];171 172    i++;173    j++;174 175    if (i === c)176      i = 0;177 178    return {179      value: value,180      done: false181    };182  });183};184 185/**186 * Attaching the #.values method to Symbol.iterator if possible.187 */188if (typeof Symbol !== 'undefined')189  SparseQueueSet.prototype[Symbol.iterator] = SparseQueueSet.prototype.values;190 191/**192 * Convenience known methods.193 */194SparseQueueSet.prototype.inspect = function() {195  var proxy = [];196 197  this.forEach(function(member) {198    proxy.push(member);199  });200 201  // Trick so that node displays the name of the constructor202  Object.defineProperty(proxy, 'constructor', {203    value: SparseQueueSet,204    enumerable: false205  });206 207  proxy.capacity = this.capacity;208 209  return proxy;210};211 212if (typeof Symbol !== 'undefined')213  SparseQueueSet.prototype[Symbol.for('nodejs.util.inspect.custom')] = SparseQueueSet.prototype.inspect;214 215/**216 * Exporting.217 */218module.exports = SparseQueueSet;219