FractionalIndexing

A Swift port of fractional-indexing for generating lexicographically sortable ordering keys.

Fractional indexing lets you insert items anywhere in an ordered collection without renumbering the items around them. Store the generated key with each item and sort by that key.

Add it to a package

Add FractionalIndexing as a dependency in your app or library's Package.swift:

dependencies: [
    .package(url: "https://github.com/<owner>/FractionalIndexing.git", from: "1.0.0"),
],
targets: [
    .target(
        name: "MyApp",
        dependencies: ["FractionalIndexing"]
    ),
]

Replace <owner> and the version with the repository's published location and release. While developing both packages locally, use a path dependency instead:

.package(path: "../FractionalIndexing")

In Xcode, choose File → Add Package Dependencies…, enter the repository URL, then add the FractionalIndexing product to your target.

Getting started

Create the first key with initial(). To append an item, generate a key after the current last key. To insert, generate one between the item's immediate neighbours.

import FractionalIndexing

struct Task {
    let title: String
    let order: OrderKey
}

var tasks = [
    Task(title: "Plan", order: try .initial()), // "a0"
]

let last = tasks.last?.order
tasks.append(Task(title: "Ship", order: try .between(last, nil))) // "a1"

let inserted = try OrderKey.between(tasks[0].order, tasks[1].order) // "a0V"
tasks.insert(Task(title: "Build", order: inserted), at: 1)

let orderedTasks = tasks.sorted { $0.order < $1.order }
// Plan, Build, Ship

Pass nil for the start or end of the key space. between accepts bounds in either order, but equal bounds are an error.

Generate several keys

Use generate when creating multiple adjacent items. Its result is already sorted and contains distinct keys.

let keys = try OrderKey.generate(3, between: nil, and: nil)
// ["a0", "a1", "a2"]

let beforeFirst = try OrderKey.generate(2, between: nil, and: keys[0])
// ["Zy", "Zz"]

Store and restore keys

OrderKey is Comparable, Hashable, and Codable. Persist rawValue when storing a plain string, then construct a new OrderKey when reading external or persisted data. Construction validates the string; keys created by the library are valid by construction.

let key = try OrderKey("a0V")
let valueToStore = key.rawValue

let restored = try OrderKey(valueToStore)

let json = try JSONEncoder().encode(key) // "\"a0V\""
let decoded = try JSONDecoder().decode(OrderKey.self, from: json)

Keys use base-62 digits and A-Z/a-z integer heads. Lexicographic string ordering matches OrderKey ordering, so database and in-memory sorts can use the persisted values directly.