The refinable partition data structure is used to store and refine the partitioning of a (dynamic) set of elements.
A partition of a set is a set of disjoint subsets such that . A partition is called a refinement of a partition , if each can be given as a union of some sets in . In such a case the is called finer than , and is called coarser than . The coarsest partition is the singleton set , while the finest partition is the set of singletons of . The refinement relation is a partial order on the set of partitions.
The idea of the data structure is the following. When a set in the partition is wanted to be split into two, this split is denoted by marking the elements of the other part. Multiple sets in the partition can be marked this way, perhaps incrementally. The actual refinement is committed by the split() function which splits all those sets that have both marked and unmarked elements. Such lazy splitting amortizes the cost of splitting.
The refinable partition data structure implemented in Pastel has the following properties:
| Task / Property | Complexity |
|---|---|
| Mark / unmark an element. | |
| Insert / remove an element into / from a set. | |
| Insert / remove an empty set. | |
| Split a set. | amortized |
| Provide the list (and number) of elements in the partition. | |
| Provide the list (and number) of sets in the partition. | |
| Provide the list (and number) of elements in a set. | |
| Provide the list (and number) of marked elements in a set. | |
| Provide the list (and number) of unmarked elements in a set. | |
| Find the set that contains a given element. | |
| Provide the list of those sets which contain marked elements. | |
| Find out whether an element is marked or not. | |
| Space |
Here is the number of elements contained in a set, and is the number of elements in the partition.