Choose a fixed positive capacity and represent the abstract state by a finite partial function . Its domain of a partial function has at most members; each belongs to and is a fixed point:The blocks of a set partition are the nonempty fibres of
rep, and their shared values are their disjoint-set representatives. Initially , so . Representatives need not be the minimum members of their blocks.trait DisjointSets {
val capacity: Int
// State: rep is a finite idempotent map, |dom rep| <= capacity.
// Initially: rep is empty; capacity is fixed and positive.
// Pre: x is absent and |dom rep| < capacity.
// Post: add x -> x; leave every old mapping unchanged.
def makeSet(x: Int): Unit
// Pre: x belongs to dom rep.
// Post: state unchanged; return rep(x).
def find(x: Int): Int
// Pre: x and y belong to dom rep.
// Post: merge their blocks, retaining old rep(x).
def union(x: Int, y: Int): Unit
}Precisely,
makeSet(x) extends the domain of a partial function by with . For union(x,y), snapshot and , keep unchanged, and setThis merges the two blocks and keeps the representative of the first argument's block. If , it is an identity operation. This deterministic design choice satisfies disjoint set union without imposing minimum-element representatives. The capacity bound is explicit in the abstract data type so that the bounded implementation does not silently strengthen makeSet's precondition. Articles by others on the same topic
There are currently no matching articles.