Repository navigation
Expand file tree
/
Copy pathstring_fugue.ts
More file actions
55 lines (51 loc) · 1.8 KB
/
Copy pathstring_fugue.ts
File metadata and controls
55 lines (51 loc) · 1.8 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import { LexUDTotalOrder } from "../lex_ud_total_order";
import { randomReplicaID } from "../utils";
/**
* A simple [[LexUDTotalOrder]] implementing the Fugue algorithm.
*
* For a description of the algorithm, see
* [https://mattweidner.com/2022/10/05/basic-list-crdt.html#intro-string-implementation](https://mattweidner.com/2022/10/05/basic-list-crdt.html#intro-string-implementation)
*/
export class StringFugue extends LexUDTotalOrder {
/**
* Local replica ID, set in constructor.
* All replicaIDs have the same length.
*/
readonly replicaID: string;
// Local counter.
private counter = 0;
/**
* @param options.replicaID A unique replicaID. Must be unique among all
* collaborating replicas, including past or concurrent replicas for the
* same device or user. All collaborating replicas' replicaIDs must be the
* same length.
*/
constructor(options: { replicaID?: string } = {}) {
super();
this.replicaID = options.replicaID ?? randomReplicaID();
}
createBetween(a: string | undefined, b: string | undefined): string {
// A globally unique new string, in the form of a causal dot.
const uniqueStr = `${this.replicaID}${this.counter++}`;
if (a !== undefined && b !== undefined) {
if (!b.startsWith(a)) {
// a is not a prefix of b.
return a + uniqueStr + "R";
} else {
// a is a strict prefix of b.
const bWithL = b.slice(0, -1) + "L";
return bWithL + uniqueStr + "R";
}
} else {
// Edge cases.
if (b === undefined) {
// Treat a (possibly undefined) as not a prefix of b.
return (a ?? "") + uniqueStr + "R";
} else {
// Treat a (undefined) as a strict prefix of b.
const bWithL = b.slice(0, -1) + "L";
return bWithL + uniqueStr + "R";
}
}
}
}