Implementation

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 three fields--item, parent, and rank. Each instance of this class represents one node of a 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 © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.