IAVector

An Immutable Asynchronous Vector.

Warning

This is both experimental and a work in progress. The current form is not likely to be the final form. No guarantees are provided that serialised versions of today's version will be loadable in the future. This project may even be archived if significantly improved forms are discovered or derived.

However, rich documentation is provided as an invitation for collaboration to work on that final form; or as inspiration for alternative approaches to this problem space.

Caveat emptor for versions less than 1.0.0.

See also IAMap

Contents

• Warning
• Contents
• About

About

IAVector provides an Array-like interface that can organise data in a storage system that does not lend itself to organisation, such as a content addressed storage system like IPFS where you have to know the address of an element before you can fetch it.

IPLD

IPLD is the data layer of IPFS. One aim of this project is to work toward useful primitives that will allow more complex applications to be built that do not necessarily relate to the current IPFS file-focused use-case.

While IAVector is intended to operate on top of IPLD, it is intentionally built independent from it such that it could be used across any other datastore that presents similar challenges to storing and retrieving structured data.

Immutability

IAMap instances cannot be mutated, once instantiated, you cannot (or should not) modify its properties. Therefore, mutation requires the creation of new instances. Every map.set() and map.delete() operation will result in a new IAMap root node, which will have a new, unique identifier. New instances created by mutations essentially perform a copy-on-write (CoW), so only the modified node and its parents are impacted, all reference to unmodified nodes remain intact as links.

Mutation on a large data set may involve the creation of many new internal nodes, as references between nodes form part of the "content" and therefore require new identifiers. This is handled transparently but users should be aware that many intermediate nodes are created in a backing store during mutation operations.

Algorithm

Width: 3
Height
↓
0:     1 2 3

       Head chain: 1
       Tail chain: 3(full)


1:             a b
         ┌─────┘ │
0:     1 2 3   4 5

       Head chain: a → 1
       Tail chain: b → 5


1:             a b c
         ┌─────┘ │ └─────┐
0:     1 2 3   4 5 6   7 8 9

       Head chain: a → 1
       Tail chain: c(full) → 9(full)


2:                                        A  B
                 ┌────────────────────────┘  │
1:             a b c                      d  e
         ┌─────┘ │ └─────┐        ┌───────┘  │
0:     1 2 3   4 5 6   7 8 9   10 11 12   13 14 15

       Head chain: A → a → 1
       Tail chain: B → d → 15(full)

2:                                        A  B
                 ┌────────────────────────┘  │
1:             a b c                      d  e  f
         ┌─────┘ │ └─────┐        ┌───────┘  │  └────────┐
0:     1 2 3   4 5 6   7 8 9   10 11 12   13 14 15   16 17 18

       Head chain: A → a → 1
       Tail chain: B → f(full) → 18(full)


2:                                        A  B  C
                ┌─────────────────────────┘  │  └─────────────────────────────┐
1:             a b c                      d  e  f                          g  h  i
         ┌─────┘ │ └─────┐        ┌───────┘  │  └────────┐         ┌───────┘  │  └────────┐
0:     1 2 3   4 5 6   7 8 9   10 11 12   13 14 15   16 17 18   19 20 21   22 23 24   25 26 27

       Head chain: A → a → 1
       Tail chain: C(full) → i(full) → 27(full)


3:                                                                                               i  ii
                                             ┌───────────────────────────────────────────────────┘  │
2:                                        A  B  C                                                   D
                ┌─────────────────────────┘  │  └─────────────────────────────┐                     │
1:             a b c                      d  e  f                          g  h  i                  j
         ┌─────┘ │ └─────┐        ┌───────┘  │  └────────┐         ┌───────┘  │  └────────┐         │
0:     1 2 3   4 5 6   7 8 9   10 11 12   13 14 15   16 17 18   19 20 21   22 23 24   25 26 27   28 29 30

       Head chain: i → A → a → 1
       Tail chain: ii → D → j → 30(full)

FIXME: not quite right, doesn't deal with bounds

function dataIndex (width, height, i) {
  let ceil = width ** (height + 1)
  let floor = width ** height
  return Math.floor((i % ceil) / floor)
}

function dataIndexChain (width, height, i) {
  let ind = []
  do {
    ind.push(dataIndex(width, height, i))
  } while (height-- > 0)
  return ind
}

