iavector.js

// Copyright Rod Vagg; Licensed under the Apache License, Version 2.0, see README.md for more information

const assert = require('assert')

/**
 * ```js
 * let vector = await iavector.create(store)
 * ```
 *
 * Create a new `IAVector` instance with a backing store. This operation is asynchronous and returns a `Promise` that
 * resolves to an `IAVector` instance. A `create()` will perform at least one `save()` on the backing store, to store
 * the root node and any child nodes required if a `from` argument is supplied.
 *
 * @name iavector.create
 * @function
 * @async
 * @param {Object} store A backing store for this `IAVector`. The store should be able to save and load a serialised
 * form of a single node of a `IAVector` which is provided as a plain object representation. `store.save(node)` takes
 * a serialisable node and should return a content address / ID for the node. `store.load(id)` serves the inverse
 * purpose, taking a content address / ID as provided by a `save()` operation and returning the serialised form
 * of a node which can be instantiated by `IAVector`.
 * The `store` object should take the following form: `{ async save(node):id, async load(id):node }`
 * @param {number} [width=256] The width of this `IAVector`, in that each node of the tree structure generated by will
 * have, at most, `width` child nodes, or `width` values at the leaves.
 * @param {Array} [from] An optional Array to marshall into an `IAVector`. Each element of the `from` array will be
 * stored at a leaf node, in order. If no `from` argument is supplied, a zero-length `IAVector` is returned.
 */
async function create (store, width = 256, from) {
  if (!from || (Array.isArray(from) && from.length === 0)) {
    const newNode = new IAVector(store, width)
    return save(store, newNode)
  } else if (Array.isArray(from)) {
    return createFromArray(store, from, width)
  } else {
    throw new TypeError('Unsupported `from` type')
  }
}

/**
 * Immutable Asynchronous Vector
 *
 * The `IAVector` constructor should not be used directly. Use `iavector.create()` to instantiate.
 *
 * @class
 * @property {any} id - A unique identifier for this `IAVector` instance. IDs are generated by the backing store and
 * are returned on `save()` operations.
 * @property {number} width - Width of the current `IAVector`. This determines the maximum number of elements that
 * can be stored in the `data` array. It is assumed that all nodes in an `IAVector` tree structure will have the same
 * `width` value or the traversal algorithms will fail.
 * @property {number} [height=0] - Height of the current node in the `IAVector`. This is used to determine the indexing
 * of lookups within the `data` array for this level of the tree structure. Height values are the inverse of depth from
 * a root node perspective. That is, the further from the root node, the lower the `height` value, until `0` where the
 * leaf nodes and their values exist.
 * @property {Array} [data=[]] - Array of data elements. For `height` `0` nodes, these elements are leaf values, or
 * the raw values stored in the `IAVector`. For `height` greater than `0` nodes, these elements store IDs of child
 * nodes within the tree structure.
 * See {@link iavector.create} for more details.
 */
class IAVector {
  constructor (store, width, height = 0, data = []) {
    if (!store || typeof store.save !== 'function' ||
        typeof store.load !== 'function') {
      throw new TypeError('Invalid `store` parameter, must be of type: { save(node):id, load(id):node }')
    }
    ro(this, 'store', store)

    if (typeof width !== 'number' || !Number.isInteger(width) || width <= 1) {
      throw new TypeError('Invalid `width` parameter, must be an integer greater than 1')
    }
    ro(this, 'width', width)

    if (typeof height !== 'number' || !Number.isInteger(height)) {
      throw new TypeError('Invalid `height` parameter, must be an integer')
    }
    ro(this, 'height', height)

    if (!Array.isArray(data)) {
      throw new TypeError('Invalid `data` parameter, must be an array')
    }
    ro(this, 'data', data)

    this.id = null
    this._tailChain = null
  }

