vectrie - npm Package Compare versions

+88

.github/workflows/ci.yml

		name: CI

		on:
		push:
		branches:
		- main
		paths:
		- "src/**"
		pull_request:
		branches:
		- main
		paths:
		- "src**"
		- ".github/workflows/ci.yml"
		workflow_dispatch:

		jobs:
		check:
		name: Typecheck
		runs-on: ubuntu-latest
		strategy:
		matrix:
		node-version:
		- 16
		steps:
		- name: Checkout
		uses: actions/checkout@v2

		- name: Setup node ${{ matrix.node-version }}
		uses: actions/setup-node@v2
		with:
		node-version: ${{ matrix.node-version }}

		- name: Install dependencies
		uses: bahmutov/npm-install@v1

		- name: Typecheck
		uses: gozala/typescript-error-reporter-action@v1.0.8
		with:
		project: ./tsconfig.json
		test-node:
		name: Test Node
		runs-on: ${{ matrix.os }}

		strategy:
		matrix:
		node-version:
		- 16
		os:
		- ubuntu-latest

		steps:
		- name: Checkout
		uses: actions/checkout@v2

		- name: Setup Node
		uses: actions/setup-node@v2
		with:
		node-version: ${{ matrix.node-version }}

		- name: Install dependencies
		uses: bahmutov/npm-install@v1

		- name: Test
		run: yarn test:node
		test-web:
		name: Test Web
		runs-on: ubuntu-latest

		strategy:
		matrix:
		node-version:
		- 16

		steps:
		- name: Checkout
		uses: actions/checkout@v2

		- name: Setup Node
		uses: actions/setup-node@v2
		with:
		node-version: 16

		- name: Install dependencies
		uses: bahmutov/npm-install@v1

		- name: Test
		run: yarn test:web

+35

.github/workflows/release.yml

		on:
		push:
		branches:
		- main
		workflow_dispatch:

		name: release
		jobs:
		release-please:
		runs-on: ubuntu-latest
		steps:
		- uses: GoogleCloudPlatform/release-please-action@v2
		id: release
		with:
		token: ${{ secrets.GITHUB_TOKEN }}
		release-type: node
		package-name: "vectrie"
		# The logic below handles the npm publication:
		- uses: actions/checkout@v2
		# these if statements ensure that a publication only occurs when
		# a new release is created:
		if: ${{ steps.release.outputs.release_created }}
		- uses: actions/setup-node@v2
		with:
		node-version: "16"
		registry-url: https://registry.npmjs.org/
		if: ${{ steps.release.outputs.release_created }}
		- name: Install
		uses: bahmutov/npm-install@v1
		if: ${{ steps.release.outputs.release_created }}
		- name: Publish
		run: npm publish
		env:
		NODE_AUTH_TOKEN: ${{secrets.NPM_TOKEN}}
		if: ${{ steps.release.outputs.release_created }}

+9

.repl.js

		// I just like having `.repl.js` for quickly bootstrapping
		// my repl environment. All exports will be added to repl
		// global

		export * from "./src/lib.js"
		export * from "./src/util.js"
		export * from "./src/core.js"

		export * as Vec from "./src/lib.js"

+8

