An Immutable Asynchronous Vector.
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
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 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.
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.
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 ]async iavector.create(store[, width][, from])class IAVectorasync 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 ConstructFromConstructFrom#construct()ConstructFrom#saved()ConstructFrom#root()iavector.traverseValues(rootBlock)class ValuesTraversalValuesTraversal#traverse()ValuesTraversal#next(block)ValuesTraversal#values()iavector.traverseGet(rootBlock, index)class GetTraversalGetTraversal#traverse()GetTraversal#next(block)GetTraversal#value()traverseGetOne(node, index)iavector.traverseSize(rootBlock)class SizeTraversalSizeTraversal#traverse()SizeTraversal#next(block)SizeTraversal#size()
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 thisIAVector. The store should be able to save and load a serialised form of a single node of aIAVectorwhich 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 asave()operation and returning the serialised form of a node which can be instantiated byIAVector. Thestoreobject should take the following form:{ async save(node):id, async load(id):node }width(number, optional, default=256): The width of thisIAVector, in that each node of the tree structure generated by will have, at most,widthchild nodes, orwidthvalues at the leaves.from(Array, optional): An optional Array to marshall into anIAVector. Each element of thefromarray will be stored at a leaf node, in order. If nofromargument is supplied, a zero-lengthIAVectoris returned.
Immutable Asynchronous Vector
The IAVector constructor should not be used directly. Use iavector.create() to instantiate.
Properties:
id(any): A unique identifier for thisIAVectorinstance. IDs are generated by the backing store and are returned onsave()operations.width(number): Width of the currentIAVector. This determines the maximum number of elements that can be stored in thedataarray. It is assumed that all nodes in anIAVectortree structure will have the samewidthvalue or the traversal algorithms will fail.height(number, optional, default=0): Height of the current node in theIAVector. This is used to determine the indexing of lookups within thedataarray 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 theheightvalue, until0where the leaf nodes and their values exist.data(Array, optional, default=[]): Array of data elements. Forheight0nodes, these elements are leaf values, or the raw values stored in theIAVector. Forheightgreater than0nodes, these elements store IDs of child nodes within the tree structure. Seeiavector.createfor more details.
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.
Asynchronously create a new IAVector instance identical to this one but with value appended to the
end.
Parameters:
value(*): The value to append atsize() + 1.
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.
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.
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.
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.
Determine if an object is an instance of an IAVector
Parameters:
node(Object)
Return value (boolean)
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. Seeiavector.create.id: An content address / ID understood by the backingstore.
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 anIAVectornode
Return value (boolean): An indication that the serialisable form is or is not an IAVector node
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. Seeiavector.create.id(Object): An optional ID for the instantiatedIAVectornode. Unlikeiavector.create,fromSerializable()does notsave()a newly createdIAVectornode so an ID is not generated for it. If one is required for downstream purposes it should be provided, if the value isnullorundefined,node.idwill benullbut will remain writable.serializable(Object): The serializable form of anIAVectornode to be instantiatedexpectedWidth(Object, optional): Awidthto expect from the new node, ifexpectedWidthis provided and the node does not have that value forwidth, anErrorwill be thrown.expectedHeight(Object, optional): Aheightto expect from the new node, ifexpectedHeightis provided and the node does not have that value forheight, anErrorwill be thrown.
Return value (Object): An IAVector instance
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 eachIAVectornode, seeiavector.create.values(Array): The values to be stored in the newIAVectorstructure.store(Object, optional): The backing store to be used for newIAVectornodes.
Return value : A ConstructFrom object to perform the creation block-by-block
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).
TODO
TODO
TODO
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 theIAVectorconfiguration data
Return value : A ValuesTraversal object for performing the traversal block-by-block and collecting their
values.
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.
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.
Provide the next block required for traversal.
Parameters:
block(Object): A serialized form of anIAVectorintermediate/child block identified by an identifier returned fromValuesTraversal#traverse.
An iterator providing all of the values in the current IAVector node being traversed.
Return value (Iterator): An iterator that yields value objects.
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 theIAVectorconfiguration dataindex(number): an index to look up.
Return value : A GetTraversal object for performing the traversal block-by-block.
An GetTraversal object is returned by the iavector.traverseGet function for performing
block-by-block traversals on an IAVector.
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.
Provide the next block required for traversal.
Parameters:
block(Object): A serialized form of anIAVectorintermediate/child block identified by an identifier returned fromValuesTraversal#traverse.
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)
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): AnIAVectornode, 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.
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 theIAVectorconfiguration data
Return value : A SizeTraversal object for performing the traversal block-by-block.
An SizeTraversal object is returned by the iavector.traverseSize function for performing
block-by-block traversals on an IAVector.
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)
Provide the next block required for traversal.
Parameters:
block(Object): A serialized form of anIAVectorintermediate/child block identified by an identifier returned fromValuesTraversal#traverse.
Get the final size calculated by this traversal.
Return value (number): the size of this IAVector if the traversal has completed, otherwise undefined
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.