File Explorer

1/**2 * Mnemonist Queue3 * ================4 *5 * Queue implementation based on the ideas of Queue.js that seems to beat6 * a LinkedList one in performance.7 */8var Iterator = require('obliterator/iterator'),9    forEach = require('obliterator/foreach');10 11/**12 * Queue13 *14 * @constructor15 */16function Queue() {17  this.clear();18}19 20/**21 * Method used to clear the queue.22 *23 * @return {undefined}24 */25Queue.prototype.clear = function() {26 27  // Properties28  this.items = [];29  this.offset = 0;30  this.size = 0;31};32 33/**34 * Method used to add an item to the queue.35 *36 * @param  {any}    item - Item to enqueue.37 * @return {number}38 */39Queue.prototype.enqueue = function(item) {40 41  this.items.push(item);42  return ++this.size;43};44 45/**46 * Method used to retrieve & remove the first item of the queue.47 *48 * @return {any}49 */50Queue.prototype.dequeue = function() {51  if (!this.size)52    return;53 54  var item = this.items[this.offset];55 56  if (++this.offset * 2 >= this.items.length) {57    this.items = this.items.slice(this.offset);58    this.offset = 0;59  }60 61  this.size--;62 63  return item;64};65 66/**67 * Method used to retrieve the first item of the queue.68 *69 * @return {any}70 */71Queue.prototype.peek = function() {72  if (!this.size)73    return;74 75  return this.items[this.offset];76};77 78/**79 * Method used to iterate over the queue.80 *81 * @param  {function}  callback - Function to call for each item.82 * @param  {object}    scope    - Optional scope.83 * @return {undefined}84 */85Queue.prototype.forEach = function(callback, scope) {86  scope = arguments.length > 1 ? scope : this;87 88  for (var i = this.offset, j = 0, l = this.items.length; i < l; i++, j++)89    callback.call(scope, this.items[i], j, this);90};91 92/*93 * Method used to convert the queue to a JavaScript array.94 *95 * @return {array}96 */97Queue.prototype.toArray = function() {98  return this.items.slice(this.offset);99};100 101/**102 * Method used to create an iterator over a queue's values.103 *104 * @return {Iterator}105 */106Queue.prototype.values = function() {107  var items = this.items,108      i = this.offset;109 110  return new Iterator(function() {111    if (i >= items.length)112      return {113        done: true114      };115 116    var value = items[i];117    i++;118 119    return {120      value: value,121      done: false122    };123  });124};125 126/**127 * Method used to create an iterator over a queue's entries.128 *129 * @return {Iterator}130 */131Queue.prototype.entries = function() {132  var items = this.items,133      i = this.offset,134      j = 0;135 136  return new Iterator(function() {137    if (i >= items.length)138      return {139        done: true140      };141 142    var value = items[i];143    i++;144 145    return {146      value: [j++, value],147      done: false148    };149  });150};151 152/**153 * Attaching the #.values method to Symbol.iterator if possible.154 */155if (typeof Symbol !== 'undefined')156  Queue.prototype[Symbol.iterator] = Queue.prototype.values;157 158/**159 * Convenience known methods.160 */161Queue.prototype.toString = function() {162  return this.toArray().join(',');163};164 165Queue.prototype.toJSON = function() {166  return this.toArray();167};168 169Queue.prototype.inspect = function() {170  var array = this.toArray();171 172  // Trick so that node displays the name of the constructor173  Object.defineProperty(array, 'constructor', {174    value: Queue,175    enumerable: false176  });177 178  return array;179};180 181if (typeof Symbol !== 'undefined')182  Queue.prototype[Symbol.for('nodejs.util.inspect.custom')] = Queue.prototype.inspect;183 184/**185 * Static @.from function taking an arbitrary iterable & converting it into186 * a queue.187 *188 * @param  {Iterable} iterable   - Target iterable.189 * @return {Queue}190 */191Queue.from = function(iterable) {192  var queue = new Queue();193 194  forEach(iterable, function(value) {195    queue.enqueue(value);196  });197 198  return queue;199};200 201/**202 * Static @.of function taking an arbitrary number of arguments & converting it203 * into a queue.204 *205 * @param  {...any} args206 * @return {Queue}207 */208Queue.of = function() {209  return Queue.from(arguments);210};211 212/**213 * Exporting.214 */215module.exports = Queue;216