Fractional Indexing

Note

This is Doist's fork of httpie/fractional-indexing-python, modernised to parity with the JS reference rocicorp/fractional-indexing v4.0.0. It is published to Doist's private AWS CodeArtifact index as doist-fractional-indexing (the import name is still fractional_indexing). The parity changes have been offered upstream in httpie/fractional-indexing-python#3, but releases here are not blocked on it.

This is based on Implementing Fractional Indexing by David Greenspan .

Fractional indexing is a technique to create an ordering that can be used for Realtime Editing of Ordered Sequences.

This implementation includes variable-length integers, and the prepend/append optimization described in David's article.

Installation

$ pip install fractional-indexing

Usage

Generate a single key

from fractional_indexing import generate_key_between


# Insert at the beginning
first = generate_key_between(None, None)
assert first == 'a0'

# Insert after 1st
second = generate_key_between(first, None)
assert second == 'a1'

# Insert after 2nd
third = generate_key_between(second, None)
assert third == 'a2'

# Insert before 1st
zeroth = generate_key_between(None, first)
assert zeroth == 'Zz'

# Insert in between 2nd and 3rd (midpoint)
second_and_half = generate_key_between(second, third)
assert second_and_half == 'a1V'

Generate multiple keys

Use this when generating multiple keys at some known position, as it spaces out indexes more evenly and leads to shorter keys.

from fractional_indexing import generate_n_keys_between


# Insert 3 at the beginning
keys = generate_n_keys_between(None, None, n=3)
assert keys == ['a0', 'a1', 'a2']

# Insert 3 after 1st
keys = generate_n_keys_between('a0', None, n=3)
assert keys == ['a1', 'a2', 'a3']

# Insert 3 before 1st
keys = generate_n_keys_between(None, 'a0', n=3)
assert keys == ['Zx', 'Zy', 'Zz']

# Insert 3 in between 2nd and 3rd (midpoint)
keys = generate_n_keys_between('a1', 'a2', n=3)
assert keys == ['a1G', 'a1V', 'a1l']

Validate a key

from fractional_indexing import validate_order_key, FIError


validate_order_key('a0')

try:
    validate_order_key('foo')
except FIError as e:
    print(e)  # fractional_indexing.FIError: invalid order key: foo

Jittered keys for concurrent inserts

generate_key_between() is deterministic: two devices concurrently inserting between the same pair of keys generate the same key, and a later insert between two equal keys raises FIError. When concurrent writers are possible, use generate_jittered_key_between(), which appends a few random digits (default 3) so simultaneous identical inserts diverge with high probability:

import random

from fractional_indexing import generate_jittered_key_between


key = generate_jittered_key_between('a0', 'a1')                          # e.g. 'a0Vk2P'
key = generate_jittered_key_between('a0', 'a1', jitter_length=4)         # longer suffix, lower collision odds
key = generate_jittered_key_between('a0', 'a1', rng=random.Random(42))   # seeded for reproducible tests

The result is always a valid order key strictly between the bounds. In one corner case (the generated key is a prefix of the upper bound) the suffix is skipped and the plain key returned. There is deliberately no jittered variant of generate_n_keys_between() — bulk generation is single-writer, and suffixes could reorder prefix-related neighbours.

Use custom base digits

By default, this library uses Base62 character encoding. To use a different set of digits, pass them in as the digits argument to generate_key_between(), generate_n_keys_between(), and validate_order_key().

Every key starts with a "head" character that encodes the length of its integer part. Since v0.2.0 (matching the JS reference v4.0.0), the head alphabet (int_digits) defaults to digits itself, so a custom alphabet produces self-contained keys drawn only from that alphabet:

from fractional_indexing import generate_key_between


assert generate_key_between(None, None, digits='0123456789') == '50'
assert generate_key_between('50', None, digits='0123456789') == '51'

To keep the pre-0.2 behaviour (A-Z/a-z head markers, e.g. a0), pass BASE_52_DIGITS as int_digits. An odd-length alphabet such as Base95 cannot supply its own (even-length) head alphabet, so it must be paired with an explicit int_digits:

from fractional_indexing import BASE_52_DIGITS, generate_key_between, generate_n_keys_between, validate_order_key


BASE_95_DIGITS = ' !"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~'

assert generate_key_between(None, None, digits=BASE_95_DIGITS, int_digits=BASE_52_DIGITS) == 'a '
assert generate_key_between('a ', None, digits=BASE_95_DIGITS, int_digits=BASE_52_DIGITS) == 'a!'
assert generate_key_between(None, 'a ', digits=BASE_95_DIGITS, int_digits=BASE_52_DIGITS) == 'Z~'

assert generate_n_keys_between('a ', 'a!', n=3, digits=BASE_95_DIGITS, int_digits=BASE_52_DIGITS) == ['a 8', 'a P', 'a h']

validate_order_key('a ', digits=BASE_95_DIGITS, int_digits=BASE_52_DIGITS)

Alphabets are validated: they must be at least two characters, single-byte (char code 0-255), and in strictly ascending character-code order; int_digits must also have even length. Invalid alphabets raise FIError.

Other Languages

This is a Python port of the original JavaScript implementation by @rocicorp (as of its v4.0.0). That means that this implementation is byte-for-byte compatible with:

Language	Repo
JavaScript	https://github.com/rocicorp/fractional-indexing
Go	https://github.com/rocicorp/fracdex
Kotlin	https://github.com/darvelo/fractional-indexing-kotlin
Ruby	https://github.com/kazu-2020/fractional_indexer

Changelog

1.1.0

• New generate_jittered_key_between(): appends jitter_length (default 3) random digits so concurrent inserts between the same pair of keys diverge instead of colliding. Takes an optional seeded rng for reproducibility. Skips the suffix in the one corner case where the generated key is a prefix of the upper bound.

1.0.1

• generate_n_keys_between() now raises FIError for a negative n, instead of silently returning a single key (one bound None) or hitting RecursionError (both bounds set). Deviation from the JS reference, which only documents the n >= 0 precondition.

0.2.0

Brings the library to parity with rocicorp/fractional-indexing v4.0.0:

• Breaking: the head alphabet now defaults to digits itself, so custom alphabets produce self-contained keys (e.g. generate_key_between(None, None, digits='0123456789') returns '50', not 'a0'). Pass int_digits=BASE_52_DIGITS to restore the previous A-Z/a-z head markers. Keys generated with the default Base62 alphabet are unchanged.
• New int_digits argument on generate_key_between(), generate_n_keys_between(), and validate_order_key() to customise the head alphabet, plus a new BASE_52_DIGITS export.
• generate_key_between() now accepts its bounds in either order and swaps them, instead of raising FIError.
• Alphabets are validated (length, ascending character-code order, single-byte); invalid alphabets and unknown digits now raise FIError consistently instead of leaking ValueError.
• Digit lookups are cached per alphabet, and the midpoint calculation uses integer arithmetic (the decimal dependency is gone).