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.
Subclasses that implement path compression should override findAndCompress. The default implementation simply delegates to getDisjointSet and returns this unchanged, so non-compressing subclasses need not override it. The connect method in this class calls findAndCompress for both arguments, so compression is applied automatically during every merge in subclasses that override it.
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.
Returns the root of the component containing key, together with a (potentially restructured) copy of this disjoint set.
Returns the root of the component containing key, together with a (potentially restructured) copy of this disjoint set.
Making compression explicit here (rather than hiding it inside getDisjointSet) keeps the design honest: a DisjointSet that does not compress still satisfies the trait, and one that does compress makes that fact visible in its API.
Value parameters
key
the element whose root is sought.
Attributes
Returns
a pair (root, updated) where root is the representative of key's component and updated is the (possibly compressed) instance.
Merges the components containing v1 and v2. Short-circuits (returning this) if v1 == v2. Delegates to findAndCompress for both arguments so that subclasses which override it get compression applied during every merge automatically. The asInstanceOf here is safe: this is always a This.
Merges the components containing v1 and v2. Short-circuits (returning this) if v1 == v2. Delegates to findAndCompress for both arguments so that subclasses which override it get compression applied during every merge automatically. 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.