// position 29, value = 30
dataIndexChain(3, 3, 29) → [ 1, 0, 0, 2 ]
// position 27, value = 28
dataIndexChain(3, 3, 27) → [ 1, 0, 0, 0 ]
// position 26, value = 27
dataIndexChain(3, 3, 27) → [ 0, 2, 2, 2 ]
// position 2, value = 3
dataIndexChain(3, 3, 2) → [ 0, 0, 0, 2 ]
// position 0, value = 1
dataIndexChain(3, 3, 0) → [ 0, 0, 0, 0 ]

API

Contents

• async iavector.create(store[, width][, from])
• class IAVector
• async IAVector#get(index)
• async IAVector#push(value)
• async IAVector#values()
• async IAVector#nodes()
• async IAVector#ids()
• IAVector#toSerializable()
• IAVector.isIAVector(node)
• async iavector.load(store, id)
• iavector.isSerializable(serializable)
• iavector.fromSerializable(store, id, serializable[, expectedWidth][, expectedHeight])
• iavector.constructFrom(width, values[, store])
• class ConstructFrom
• ConstructFrom#construct()
• ConstructFrom#saved()
• ConstructFrom#root()
• iavector.traverseValues(rootBlock)
• class ValuesTraversal
• ValuesTraversal#traverse()
• ValuesTraversal#next(block)
• ValuesTraversal#values()
• iavector.traverseGet(rootBlock, index)
• class GetTraversal
• GetTraversal#traverse()
• GetTraversal#next(block)
• GetTraversal#value()
• traverseGetOne(node, index)
• iavector.traverseSize(rootBlock)
• class SizeTraversal
• SizeTraversal#traverse()
• SizeTraversal#next(block)
• SizeTraversal#size()

async iavector.create(store[, width][, from])

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.

Parameters:

