fractional-indexing-jittered 0.2.0
An implementation of fractional indexing with jitter
Requires Python: <4,>=3.7

# Fractional Indexing

This is based on [Implementing Fractional Indexing
](https://observablehq.com/@dgreensp/implementing-fractional-indexing) by [David Greenspan
](https://github.com/dgreensp).

Fractional indexing is a technique to create an ordering that can be used
for [Realtime Editing of Ordered Sequences](https://www.figma.com/blog/realtime-editing-of-ordered-sequences/).

This implementation includes variable-length integers, and the prepend/append optimization described in David's article.
Additionally, it includes optional jittering to prevent collisions during concurrent updates.

## Installation

```bash
pip install fractional-indexing-jittered
```

## Usage

### Generate a single key

```python
from fractional_indexing_jittered 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.

```python
from fractional_indexing_jittered 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

```python
from fractional_indexing_jittered import validate_order_key, FIError


validate_order_key('a0')

try:
    validate_order_key('foo')
except FIError as e:
    print(e)  # fractional_indexing_jittered.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()`:

```python
from fractional_indexing_jittered 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)

```

## Jittering

When multiple clients insert at the same position simultaneously, they may generate identical keys, causing conflicts. Jittering adds a random suffix to keys to prevent this.

### Generate jittered keys

```python
from fractional_indexing_jittered import generate_jittered_key_between, generate_n_jittered_keys_between


# Generate a single jittered key
key = generate_jittered_key_between(None, None)
# Returns something like 'a0Gx3f' - 'a0' plus a random suffix

# Insert between two keys with jitter
key = generate_jittered_key_between('a0', 'a1')
# Returns something like 'a0V3kQ' - midpoint plus random suffix

# Generate multiple jittered keys
keys = generate_n_jittered_keys_between('a0', 'a1', 3)
# Returns 3 keys with jitter, e.g. ['a0F2xK', 'a0V8mP', 'a0k4nR']
```

### Using IndexGenerator

The `IndexGenerator` class provides a convenient interface for managing ordered lists:

```python
from fractional_indexing_jittered import IndexGenerator, GeneratorOptions


# Create a generator (jittering enabled by default)
gen = IndexGenerator([])

# Generate keys at the end
key1 = gen.key_end()
gen.update_list([key1])

key2 = gen.key_end()
gen.update_list([key1, key2])

key3 = gen.key_end()
# Keys are automatically ordered: key1 < key2 < key3
```

### IndexGenerator without jittering

```python
from fractional_indexing_jittered import IndexGenerator, GeneratorOptions


# Disable jittering for deterministic keys
gen = IndexGenerator([], GeneratorOptions(use_jitter=False))

key1 = gen.key_end()  # 'a0'
gen.update_list([key1])

key2 = gen.key_end()  # 'a1'
gen.update_list([key1, key2])

# Insert between existing keys
key_between = gen.key_after(key1)  # 'a0V'
```

### IndexGenerator methods

```python
from fractional_indexing_jittered import IndexGenerator, GeneratorOptions


gen = IndexGenerator(['a0', 'a5'], GeneratorOptions(use_jitter=False))

# Single key generation
gen.key_start()        # Key before all items: 'Zz'
gen.key_end()          # Key after all items: 'a6'
gen.key_before('a5')   # Key before 'a5': 'a4' (or between 'a0' and 'a5')
gen.key_after('a0')    # Key after 'a0': 'a1' (or between 'a0' and 'a5')

# Multiple key generation
gen.n_keys_start(3)          # 3 keys before all items
gen.n_keys_end(3)            # 3 keys after all items
gen.n_keys_before('a5', 3)   # 3 keys before 'a5'
gen.n_keys_after('a0', 3)    # 3 keys after 'a0'
```

### IndexGenerator with groups

Groups allow you to maintain separate orderings within the same list:

```python
from fractional_indexing_jittered import IndexGenerator, GeneratorOptions


# Enable groups with a 2-character group ID prefix
gen = IndexGenerator([], GeneratorOptions(use_jitter=False, group_id_length=2))

# Generate keys for group 'g1'
key1 = gen.key_end('g1')  # 'g1a0'
gen.update_list([key1])

key2 = gen.key_end('g1')  # 'g1a1'
gen.update_list([key1, key2])

# Generate keys for a different group 'g2'
key3 = gen.key_end('g2')  # 'g2a0' - independent of group 'g1'
```

### Custom character sets with jittering

```python
from fractional_indexing_jittered import (
    index_character_set,
    generate_jittered_key_between,
    IndexGenerator,
    GeneratorOptions,
)


# Create a custom character set
custom_chars = index_character_set(
    chars='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz',
    first_positive='a',
    most_positive='z',
    most_negative='A',
)

# Use with jittered key generation
key = generate_jittered_key_between(None, None, custom_chars)

# Use with IndexGenerator
gen = IndexGenerator([], GeneratorOptions(char_set=custom_chars, use_jitter=True))
```

## Other Languages

This is a Python port of the original JavaScript implementation by [@rocicorp](https://github.com/rocicorp). That means
that this implementation is byte-for-byte compatible with:

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