Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Implementation

Program gif 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.

   program28398
Program: PartitionAsForest and PartitionTree fields.

The PartitionTree class extends the AbstractSet class defined in Program gif and it implements the Tree interface defined in Program gif. 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 gif and it implements the Partition interface defined in Program gif. The PartitionAsForest class contains a single field, array, which is an array PartitionTrees. The tex2html_wrap_inline57340 element of the array always refers to the tree node that contains element i of the universe.


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.