Fractional Indexing #

This is based on Implementing Fractional Indexing by David Greenspan.

Fractional indexing is a technique to create an ordering that can be used for Realtime Editing of Ordered Sequences.

This implementation includes variable-length integers, and the prepend/append optimization described in David's article.

API #

generateKeyBetween #

Generate a single key in between two points.

String generateKeyBetween(
  String? a, // start
  String? b, // end
  [String digits = base62Digits], // optional character encoding
);

import 'package:fractional_indexing_dart/fractional_indexing_dart.dart' as findex;

final first = findex.generateKeyBetween(null, null); // "a0"

// Insert after 1st
final second = findex.generateKeyBetween(first, null); // "a1"

// Insert after 2nd
final third = findex.generateKeyBetween(second, null); // "a2"

// Insert before 1st
final zeroth = findex.generateKeyBetween(null, first); // "Zz"

// Insert in between 2nd and 3rd (midpoint)
final secondAndHalf = findex.generateKeyBetween(second, third); // "a1V"

generateNKeysBetween #

Use this when generating multiple keys at some known position, as it spaces out indexes more evenly and leads to shorter keys.

List<String> generateNKeysBetween(
  String? a, // start
  String? b, // end
  int n, // number of keys to generate evenly between start and end
  [String digits = base62Digits], // optional character encoding
);

import 'package:fractional_indexing_dart/fractional_indexing_dart.dart' as findex;

final first = findex.generateNKeysBetween(null, null, 2); // ['a0', 'a1']

// Insert two keys after 2nd
findex.generateNKeysBetween(first[1], null, 2); // ['a2', 'a3']

// Insert two keys before 1st
findex.generateNKeysBetween(null, first[0], 2); // ['Zy', 'Zz']

// Insert two keys in between 1st and 2nd (midpoints)
// Assuming second and third are defined as above
findex.generateNKeysBetween(second, third, 2); // ['a0G', 'a0V']

Sorting #

The indexes generated by this library are case-sensitive. Dart's default String comparison is case-sensitive, so standard sorting works out of the box.

class Todo {
  final String id;
  final String content;
  final String fractionalIndex;

  Todo(this.id, this.content, this.fractionalIndex);
}

void main() {
  final todos = [
    Todo("todo_1253241", "Read the docs", "YzZ"),
    Todo("todo_8973942", "Open a PR", "Yza"),
  ];

  todos.sort((a, b) => a.fractionalIndex.compareTo(b.fractionalIndex));
}

Other Implementations #

Languages #

This is a Dart port of the original JavaScript implementation by @rocicorp. That means that this implementation is byte-for-byte compatible with: