Concrete disjoint-set implementation using "Weighted Quick Union with Path Compression."
Extends ConnectivityLazy with path compression: during every findAndCompress traversal to the root, all nodes along the path are rewired to point directly to the root. This flattens the tree lazily, giving amortized near-O(1) performance (formally O(α(n)), where α is the inverse Ackermann function).
Path compression is implemented purely functionally: the rewired nodes are accumulated into a new immutable Map which is returned alongside the root as a fresh ConnectivityOptimized instance. No mutation occurs.
Note that after path compression, rank (tracked via ParentSize.size) becomes an upper bound on depth rather than the true depth — this is the standard behaviour of union-by-rank with path compression, and is why the field is called size (a weaker proxy) rather than depth.
unit and put return ConnectivityOptimized[V] directly, with no overrides required, courtesy of the F-bounded type parameter.
Type parameters
- V
-
the underlying object type.
Value parameters
- map
-
the component map.
Attributes
- Companion
- object
- Graph
-
- Supertypes
-
trait Serializabletrait Producttrait Equalstrait Connectivity[V]trait Connected[V]class Objecttrait Matchableclass AnyShow all
Members list
Value members
Concrete methods
Finds the root of key's component and simultaneously compresses the path, rewiring every node visited to point directly to the root.
Finds the root of key's component and simultaneously compresses the path, rewiring every node visited to point directly to the root.
The traversal collects the path from key to the root into a List[V], then folds over it to produce an updated Map in which every node on the path (except the root itself) has its parent set directly to the root. A fresh ConnectivityOptimized wrapping the updated map is returned alongside the root — no mutation occurs at any point.
Value parameters
- key
-
the element whose root is sought.
Attributes
- Returns
-
a pair
(root, compressed)whererootis the representative ofkey's component andcompressedis the path-compressed instance.
Adds the specified key to the disjoint set data structure and initializes it as a new singleton set if it does not already exist.
Adds the specified key to the disjoint set data structure and initializes it as a new singleton set if it does not already exist.
Value parameters
- key
-
the element to be added to the disjoint set.
Attributes
- Returns
-
the updated disjoint set containing the newly added key.
Constructs a new instance of the concrete subtype from the given map. Subclasses must implement this to return This.
Constructs a new instance of the concrete subtype from the given map. Subclasses must implement this to return This.
Attributes
Inherited methods
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.
Attributes
- Definition Classes
- Inherited from:
- AbstractDisjointSetWithCompression
Returns the depth of v in the component tree (root has depth 1).
Returns the depth of v in the component tree (root has depth 1).
Attributes
- Inherited from:
- AbstractDisjointSet
Returns the W value associated with key, if present.
Returns the root of the component containing key.
True if v1 and v2 belong to the same disjoint set.
True if v is the root of its own component (i.e. has no parent).
True if v is the root of its own component (i.e. has no parent).
Attributes
- Inherited from:
- AbstractDisjointSet
Returns an iterator over all (V, W) entries.
The maximum path length to root across all objects.
The mean path length to root across all objects.
Returns the optional parent of v.
An iterator over the names of all the elements of this product.
An iterator over the names of all the elements of this product.
Attributes
- Inherited from:
- Product
An iterator over all the elements of this product.
An iterator over all the elements of this product.
Attributes
- Returns
-
in the default implementation, an
Iterator[Any] - Inherited from:
- Product
Removes key from this disjoint set.
Returns the number of disjoint sets (roots).
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.
Attributes
- Inherited from:
- AbstractDisjointSet