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.
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:
Libraries
- fractional_indexing_dart
- Support for doing something awesome.