  /**
   * Asynchronously find and return a value at the given `index` if it exists within this `IAVector`.
   *
   * @param {number} index A index of the value to lookup.
   * @returns {Promise} A `Promise` that resolves to the value being sought if that value exists within this `IAVector`.
   * If the `index` is out of bounds for this `IAVector`, the `Promise` will resolve to `undefined`.
   * @async
   */
  async get (index) {
    const traversal = traverseGet(this, index)
    while (true) {
      const nextId = traversal.traverse()
      if (!nextId) {
        return traversal.value()
      }
      const child = await this.store.load(nextId)
      traversal.next(child)
    }
  }

  /**
   * Asynchronously create a new `IAVector` instance identical to this one but with `value` appended to the
   * end.
   *
   * @param {*} value The value to append at `size() + 1`.
   */
  async push (value) {
    const tailChain = (this._tailChain || await this._getTailChain()).slice()
    let tail
    let node = this
    // this will flip to true if we reach a point in the chain that has space to append
    // otherwise it will stay false, meaning we made a new right-child at each level and need to
    // overflow at the top level
    let mutatedExisting = false
    while ((tail = tailChain.pop())) {
      if (mutatedExisting || tail.data.length < this.width) {
        // at the tail we either have space to fit a new one in, or we've mutated a child
        // and just need to replace the ref
        const newData = tail.height === 0 || !mutatedExisting ? tail.data.slice() : tail.data.slice(0, -1)
        newData.push(tail.height === 0 ? value : node.id)
        node = await save(this.store, new IAVector(this.store, this.width, tail.height, newData))
        mutatedExisting = true
      } else {
        // overflow
        node = await save(this.store, new IAVector(this.store, this.width, tail.height, [tail.height === 0 ? value : node.id]))
        mutatedExisting = false
      }
    }

    if (!mutatedExisting) {
      // top level overflow, new level needed, safe to assume the above operation produced a new 1-element node
      return save(this.store, new IAVector(this.store, this.width, this.height + 1, [this.id, node.id]))
    }

    return node
  }

  async size () {
    const tailChain = (this._tailChain || await this._getTailChain()).slice()
    const traversal = traverseSize(tailChain.shift())
    while (true) {
      const nextId = traversal.traverse()
      if (!nextId) {
        assert.strictEqual(tailChain.length, 0)
        return traversal.size()
      }
      traversal.next(tailChain.shift())
    }
  }

  async _getTailChain () {
    let chainHeight = this.height
    let node = this
    this._tailChain = [this]
    while (chainHeight-- > 0) {
      const tailId = node.data[node.data.length - 1]
      node = await load(this.store, tailId, this.width, chainHeight)
      this._tailChain.push(node)
    }
    return this._tailChain
  }

  /**
   * Asynchronously emit all values that exist within this `IAVector`. This will cause a full traversal of all nodes
   * if allowed to complete.
   *
   * @returns {AsyncIterator} An async iterator that yields values.
   * @async
   */
  async * values () {
    yield * performValuesTraversal(this)
  }

  /**
   * Asynchronously emit all nodes that exist within this `IAVector`. Values emitted by the `AsyncIterator` will
   * take the form `{ id, node }`.
   *
   * @returns {AsyncIterator} An async iterator that yields nodes.
   * @async
   */
  async * nodes () {
    yield * traverseNodes(this)
  }

  /**
   * Asynchronously emit the IDs of this `IAVector` and all of its children.
   *
   * @returns {AsyncIterator} An async iterator that yields the ID of this `IAVector` and all of its children.
   * The type of ID is determined by the backing store which is responsible for generating IDs upon `save()` operations.
   */
  async * ids () {
    yield this.id
    for await (const node of traverseNodes(this)) {
      yield node.id
    }
  }

  /**
   * Returns a serialisable form of this `IAVector` node. The internal representation of this local node is copied into
   * a plain JavaScript `Object` including a representation of its `data` array which will either contain raw values (for
   * `height` of `0`) or IDs of child nodes (for `height` of greater than `0`).
   *
   * Nodes take the serialised form:
   * ```
   * {
   *   width: number,
   *   height: number,
   *   data: Array
   * }
   * ```
   *
   * @returns {Object} An object representing the internal state of this local `IAVector` node, including links to
   * child nodes, if any.
   */
  toSerializable () {
    const r = {
      height: this.height,
      width: this.width,
      data: this.data
    }
    return r
  }
}

