# LexSortKey

Lexicographically sortable keys for ordered sequences in Elixir.

This library implements fractional indexing as outlined in:
- [Real-time Editing of Ordered Sequences](https://www.figma.com/blog/realtime-editing-of-ordered-sequences/) (Figma)
- [Implementing Fractional Indexing](https://observablehq.com/@dgreensp/implementing-fractional-indexing)

## Use Cases

- Real-time collaborative editing (like Figma, Notion, Linear)
- Ordered lists in databases without reindexing
- Distributed systems where clients generate keys independently
- Any scenario requiring insertion at arbitrary positions

## Installation

Add `lex_sort_key` to your list of dependencies in `mix.exs`:

```elixir
def deps do
  [
    {:lex_sort_key, "~> 0.1.0"}
  ]
end
```

## Quick Start

```elixir
# Create initial keys for a list
keys = LexSortKey.n_first(3)
# => ["a0", "a1", "a2"]

# Insert between two keys
{:ok, between} = LexSortKey.between("a0", "a1")
# => {:ok, "a0V"}

# Keys sort correctly as strings
Enum.sort(["a1", "a0V", "a0"])
# => ["a0", "a0V", "a1"]
```

## How It Works

Keys consist of two parts: a **variable-length integer** and an optional **fractional part**.

### Variable-Length Integer Encoding

The first character determines the length, enabling correct lexicographic sorting:

| Prefix | Length | Range | Example |
|--------|--------|-------|---------|
| `Z` | 2 chars | 62 values | `Z0` to `Zz` |
| `a` | 2 chars | 62 values | `a0` to `az` |
| `b` | 3 chars | 3,844 values | `b00` to `bzz` |
| `c` | 4 chars | 238,328 values | `c000` to `czzz` |

Uppercase letters (`A-Z`) represent values before `a0`, lowercase (`a-z`) represent values after.

### Fractional Part

When inserting between adjacent integers, a fractional part is appended:

```elixir
LexSortKey.between("a0", "a1")    # => "a0V"
LexSortKey.between("a0", "a0V")   # => "a0F"
LexSortKey.between("a0V", "a1")   # => "a0k"
```

## API Reference

### Basic Operations

```elixir
# Get the first key (zero key)
LexSortKey.first()
# => "a0"

# Generate key after another
{:ok, key} = LexSortKey.key_after("a0")
# => {:ok, "a1"}

# Generate key before another
{:ok, key} = LexSortKey.key_before("a1")
# => {:ok, "a0"}

# Generate key between two keys
{:ok, key} = LexSortKey.between("a0", "a1")
# => {:ok, "a0V"}
```

### Bulk Operations

```elixir
# Generate N consecutive keys starting from a0
LexSortKey.n_first(5)
# => ["a0", "a1", "a2", "a3", "a4"]

# Generate N keys after a given key
{:ok, keys} = LexSortKey.n_after("a0", 3)
# => {:ok, ["a1", "a2", "a3"]}

# Generate N keys before a given key
{:ok, keys} = LexSortKey.n_before("a2", 2)
# => {:ok, ["a0", "a0V"]}

# Generate N keys between two keys
{:ok, keys} = LexSortKey.n_between("a0", "a1", 3)
# => {:ok, ["a0V", "a0k", "a0s"]}

# Distributed insertion (shorter keys)
{:ok, keys} = LexSortKey.n_between_distributed("a0", "a1", 3)
# => {:ok, ["a0F", "a0V", "a0k"]}

# Efficient prepending
{:ok, keys} = LexSortKey.prepend_n("a0", 3)
# => {:ok, ["Zx", "Zy", "Zz"]}
```

### Rebalancing

After many insertions, keys can grow long. Rebalance to get compact keys:

```elixir
# Long keys from repeated insertions
long_keys = ["a0", "a0VVVVVV", "a0VVVVVk", "a1"]

# Rebalance to short keys
{:ok, short_keys} = LexSortKey.rebalance(long_keys)
# => {:ok, ["a0", "a1", "a2", "a3"]}

# Rebalance with bounds (preserves surrounding keys)
{:ok, keys} = LexSortKey.rebalance(keys, lower_bound: "a0", upper_bound: "b00")

# Rebalance only a portion of the list
{:ok, keys} = LexSortKey.rebalance_range(keys, 1..3)
```

## Performance Considerations

- **Sequential insertions best case**: Inserting on first or last position keeps the keys sweet and short. 1M keys is 5 chars and takes few usec per key to generate.
- **Sequential insertions worst case**: But in worst case scenario keys can grow logarithmically. After 1000 sequential inserts on a second position, max key length is ~169 characters.
- **Distributed insertions**: Using `n_between_distributed/3` keeps keys much shorter (~4 characters for 1000 keys).
- **Rebalancing**: Call `rebalance/1` periodically to reset key lengths to optimal (~2-3 characters).

```elixir
iex()> Enum.reduce(1..1000, nil, fn _, acc -> LexSortKey.key_before(acc) |> elem(1)  end) |> IO.puts
Ykt
iex()> Enum.reduce(1..1000, nil, fn _, acc -> LexSortKey.key_after(acc) |> elem(1)  end) |> IO.puts
bF7
iex()> Enum.reduce(1..1000, nil, fn _, acc -> LexSortKey.between("a0", acc) |> elem(1)  end) |> IO.puts
a000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003
:timer.tc(fn -> Enum.reduce(1..1000000, nil, fn _, acc -> LexSortKey.key_after(acc) |> elem(1)  end) end)
{3345962, "d3B81"}
```

## License

MIT License. See [LICENSE](LICENSE) for details.