CHANGELOG.md

		# Changelog

		## 1.0.0 (2022-03-16)


		### Features

		* initial implementation [#1](https://www.github.com/Gozala/vectrie/issues/1) ([17a67a3](https://www.github.com/Gozala/vectrie/commit/17a67a35bfc717cb0213fe21a21d4f4d43504887))

LICENSE-APACHE

Sorry, the diff of this file is not supported yet

LICENSE-MIT

Sorry, the diff of this file is not supported yet

src/api.js

+127

src/api.ts

		export interface PersistentVector<T> {
		readonly size: number
		readonly shift: number // BITS times (the depth of this trie minus one)
		readonly root: Branch<T>
		readonly tail: T[]
		}

		export interface MutableVector<T> {
		size: number
		shift: number
		root: Branch<T>
		tail: T[]
		}

		export interface MutableVectorView<T>
		extends MutableVector<T>,
		IndexedView<T>,
		LookupView<T>,
		AssociativeView<T, MutableVectorView<T>>,
		StackView<T, MutableVectorView<T>>,
		IterableView<T> {}

		export interface AssociativeView<T, Self> {
		set(n: number, value: T): Self
		}

		export interface StackView<T, Self> {
		push(value: T): Self
		pop(): Self

		peek<U = undefined>(notFound?: U): T \| U
		}

		export interface LookupView<T> {
		get(n: number): T \| undefined
		}
		export interface IndexedView<T> extends LookupView<T> {
		readonly [n: number]: T
		}

		export interface IterableView<T> extends Iterable<T> {
		values(options?: Partial<RangedIteratorOptions>): IterableIterator<T>
		entries(
		options?: Partial<RangedIteratorOptions>
		): IterableIterator<[number, T]>
		keys(): IterableIterator<number>
		}

		export interface CloneableView<Self> {
		clone(): Self
		}

		export interface EmptyableView<Self> {
		clear(): Self
		}

		export interface EqualityView<Other, Self extends Other> {
		equals(other: Other): other is Self
		}

		export interface PersistentVectorView<T>
		extends PersistentVector<T>,
		IndexedView<T>,
		LookupView<T>,
		AssociativeView<T, PersistentVectorView<T>>,
		StackView<T, PersistentVectorView<T>>,
		IterableView<T>,
		CloneableView<PersistentVectorView<T>>,
		EmptyableView<PersistentVectorView<T>>,
		EqualityView<PersistentVector<T>, PersistentVectorView<T>> {}

		/**
		* `VectorNode` reprenests nodes of the bit-partitioned vector trie. Which may
		* represent either `branch` nodes containing children or `leaf` nodes
		* containing `leaves`. Using type union e.g. `Node<T> = Branch<T> \| Leaf<T>`
		* would be more accurate however it would also require excessive checks even
		* though we have more effetive way to traverse trie. Which why instead we
		* encode nodes as `Branch<T> & Leaf<T>` so we do not have to convince type
		* checker which node we're dealing with.
		*/
		// export interface VectorNode<T> {
		// /**
		// * `MutableVector` tags nodes it creates with `edit`'s so it can tell which
		// * nodes it can safely update in-place and which it can't.
		// */
		// edit: null \| Edit

		// children: VectorNode<T>[]
		// leaves: T[]
		// }

		export interface Branch<T> {
		edit: null \| Edit
		leaves: never
		children: Trie<T>[]
		}

		export interface Leaf<T> {
		edit: null \| Edit
		children: never

		leaves: T[]
		}

		export type Trie<T> = Branch<T> \| Leaf<T>
		export type VectorNode<T> = Trie<T>

		export interface Edit {}

		export interface RangedIteratorOptions {
		readonly start: number
		readonly end: number
		}
		export interface RangedIterator<T> extends RangedIteratorOptions {
		offset: number
		base: number
		leaf: ReadonlyArray<T>
		readonly source: PersistentVector<T>
		}

		export interface RangedIteratorView<T>
		extends RangedIterator<T>,
		IterableIterator<T> {}

		export interface Editor<Edit> {
		forkVector<T>(self: PersistentVector<T>): MutableVector<T>
		}

+312

src/core.js

		import * as API from "./api.js"
		export * from "./api.js"
		import {
		BITS,
		WIDTH,
		MASK,
		createBranch,
		createLeaf,
		newPath,
		forkTail,
		forkBranch,
		forkLeaf,
		} from "./trie.js"

		export { BITS, WIDTH, MASK }

		/**
		* @template T
		* @param {API.Edit\|null} edit
		* @param {API.PersistentVector<T>} vector
		* @param {T} value
		* @returns {API.MutableVector<T>}
		*/
		export const conj = (edit, { size, tail, shift, root }, value) => {
		// There is room for a new value in the rightmost leaf node
		if (size - tailOffset(size) < WIDTH) {
		const newTail = forkTail(tail, edit)
		newTail[size & MASK] = value

		return { size: size + 1, tail: newTail, shift, root }
		} else {
		const newTail = new Array(WIDTH)
		newTail[0] = value

		const rootOverflow = size >>> BITS > 1 << shift
		const newShift = rootOverflow ? shift + BITS : shift
		const tailNode = createLeaf(edit, tail)
		const newRoot = rootOverflow
		? createBranch(edit, [root, newPath(edit, shift, tailNode)])
		: pushTail(edit, root, shift, size - 1, tailNode)

		return {
		size: size + 1,
		shift: newShift,
		root: newRoot,
		tail: newTail,
		}
		}
		}

		/**
		* @template T
		* @param {API.Edit\|null} edit
		* @param {API.Branch<T>} trie
		* @param {number} level
		* @param {number} index
		* @param {API.Leaf<T>} tailNode
		*/
		// export const pushTail = (edit, trie, level, index, tailNode) => {
		// let root = forkBranch(trie, edit)
		// let parent = root
		// let n = (index >>> level) & MASK

		// while (level > BITS) {
		// const child = parent.children[n]
		// if (child != null) {
		// const node = forkBranch(/** @type {API.Branch<T>} */ (child), edit)
		// parent.children[n] = node
		// parent = node
		// level -= BITS
		// n = (index >>> level) & MASK
		// } else {
		// const node = newPath(null, level - BITS, tailNode)
		// parent.children[n] = node
		// return root
		// }
		// }

		// parent.children[n] = tailNode
		// return root
		// }
		export const pushTail = (edit, trie, level, index, tailNode) => {
		const node = forkBranch(trie, edit)
		const n = (index >>> level) & MASK
		if (level > BITS) {
		const child = /** @type {API.Branch<T>\|null} */ (node.children[n])
		node.children[n] =
		child != null
		? pushTail(edit, child, level - BITS, index, tailNode)
		: newPath(edit, level - BITS, tailNode)
		} else {
		node.children[n] = tailNode
		}
		return node
		}

		/**
		* @template T
		* @param {API.Edit\|null} edit
		* @param {API.PersistentVector<T>} vector
		* @param {number} n
		* @param {T} value
		*/
		export const set = (edit, vector, n, value) => {
		if (n >= 0 && n < vector.size) {
		// If falls into the tail we just copy tail, set value and create
		// a new vector sharing with tail copy.
		if (n >= tailOffset(vector.size)) {
		const tail = forkTail(vector.tail, edit)
		tail[n & MASK] = value

		return { ...vector, tail }
		}
		// Otherwise we need to set the value inside a root.
		else {
		return {
		...vector,
		root: setInRoot(edit, vector.root, vector.shift, n, value),
		}
		}
		} else if (n === vector.size) {
		return conj(edit, vector, value)
		} else {
		throw new RangeError(`Index ${n} is out of bounds [0, ${vector.size}]`)
		}
		}

		/**
		* Creates a new vec
		*
		* @template T
		* @param {API.Edit\|null} edit
		* @param {API.Branch<T>} trie
		* @param {number} shift
		* @param {number} index
		* @param {T} value
		* @returns {API.Branch<T>}
		*/
		export const setInRoot = (edit, trie, shift, index, value) => {
		let level = shift

		// copy the root
		let root = forkBranch(trie, edit)
		let parent = root
		let n = (index >>> level) & MASK
		/** @type {API.VectorNode<T>} */
		let node = parent.children[n]
		while (level > BITS) {
		level -= BITS
		node = forkBranch(/** @type {API.Branch<T>} */ (node), edit)
		parent.children[n] = node

		n = (index >>> level) & MASK
		parent = node
		node = node.children[n]
		}

		const leaf = forkLeaf(/** @type {API.Leaf<T>} */ (node), edit)
		parent.children[n] = leaf
		leaf.leaves[index & MASK] = value

		return root
		}

		/**
		* @template T
		* @template {API.Edit\|null} E
		* @param {E} edit
		* @param {API.PersistentVector<T>} vector
		* @returns {API.MutableVector<T>}
		*/
		export const pop = (edit, vector) => {
		switch (vector.size) {
		case 0:
		throw new RangeError(`Can't pop empty vector`)
		case 1:
		const tail = forkTail(vector.tail, edit)
		delete tail[0]

		return { ...vector, size: 0, tail }
		default: {
		const n = (vector.size - 1) & MASK
		if (n > 0) {
		const tail = forkTail(vector.tail, edit)
		delete tail[n]
		const size = vector.size - 1

		return { ...vector, size: size, tail }
		} else {
		// Find a array containing elements and make copy if it has
		// a different edit field because if it saved into mutable
		// vector tail it can be mutated.
		const tail = leavesFor(vector, vector.size - 2, edit)
		const root =
		popTail(edit, vector.root, vector.shift, vector.size - 2) \|\|
		createBranch(edit)

		if (vector.shift > BITS && root.children[1] == null) {
		const newRoot = /** @type {API.Branch<T>} */ (root.children[0])
		return {
		...vector,
		size: vector.size - 1,
		tail,
		shift: vector.shift - BITS,
		// if this is mutable API we need to make sure that correct edit
		// field is set, however if it is immutable API (in which case
		// edit is null) we do not want to create unecessary root copy.
		root: edit ? forkBranch(newRoot, edit) : newRoot,
		}
		} else {
		return { ...vector, root, tail, size: vector.size - 1 }
		}
		}
		}
		}
		}

		/**
		* @template T
		* @param {API.Edit\|null} edit
		* @param {API.Branch<T>} trie
		* @param {number} level
		* @param {number} index
		* @returns {API.Branch<T>\|null}
		*/
		const popTail = (edit, trie, level, index) => {
		const offset = (index >>> level) & MASK

		if (level > BITS) {
		const child =
		/** @type {API.Branch<T>} - We know it's level isn't 0 so it'a a branch */
		(trie.children[offset])
		const newChild = popTail(edit, child, level - BITS, index)
		if (newChild == null && offset === 0) {
		return null
		} else {
		const node = forkBranch(trie, edit)
		newChild == null
		? delete node.children[offset]
		: (node.children[offset] = newChild)
		return node
		}
		} else if (offset === 0) {
		return null
		} else {
		const node = forkBranch(trie, edit)
		delete node.children[offset]
		return node
		}
		}

		/**
		* Returns leaves array in which element with given index `n` resides.
		*
		* @see https://hypirion.com/musings/understanding-persistent-vector-pt-2
		*
		* @template T
		* @param {API.PersistentVector<T>} self
		* @param {number} n
		* @param {API.Edit\|null} [edit=null]
		* @returns {T[]}
		*/
		export const leavesFor = (self, n, edit = null) => {
		// If n falls in a tail of the vector we simply return the referce of the
		// tail.
		if (n >= tailOffset(self.size)) {
		return self.tail
		}
		// Otherwise we traverse the trie branches
		else {
		// Node containing several levels branch nodes as children and the leaf
		// nodes at the bottom.
		/** @type {API.VectorNode<T>} */
		let node = self.root
		// BITS times (the depth of this trie minus one).
		let level = self.shift
		// Perform branching on internal nodes. Please note that all the nodes up
		// until ground level will be "branch"es (that have children) and only at
		// the ground level we will have "leaf" nodes. However this invariant can
		// no be captured in the types which is why our nodes have `children` it's
		// just for leaves they're empty and all our nodes have `leaves` that are
		// empty on branches. That way type checker is happy but also of limited use.
		while (level > 0) {
		node = node.children[(n >>> level) & MASK]
		level -= BITS
		}

		// Note we know ground level contains leaf nodes so we return the leaves
		// back.
		// If optional `edit` is passed and it is different from the owner we make
		// a copy so that caller can mutate it.
		return edit === null \|\| node.edit === edit
		? node.leaves
		: node.leaves.slice()
		}
		}

		/**
		* PersistentVector keeps the rightmost leaf in the tree a.k.a tail as an
		* important performance optimization. This function derives tail offset (that
		* is index of the first element that would fall into tail) from the vector
		* size.
		*
		* It is useful in lookup / update operations as to identify if element as it
		* tells if element at given index will be in the tree or a tail.
		*
		* @see https://hypirion.com/musings/understanding-persistent-vector-pt-3
		*
		* @param {number} size
		*/
		export const tailOffset = size =>
		size < WIDTH ? 0 : ((size - 1) >>> BITS) << BITS

+25

src/equality.js

		import * as API from "./api.js"
		import { iterator } from "./iteration.js"

		/**
		* @template T
		* @param {API.PersistentVector<T>} self
		* @param {API.PersistentVector<T>} other
		* @returns {other is self}
		*/
		export const equals = (self, other) => {
		if (self.size === other.size) {
		const left = iterator(self)
		const right = iterator(other)
		while (true) {
		const { value, done } = left.next()
		if (done) {
		return true
		} else if (value !== right.next().value) {
		return false
		}
		}
		} else {
		return false
		}
		}

+81

src/iteration.js

		import * as API from "./api.js"
		import { range } from "./util.js"
		import { leavesFor, WIDTH, MASK } from "./core.js"

		/**
		* @template T
		* @param {API.PersistentVector<T>} self
		* @param {{start?:number, end?:number}} [options]
		* @returns {IterableIterator<T>}
		*/
		export const iterator = (self, { start = 0, end = self.size } = {}) =>
		new RangedIteratorView({
		offset: start,
		base: start - (start % WIDTH),
		leaf: start < self.size ? leavesFor(self, start) : [],
		start,
		end,
		source: self,
		})

		/**
		* @template T
		* @implements {API.RangedIteratorView<T>}
		*/
		class RangedIteratorView {
		/**
		* @param {API.RangedIterator<T>} input
		*/
		constructor({ offset, base, leaf, start, end, source }) {
		this.offset = offset
		this.base = base
		this.leaf = leaf
		this.start = start
		this.end = end
		this.source = source
		}
		[Symbol.iterator]() {
		return this
		}
		/**
		* @returns {{done:true, value:void}\|{done:false, value:T}}
		*/
		next() {
		if (this.offset >= this.end) {
		return { done: true, value: undefined }
		} else {
		if (this.offset - this.base === WIDTH) {
		this.leaf = leavesFor(this.source, this.offset)
		this.base += WIDTH
		}

		const value = this.leaf[this.offset & MASK]
		this.offset++

		return { done: false, value }
		}
		}
		}

		/**
		* @template T
		* @param {API.PersistentVector<T>} self
		* @param {{start?:number, end?:number}} [options]
		* @returns {IterableIterator<[number, T]>}
		*/
		export const entries = function* (self, { start = 0, end = self.size } = {}) {
		let n = start
		for (const value of values(self, { start, end })) {
		yield [n, value]
		n++
		}
		}

		export const values = iterator

		/**
		* @template T
		* @param {API.PersistentVector<T>} self
		* @returns {IterableIterator<number>}
		*/
		export const keys = self => range(0, self.size)

+6

src/lib.js

		export * from "./api.js"
		export * from "./persistent.js"
		export * from "./equality.js"
		export * from "./iteration.js"
		export * from "./lookup.js"
		export * as mutable from "./mutable.js"

+29

src/lookup.js

		import * as API from "./api.js"
		import { leavesFor, MASK } from "./core.js"

		/**
		* @template T
		* @template [U=undefined]

		* @param {API.PersistentVector<T>} self
		* @param {number} n
		* @param {U} [notFound=undefined]
		* @returns {T\|U}
		*/
		export const nth = (self, n, notFound = undefined) =>
		n >= 0 && n < self.size
		? leavesFor(self, n)[n & MASK]
		: /** @type {U} */ (notFound)

		export const get = nth

		/**
		* @template T, M
		* @template [U=undefined]

		* @param {API.PersistentVector<T>} self
		* @param {U} [notFound=undefined]
		* @returns {T\|U}
		*/
		export const peek = (self, notFound = undefined) =>
		nth(self, self.size - 1, notFound)

+172

src/mutable.js

		import * as API from "./api.js"
		import * as Node from "./trie.js"
		import { WIDTH, conj as doconj, pop as dopop, set as doset } from "./core.js"
		import { values, entries, keys } from "./iteration.js"
		import { nth, peek } from "./lookup.js"
		import { ReadonlyIndexedView } from "./sugar.js"

		/**
		* @template T
		* @template {API.MutableVector<T>} Self
		* @param {Self} self
		* @param {T} value
		*/
		export const conj = (self, value) => {
		if (self.root.edit) {
		return patch(self, doconj(self.root.edit, self, value))
		} else {
		throw new RangeError("mutable.push called after seal()")
		}
		}
		export const push = conj

		/**
		* @template T
		* @template {API.MutableVector<T>} Self
		* @param {Self} self
		*/
		export const pop = self => {
		if (self.root.edit) {
		return patch(self, dopop(self.root.edit, self))
		} else {
		throw new RangeError("mutable.pop called after seal()")
		}
		}

		/**
		* @template T
		* @template {API.MutableVector<T>} Self
		* @param {Self} self
		* @param {number} index
		* @param {T} value
		*/
		export const set = (self, index, value) => {
		if (self.root.edit) {
		return patch(self, doset(self.root.edit, self, index, value))
		} else {
		throw new RangeError("mutable.set called after seal()")
		}
		}

		/**
		* @template T
		* @param {API.PersistentVector<T>} vector
		* @returns {API.MutableVectorView<T>}
		*/
		export const from = ({ size: size, shift, root, tail }) =>
		new MutableVectorView({
		size,
		shift,
		root: Node.forkBranch(root, {}),
		tail: editableTail(tail),
		})

		/**
		* @template T
		* @param {ReadonlyArray<T>} tail
		* @returns {T[]}
		*/
		const editableTail = tail => {
		const newTail = tail.slice()
		newTail.length = WIDTH
		return newTail
		}

		/**
		* @template T
		* @template {API.MutableVector<T>} Self
		* @param {Self} self
		* @param {API.PersistentVector<T>} delta
		*/
		const patch = (self, { size, shift, root, tail }) => {
		self.size = size
		self.shift = shift
		self.root = root
		self.tail = tail
		return self
		}

		/**
		* @template T
		* @implements {API.MutableVectorView<T>}
		* @extends {ReadonlyIndexedView<T>}
		*/
		class MutableVectorView extends ReadonlyIndexedView {
		/**
		* @param {API.MutableVector<T>} input
		*/
		constructor({ size, shift, root, tail }) {
		super()
		this.size = size
		this.shift = shift
		this.root = root
		this.tail = tail
		}

		// Stack API

		/**
		* @param {T} value
		*/

		push(value) {
		return push(this, value)
		}

		/**
		* @template [U=undefined]
		* @param {U} [fallback]
		*/
		peek(fallback) {
		return peek(this, fallback)
		}
		pop() {
		return pop(this)
		}

		// ArrayLike API

		/**
		* @template [U=undefined]
		* @param {number} index
		* @param {U} [fallback]
		*/
		get(index, fallback) {
		return nth(this, index, fallback)
		}

		/**
		* @param {number} n
		* @param {T} value
		*/
		set(n, value) {
		return set(this, n, value)
		}

		// Iteraction API

		get [Symbol.iterator]() {
		return this.values
		}

		/**
		* @param {{start?:number, end?:number}} [options]
		*/
		values(options) {
		return values(this, options)
		}

		/**
		* @param {{start?:number, end?:number}} [options]
		*/
		entries(options) {
		return entries(this, options)
		}

		/**
		* @returns {IterableIterator<number>}
		*/
		keys() {
		return keys(this)
		}
		}

+254

src/persistent.js

		import * as API from "./api.js"
		import * as Node from "./trie.js"
		import { ReadonlyIndexedView } from "./sugar.js"
		import {
		tailOffset,
		BITS,
		conj as doconj,
		pop as dopop,
		set as doset,
		} from "./core.js"
		import * as mutable from "./mutable.js"
		import { nth, peek } from "./lookup.js"
		import { values, entries, keys } from "./iteration.js"
		import { equals } from "./equality.js"

		/**
		* @template T
		* @returns {API.PersistentVectorView<T>}
		*/
		export const empty = () => EMPTY

		/**
		* @template T
		* @param {API.PersistentVector<T>} _self
		* @returns {API.PersistentVectorView<T>}
		*/
		export const clear = _self => EMPTY

		/**
		* @template T
		* @param {API.PersistentVector<T>} self
		* @returns {API.PersistentVectorView<T>}
		*/
		export const clone = self => new PersistentVectorView(self)

		/**
		* @template T
		* @param {API.PersistentVector<T>} self
		*/
		export const count = self => self.size

		/**
		* @template T

		* @param {API.PersistentVector<T>} self
		* @returns {API.PersistentVectorView<T>}
		*/
		export const pop = self => new PersistentVectorView(dopop(null, self))

		/**
		* @template T
		* @param {API.PersistentVector<T>} self
		* @param {T} value
		* @returns {API.PersistentVectorView<T>}
		*/
		export const conj = (self, value) =>
		new PersistentVectorView(doconj(null, self, value))
		export const push = conj

		/**
		* @template T
		* @param {API.PersistentVector<T>} self
		* @param {number} offset
		* @param {T} value
		*/
		export const set = (self, offset, value) =>
		new PersistentVectorView(doset(null, self, offset, value))

		/**
		* @template T
		* @param {Iterable<T>} input
		* @returns {API.PersistentVectorView<T>}
		*/
		export const from = input => {
		const array = Array.isArray(input) ? input : [...input]
		const { length } = array
		if (length < 32) {
		return new PersistentVectorView({
		size: length,
		shift: BITS,
		root: Node.emptyBranch(),
		tail: array.slice(),
		})
		} else {
		let vec = new PersistentVectorView({
		size: 32,
		shift: BITS,
		root: Node.emptyBranch(),
		tail: array.slice(0, 32),
		})
		let node = mutable.from(vec)

		let i = 32

		while (i < length) {
		node = mutable.conj(node, array[i])
		i += 1
		}

		return seal(node)
		}
		}

		/**
		* @template T
		* @param {T[]} items
		*/
		export const of = (...items) => from(items)

		/**
		* @template T, M
		* @param {API.MutableVector<T>} self
		* @returns {API.PersistentVectorView<T>}
		*/
		export const seal = self => {
		if (self.root.edit) {
		self.root.edit = null
		const length = self.size - tailOffset(self.size)
		const tail = new Array(length)
		let n = 0
		while (n < length) {
		tail[n] = self.tail[n]
		n++
		}

		return new PersistentVectorView({
		...self,
		tail,
		})
		} else {
		throw new RangeError("Seal called twice")
		}
		}

		/**
		* @template T
		* @implements {Iterable<T>}
		* @implements {API.PersistentVectorView<T>}
		* @extends {ReadonlyIndexedView<T>}
		*/
		class PersistentVectorView extends ReadonlyIndexedView {
		/**
		* @param {API.PersistentVector<T>} vector
		*/
		constructor({ size, shift, root, tail }) {
		super()
		/** @readonly */
		this.size = size
		/** @readonly */
		this.shift = shift
		/** @readonly */
		this.root = root
		/** @readonly */
		this.tail = tail
		}

		/**
		* @returns {API.PersistentVectorView<T>}
		*/
		clone() {
		return clone(this)
		}

		// Stack API

		/**
		* @param {T} value
		* @returns {API.PersistentVectorView<T>}
		*/
		push(value) {
		return conj(this, value)
		}
		/**
		* @template [U=undefined]
		* @param {U} [fallback]
		*/
		peek(fallback) {
		return peek(this, fallback)
		}

		pop() {
		return pop(this)
		}

		// Lookup API

		/**
		* @template [U=undefined]
		* @param {number} index
		* @param {U} [fallback]
		*/
		get(index, fallback) {
		return nth(this, index, fallback)
		}

		// Associative API

		/**
		* @param {number} index
		* @param {T} value
		* @returns {API.PersistentVectorView<T>}
		*/
		set(index, value) {
		return set(this, index, value)
		}

		/**
		* @returns {API.PersistentVectorView<T>}
		*/
		clear() {
		return EMPTY
		}

		get [Symbol.iterator]() {
		return this.values
		}

		/**
		* @param {{start?:number, end?:number}} [options]
		*/
		values(options) {
		return values(this, options)
		}

		/**
		* @param {{start?:number, end?:number}} [options]
		*/
		entries(options) {
		return entries(this, options)
		}

		/**
		* @returns {IterableIterator<number>}
		*/
		keys() {
		return keys(this)
		}

		/**
		* @param {API.PersistentVector<T>} other
		* @returns {other is API.PersistentVectorView<T>}
		*/
		equals(other) {
		return equals(this, other)
		}
		}

		/** @type {API.PersistentVectorView<any>} */
		const EMPTY = new PersistentVectorView({
		size: 0,
		shift: 5,
		root: Node.emptyBranch(),
		tail: [],
		})

+27

src/sugar.js

		import * as API from "./api.js"

		function ReadonlyIndexedView() {}
		Object.defineProperties(ReadonlyIndexedView, {
		prototype: {
		value: new Proxy(Object.prototype, {
		/**
		* @template T
		* @param {object} _target
		* @param {PropertyKey} property
		* @param {API.IndexedView<T>} receiver
		*/
		get(_target, property, receiver) {
		const n = parseKey(property)
		return n != null ? receiver.get(n) : undefined
		},
		}),
		},
		})

		/**
		* @param {PropertyKey} key
		* @returns {number\|null}
		*/
		const parseKey = key => (typeof key === "string" ? parseInt(key) : null)

		export { ReadonlyIndexedView }

+5

src/sugar.ts

		export declare class ReadonlyIndexedView<T> {
		readonly [n: number]: T

		get(n: number): T \| undefined
		}

+154

src/trie.js

		import * as API from "./api.js"
		export const BITS = 5

		export const WIDTH = /** @type {32} */ (1 << BITS) // 2^5 = 32
		export const MASK = /** @type {32} */ (WIDTH - 1) // 31 or 0x1f

		/**
		* @template T
		* @returns {API.Branch<T>}
		*/
		export const emptyBranch = () => EMPTY_BRANCH_NODE

		/**
		* @template T
		* @param {API.Edit\|null} edit
		* @param {API.VectorNode<T>[]} children
		* @returns {API.Branch<T>}
		*/
		export const createBranch = (edit, children = new Array(WIDTH)) => {
		children.length = WIDTH
		return new BranchNodeView({ edit, children })
		}

		/**
		* @template T
		* @param {API.Edit\|null} edit
		* @param {T[]} leaves
		* @returns {API.Leaf<T>}
		*/
		export const createLeaf = (edit, leaves = new Array(WIDTH)) => {
		leaves.length = WIDTH
		return new LeafNodeView({ edit, leaves })
		}

		/**
		* @template T
		* @param {API.Branch<T>} node
		* @param {API.Edit\|null} edit
		* @returns {API.Branch<T>}
		*/
		export const cloneBranch = (node, edit = node.edit) =>
		createBranch(edit, node.children.slice())

		/**
		* @template T
		* @param {API.Leaf<T>} node
		* @param {API.Edit\|null} edit
		* @returns {API.Leaf<T>}
		*/
		export const cloneLeaf = (node, edit = node.edit) =>
		createLeaf(edit, node.leaves.slice())

		/**
		* Creates path to a given `embed` node of the `shift / BITS` deep.
		*
		* @template T
		* @param {API.Edit\|null} edit
		* @param {number} shift
		* @param {API.VectorNode<T>} embed
		*/

		export const newPath = (edit, shift, embed) => {
		let level = shift
		let node = embed

		while (level !== 0) {
		const embed = node
		node = createBranch(edit, [embed])

		level -= BITS
		}

		return node
		}

		/**
		* @template T
		* @implements {API.Branch<T>}
		*/
		class BranchNodeView {
		/**
		* @param {object} input
		* @param {API.Edit\|null} input.edit
		* @param {API.VectorNode<T>[]} input.children
		*/
		constructor({ edit, children }) {
		this.edit = edit
		this.children = children
		}
		/**
		* @type {never}
		*/
		/* c8 ignore next 3 */
		get leaves() {
		throw new Error("Branch nodes contain no leaves")
		}
		}

		/**
		* @template T
		* @implements {API.Leaf<T>}
		*/
		class LeafNodeView {
		/**
		* @param {object} input
		* @param {API.Edit\|null} input.edit
		* @param {T[]} input.leaves
		*/
		constructor({ edit, leaves }) {
		this.edit = edit
		this.leaves = leaves
		}
		/**
		* @type {never}
		*/
		/* c8 ignore next 3 */
		get children() {
		throw new Error("Leaf nodes contain no children")
		}
		}

		const EMPTY_BRANCH_NODE = createBranch(null)

		/**
		* @template T
		* @param {API.Edit\|null} edit
		* @param {API.Branch<T>} node
		*/

		export const forkBranch = (node, edit) =>
		edit === null
		? cloneBranch(node)
		: edit === node.edit
		? node
		: createBranch(edit, node.children.slice())

		/**
		* @template T
		* @param {API.Edit\|null} edit
		* @param {API.Leaf<T>} node
		*/
		export const forkLeaf = (node, edit) =>
		edit === null
		? cloneLeaf(node)
		: edit === node.edit
		? node
		: createLeaf(edit, node.leaves.slice())

		/**
		* @template T
		* @param {API.Edit\|null} edit
		* @param {T[]} tail
		*/
		export const forkTail = (tail, edit) => (edit === null ? tail.slice() : tail)

+14

src/util.js

		/**
		* Returns iterable of numbers in the range of `from .. to`
		* inclusive of `from` and exclusive of of `to`.
		*
		* @param {number} from
		* @param {number} to
		*/
		export const range = function* (from, to) {
		let n = from
		while (n < to) {
		yield n
		n += 1
		}
		}

+496

test/all.spec.js

		import { describe, assert, it } from "./test.js"
		import * as Vec from "../src/lib.js"
		import { range } from "../src/util.js"

		describe("persistent API", () => {
		describe("basics", () => {
		it("nth", () => {
		assert.equal(Vec.nth(Vec.from(["a", "b", "c", "d"]), 0), "a")
		assert.equal(Vec.nth(Vec.from(["a", "b", "c", "d"]), 0.1), "a")
		})

		it("set in the root", () => {
		const v1 = Vec.from(range(0, 90))
		const v2 = Vec.set(v1, 0, -1)

		assert.equal(Vec.get(v1, 0), 0)
		assert.equal(Vec.get(v2, 0), -1)
		assert.equal(Vec.get(v1, 1), 1)
		assert.equal(Vec.get(v2, 1), 1)
		})

		it("basic ops", () => {
		const pv = Vec.from(range(0, 97))
		assert.equal(Vec.nth(pv, 96), 96)

		assert.equal(Vec.nth(pv, 97), undefined)
		assert.equal(Vec.nth(pv, 97, { nothing: true }), { nothing: true })
		})

		it("push", () => {
		assert.equal(Vec.push(Vec.empty(), 1), Vec.from([1]))
		assert.equal(Vec.empty().push(1).push(2), Vec.from([1, 2]))
		assert.equal(Vec.from([2, 3]).push(1), Vec.from([2, 3, 1]))
		})
		it("pop", () => {
		const pv = Vec.from(range(0, 33))
		const pv2 = pv.pop().pop().push(31).push(32)

		assert.ok(Vec.equals(pv, pv2))
		assert.equal([...pv], [...pv2])
		})

		it("stack", () => {
		const v0 = Vec.from(range(0, 97))
		const v1 = Vec.pop(v0)
		const v2 = Vec.pop(v1)

		assert.equal(Vec.peek(v1), 95)
		assert.equal(Vec.peek(v2), 94)

		assert.equal(v1.peek(), 95)
		assert.equal(v2.peek(), 94)
		})

		it("indexed access", () => {
		const pv = Vec.from(range(0, 97))

		for (const n of range(0, 97)) {
		assert.equal(pv[n], n, `pv[${n}] == ${pv[n]} != ${n}`)
		}
		assert.equal(pv[98], undefined)

		// @ts-expect-error - no such property
		assert.equal(pv["third"], undefined)
		})

		// Ported from https://github.com/immutable-js/immutable-js/blob/main/__tests__/List.ts
		it("of provides initial values", () => {
		const v = Vec.of("a", "b", "c")
		assert.equal(v.get(0), "a")
		assert.equal(v.get(1), "b")
		assert.equal(v.get(2), "c")
		})

		it("can be spread into array", () => {
		const v = Vec.of("a", "b", "c")
		assert.equal([...v], ["a", "b", "c"])
		})

		it("does not accept a scalar", () => {
		assert.throws(() => {
		// @ts-expect-error - must be iterable
		Vec.from(3)
		})
		})
		it("accepts an array", () => {
		const v = Vec.from(["a", "b", "c"])
		assert.equal(v.get(1), "b")
		assert.equal([...v], ["a", "b", "c"])
		})

		it("accepts iterables, including strings", () => {
		const v = Vec.from("abc")
		assert.equal(v.get(1), "b")
		assert.equal([...v], ["a", "b", "c"])
		})

		it("can set and get a value", () => {
		const v = Vec.empty()
		assert.equal(v.get(0), undefined)
		const v2 = v.set(0, "value")
		assert.equal(v2.get(0), "value")
		assert.equal(v.get(0), undefined)
		})

		it("setting creates a new instance", () => {
		const v0 = Vec.of("a")
		const v1 = v0.set(0, "A")
		assert.equal(v0.get(0), "a")
		assert.equal(v1.get(0), "A")
		})

		it("size includes the highest index", () => {
		const v0 = Vec.empty()
		const v1 = v0.set(0, "a")
		const v2 = v1.set(1, "b")
		const v3 = v2.set(2, "c")

		assert.equal(v0.size, 0)
		assert.equal(v1.size, 1)
		assert.equal(v2.size, 2)
		assert.equal(v3.size, 3)
		})

		it("can contain a large number of indices", () => {
		const r = Vec.from(range(0, 20000))
		let iterations = 0
		for (const v of r) {
		assert.equal(v, iterations)
		iterations++
		}
		})

		it("describes throws on out of range sets", () => {
		assert.throws(() => {
		const v = Vec.of("a", "b", "c").push("d").set(14, "o")
		}, "Index 14 is out of bounds [0, 4]")
		})

		it("can be cleared with Vec.clear", () => {
		const vec = Vec.of("a", "b", "c")
		assert.equal(Vec.clear(vec), Vec.empty())
		assert.equal(vec.clear(), Vec.empty())
		assert.equal([...vec], ["a", "b", "c"])
		})
		})

		describe("pop", () => {
		it("throws on empty", () => {
		assert.throws(() => Vec.pop(Vec.empty()), "can not pop from empty")
		})

		it("pop from vec with only item", () => {
		const v1 = Vec.of(1)
		const v2 = Vec.pop(v1)

		assert.equal(Vec.count(v2), 0)
		assert.ok(v2.equals(Vec.empty()))
		})

		it("pop with fork tail", () => {
		const v1 = Vec.from(range(0, 17))
		const v2 = Vec.pop(v1)

		assert.equal(v2.size, 16)
		assert.equal([...v2], [...range(0, 16)])
		assert.equal(v1.size, 17)
		assert.equal([...v1], [...range(0, 17)])
		})

		it("pop with fork branch", () => {
		const v1 = Vec.from(range(0, 1025))
		const v2 = Vec.pop(v1)

		assert.equal(v2.size, 1024)
		assert.equal([...v2], [...range(0, 1024)])

		assert.equal(v1.size, 1025)
		assert.equal([...v1], [...range(0, 1025)])
		})

		it("fuzz pop", function () {
		this.timeout(20000)
		const array = [...range(0, 60000)]
		let vec = Vec.from(array)
		while (array.length > 0) {
		array.pop()
		vec = vec.pop()
		assert.equal(vec.size, array.length)
		assert.equal(vec[array.length], undefined)
		assert.equal(vec[array.length - 1], array[array.length - 1])

		const index = (Math.random() * array.length - 1) \| 0
		assert.equal(vec[index], array[index])
		}
		})
		})

		describe("push", () => {
		it("fuzz", function () {
		this.timeout(20000)
		const max = 50000
		const array = []
		let vec = Vec.empty()
		while (array.length < max) {
		const value = Math.random()
		array.push(value)
		const v = vec.push(value)
		assert.equal(vec.size, array.length - 1)
		assert.equal(vec[array.length - 1], undefined)

		vec = v

		assert.equal(vec.size, array.length)
		assert.equal(vec[array.length], undefined)
		assert.equal(vec[array.length - 1], array[array.length - 1])

		const index = (Math.random() * array.length - 1) \| 0
		assert.equal(vec[index], array[index])
		}
		})
		})

		describe("set", () => {
		it("fuzz", function () {
		this.timeout(20000)
		let n = 50000
		const array = [...range(0, n)]
		let vec = Vec.from(array)
		while (n > 0) {
		const value = Math.random()
		const index = (Math.random() * n) \| 0

		assert.equal(vec.get(index), array[index])
		array[index] = value
		vec = vec.set(index, value)

		if (vec[index] !== array[index]) {
		console.log(index, vec, vec[index], array[index], value)
		vec.set(index, value)
		}
		assert.equal(vec[index], array[index])
		n--
		}
		})
		})
		describe("iteration", () => {
		const vec = Vec.of("a", "b", "c", "d")
		it("has keys method", () => {
		const keys = vec.keys()
		assert.equal(keys.next(), { value: 0, done: false })
		assert.equal([...keys], [1, 2, 3])
		})

		it("has values method", () => {
		const vals = vec.values()
		assert.equal(vals.next(), { value: "a", done: false })

		assert.equal([...vals], ["b", "c", "d"])

		assert.equal([...vec.values({ start: 2 })], ["c", "d"])
		})

		it("has entries method", () => {
		const entries = vec.entries()
		assert.equal(entries.next(), { value: [0, "a"], done: false })

		assert.equal(
		[...entries],
		[
		[1, "b"],
		[2, "c"],
		[3, "d"],
		]
		)

		assert.equal(
		[...vec.entries({ start: 1, end: 3 })],
		[
		[1, "b"],
		[2, "c"],
		]
		)

		assert.equal([...vec.entries({ start: 10 })], [])
		})
		})

		describe("indexed access", () => {
		it("supports indexed access", () => {
		const vec = Vec.of("a", "b", "c", "d")
		assert.equal(vec[0], "a")
		assert.equal(vec[1], "b")
		assert.equal(vec[2], "c")
		assert.equal(vec[3], "d")
		assert.equal(vec[-1], undefined)
		assert.equal(vec[4], undefined)
		})
		})

		describe("equality", () => {
		it("equal vecs", () => {
		const equal = [
		[Vec.of(1, 2, 3), Vec.of(1, 2, 3)],
		[Vec.empty(), Vec.of(1).pop()],
		[Vec.of(1), Vec.of(1)],
		[Vec.of(1, 2), Vec.conj(Vec.of(1), 2)],
		[Vec.empty(), Vec.of(1, 2, 3).clear()],
		[Vec.of(1, 2).clone(), Vec.of(1, 2)],
		]

		for (const [left, right] of equal) {
		assert.equal(Vec.equals(left, right), true)
		assert.equal(left.equals(right), true)
		assert.equal(right.equals(left), true)
		}
		})

		it("non equal", () => {
		const data = [
		[Vec.of(1, 2, 3), Vec.of(1, 3, 2)],
		[Vec.empty(), Vec.of(1)],
		[Vec.of(1), Vec.of("one")],
		]

		for (const [left, right] of data) {
		assert.equal(Vec.equals(left, right), false)
		assert.equal(left.equals(right), false)
		assert.equal(right.equals(left), false)
		}
		})
		})
		})

		describe("mutable API", () => {
		it("conj", () => {
		const pv1 = Vec.of(1, 2, 3)
		const tv1 = Vec.mutable.from(pv1)
		const tv2 = Vec.mutable.push(tv1, 4)
		const tv3 = Vec.mutable.push(tv2, 5)
		const tv4 = Vec.mutable.push(tv3, 6)
		const pv2 = Vec.seal(tv4)

		assert.equal([...pv1], [1, 2, 3])
		assert.equal([...pv2], [1, 2, 3, 4, 5, 6])
		assert.ok(tv1 === tv2)
		assert.ok(tv1 === tv3)
		assert.ok(tv1 === tv4)

		assert.throws(() => Vec.seal(tv4))
		assert.throws(() => tv1.push(4))
		assert.throws(() => Vec.mutable.push(tv2, 4))
		})

		it("pop", () => {
		const pv = Vec.from(range(0, 33))
		const tv1 = Vec.mutable.from(pv)
		const tv2 = tv1.pop()
		const tv3 = tv2.pop()

		assert.equal([...tv3], [...range(0, 31)])
		assert.ok(tv1 === tv2)
		assert.ok(tv1 === tv3)

		const pv2 = Vec.seal(tv3)
		assert.equal([...pv2], [...range(0, 31)])

		assert.throws(() => tv3.pop(), "throws after sealed")
		assert.throws(() => Vec.seal(tv1))
		assert.throws(() => Vec.mutable.pop(tv3))
		assert.throws(() => Vec.mutable.pop(pv2))
		})

		it("set", () => {
		const v1 = Vec.from(range(0, 5))
		const v2 = Vec.mutable.from(v1)

		const v3 = Vec.mutable.set(v2, 1, -1)
		const v4 = v3.set(2, -2)
		const v5 = Vec.seal(v4)

		assert.equal([...v5], [0, -1, -2, 3, 4])
		assert.equal([...v4], [0, -1, -2, 3, 4])
		assert.equal([...v1], [0, 1, 2, 3, 4])

		assert.throws(() => v2.set(3, 0), "throws after sealed")
		assert.throws(() => Vec.mutable.set(v4, 3, 0))
		assert.throws(() => Vec.seal(v3))

		assert.ok(v2 === v3)
		assert.ok(v2 === v4)
		})

		describe("iteration", () => {
		const vec = Vec.mutable.from(Vec.of("a", "b", "c", "d"))
		it("has keys method", () => {
		const keys = vec.keys()
		assert.equal(keys.next(), { value: 0, done: false })
		assert.equal([...keys], [1, 2, 3])
		})

		it("has values method", () => {
		const vals = vec.values()
		assert.equal(vals.next(), { value: "a", done: false })

		assert.equal([...vals], ["b", "c", "d"])

		assert.equal([...vec.values({ start: 2 })], ["c", "d"])
		})

		it("has entries method", () => {
		const entries = vec.entries()
		assert.equal(entries.next(), { value: [0, "a"], done: false })

		assert.equal(
		[...entries],
		[
		[1, "b"],
		[2, "c"],
		[3, "d"],
		]
		)

		assert.equal(
		[...vec.entries({ start: 1, end: 3 })],
		[
		[1, "b"],
		[2, "c"],
		]
		)

		assert.equal([...vec.entries({ start: 10 })], [])
		})
		})

		describe("fuzz", () => {
		it("set", function () {
		this.timeout(20000)
		let n = 50000
		const array = [...range(0, n)]
		let vec = Vec.mutable.from(Vec.from(array))
		while (n > 0) {
		const value = Math.random()
		const index = (Math.random() * n) \| 0

		assert.equal(vec.get(index), array[index])
		array[index] = value
		vec = vec.set(index, value)

		if (vec[index] !== array[index]) {
		console.log(index, vec, vec[index], array[index], value)
		vec.set(index, value)
		}
		assert.equal(vec[index], array[index])
		n--
		}
		})

		it("push", function () {
		this.timeout(20000)
		const max = 50000
		const array = []
		let vec = Vec.mutable.from(Vec.empty())
		while (array.length < max) {
		const value = Math.random()
		array.push(value)
		vec = vec.push(value)

		assert.equal(vec.size, array.length)
		assert.equal(vec[array.length], undefined)
		assert.equal(vec[array.length - 1], array[array.length - 1])

		assert.equal(vec.peek(), value)

		const index = (Math.random() * array.length - 1) \| 0
		assert.equal(vec[index], array[index])
		}
		})

		it("pop", function () {
		this.timeout(20000)
		const array = [...range(0, 60000)]
		let vec = Vec.mutable.from(Vec.from(array))
		while (array.length > 0) {
		array.pop()
		vec = vec.pop()
		assert.equal(vec.size, array.length)
		assert.equal(vec[array.length], undefined)
		assert.equal(vec[array.length - 1], array[array.length - 1])

		const index = (Math.random() * array.length - 1) \| 0
		assert.equal(vec[index], array[index])
		}
		})
		})
		})

+3

test/test.js

		import * as assert from "uvu/assert"
		const { it, describe } = globalThis
		export { it, describe, assert }

+102

tsconfig.json

		{
		"compilerOptions": {
		/* Visit https://aka.ms/tsconfig.json to read more about this file */

		/* Projects */
		"incremental": true, /* Enable incremental compilation */
		"composite": true, /* Enable constraints that allow a TypeScript project to be used with project references. */
		// "tsBuildInfoFile": "./", /* Specify the folder for .tsbuildinfo incremental compilation files. */
		// "disableSourceOfProjectReferenceRedirect": true, /* Disable preferring source files instead of declaration files when referencing composite projects */
		// "disableSolutionSearching": true, /* Opt a project out of multi-project reference checking when editing. */
		// "disableReferencedProjectLoad": true, /* Reduce the number of projects loaded automatically by TypeScript. */

		/* Language and Environment */
		"target": "ES2020", /* Set the JavaScript language version for emitted JavaScript and include compatible library declarations. */
		// "lib": [], /* Specify a set of bundled library declaration files that describe the target runtime environment. */
		// "jsx": "preserve", /* Specify what JSX code is generated. */
		// "experimentalDecorators": true, /* Enable experimental support for TC39 stage 2 draft decorators. */
		// "emitDecoratorMetadata": true, /* Emit design-type metadata for decorated declarations in source files. */
		// "jsxFactory": "", /* Specify the JSX factory function used when targeting React JSX emit, e.g. 'React.createElement' or 'h' */
		// "jsxFragmentFactory": "", /* Specify the JSX Fragment reference used for fragments when targeting React JSX emit e.g. 'React.Fragment' or 'Fragment'. */
		// "jsxImportSource": "", /* Specify module specifier used to import the JSX factory functions when using `jsx: react-jsx`.` /
		// "reactNamespace": "", /* Specify the object invoked for `createElement`. This only applies when targeting `react` JSX emit. */
		// "noLib": true, /* Disable including any library files, including the default lib.d.ts. */
		// "useDefineForClassFields": true, /* Emit ECMAScript-standard-compliant class fields. */

		/* Modules */
		"module": "ES2020", /* Specify what module code is generated. */
		// "rootDir": "./", /* Specify the root folder within your source files. */
		"moduleResolution": "node", /* Specify how TypeScript looks up a file from a given module specifier. */
		// "baseUrl": "./", /* Specify the base directory to resolve non-relative module names. */
		// "paths": {}, /* Specify a set of entries that re-map imports to additional lookup locations. */
		// "rootDirs": [], /* Allow multiple folders to be treated as one when resolving modules. */
		// "typeRoots": [], /* Specify multiple folders that act like `./node_modules/@types`. */
		// "types": [], /* Specify type package names to be included without being referenced in a source file. */
		// "allowUmdGlobalAccess": true, /* Allow accessing UMD globals from modules. */
		// "resolveJsonModule": true, /* Enable importing .json files */
		// "noResolve": true, /* Disallow `import`s, `require`s or `<reference>`s from expanding the number of files TypeScript should add to a project. */

		/* JavaScript Support */
		"allowJs": true, /* Allow JavaScript files to be a part of your program. Use the `checkJS` option to get errors from these files. */
		"checkJs": true, /* Enable error reporting in type-checked JavaScript files. */
		// "maxNodeModuleJsDepth": 1, /* Specify the maximum folder depth used for checking JavaScript files from `node_modules`. Only applicable with `allowJs`. */

		/* Emit */
		"declaration": true, /* Generate .d.ts files from TypeScript and JavaScript files in your project. */
		"declarationMap": true, /* Create sourcemaps for d.ts files. */
		"emitDeclarationOnly": true, /* Only output d.ts files and not JavaScript files. */
		// "sourceMap": true, /* Create source map files for emitted JavaScript files. */
		// "outFile": "./", /* Specify a file that bundles all outputs into one JavaScript file. If `declaration` is true, also designates a file that bundles all .d.ts output. */
		"outDir": "./dist", /* Specify an output folder for all emitted files. */
		// "removeComments": true, /* Disable emitting comments. */
		// "noEmit": true, /* Disable emitting files from a compilation. */
		// "importHelpers": true, /* Allow importing helper functions from tslib once per project, instead of including them per-file. */
		// "importsNotUsedAsValues": "remove", /* Specify emit/checking behavior for imports that are only used for types */
		// "downlevelIteration": true, /* Emit more compliant, but verbose and less performant JavaScript for iteration. */
		// "sourceRoot": "", /* Specify the root path for debuggers to find the reference source code. */
		// "mapRoot": "", /* Specify the location where debugger should locate map files instead of generated locations. */
		// "inlineSourceMap": true, /* Include sourcemap files inside the emitted JavaScript. */
		// "inlineSources": true, /* Include source code in the sourcemaps inside the emitted JavaScript. */
		// "emitBOM": true, /* Emit a UTF-8 Byte Order Mark (BOM) in the beginning of output files. */
		// "newLine": "crlf", /* Set the newline character for emitting files. */
		// "stripInternal": true, /* Disable emitting declarations that have `@internal` in their JSDoc comments. */
		// "noEmitHelpers": true, /* Disable generating custom helper functions like `__extends` in compiled output. */
		"noEmitOnError": true, /* Disable emitting files if any type checking errors are reported. */
		// "preserveConstEnums": true, /* Disable erasing `const enum` declarations in generated code. */
		// "declarationDir": "./", /* Specify the output directory for generated declaration files. */
		// "preserveValueImports": true, /* Preserve unused imported values in the JavaScript output that would otherwise be removed. */

		/* Interop Constraints */
		// "isolatedModules": true, /* Ensure that each file can be safely transpiled without relying on other imports. */
		// "allowSyntheticDefaultImports": true, /* Allow 'import x from y' when a module doesn't have a default export. */
		"esModuleInterop": true, /* Emit additional JavaScript to ease support for importing CommonJS modules. This enables `allowSyntheticDefaultImports` for type compatibility. */
		// "preserveSymlinks": true, /* Disable resolving symlinks to their realpath. This correlates to the same flag in node. */
		"forceConsistentCasingInFileNames": true, /* Ensure that casing is correct in imports. */

		/* Type Checking */
		"strict": true, /* Enable all strict type-checking options. */
		// "noImplicitAny": true, /* Enable error reporting for expressions and declarations with an implied `any` type.. */
		// "strictNullChecks": true, /* When type checking, take into account `null` and `undefined`. */
		// "strictFunctionTypes": true, /* When assigning functions, check to ensure parameters and the return values are subtype-compatible. */
		// "strictBindCallApply": true, /* Check that the arguments for `bind`, `call`, and `apply` methods match the original function. */
		// "strictPropertyInitialization": true, /* Check for class properties that are declared but not set in the constructor. */
		// "noImplicitThis": true, /* Enable error reporting when `this` is given the type `any`. */
		// "useUnknownInCatchVariables": true, /* Type catch clause variables as 'unknown' instead of 'any'. */
		// "alwaysStrict": true, /* Ensure 'use strict' is always emitted. */
		// "noUnusedLocals": true, /* Enable error reporting when a local variables aren't read. */
		// "noUnusedParameters": true, /* Raise an error when a function parameter isn't read */
		// "exactOptionalPropertyTypes": true, /* Interpret optional property types as written, rather than adding 'undefined'. */
		// "noImplicitReturns": true, /* Enable error reporting for codepaths that do not explicitly return in a function. */
		// "noFallthroughCasesInSwitch": true, /* Enable error reporting for fallthrough cases in switch statements. */
		// "noUncheckedIndexedAccess": true, /* Include 'undefined' in index signature results */
		// "noImplicitOverride": true, /* Ensure overriding members in derived classes are marked with an override modifier. */
		// "noPropertyAccessFromIndexSignature": true, /* Enforces using indexed accessors for keys declared using an indexed type */
		// "allowUnusedLabels": true, /* Disable error reporting for unused labels. */
		// "allowUnreachableCode": true, /* Disable error reporting for unreachable code. */

		/* Completeness */
		// "skipDefaultLibCheck": true, /* Skip type checking .d.ts files that are included with TypeScript. */
		"skipLibCheck": true /* Skip type checking all .d.ts files. */
		},
		"include": ["src", "test"]
		}

+65

yarn-error.log

		Arguments:
		/usr/local/bin/node /usr/local/Cellar/yarn/1.22.0/libexec/bin/yarn.js add --dev mocha

		PATH:
		/Users/gozala/.local/bin:/Users/gozala/.mozbuild/arcanist/bin:/Users/gozala/.mozbuild/moz-phab:/Users/gozala/.deno/bin:/Users/gozala/.cargo/bin:/Users/gozala/Projects/clojurescript/bin:/Users/gozala/.mozbuild/git-cinnabar:/Users/gozala/Projects/vectrie/node_modules/.bin:/Users/gozala/.lein/bin:/Users/gozala/.local/bin:/usr/local/bin:/usr/local/sbin:/Users/gozala/Projects/moz-git-tools:/Users/gozala/Projects/vectrie/node_modules/.bin:/Users/gozala/.lein/bin:/Users/gozala/.local/bin:/usr/local/bin:/usr/local/sbin:/Users/gozala/.nvm/versions/node/v8.9.4/bin:/usr/local/bin:/usr/bin:/bin:/usr/sbin:/sbin:/usr/local/MacGPG2/bin:/opt/X11/bin:/Library/Apple/usr/bin:/Users/gozala/.go/bin:/usr/local/bin/bin

		Yarn version:
		1.22.0

		Node version:
		16.13.0

		Platform:
		darwin x64

		Trace:
		SyntaxError: /Users/gozala/Projects/vectrie/package.json: Unexpected token } in JSON at position 650
		at JSON.parse (<anonymous>)
		at /usr/local/Cellar/yarn/1.22.0/libexec/lib/cli.js:1625:59
		at Generator.next (<anonymous>)
		at step (/usr/local/Cellar/yarn/1.22.0/libexec/lib/cli.js:310:30)
		at /usr/local/Cellar/yarn/1.22.0/libexec/lib/cli.js:321:13

		npm manifest:
		{
		"name": "vectrie",
		"version": "0.0.0",
		"description": "S implementation of persistent bit-partitioned vector trie a.k.a vector data structure in Clojure",
		"keywords": [
		"typescript",
		"growable array",
		"immutable",
		"array",
		"list",
		"persistent",
		"bit partitioned",
		"vector",
		"trie"
		],
		"author": "Irakli Gozalshvili <dev@gozala.io> (https://gozala.io/work)",
		"license": "(Apache-2.0 AND MIT)",
		"type": "module",
		"scripts": {
		"typecheck": "tsc --build",
		"test:es": "uvu test all.spec.js",
		"test:web": "playwright-test -r uvu test/web.spec.js",
		"test:es": "uvu test all.spec.js",
		},
		"devDependencies": {
		"typescript": "4.5.5"
		}
		}

		yarn manifest:
		No manifest

		Lockfile:
		# THIS IS AN AUTOGENERATED FILE. DO NOT EDIT THIS FILE DIRECTLY.
		# yarn lockfile v1


		typescript@4.5.5:
		version "4.5.5"
		resolved "https://registry.yarnpkg.com/typescript/-/typescript-4.5.5.tgz#d8c953832d28924a9e3d37c73d729c846c5896f3"
		integrity sha512-TCTIul70LyWe6IJWT8QSYeA54WQe8EjQFU4wY52Fasj5UKx88LNYKCgBEHcOMOrFF1rKGbD8v/xcNWVUq9SymA==

+33

-2

package.json

		{
		"name": "vectrie",
		"version": "0.0.0",
		"version": "1.0.0",
		"description": "JS implementation of persistent bit-partitioned vector trie a.k.a vector data structure in Clojure",
		"keywords": [
		@@ -14,3 +15,33 @@ "typescript",
		"trie"
		]
		],
		"author": "Irakli Gozalshvili <dev@gozala.io> (https://gozala.io/work)",
		"license": "(Apache-2.0 AND MIT)",
		"type": "module",
		"main": "./src/lib.js",
		"types": "./dist/src/lib.d.ts",
		"exports": {
		".": {
		"import": "./src/lib.js"
		}
		},
		"scripts": {
		"typecheck": "tsc --build",
		"test:web": "playwright-test test/all.spec.js",
		"test:node": "c8 --check-coverage --branches 100 --functions 100 --lines 100 mocha test/all.spec.js",
		"test": "npm run test:node && npm run test:web"
		},
		"c8": {
		"exclude": [
		"test/**",
		"src/sugar.js"
		]
		},
		"devDependencies": {
		"c8": "^7.11.0",
		"@types/mocha": "9.1.0",
		"mocha": "9.2.0",
		"playwright-test": "7.2.2",
		"typescript": "4.5.5",
		"uvu": "0.5.3"
		}
		}

