peoplesgrocers-lseq

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

Installation

Add this to your Cargo.toml:

[dependencies]
peoplesgrocers-lseq = "1.0.0"

Usage

use peoplesgrocers_lseq::{LSEQ, SortKey, compare_lseq};
use rand::thread_rng;

// Create a new L-SEQ instance
let mut lseq = LSEQ::new(thread_rng());

// Allocate identifiers
let id1 = lseq.alloc(None, None);           // First identifier
let id2 = lseq.alloc(Some(&id1), None);     // After id1
let id3 = lseq.alloc(Some(&id1), Some(&id2)); // Between id1 and id2

// Sort identifiers
let mut ids = vec![id3.clone(), id1.clone(), id2.clone()];
ids.sort();
println!("{:?}", ids); // [id1, id3, id2] - properly ordered

// Convert to/from strings
let key_str = id1.to_string();
let parsed_key: SortKey = key_str.parse().unwrap();
assert_eq!(id1, parsed_key);

// Use with deterministic RNG for testing
use rand::rngs::StdRng;
use rand::SeedableRng;

let rng = StdRng::seed_from_u64(42);
let mut deterministic_lseq = LSEQ::new(rng);

Features

• Fractional indexing: Generate identifiers that can be inserted between any two existing ones
• Serialization: Full support for serde serialization/deserialization
• Ordering: SortKey implements Ord and can be used directly with Rust's sorting
• String conversion: Convert to/from strings for storage and transmission
• Even spacing: Utilities for generating evenly distributed keys for bulk operations

API

LSEQ<R: Rng>

new(rng: R) -> Self

Creates a new L-SEQ instance with the given random number generator.

alloc(&mut self, before: Option<&SortKey>, after: Option<&SortKey>) -> SortKey

Allocates a new identifier between two existing identifiers.

• before: The identifier that should come before the new one (or None for beginning)
• after: The identifier that should come after the new one (or None for end)
• Returns: A new SortKey that sorts between before and after

SortKey

A sort key that implements Ord, Serialize, Deserialize, and string conversion.

EvenSpacingIterator

Utility for generating evenly spaced sort keys for bulk operations.

How it works

L-SEQ generates identifiers using a base-64 alphabet that maintains lexicographic ordering. Each identifier is a sequence of characters from this alphabet, and new identifiers are generated by finding space between existing ones at different depths.

The algorithm uses alternating allocation strategies (bias toward min or max) at different depths to avoid degenerative cases and maintain good performance characteristics.