fractional_indexing

This library implements fractional indexing outlined in these two blog posts:

Fractional indexing is useful in maintaining an ordered sequence of keys where you want to insert keys at arbitary locations in the list. The original Figma post above outlined a system used in their product to achieve eventual consistency using a decimal index. For example, in a list with keys [0, 1] you could add a new item between them with index 0.5.

Indexing using floats runs into precision issues in Javascript and starts to yield very long keys. This library implements a system of variable length integer encoding followed by fractional indexing to keep keys short. Instead of sorting items by their numerical index, these keys sort lexicographically using the algorithm at the second link above.

Example

import fractional_indexing as fi

// start with a list of items
let items = [1, 3]

// create some keys for them, here we will use the bulk API
// to generate several keys at once and zip them up
let keys = fi.n_first(num_keys: items |> list.length)

let zipped = list.zip(keys, items)
// [#("a0", 1), #("a1", 3)]

// now you want to add an item between these two values, so
// generate a key to index between `a0` and `a1`. Note
// that key generation can fail in exotic situations, but under
// normal use should return a suitable key
let assert [key1, key2] = keys // a0, a1
let assert Ok(key_between) = fi.between(key1, key2)
let zipped = [#(key_between, 2), ..zipped]

// sort them to get them in the order you want using string comparison
// for the keys
echo zipped |> list.sort(by: fn(a, b) { string.compare(a.0, b.0) })
// [#("a0", 1), #("a0V", 2) #("a1", 3)]

Types

KeyError

</>

Key generation is not guaranteed under all conditions. Billions of values are possible before exhausting the key space. Keys are encoded using a combination of variable length integer encoding and fractional indices. This means that you cannot generate a key starting from an arbitrary string.

pub type KeyError {
  ErrWrongOrder
  ErrInvalid
}

Constructors

```
ErrWrongOrder
```
When generating a key between two values, the first value must be lexicographically smaller than the first
```
ErrInvalid
```
Something about the encoding of the key is invalid or the keyspace is exhausted. You can generate billions of keys before running out.

Values

after

</>

pub fn after(key: String) -> Result(String, KeyError)

Generate a key that will sort later than the given key

before

</>

pub fn before(key: String) -> Result(String, KeyError)

Generate a key that will sort before the given key

between

</>

pub fn between(
  key1: String,
  key2: String,
) -> Result(String, KeyError)

Generate a key that will sort between key1 and key2

first

</>

pub fn first() -> String

Return the first key, defined as the zero-key a0. This is useful when assigning a key to the first element of a list. Note that you cannot start a list of keys from any arbitrary string because the encoding of the key matters.

n_after

</>

pub fn n_after(
  key: String,
  num_keys n: Int,
) -> Result(List(String), KeyError)

Generate N keys after the given key

n_before

</>

pub fn n_before(
  key: String,
  num_keys n: Int,
) -> Result(List(String), KeyError)

Generate N keys before the given key

n_between

</>

pub fn n_between(
  key1: String,
  key2: String,
  num_keys n: Int,
) -> Result(List(String), KeyError)

Generate N keys between key1 and key 2

Example

import fractional_indexing as fi

// start with a list of some items which we want to index between existing keys `a0` and `a1`
let items = [1, 2, 3]

// generate some keys
let assert Ok(keys) = fi.n_between("a0", "a1")

// do something with the keys
items
|> list.map2(keys, fn(item, key) {
     #(key, item)
})
// output: [#("a0V", 1), #("a0k", 2), #("a0s", 3)]

n_first

</>

pub fn n_first(num_keys n: Int) -> List(String)

Generate N consecutive keys starting from the zero key a0