82 lines
2.6 KiB
Markdown
82 lines
2.6 KiB
Markdown
|
# peoplesgrocers-lseq
|
||
|
|
|
||
|
|
Rust implementation of the L-SEQ algorithm for fractional indexing and list CRDTs.
|
||
|
|
|
||
|
|
## Installation
|
||
|
|
|
||
|
|
Add this to your `Cargo.toml`:
|
||
|
|
|
||
|
|
```toml
|
||
|
|
[dependencies]
|
||
|
|
peoplesgrocers-lseq = "1.0.0"
|
||
|
|
```
|
||
|
|
|
||
|
|
## Usage
|
||
|
|
|
||
|
|
```rust
|
||
|
|
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.
|