+68

-2

Readme.md

		@@ -1,5 +0,71 @@
		# vetrie
		# vectrie

		JS implementation of persistent bit-partitioned vector trie a.k.a vector data structure in Clojure.

		## Status - Name claimed
		Library provides `PersistentVector` immutable and fully persistent data type with `O(log32 N)` `get` and `set` operations, and `O(1)` `push` and `pop` operations.

		In addition companion `MutableVector` mutabale dual is provided for performance critical code paths and batch operations that provides compatible API but with a smaller memory overhead.

		## Usage

		```ts
		import * as Vec from "vectrie"

		const pv1 = Vec.from([1, 2, 3, 4])
		Vec.get(pv1, 0) // => 1
		Vec.get(pv1, 4) // => undefined
		Vec.get(pv1, 4, "not-found") // => not-found

		const pv2 = Vec.push(pv1, 5)
		Vec.get(pv2, 4) // => 5
		```

		In performance critical code & batch operations you can use [transient][] vector:

		```ts
		let tv = Vec.mutable.from(pv1)
		for (const n of input) {
		tv = Vec.mutable.push(tv, n)
		}
		const pv3 = Vec.seal(tv)
		```

		If you want some sugar and more conventional JS API, there is `PersistentVectorView` to help you with that:

		```js
		const v1 = Vec.PersistentVectorView.from([1, 2, 3, 4])
		v1.get(0) // => 1
		v1[0] // => 1

		const v2 = v1.set(0, 5)
		v2[0] // => 5
		```

		## Comparison to alternatives

		### [ImmutableJS](https://immutable-js.com/)

		ImmutableJS is a good and a lot more mature library which comes with a lot more data structures out of the box. [List](https://immutable-js.com/docs/v4.0.0/List/) data structure is an equivalent of a `PersistentVector` and to my knowledge they are both ports of the Clojure's vector implementation. Here is how this library differs

		1. vectrie (deliberately) provides _only_ `PersistentVector` data type.
		2. vectrie is written in typescript _([JS with JSDoc types][ts-jsdoc] to be accurate)_ which affects API design:

		- `PersistentVector<T>` unlike `Immutable.List` is continues and not sparse. It would be fare to say that `PersistentVector<T>` is more like [Vector in rust][rust-vec] while `Immutable.List` is more like JS `Array`.
		- Setting out of bound value on `PersistentVector` a `RangeError` while in `Immutable.List` it creates sparse list.
		- `PersistentVector<T>` has no `splice`, `slice`, `unshift`, `reverse` because there is no effecient way to perfrom those operations on bit-partitioned vector tries while retaining desired performance profile _(which is why both clojure and immutable JS return different data structure when you do so)_.

		vectrie does not do that because in many cases modeling data with different types is a better alternative to abstracting it away.

		3. `PersistentVector` implementation decouples data from operations that can be performed on it. This makes moving them across realms / threads, serailzing / deserializing hassle free.

		Library also provides sugar via `PersistentVectorView` to provide more conventional API in JS. It also makes it possible for you to write your own `View` providing alternative API without inheritence or other counterproductive features.

		4. `PersistentVectorView` provides indexed access to underlying elements (e.g. `pv[0]` to get first element) which is of questionable benefit, but does seem more natural in JS. Note that updates do not work the same way.

		### [Immer](https://immerjs.github.io/immer/)

		Immer is popular library which provide immutablity from the comfort of the mutable interface. Vectrie library borrows from clojure [transient][]s and goes other way round, providing mutability (when needed) from the comfort of immutable interface.

		[ts-jsdoc]: https://www.typescriptlang.org/docs/handbook/jsdoc-supported-types.html
		[rust-vec]: https://doc.rust-lang.org/rust-by-example/std/vec.html
		[transient]: https://clojure.org/reference/transients

vectrie - npm Package Compare versions

New alerts

Fixed alerts

Improved metrics

Worsened metrics