| |
Develop a class Partition supporting union-find in set
partitions. The class is prototyped in
partition.h as follows:
#ifndef _PARTITION
#define _PARTITION
#include <iostream>
#include "hashtable.h"
#include "funcs.h"
using namespace std;
// Wrapper for user-supplied compare function
class compPart : public compareFunc {
compareFunc *cmpfn;
public:
compPart (compareFunc*);
int compare(void*, void*);
};
// Wrapper for user-supplied hash function
class hashPart : public hashFunc {
hashFunc *hash;
public:
hashPart (hashFunc*);
int hashfn (void*);
};
// Wrapper for user-supplied display function
class dispPart : public displayFunc {
displayFunc *dispfn;
public:
dispPart (displayFunc*);
void display (void*);
};
// Default compare function
class compPartDef : public compareFunc {
valueFunc *val;
public:
compPartDef (valueFunc*);
int compare (void*, void*);
};
// Default hash function
class hashPartDef : public hashFunc {
valueFunc *val;
int number;
public:
hashPartDef (valueFunc*, int);
int hashfn (void*);
};
// The Partition class prototype
class Partition {
friend ostream &operator<<(ostream&, Partition*);
HashTable *hash;
Node *identify (Node*);
public:
Partition (int, compareFunc*, hashFunc*, displayFunc*);
Partition (int, compareFunc*, hashFunc*);
Partition (int, valueFunc*);
Partition (valueFunc*);
void add (void*);
void setunion (void*, void*);
bool redundant (void*, void*);
};
ostream &operator<<(ostream&, Partition*);
#endif
As can be seen from the above, the Partition class depends on
the HashTable class that was developed in the previous
homework. As was the case for the HashTable class, the
Partition class also depends on compareFunc,
valueFunc, hashFunc, and displayFunc and
the discussion in the previous homework regarding these classes
applies here. An implementation of these is in partition.cc which is
partially listed here:
#include <stdlib.h>
#include "partition.h"
compPartDef::compPartDef(valueFunc *val) { this->val = val; }
int compPartDef::compare(void *obj1, void *obj2) {
long long v1 = val->value(((Node*)obj1)->getObject());
long long v2 = val->value(((Node*)obj2)->getObject());
return (v1 == v2) ? 1 : 0;
}
compPart::compPart(compareFunc *cmpfn) { this->cmpfn = cmpfn; }
int compPart::compare(void *obj1, void *obj2) {
return cmpfn->compare(((Node*)obj1)->getObject(),
((Node*)obj2)->getObject());
}
hashPart::hashPart (hashFunc *hash) { this->hash = hash; }
int hashPart::hashfn (void *object) {
return hash->hashfn(((Node*)object)->getObject());
}
hashPartDef::hashPartDef (valueFunc *val, int number) {
this->val = val;
this->number = number;
}
int hashPartDef::hashfn (void *object) {
long long n = (long long)abs(val->value(((Node*)object)->getObject()));
return (int)(abs(n*357) % number);
}
dispPart::dispPart (displayFunc *dispfn) { this->dispfn = dispfn; }
void dispPart::display (void *object) {
dispfn->display(((Node*)object)->getObject());
}
The inverted tree is implemented using objects of the Node
class. This class is prototyped as follows and in file
node.h:
// Node objects are intended for use only by the Partition class to
// "carry" any kind of set objects. Objects of the Node class contain
// the "parent" and "size" fields needed to implement an inverted tree
// and contain the "identity" method which not only finds an object in
// the partition set but also compresses the path to the representative
// partition set object when performing the find.
//
// Any object that gets placed into a partition needs to have meaningful
// display and value functions. Thus, the Node class is a subclass of
// the Object class.
#ifndef _NODE
#define _NODE
#include <iostream>
using namespace std;
class Node {
friend class Partition;
friend ostream &operator<<(ostream &, Node*);
Node *parent; // Link on path to representing city
int size; // If this object is a representative, size of its subset
void *object; // Object carried by the node
Node *next; // Used by the List class, not by Partition
public:
Node(void*, Node*); // Not used by Partition
Node (void*); // Constructor takes a set object as argument
void *getObject(); // Return carried object
Node *identify(); // Return representative Node object
};
#endif
An implementation of the Node class is in file
node.cc and listed here:
#include "node.h"
Node::Node(void *obj, Node *lst) {
parent = this;
size = -1; // No significance
object = obj;
next = lst;
}
Node::Node (void *obj) {
parent = this;
size = 1; // Only for inverted trees
object = obj;
next = NULL;
}
void *Node::getObject() { return object; }
Node *Node::identify() {
if (this == parent) return this;
return parent = parent->identify();
}
The Node class was previously used to construct List
objects.
The following is a sample use of the Partition class as
prototyped above. It uses objects of type A from the
previous homework. The class A is defined in files
a.h and a.cc.
#include <iostream>
#include "partition.h"
using namespace std;
// Consider a collection of objects. Define groups. Place every object
// into exactly one group (no more, no less). The assignment is called
// a partition. The Partition class facilitates maintenance of a partition.
// It provides the following services:
// 1. redundant: A test whether two given objects are in the same group
// 2. setunion: Joining all objects of two groups into one group
// Any type of object can be placed into a "Partition". All that is needed
// is to define a "value" function which is used to hash, compare, and
// display in the HashTable, and List classes.
int main () {
Partition *part = new Partition(new valueA());
part->add(new A(1));
part->add(new A(2));
part->add(new A(3));
part->add(new A(4));
cout << part;
cout << "==Redundancies===============\n";
for (int i=1 ; i <= 4 ; i++) {
cout << "[" << i << "] ";
for (int j=1 ; j <= 4 ; j++) {
cout << j << ":"
<< part->redundant(new A(i), new A(j)) << " ";
}
cout << " ";
}
cout << "\n\n==Set Union 1 and 3==========\n";
part->setunion(new A(1), new A(3));
cout << "==Redundancies===============\n";
for (int i=1 ; i <= 4 ; i++) {
cout << "[" << i << "] ";
for (int j=1 ; j <= 4 ; j++) {
cout << j << ":"
<< part->redundant(new A(i), new A(j)) << " ";
}
cout << " ";
}
cout << "\n\n==Set Union 2 and 4==========\n";
part->setunion(new A(2), new A(4));
cout << "==Redundancies===============\n";
for (int i=1 ; i <= 4 ; i++) {
cout << "[" << i << "] ";
for (int j=1 ; j <= 4 ; j++) {
cout << j << ":"
<< part->redundant(new A(i), new A(j)) << " ";
}
cout << " ";
}
cout << "\n\n==Set Union 2 and 3==========\n";
part->setunion(new A(2), new A(3));
cout << "==Redundancies===============\n";
for (int i=1 ; i <= 4 ; i++) {
cout << "[" << i << "] ";
for (int j=1 ; j <= 4 ; j++) {
cout << j << ":"
<< part->redundant(new A(i), new A(j)) << " ";
}
cout << " ";
}
cout << "\n=============================\n";
}
For convenience, the files you will link to are as follows:
list.cc,
list.h,
node.cc,
node.h,
funcs.h,
a.h,
a.cc,
hashtable.h,
partition.h, and
hw6.cc.
Your assignment is to supply hashtable.cc from homework 5 and
partition.cc. The following
Makefile may be used to compile and
link all the files.
|