• store (Object): 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 }
• width (number, optional, default=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.
• from (Array, optional): 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.

class IAVector

Immutable Asynchronous Vector

The IAVector constructor should not be used directly. Use iavector.create() to instantiate.

Properties:

• id (any): A unique identifier for this IAVector instance. IDs are generated by the backing store and are returned on save() operations.
• width (number): 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.
• height (number, optional, default=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.
• data (Array, optional, default=[]): 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 iavector.create for more details.

async IAVector#get(index)

Asynchronously find and return a value at the given index if it exists within this IAVector.

Parameters:

• index (number): A index of the value to lookup.

Return value (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 IAVector#push(value)

Asynchronously create a new IAVector instance identical to this one but with value appended to the end.

Parameters:

• value (*): The value to append at size() + 1.

async IAVector#values()

Asynchronously emit all values that exist within this IAVector. This will cause a full traversal of all nodes if allowed to complete.

Return value (AsyncIterator): An async iterator that yields values.

async IAVector#nodes()

Asynchronously emit all nodes that exist within this IAVector. Values emitted by the AsyncIterator will take the form { id, node }.

Return value (AsyncIterator): An async iterator that yields nodes.

async IAVector#ids()

Asynchronously emit the IDs of this IAVector and all of its children.

Return value (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.

IAVector#toSerializable()

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
}

Return value (Object): An object representing the internal state of this local IAVector node, including links to child nodes, if any.

IAVector.isIAVector(node)

Determine if an object is an instance of an IAVector

Parameters:

• node (Object)

Return value (boolean)

async iavector.load(store, id)

let vector = await iavector.load(store, id)

Create an IAVector instance loaded from a serialised form in a backing store. See iavector.create.

Parameters:

• store (Object): A backing store for this Vector. See iavector.create.
• id: An content address / ID understood by the backing store.

iavector.isSerializable(serializable)

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.

Parameters:

• serializable (Object): An object that may be a serialisable form of an IAVector node

Return value (boolean): An indication that the serialisable form is or is not an IAVector node

iavector.fromSerializable(store, id, serializable[, expectedWidth][, expectedHeight])

Instantiate an IAVector from a valid serialisable form of an IAVector node. The serializable should be the same as produced by IAVector#toSerializable. Serialised forms must contain height, width properties, both integers, and a data array of between zero and width elements.

Parameters:

• store (Object): A backing store for this Map. See iavector.create.
• id (Object): An optional ID for the instantiated IAVector node. Unlike 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.
• serializable (Object): The serializable form of an IAVector node to be instantiated
• expectedWidth (Object, optional): 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.
• expectedHeight (Object, optional): 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.

Return value (Object): An IAVector instance

iavector.constructFrom(width, values[, store])

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 ConstructFrom object for performing the save operation.

If store is not provied, an internal non-functioning "dummy store" will be used and the resulting IAVectors, including the new root won't be able to perform standard functions such as get() and append(), although they will be suitable for serialisation.

Parameters:

• width (number): The width to be used for each IAVector node, see iavector.create.
• values (Array): The values to be stored in the new IAVector structure.
• store (Object, optional): The backing store to be used for new IAVector nodes.

Return value : A ConstructFrom object to perform the creation block-by-block

class ConstructFrom

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).

ConstructFrom#construct()

TODO

ConstructFrom#saved()

TODO

ConstructFrom#root()

TODO

iavector.traverseValues(rootBlock)

Perform a per-block synchronous traversal of all nodes in the IAVector under the rootBlock node provided. Returns a 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.

Parameters:

• rootBlock (Object): The root block, for extracting the IAVector configuration data

Return value : A ValuesTraversal object for performing the traversal block-by-block and collecting their values.

class ValuesTraversal

An ValuesTraversal object is returned by the iavector.traverseValues function for performing block-by-block traversals on an IAVector for the purpose of iterating over or collecting values.

ValuesTraversal#traverse()

Perform a single-block traversal.

Return value (Object): A link to the next block required for further traversal (to be provided via ValuesTraversal#next) or null if there are no more nodes to be traversed in this IAVector.

ValuesTraversal#next(block)

Provide the next block required for traversal.

Parameters:

• block (Object): A serialized form of an IAVector intermediate/child block identified by an identifier returned from ValuesTraversal#traverse.

ValuesTraversal#values()

An iterator providing all of the values in the current IAVector node being traversed.

Return value (Iterator): An iterator that yields value objects.

iavector.traverseGet(rootBlock, index)

Perform a per-block synchronous traversal as a get() operation. Takes a root block, the index being looked up and returns a GetTraversal object for performing traversals block-by-block.

Parameters:

• rootBlock (Object): The root block, for extracting the IAVector configuration data
• index (number): an index to look up.

Return value : A GetTraversal object for performing the traversal block-by-block.

class GetTraversal

An GetTraversal object is returned by the iavector.traverseGet function for performing block-by-block traversals on an IAVector.

GetTraversal#traverse()

Perform a single-block traversal.

Return value (Object): A link to the next block required for further traversal (to be provided via GetTraversal#next) or null if a value has been found (and is available via GetTraversal#value) or the value doesn't exist.

GetTraversal#next(block)

Provide the next block required for traversal.

Parameters:

• block (Object): A serialized form of an IAVector intermediate/child block identified by an identifier returned from ValuesTraversal#traverse.

GetTraversal#value()

Get the final value of the traversal, if one has been found.

Return value : A value, if one has been found, otherwise undefined (if one has not been found or we are mid-traversal)

traverseGetOne(node, index)

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.

Parameters:

• node (Object): An IAVector node, or a serialized form of one.
• index (number): The index to look up in this node.

Return value (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.

iavector.traverseSize(rootBlock)

Perform a per-block synchronous traversal as a size() operation. Takes a root block and returns a SizeTraversal object for performing traversals block-by-block.

Parameters:

• rootBlock (Object): The root block, for extracting the IAVector configuration data

Return value : A SizeTraversal object for performing the traversal block-by-block.

class SizeTraversal

An SizeTraversal object is returned by the iavector.traverseSize function for performing block-by-block traversals on an IAVector.

SizeTraversal#traverse()

Perform a single-block traversal.

Return value (Object): A link to the next block required for further traversal (to be provided via SizeTraversal#next) or null if a size has been calculated (and is available via SizeTraversal#value)

SizeTraversal#next(block)

Provide the next block required for traversal.

Parameters:

• block (Object): A serialized form of an IAVector intermediate/child block identified by an identifier returned from ValuesTraversal#traverse.

SizeTraversal#size()

Get the final size calculated by this traversal.

Return value (number): the size of this IAVector if the traversal has completed, otherwise undefined

License and Copyright

Copyright 2019 Rod Vagg

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.