Fractional index library with jittering and generator
npm install fractional-indexing-jitteredGoal of this package is a abstraction to use Fractional indexing,
a technique to generate new order keys in between a existing list without
having to reorder all the existing keys.
This package supports Jittering the key to have a high probability of a unique key.
The package consist of two parts:
- Fractional index API is a collection of functions to generate order keys, either jittered or not
- Generator is a class to help with the generator process, with support for groups
This package builds on a solid foundation both in writing and in code, see credits
Some examples using react are available in the examples folder and can be viewed on Github Pages
The default character set has a chance of roughly one in 47.000 to generate the same key for the same input at the cost of making the keys 3 characters longer on average.
(Not taking into account that Math.random is not 100% random)
1 utility functions
- indexCharacterSet -> create a custom character set if you want more control
The default will use a base62 character set, with generated keys starting from 'a0', 'a1', 'a2' etc, with random jitter
Read more about Generator Groups and the API at the Generator Docs
``ts
import { IndexGenerator } from 'fractional-indexing-jittered';
const generator = new IndexGenerator([]);
// dummy code, would normally be stored in database or CRDT and updated from there
const list: string[] = [];
function updateList(newKey: string) {
list.push(newKey);
generator.updateList(list);
}
// "a01TB" a0 with jitter
const firstKey = generator.keyStart();
updateList(firstKey);
// "a10Vt" a1 with jitter
const secondKey = generator.keyEnd();
updateList(secondKey);
// "a0fMq" jittered midpoint between firstKey and secondKey
const keyInBetween = generator.keyAfter(firstKey);
updateList(keyInBetween);
// "a0M3o" jittered midpoint between firstKey and keyInBetween
const anotherKeyInBetween = generator.keyBefore(keyInBetween);
updateList(anotherKeyInBetween);
// [ 'a01TB', 'a0M3o', 'a0fMq', 'a10Vt' ]
// [ firstKey, anotherKeyInBetween, keyInBetween, secondKey ]
console.log(list.sort());
``
Kudos to them and David Greenspan, this implementation also includes a slightly adjusted
version of variable-length integers, and the prepend/append optimization described in David's article.
This means that this package is not well suited for situations where object adjacency is critical
(like character order in collaborative text editing)
Best practice is use another ID as tiebreaker like the object ID.
If you detect an Identical key, you can always just regenerate one (or both)