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';

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

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

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

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

// Insert in between 2nd and 3rd (midpoint)
final secondAndHalf = FractionalIndexing.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';

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

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

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

// Insert two keys in between 1st and 2nd (midpoints)
// Assuming second and third are defined as above
FractionalIndexing.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));
}

RankedLinkedList #

This package also provides a RankedLinkedList that automatically maintains the order of elements based on their fractional index. It extends Dart's LinkedList and ensures that elements remain sorted.

Usage #

First, create a class that mixes in RankedLinkedListEntry:

base class TodoEntry extends LinkedListEntry<TodoEntry>
    with RankedLinkedListEntry<TodoEntry> {
  final String id;
  final String content;

  TodoEntry(this.id, this.content);

  @override
  String toString() => '$id ($rank): $content';
}

If your class already extends another class, you can apply both as mixins:

base class TodoEntry extends MyBaseClass
    with LinkedListEntry<TodoEntry>, RankedLinkedListEntry<TodoEntry> {
  // ...
}

Then you can use RankedLinkedList to manage your items:

final list = RankedLinkedList<TodoEntry>();

// Add items - ranks are automatically generated if not provided
final todo1 = TodoEntry('1', 'Buy milk');
list.add(todo1); // Rank: "a0"

final todo3 = TodoEntry('3', 'Walk the dog');
list.add(todo3); // Rank: "a1"

// Insert between items
final todo2 = TodoEntry('2', 'Clean room');
todo1.insertAfter(todo2); // Rank: "a0V"

// Iterate
for (final todo in list) {
  print(todo);
}

// Access by index (efficiently cached)
print(list[1]); // todo2

The list validates ranks on insertion relative to neighbors. If you try to insert an item with a rank that violates the order, it will throw an ArgumentError.

// Throws ArgumentError because "a0" is not greater than "a1"
// list.add(TodoEntry('4', 'Invalid')..rank = "a0");

Loading Existing Data #

When loading data from a database or other source where ranks are already defined, use insert to insert items in the correct position efficiently.

final loadedList = RankedLinkedList<TodoEntry>();
final items = [
  TodoEntry('3', 'C')..rank = 'a2',
  TodoEntry('1', 'A')..rank = 'a0',
  TodoEntry('2', 'B')..rank = 'a1',
];

// Items can be added in any order
for (final item in items) {
  loadedList.insert(item.rank!, item);
}

// loadedList is now sorted: A, B, C

insert utilizes binary search to efficiently calculate the insertion index (O(log N) search time), making it highly performant for inserting items into their correct sorted positions. It throws an Exception if a duplicate rank is encountered.

Finding Entries by Rank #

You can efficiently find an entry by its rank using getByRank, which also uses binary search for O(log N) performance:

final list = RankedLinkedList<TodoEntry>();
final todo1 = TodoEntry('1', 'Buy milk')..rank = 'a0';
final todo2 = TodoEntry('2', 'Clean room')..rank = 'a1';
final todo3 = TodoEntry('3', 'Walk the dog')..rank = 'a2';

list.add(todo1);
list.add(todo2);
list.add(todo3);

// Find entry by rank
final found = list.getByRank('a1');
print(found); // 2 (a1): Clean room

// Returns null if rank doesn't exist
final notFound = list.getByRank('z99');
print(notFound); // null

getByRank uses binary search on the cached indexed list, making it efficient even for large lists.

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: