Abstract base class for disjoint-set implementations that relies on an immutable Map to associate objects with their parent disjoint set.
All operations are purely functional: every "mutation" returns a new instance constructed via unit, leaving the original unchanged. This makes instances persistent data structures — an old reference remains valid after any connect or put.
Each object V in map is associated with a value of type W. The function f extracts an optional parent V from a W value. If f(w) == None the object is the root of its own component.
The F-bound This <: AbstractDisjointSet[V, W, This] ensures that connect, put, and remove all return the concrete subtype without casting at the call site. The only remaining asInstanceOf casts are in the short-circuit cases where this is returned unchanged — these are safe but unavoidable, since the compiler cannot prove this: This without them.
This abstract class does not perform path compression. For path compression, you must extend the subclass AbstractDisjointSetWithCompression.
Type parameters
This
the concrete subtype (F-bounded polymorphism).
V
the underlying object type.
W
the map value type (may equal Option[V] or compound it with extra data).
Value parameters
f
extracts the optional parent from a W value.
map
the component map: each V maps to its associated W.
Merges the components containing v1 and v2. Short-circuits (returning this) if they are already in the same component or if v1 == v2. The asInstanceOf here is safe: this is always a This.
Merges the components containing v1 and v2. Short-circuits (returning this) if they are already in the same component or if v1 == v2. The asInstanceOf here is safe: this is always a This.
Returns an updated map with key -> value. Note: Map.updated is a purely functional operation on an immutable Map — it returns a new Map and does not mutate the receiver.
Returns an updated map with key -> value. Note: Map.updated is a purely functional operation on an immutable Map — it returns a new Map and does not mutate the receiver.