/**
 * Determine if an object is an instance of an `IAVector`
 *
 * @param {Object}
 * @returns {boolean}
 */
IAVector.isIAVector = function isIAVector (node) {
  return node instanceof IAVector
}

// store a new node and assign it an ID
async function save (store, newNode) {
  const id = await store.save(newNode.toSerializable())
  ro(newNode, 'id', id)
  return newNode
}

/**
 * ```js
 * let vector = await iavector.load(store, id)
 * ```
 *
 * Create an IAVector instance loaded from a serialised form in a backing store. See {@link iavector.create}.
 *
 * @name iavector.load
 * @function
 * @async
 * @param {Object} store - A backing store for this Vector. See {@link iavector.create}.
 * @param id - An content address / ID understood by the backing `store`.
 */
async function load (store, id, expectedWidth, expectedHeight) {
  const serialized = await store.load(id)
  return fromSerializable(store, id, serialized, expectedWidth, expectedHeight)
}

/**
 * Determine if a serializable object is an `IAVector` node type, can be used to assert whether a data block is
 * an `IAVector` node before trying to instantiate it.
 *
 * @name iavector.isSerializable
 * @function
 * @param {Object} serializable An object that may be a serialisable form of an `IAVector` node
 * @returns {boolean} An indication that the serialisable form is or is not an `IAVector` node
 */
function isSerializable (serializable) {
  return typeof serializable === 'object' &&
    typeof serializable.height === 'number' &&
    typeof serializable.width === 'number' &&
    Array.isArray(serializable.data)
}

/**
 * Instantiate an `IAVector` from a valid serialisable form of an `IAVector` node. The serializable should be the same as
 * produced by {@link IAVector#toSerializable}.
 * Serialised forms must contain `height`, `width` properties, both integers, and a `data` array of between zero and
 * `width` elements.
 *
 * @name iavector.fromSerializable
 * @function
 * @param {Object} store A backing store for this Map. See {@link iavector.create}.
 * @param {Object} id An optional ID for the instantiated `IAVector` node. Unlike {@link iavector.create},
 * `fromSerializable()` does not `save()` a newly created `IAVector` node so an ID is not generated for it. If one is
 * required for downstream purposes it should be provided, if the value is `null` or `undefined`, `node.id` will
 * be `null` but will remain writable.
 * @param {Object} serializable The serializable form of an `IAVector` node to be instantiated
 * @param {Object} [expectedWidth] A `width` to expect from the new node, if `expectedWidth` is provided and the node
 * does not have that value for `width`, an `Error` will be thrown.
 * @param {Object} [expectedHeight] A `height` to expect from the new node, if `expectedHeight` is provided and the node
 * does not have that value for `height`, an `Error` will be thrown.
 * @returns {Object} An `IAVector` instance
 */
function fromSerializable (store, id, serializable, expectedWidth, expectedHeight) {
  if (!isSerializable(serializable)) {
    throw new Error('Object is not a valid IAVector node')
  }
  if (typeof expectedWidth === 'number') {
    if (serializable.width !== expectedWidth) {
      throw new Error(`IAVector node does not have expected width of ${expectedWidth} (${serializable.width})`)
    }
  }
  if (typeof expectedHeight === 'number') {
    if (serializable.height !== expectedHeight) {
      throw new Error(`IAVector node does not have expected height of ${expectedHeight} (${serializable.height})`)
    }
  }
  if (IAVector.isIAVector(serializable)) {
    // should we check id?
    return serializable
  }
  const node = new IAVector(store, serializable.width, serializable.height, serializable.data)
  if (id != null) {
    ro(node, 'id', id)
  }
  return node
}

async function createFromArray (store, values, width) {
  const construction = constructFrom(values, width, store)
  while (true) {
    let c = 0
    for (const node of construction.construct()) {
      c++
      construction.saved(await save(store, node))
    }
    if (c === 0) {
      break
    }
  }
  return construction.root()
}

