File Explorer

1/**2 * Mnemonist FixedStack3 * =====================4 *5 * The fixed stack is a stack whose capacity is defined beforehand and that6 * cannot be exceeded. This class is really useful when combined with7 * byte arrays to save up some memory and avoid memory re-allocation, hence8 * speeding up computations.9 *10 * This has however a downside: you need to know the maximum size you stack11 * can have during your iteration (which is not too difficult to compute when12 * performing, say, a DFS on a balanced binary tree).13 */14var Iterator = require('obliterator/iterator'),15    iterables = require('./utils/iterables.js');16 17/**18 * FixedStack19 *20 * @constructor21 * @param {function} ArrayClass - Array class to use.22 * @param {number}   capacity   - Desired capacity.23 */24function FixedStack(ArrayClass, capacity) {25 26  if (arguments.length < 2)27    throw new Error('mnemonist/fixed-stack: expecting an Array class and a capacity.');28 29  if (typeof capacity !== 'number' || capacity <= 0)30    throw new Error('mnemonist/fixed-stack: `capacity` should be a positive number.');31 32  this.capacity = capacity;33  this.ArrayClass = ArrayClass;34  this.items = new this.ArrayClass(this.capacity);35  this.clear();36}37 38/**39 * Method used to clear the stack.40 *41 * @return {undefined}42 */43FixedStack.prototype.clear = function() {44 45  // Properties46  this.size = 0;47};48 49/**50 * Method used to add an item to the stack.51 *52 * @param  {any}    item - Item to add.53 * @return {number}54 */55FixedStack.prototype.push = function(item) {56  if (this.size === this.capacity)57    throw new Error('mnemonist/fixed-stack.push: stack capacity (' + this.capacity + ') exceeded!');58 59  this.items[this.size++] = item;60  return this.size;61};62 63/**64 * Method used to retrieve & remove the last item of the stack.65 *66 * @return {any}67 */68FixedStack.prototype.pop = function() {69  if (this.size === 0)70    return;71 72  return this.items[--this.size];73};74 75/**76 * Method used to get the last item of the stack.77 *78 * @return {any}79 */80FixedStack.prototype.peek = function() {81  return this.items[this.size - 1];82};83 84/**85 * Method used to iterate over the stack.86 *87 * @param  {function}  callback - Function to call for each item.88 * @param  {object}    scope    - Optional scope.89 * @return {undefined}90 */91FixedStack.prototype.forEach = function(callback, scope) {92  scope = arguments.length > 1 ? scope : this;93 94  for (var i = 0, l = this.items.length; i < l; i++)95    callback.call(scope, this.items[l - i - 1], i, this);96};97 98/**99 * Method used to convert the stack to a JavaScript array.100 *101 * @return {array}102 */103FixedStack.prototype.toArray = function() {104  var array = new this.ArrayClass(this.size),105      l = this.size - 1,106      i = this.size;107 108  while (i--)109    array[i] = this.items[l - i];110 111  return array;112};113 114/**115 * Method used to create an iterator over a stack's values.116 *117 * @return {Iterator}118 */119FixedStack.prototype.values = function() {120  var items = this.items,121      l = this.size,122      i = 0;123 124  return new Iterator(function() {125    if (i >= l)126      return {127        done: true128      };129 130    var value = items[l - i - 1];131    i++;132 133    return {134      value: value,135      done: false136    };137  });138};139 140/**141 * Method used to create an iterator over a stack's entries.142 *143 * @return {Iterator}144 */145FixedStack.prototype.entries = function() {146  var items = this.items,147      l = this.size,148      i = 0;149 150  return new Iterator(function() {151    if (i >= l)152      return {153        done: true154      };155 156    var value = items[l - i - 1];157 158    return {159      value: [i++, value],160      done: false161    };162  });163};164 165/**166 * Attaching the #.values method to Symbol.iterator if possible.167 */168if (typeof Symbol !== 'undefined')169  FixedStack.prototype[Symbol.iterator] = FixedStack.prototype.values;170 171 172/**173 * Convenience known methods.174 */175FixedStack.prototype.toString = function() {176  return this.toArray().join(',');177};178 179FixedStack.prototype.toJSON = function() {180  return this.toArray();181};182 183FixedStack.prototype.inspect = function() {184  var array = this.toArray();185 186  array.type = this.ArrayClass.name;187  array.capacity = this.capacity;188 189  // Trick so that node displays the name of the constructor190  Object.defineProperty(array, 'constructor', {191    value: FixedStack,192    enumerable: false193  });194 195  return array;196};197 198if (typeof Symbol !== 'undefined')199  FixedStack.prototype[Symbol.for('nodejs.util.inspect.custom')] = FixedStack.prototype.inspect;200 201/**202 * Static @.from function taking an arbitrary iterable & converting it into203 * a stack.204 *205 * @param  {Iterable} iterable   - Target iterable.206 * @param  {function} ArrayClass - Array class to use.207 * @param  {number}   capacity   - Desired capacity.208 * @return {FixedStack}209 */210FixedStack.from = function(iterable, ArrayClass, capacity) {211 212  if (arguments.length < 3) {213    capacity = iterables.guessLength(iterable);214 215    if (typeof capacity !== 'number')216      throw new Error('mnemonist/fixed-stack.from: could not guess iterable length. Please provide desired capacity as last argument.');217  }218 219  var stack = new FixedStack(ArrayClass, capacity);220 221  if (iterables.isArrayLike(iterable)) {222    var i, l;223 224    for (i = 0, l = iterable.length; i < l; i++)225      stack.items[i] = iterable[i];226 227    stack.size = l;228 229    return stack;230  }231 232  iterables.forEach(iterable, function(value) {233    stack.push(value);234  });235 236  return stack;237};238 239/**240 * Exporting.241 */242module.exports = FixedStack;243