README.md

Cow List 🐄🐄🐄

Cow List provides a Copy-On-Write iterable list that supports logarithmic searches. It provides also a mutable iterable List with versioning capabilities.

Cow List naively supports lengthy values (objects with a length property). This makes Cow List a perfect fit to implement a rope.

Highlights

Immutable or mutable

Cow List provides immutable lists and mutable lists. Immutable lists are well-suited for projects that embrace immutability and purity. They use a copy-on-write strategy to achieve better performances. Mutable lists have versioning capabilities that enable to fork a list into two independent mutable lists. They are well-suited for projects that implements their own copy-on-write data structures.

A building block

Cow List implements a close to minimum set of features. This makes Cow List lightweight (2 kB minified and gziped). These features are carefully chosen for enabling the design of advanced data structures. For instance, Cow List enables to implement sorted lists and ropes.

Lengthy values

Cow List is aware of lengthy values (objects with a length property). When you iterate over a list, you have access to the cumulated length (summary) of the traversed values. This enables to efficiently implement a rope.

Logarithmic searches

The main way to traverse a list is to get an iterator. Cow List enables to logarithmically chooses where to start the iteration.

Getting started

Install cow-list as a dependency:

npm install cow-list

Immutable list

import { CowList } from "cow-list"

let l = CowList.empty<string>()
l = l.inserted(0, "ab")
l = l.inserted(1, "c")
l = l.inserted(2, "d")
l = l.deleted(1)
l = l.replaced(1, "de")

for (const v of l) {
    console.log(v)
    // ab
    // de
}

Mutable list

import { MutList } from "cow-list"

let l = MutList.empty<string>()
l.insert(0, "ab")
l.insert(1, "c")
l.insert(2, "d")
l.delete(1)
l.replace(1, "de")

for (const v of l) {
    console.log(v)
    // ab
    // de
}

Advanced usages

Please take a look to the provided examples.

FAQ

Why did you design yet another list?

I wished to have a generic building block to implement Dotted LogootSplit. Dotted LogootSplit is a replicated data structure designed for collaborative editing. The data structure combines a search tree and a rope.

Internally used data structure

For now, Cow List uses a partially persistent AVL tree. This could change in the future in order to achieve better performances.