Implementation

Program  declares two classes--PartitionTree and PartitionAsForest. The former is used to represent the individual elements or parts of a partition and the latter encapsulates all of the parts that make up a given partition.

  
Program: PartitionTree and PartitionAsForest Class Definitions

The PartitionTree class is derived from the abstract base classes Set and Tree. Since we are representing the parts of a partition using trees, it makes sense that we derive them from the Tree class. On the other hand, since a partition is a set of sets, we must also derive the parts of a partition from the Set class. In particular, this is necessary because of the way that the Find and Join member functions are defined.

The PartitionTree class has three member variables--parent, item and rank. Each instance of this class represents one node of a tree. The parent member variable points to the parent of a given node and the item member variable 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. Since a partition is a set of sets, it is a container. And since it supports a find operation, the class PartitionAsForest is derived from the abstract base class SearchableContainer. The PartitionAsForest class contains a single member variable, array, which is an array of pointers to PartitionTree instances. The element of the array always points to the tree node that contains element i of the universe.

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