Concrete disjoint-set implementation using "Quick Union" (lazy union), with the ASP (Arbitrary Substitution Principle) violation noted in the code.
Each object maps to Option[V]: None means the object is a root; Some(parent) means the object's parent in the component tree.
This is O(n) in the worst case due to potentially unbalanced trees. Prefer ConnectivityLazy for production use.
unit and put return ConnectivityASP[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
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 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.
Attributes
- Inherited from:
- AbstractDisjointSet
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