Fractional Inde xing

This is based onImplementing Fractional Inde xing byDavid Greenspan .

Fractional inde xing is a technique to create an ordering that can be used forRealtime Editing of Ordered Sequences.

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

Installation

$ pip install fractional-inde xing

Usage

Generate a single key

fromfractional_inde xingimportgenerate_key_between


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

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

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

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

# Insert in between 2nd and 3rd (midpoint)
second_and_half=generate_key_between(second,third)
assertsecond_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.

fromfractional_inde xingimportgenerate_n_keys_between


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

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

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

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

Validate a key

fromfractional_inde xingimportvalidate_order_key,FIError


validate_order_key('a0')

try:
validate_order_key('foo')
exceptFIErrorase:
print(e)# fractional_inde xing.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 thedigits argument togenerate_key_between(),generate_n_keys_between(),andvalidate_order_key():

fromfractional_inde xingimportgenerate_key_between,generate_n_keys_between,validate_order_key


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

assertgenerate_key_between(None,None,digits=BASE_95_DIGITS)=='a '
assertgenerate_key_between('a ',None,digits=BASE_95_DIGITS)=='a!'
assertgenerate_key_between(None,'a ',digits=BASE_95_DIGITS)=='Z~'

assertgenerate_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
JavaScript	https://github /rocicorp/fractional-inde xing
Go	https://github /rocicorp/fracdex
Kotlin	https://github /darvelo/fractional-inde xing -kotlin
Ruby	https://github /kazu-2020/fractional_indexer