|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
Program 
declares two classes--PartitionAsForest
and the inner class PartitionTree.
The latter is used to represent the individual elements or parts of a partition
and the former encapsulates all of the parts that make up a given partition.
Program: PartitionAsForest and PartitionTree fields.
The PartitionTree class extends the AbstractSet
class defined in Program
and it implements the Tree interface defined in Program .
Since we are representing the parts of a partition using trees,
it makes sense that they implement the Tree interface.
On the other hand, since a partition is a set of sets,
we must derive the parts of a partition from the AbstractSet class.
The PartitionTree class has four fields--partition, item, parent, and rank. Each instance of this class represents one node of a tree. The partition field refers to the PartitionAsForest instance that contains this tree. The parent field refers to the parent of a given node and the item field records the element of the universal set that the given node represents. The remaining variable, rank, is optional. While it is not required in order to provide the basic functionality, as shown below, the rank variable can be used in the implementation of the Join operation to improve the performance of subsequent Find operations.
The PartitionAsForest class represents a complete partition.
The PartitionAsForest class extends the AbstractSet
class defined in Program
and it implements the Partition interface
defined in Program .
The PartitionAsForest class contains
a single field, array,
which is an array PartitionTrees.
The 
element of the array always refers to the tree node
that contains element i of the universe.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.