# lseq

Go implementation of the L-SEQ algorithm for fractional indexing and list CRDTs.

The library handles edge cases that break other more naive implementations of
fractional indexing. With this library you can always insert before the first
item or after the last item, indefinitely.

This is exactly what you need to build realtime collaborative apps with
ordering for lists or trees of items. Users can reorder or insert at arbitrary
positions but in practice people really like moving items to the top or end of
a list.

## Installation

```bash
go get peoplesgrocers.com/code/oss/lseq/golang
```

## Usage

```go
package main

import (
    "fmt"
    "math/rand"
    "sort"

    "peoplesgrocers.com/code/oss/lseq/golang"
)

func main() {
    l := lseq.NewLSEQ(rand.Float64)

    first := l.Alloc(nil, nil)
    second := l.Alloc(&first, nil)
    between := l.Alloc(&first, &second)

    // String comparison gives correct order
    keys := []string{second, first, between}
    sort.Strings(keys)
    fmt.Println(keys) // [first, between, second]
}
```

## API

### `NewLSEQ(random func() float64) *LSEQ`

Create an allocator. Requires a random function returning values in [0, 1).

### `lseq.Alloc(before, after *string) string`

Allocate a key between `before` and `after`.

- `lseq.Alloc(nil, nil)` — first key in an empty list
- `lseq.Alloc(nil, &first)` — insert at head
- `lseq.Alloc(&last, nil)` — insert at tail
- `lseq.Alloc(&a, &b)` — insert between a and b

### `CompareLSEQ(a, b string) int`

Compare two keys. Returns -1, 0, or 1.

### `EvenSpacingIterator`

Generate evenly-spaced keys for bulk initialization:

```go
k, iter, err := lseq.NewEvenSpacingIterator(1000)
if err != nil {
    panic(err)
}

var keys []string
for {
    pos, ok := iter.Next()
    if !ok {
        break
    }
    keys = append(keys, lseq.PositionToKey(k, pos))
}
```

## Design

Keys are base-64 encoded strings using the alphabet `-0-9A-Z_a-z`. Standard
string comparison produces correct ordering. Keys work in SQL `ORDER BY`,
database indexes, and any language with string sorting.

## Cross-language support

Matching implementations exist for Rust, TypeScript, and Python; validated
against a shared conformance test suite.

## References

- [LSEQ: an Adaptive Structure for Sequences in Distributed Collaborative Editing](https://hal.science/hal-00921633/document) (Nédelec et al., 2013)

## License

AGPL-3.0