Fugue<T> class

The optimised, run-length ("waypoint") Fugue list CRDT — a faithful implementation of Algorithm 1 (Weidner & Kleppmann, TPDS 2025) that stores contiguously-typed runs as single blocks instead of one node per element.

Element identity is a logical Dot (not an HLC), so a forward-typed run carries consecutive counters and collapses into one block.

Implemented types

• Crdt<Fugue<T>>

Constructors

Fugue()

Properties

blockCount → int

Number of stored blocks — for coalescing assertions in tests.

no setter

dots → Iterable<Dot>

Every element dot (live + tombstoned), for seeding a LamportClock.

no setter

elementCount → int

Total stored elements, live + tombstoned (sum of block lengths). Useful for GC accounting and diagnostics.

no setter

empty → Fugue<T>

Identity element of the join-semilattice. a.join(empty) == a for every a.

no setter, override

hashCode → int

The hash code for this object.

no setter, override

isEmpty → bool

Whether there are no live elements.

no setter

length → int

Number of live (non-tombstoned) elements.

no setter

orphanBlockCount → int

Blocks whose parent element is not present in this state — either deltas delivered ahead of their parent (transient, heals on merge) or children of pruned blocks (permanent; indicates a violated prune barrier). Non-empty AFTER a full sync = investigate.

no setter

rawBlocks → Iterable<(Dot, Dot, Side, List<T>, List<int>)>

Low-level per-block view for codecs: (start, parent, side, values, deletedRanges), where deletedRanges is a flat [start, len, …] list. The values list must not be mutated.

no setter

runtimeType → Type

A representation of the runtime type of the object.

no setter, inherited

values → List<T>

The live values in resolved order.

no setter

Methods

applyOps(List<FugueOp<T>> ops, LamportClock clk) → Fugue<T>

Apply a batch of ops locally (minting dots from clk) and return the DELTA to ship to peers: the blocks created or grown by this batch, at their final state.

clone() → Fugue<T>

A deep, independent copy — the basis of the immutable join.

delete(int i) → Dot?

Tombstone the live element at visible index i. Returns the start dot of the affected block, or null when i is out of range.

deleteDot(Dot dot) → Dot?

Tombstone the element dot (position-based delete). Returns the block start, or null if the element is absent.

deltaCompose(Fugue<T> other) → Fugue<T>

Composes two locally-produced Δ-state fragments. For most CRDT types this coincides with join. Override when the cross-replica join applies filters (tombstone semantics, max reduction) that would be wrong for in-replica delta accumulation.

override

encode(Object? encodeValue(T)) → Object

Encode to a JSON-compatible structure. encodeValue maps one element value to a JSON-compatible form.

indexOf(Dot dot) → int

The visible index of element dot, or -1 if it is not a live element.

insert(int i, T value, Dot dot) → Dot

Insert value at visible index i with identity dot. Follows Algorithm 1; coalesces into an existing block when dot continues a run.

insertAfter(Dot? anchor, T value, Dot dot) → Dot

Insert value immediately after the position anchor (null / Dot.origin = at the very start). Returns the touched block start.

isLive(Dot dot) → bool

Whether dot identifies a live (non-tombstoned) element.

join(Fugue<T> other) → Fugue<T>

Cross-replica merge. Must be commutative, associative, idempotent.

override

merge(Fugue<T> other) → void

Merge another replica's state: union blocks by start dot (the longer run subsumes the shorter — a block only ever grows for its author), with a tombstone OR-merge.

noSuchMethod(Invocation invocation) → dynamic

Invoked when a nonexistent method or property is accessed.

inherited

positionAt(int index) → Dot

The stable Dot of the live element at visible index.

prune(Set<Dot> stable) → Fugue<T>

Drop blocks that are fully tombstoned, causally stable (every element dot observed everywhere), and have no surviving descendant block.

toString() → String

A string representation of this object.

inherited

valueAt(Dot dot) → T?

The value of element dot (live or tombstoned), or null if absent.

Operators

operator ==(Object other) → bool

Structural (value) equality over the whole Δ-state: same blocks keyed by start dot, each with equal placement (parent, side), run values, and tombstone set. Two replicas that have converged compare equal, so join is a value-idempotent semilattice op and Mutator.hasPendingDelta / CrdtMap<K, Fugue> behave consistently with the HLC-based types (which all define value equality). Block insertion order is irrelevant.

override

Static Methods

decode<T>(Object json, T decodeValue(Object?)) → Fugue<T>

Decode a structure produced by encode. decodeValue is the inverse of the encoder passed to encode.

fromRawBlocks<T>(Iterable<(Dot, Dot, Side, List<T>, List<int>)> blocks) → Fugue<T>

Rebuild from rawBlocks-shaped data (codec use).