/**
 * Perform a synchronous block-by-block creation of a new `IAVector` give a set of `values` to be stored in nodes with
 * `width` elements. Returns a {@link ConstructFrom} object for performing the save operation.
 *
 * If `store` is not provied, an internal non-functioning "dummy store" will be used and the resulting `IAVector`s,
 * including the new root won't be able to perform standard functions such as `get()` and `append()`, although they will
 * be suitable for serialisation.
 *
 * @name iavector.constructFrom
 * @function
 * @param {number} width The width to be used for each `IAVector` node, see {@link iavector.create}.
 * @param {Array} values The values to be stored in the new `IAVector` structure.
 * @param {Object} [store] The backing store to be used for new `IAVector` nodes.
 * @returns A {@link ConstructFrom} object to perform the creation block-by-block
 */
function constructFrom (values, width = 256, store = dummyStore) {
  return new ConstructFrom(values, width, store)
}

/**
 * A construction object for synchronous block-by-block creation of a new `IAVector` given a list of `values` to be
 * distributed over `width` sized blocks.
 *
 * Call the `construct()` generator and for each node yielded, save and send the saved node back with the `saved(node)`
 * function. Continue to call `construct()` until there are no more nodes yielded, whereupon `root()` will provide the root
 * node which should also be the last provided node via `saved(node)`.
 */
class ConstructFrom {
  constructor (values, width, store) {
    this._nextValues = values
    this._width = width
    this._height = 0
    this._store = store
  }

  /**
   * TODO
   */
  * construct () {
    if (this._nextValues.length === 1 && this._height !== 0) {
      this._root = this._nextValues[0]
      return
    }
    // save values at height=0, save child node ids at height>0
    const values = this._height === 0 ? this._nextValues : this._nextValues.map((n) => n.id)
    this._nextValues = []
    // divide up the values into this._width length blocks
    const nodesAtHeight = Math.ceil(values.length / this._width)
    for (let i = 0; i < nodesAtHeight; i++) {
      const data = values.slice(i * this._width, Math.min((i + 1) * this._width, values.length))
      yield new IAVector(this._store, this._width, this._height, data)
    }
    this._height++
  }

  /**
   * TODO
   */
  saved (node) {
    this._nextValues.push(node)
  }

  /**
   * TODO
   */
  root () {
    return this._root
  }
}

/**
 * Perform a per-block synchronous traversal of all nodes in the `IAVector` under the `rootBlock` node provided.
 * Returns a {@link ValuesTraversal} object for performing traversals block-by-block. Note that `values()`
 * will only yield values on leaf nodes, with intermediate nodes only requiring further child nodes in order to
 * proceed.
 *
 * @name iavector.traverseValues
 * @function
 * @param {Object} rootBlock The root block, for extracting the `IAVector` configuration data
 * @returns A {@link ValuesTraversal} object for performing the traversal block-by-block and collecting their
 * values.
 */
function traverseValues (rootBlock) {
  return new ValuesTraversal(rootBlock)
}

async function * performValuesTraversal (root) {
  const traversal = traverseValues(root)

  while (true) {
    yield * traversal.values()
    const id = traversal.traverse()
    if (!id) {
      break
    }
    const child = await root.store.load(id)
    traversal.next(child)
  }
}

async function * traverseNodes (root) {
  const traversal = new ValuesTraversal(root)

  while (true) {
    const id = traversal.traverse()
    if (!id) {
      break
    }
    const child = await root.store.load(id)
    yield { id, node: child }
    traversal.next(child)
  }
}

/**
 * An `ValuesTraversal` object is returned by the {@link iavector.traverseValues} function for performing
 * block-by-block traversals on an `IAVector` for the purpose of iterating over or collecting values.
 */
class ValuesTraversal {
  constructor (rootBlock) {
    this._stack = []
    this._width = null
    this._height = null
    this.next(rootBlock)
  }

  _peek () {
    return this._stack[this._stack.length - 1]
  }

