File Explorer

1/**2 * Mnemonist HashedArrayTree3 * ==========================4 *5 * Abstract implementation of a hashed array tree representing arrays growing6 * dynamically.7 */8 9/**10 * Defaults.11 */12var DEFAULT_BLOCK_SIZE = 1024;13 14/**15 * Helpers.16 */17function powerOfTwo(x) {18  return (x & (x - 1)) === 0;19}20 21/**22 * HashedArrayTree.23 *24 * @constructor25 * @param {function}      ArrayClass           - An array constructor.26 * @param {number|object} initialCapacityOrOptions - Self-explanatory.27 */28function HashedArrayTree(ArrayClass, initialCapacityOrOptions) {29  if (arguments.length < 1)30    throw new Error('mnemonist/hashed-array-tree: expecting at least a byte array constructor.');31 32  var initialCapacity = initialCapacityOrOptions || 0,33      blockSize = DEFAULT_BLOCK_SIZE,34      initialLength = 0;35 36  if (typeof initialCapacityOrOptions === 'object') {37    initialCapacity = initialCapacityOrOptions.initialCapacity || 0;38    initialLength = initialCapacityOrOptions.initialLength || 0;39    blockSize = initialCapacityOrOptions.blockSize || DEFAULT_BLOCK_SIZE;40  }41 42  if (!blockSize || !powerOfTwo(blockSize))43    throw new Error('mnemonist/hashed-array-tree: block size should be a power of two.');44 45  var capacity = Math.max(initialLength, initialCapacity),46      initialBlocks = Math.ceil(capacity / blockSize);47 48  this.ArrayClass = ArrayClass;49  this.length = initialLength;50  this.capacity = initialBlocks * blockSize;51  this.blockSize = blockSize;52  this.offsetMask = blockSize - 1;53  this.blockMask = Math.log2(blockSize);54 55  // Allocating initial blocks56  this.blocks = new Array(initialBlocks);57 58  for (var i = 0; i < initialBlocks; i++)59    this.blocks[i] = new this.ArrayClass(this.blockSize);60}61 62/**63 * Method used to set a value.64 *65 * @param  {number} index - Index to edit.66 * @param  {any}    value - Value.67 * @return {HashedArrayTree}68 */69HashedArrayTree.prototype.set = function(index, value) {70 71  // Out of bounds?72  if (this.length < index)73    throw new Error('HashedArrayTree(' + this.ArrayClass.name + ').set: index out of bounds.');74 75  var block = index >> this.blockMask,76      i = index & this.offsetMask;77 78  this.blocks[block][i] = value;79 80  return this;81};82 83/**84 * Method used to get a value.85 *86 * @param  {number} index - Index to retrieve.87 * @return {any}88 */89HashedArrayTree.prototype.get = function(index) {90  if (this.length < index)91    return;92 93  var block = index >> this.blockMask,94      i = index & this.offsetMask;95 96  return this.blocks[block][i];97};98 99/**100 * Method used to grow the array.101 *102 * @param  {number}          capacity - Optional capacity to accomodate.103 * @return {HashedArrayTree}104 */105HashedArrayTree.prototype.grow = function(capacity) {106  if (typeof capacity !== 'number')107    capacity = this.capacity + this.blockSize;108 109  if (this.capacity >= capacity)110    return this;111 112  while (this.capacity < capacity) {113    this.blocks.push(new this.ArrayClass(this.blockSize));114    this.capacity += this.blockSize;115  }116 117  return this;118};119 120/**121 * Method used to resize the array. Won't deallocate.122 *123 * @param  {number}       length - Target length.124 * @return {HashedArrayTree}125 */126HashedArrayTree.prototype.resize = function(length) {127  if (length === this.length)128    return this;129 130  if (length < this.length) {131    this.length = length;132    return this;133  }134 135  this.length = length;136  this.grow(length);137 138  return this;139};140 141/**142 * Method used to push a value into the array.143 *144 * @param  {any}    value - Value to push.145 * @return {number}       - Length of the array.146 */147HashedArrayTree.prototype.push = function(value) {148  if (this.capacity === this.length)149    this.grow();150 151  var index = this.length;152 153  var block = index >> this.blockMask,154      i = index & this.offsetMask;155 156  this.blocks[block][i] = value;157 158  return ++this.length;159};160 161/**162 * Method used to pop the last value of the array.163 *164 * @return {number} - The popped value.165 */166HashedArrayTree.prototype.pop = function() {167  if (this.length === 0)168    return;169 170  var lastBlock = this.blocks[this.blocks.length - 1];171 172  var i = (--this.length) & this.offsetMask;173 174  return lastBlock[i];175};176 177/**178 * Convenience known methods.179 */180HashedArrayTree.prototype.inspect = function() {181  var proxy = new this.ArrayClass(this.length),182      block;183 184  for (var i = 0, l = this.length; i < l; i++) {185    block = i >> this.blockMask;186    proxy[i] = this.blocks[block][i & this.offsetMask];187  }188 189  proxy.type = this.ArrayClass.name;190  proxy.items = this.length;191  proxy.capacity = this.capacity;192  proxy.blockSize = this.blockSize;193 194  // Trick so that node displays the name of the constructor195  Object.defineProperty(proxy, 'constructor', {196    value: HashedArrayTree,197    enumerable: false198  });199 200  return proxy;201};202 203if (typeof Symbol !== 'undefined')204  HashedArrayTree.prototype[Symbol.for('nodejs.util.inspect.custom')] = HashedArrayTree.prototype.inspect;205 206/**207 * Exporting.208 */209module.exports = HashedArrayTree;210