Skip to main content

Provides functions for generating ordering strings

Project description

Fractional Indexing

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.


$ pip install fractional-indexing


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

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


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

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():

from fractional_indexing import 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) == 'a '
assert generate_key_between('a ', None, digits=BASE_95_DIGITS) == 'a!'
assert generate_key_between(None, 'a ', digits=BASE_95_DIGITS) == 'Z~'

assert generate_n_keys_between('a ', 'a!', n=3, digits=BASE_95_DIGITS) == ['a"', 'a#', 'a$']

validate_order_key('a ', digits=BASE_95_DIGITS)

Other Languages

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

Language Repo

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

fractional-indexing-0.1.3.tar.gz (7.8 kB view hashes)

Uploaded Source

Built Distribution

fractional_indexing-0.1.3-py3-none-any.whl (8.0 kB view hashes)

Uploaded Python 3

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page