Parameterized Partitions (Partition)

Definition

An instance P of the data type Partition<E> consists of a finite set of items (partition_item) and a partition of this set into blocks. Each item has an associated information of type E.

Creation

Partition<E>	P;	creates an instance P of type Partition<E> and initializes it to the empty partition.

Operations

partition_item	P.make_block(E x)	returns a new partition_item it, adds the block it to partition P, and associates x with it.
partition_item	P.find(partition_item p)	returns a canonical item of the block that contains item p, i.e., iff P.same_block(p,q) then P.find(p) and P.find(q) return the same item. Precondition: p is an item in P.
int	P.size(partition_item p)	returns the size of the block containing p.
bool	P.same_block(partition_item p, partition_item q)
		returns true if p and q belong to the same block of partition P. Precondition: p and q are items in P.
void	P.union_blocks(partition_item p, partition_item q)
		unites the blocks of partition P containing items p and q. Precondition: p and q are items in P.
void	P.split(list<partition_item> L)
		turns all items in L to singleton blocks. Precondition: L is a union of blocks
E	P.inf(partition_item it)	returns the information associated with it.
void	P.change_inf(partition_item it, E x)
		changes the information associates with it to x.