  _nextLink (node, start) {
    if (node.height === 0 || start === node.data.length - 1) {
      return -1
    }
    return start + 1
  }

  /**
   * Perform a single-block traversal.
   *
   * @returns {Object} A link to the next block required for further traversal (to be provided via
   * {@link ValuesTraversal#next}) or `null` if there are no more nodes to be traversed in this `IAVector`.
   */
  traverse () {
    let n = this._peek()
    while (!n || n.nextLink === -1) {
      this._stack.pop()
      this._height++ // back up toward the root
      n = this._peek()
      if (!n) {
        return null
      }
    }
    const link = n.node.data[n.nextLink]
    n.nextLink = this._nextLink(n.node, n.nextLink)
    return link
  }

  /**
   * Provide the next block required for traversal.
   *
   * @param {Object} block A serialized form of an `IAVector` intermediate/child block identified by an identifier
   * returned from {@link ValuesTraversal#traverse}.
   */
  next (block) {
    // if we have nulls, this is the first block, for the rest the width has to be consistent and the height has to
    // be correct for where we are in the tree
    const expectedWidth = this._width === null ? block.width : this._width
    const expectedHeight = this._height === null ? block.height : this._height - 1
    const node = fromSerializable(dummyStore, 0, block, expectedWidth, expectedHeight)
    this._height = node.height // height--, down toward the leaves
    if (this._width === null) {
      this._width = node.width
    }
    this._stack.push({ node, nextLink: this._nextLink(node, -1) })
  }

  /**
   * An iterator providing all of the values in the current `IAVector` node being traversed.
   *
   * @returns {Iterator} An iterator that yields value objects.
   */
  * values () {
    const n = this._peek()
    if (n && n.node.height === 0) {
      for (const v of n.node.data) {
        yield v
      }
    }
  }
}

/**
 * Perform a per-block synchronous traversal as a `get()` operation. Takes a root block, the index being looked
 * up and returns a {@link GetTraversal} object for performing traversals block-by-block.
 *
 * @name iavector.traverseGet
 * @function
 * @param {Object} rootBlock The root block, for extracting the `IAVector` configuration data
 * @param {number} index an index to look up.
 * @returns A {@link GetTraversal} object for performing the traversal block-by-block.
 */
function traverseGet (rootBlock, index) {
  return new GetTraversal(rootBlock, index)
}

/**
 * An `GetTraversal` object is returned by the {@link iavector.traverseGet} function for performing
 * block-by-block traversals on an `IAVector`.
 */
class GetTraversal {
  constructor (rootBlock, index) {
    this._index = index
    this._width = rootBlock.width
    this._height = rootBlock.height
    this._node = fromSerializable(dummyStore, 0, rootBlock)
    this._value = undefined
  }

  /**
   * Perform a single-block traversal.
   *
   * @returns {Object} A link to the next block required for further traversal (to be provided via
   * {@link GetTraversal#next}) or `null` if a value has been found (and is available via
   * {@link GetTraversal#value}) or the value doesn't exist.
   */
  traverse () {
    const t = traverseGetOne(this._node, this._index)

    if (!t) { // probably OOB
      return null
    }

    if (t.value !== undefined) { // found
      this._value = t.value
      return null
    }

    // need another block
    this._index = t.nextIndex
    this._height = t.nextHeight
    return t.nextId
  }

  /**
   * Provide the next block required for traversal.
   *
   * @param {Object} block A serialized form of an `IAVector` intermediate/child block identified by an identifier
   * returned from {@link ValuesTraversal#traverse}.
   */
  next (block) {
    this._node = fromSerializable(dummyStore, 0, block, this._width, this._height)
  }

  /**
   * Get the final value of the traversal, if one has been found.
   *
   * @returns A value, if one has been found, otherwise `undefined` (if one has not been found or we are mid-traversal)
   */
  value () {
    return this._value
  }
}

/**
 * Perform a `get()` on a single `IAVector` node. Returns either an indication of an OOB, a `value` if the `index` is
 * found within this node, or a continuation descriptor for proceeding with the look up on a child block.
 *
 * @param {Object} node An `IAVector` node, or a serialized form of one.
 * @param {number} index The index to look up in this node.
 * @returns {Object} Either `null` if OOB, an object with a `value` property with a found value, or an object with the
 * form `{ nextId, nextHeight, nextIndex }`, where `nextId` is the next block needed for a traversal, `nextHeight` is
 * the expected height of the node identified by `nextId` and `nextIndex` being the index to continue the look-up such
 * that a `traverseGetOne(node, index)` on the `node` identified by `nextId` uses `nextIndex` as the `index` value.
 */
function traverseGetOne (node, index) {
  if (index < 0) { // -OOB
    return null
  }

  const thisMax = node.width ** (node.height + 1)
  if (index > thisMax) { // OOB
    return null
  }

  const children = node.width ** node.height
  const thisIndex = Math.floor(index / children)
  if (thisIndex >= node.data.length) {
    return null
  }

  if (node.height === 0) {
    // found
    return { value: node.data[thisIndex] }
  }

  const nextId = node.data[thisIndex] // link to next
  const nextHeight = node.height - 1
  const nextIndex = index % children

  return { nextId, nextHeight, nextIndex }
}

/**
 * Perform a per-block synchronous traversal as a `size()` operation. Takes a root block and returns a
 * {@link SizeTraversal} object for performing traversals block-by-block.
 *
 * @name iavector.traverseSize
 * @function
 * @param {Object} rootBlock The root block, for extracting the `IAVector` configuration data
 * @returns A {@link SizeTraversal} object for performing the traversal block-by-block.
 */
function traverseSize (rootBlock) {
  return new SizeTraversal(rootBlock)
}

/**
 * An `SizeTraversal` object is returned by the {@link iavector.traverseSize} function for performing
 * block-by-block traversals on an `IAVector`.
 */
class SizeTraversal {
  constructor (rootBlock) {
    this._node = fromSerializable(dummyStore, 0, rootBlock)
    this._size = rootBlock.width ** (rootBlock.height + 1) // max size
  }

  /**
   * Perform a single-block traversal.
   *
   * @returns {Object} A link to the next block required for further traversal (to be provided via
   * {@link SizeTraversal#next}) or `null` if a size has been calculated (and is available via
   * {@link SizeTraversal#value})
   */
  traverse () {
    // TODO: should we block this from running twice? `traverse()` is not idempotent in any traversal case
    // remove from max size the number of unfilled nodes at this left side of the tree
    this._size -= this._node.width ** this._node.height * (this._node.width - this._node.data.length)
    if (this._node.height === 0) {
      return null
    }
    return this._node.data[this._node.data.length - 1] // link to leftmost next level
  }

  /**
   * Provide the next block required for traversal.
   *
   * @param {Object} block A serialized form of an `IAVector` intermediate/child block identified by an identifier
   * returned from {@link ValuesTraversal#traverse}.
   */
  next (block) {
    this._node = fromSerializable(dummyStore, 0, block, this._node.width, this._node.height - 1)
  }

  /**
   * Get the final size calculated by this traversal.
   *
   * @returns {number} the size of this `IAVector` if the traversal has completed, otherwise `undefined`
   */
  size () {
    if (this._node.height !== 0) {
      return undefined
    }
    return this._size
  }
}

/* istanbul ignore next */
const dummyStore = {
  load () {
    throw new Error('load() not implemented on dummy store')
  },
  save () {
    throw new Error('save() not implemented on dummy store')
  }
}

function ro (obj, prop, value) {
  Object.defineProperty(obj, prop, { value, writable: false, enumerable: true })
}

module.exports.create = create
module.exports.load = load
module.exports.constructFrom = constructFrom
module.exports.fromSerializable = fromSerializable
module.exports.isSerializable = isSerializable
module.exports.traverseValues = traverseValues
module.exports.traverseGet = traverseGet
module.exports.traverseGetOne = traverseGetOne
module.exports.traverseSize = traverseSize