| |
Write a MergeSort class implementing a mergesort on a given
list of objects of any kind. The objects are constructed from data
given in a file. The constructor of this class should have two
arguments. The first is a pointer to an object of a class that
is prototyped as follows:
class valueA : public valueFunc {
public:
long long value (void *object);
};
where class valueFunc is prototyped in funcs.h. An object of the valueA
class is used to determine the order of objects in the input list
via its value method. The input to value is a
pointer to a list object and the output is its value.
The second constructor argument is a pointer to an object of a class
prototyped as follows:
class createT : public createFunc {
public:
void *create(fstream &fin);
};
where class createFunc is prototyped in funcs.h. An object of class createT
is used to create objects from data contained in a file. For
example, for the simple class:
class A {
long long number;
public:
A (long long number) { this->number = number; }
long long valueOf() { return number; }
};
assuming the data file contains a list of integers that are to be used as
arguments for A constructors, the needed functions are:
long long valueA::value (void *object) { return ((A*)object)->valueOf(); }
void *createT::createObject(fstream &fin) {
long long number;
fin >> number;
return (void*)new A(number);
}
The creation of a MergeSort object for a list of objects of class
A would proceed as follows:
MergeSort *ms = new MergeSort(value, createObject);
You will demonstrate the use of the MergeSort class on a list
of ints. That is, write a program to sort a file of integers using
your MergeSort class.
Examples of input files are
merge.3.dat (7 numbers),
merge.10.dat (1024 numbers), and
merge.16.dat (65536 numbers). This
program will contain the value and object creation functions as
well as the declaration of a MergeSort object for sorting the
integers, the invocation of a method which reads the data, and the
invocation of a sort method. Call is mergesort.cc.
Implement the MergeSort class in a file called
mrgsrt.cc. The methods and data of this class are given by
the following include file, called mrgsrt.h:
#ifndef _MERGESORT
#define _MERGESORT
#include <fstream>
#include "mcell.h"
#include "funcs.h"
using namespace std;
class MergeSort {
// Private Data
valueFunc *value; // Value function
createFunc *create; // Object creation function
Cell *data; // Pointer to unsorted/sorted structure
bool sorted; // true iff list is sorted
// Private methods
Cell *installData(fstream&, int); // Creates input list from file data
Cell *merge (Cell*, Cell*); // Merges two increasing lists
Cell *mergeSort(Cell*); // Sorts list pointed to by Cell object
void showTree(Cell*); // Display the input list
public:
MergeSort (valueFunc*, createFunc*);
void sort(); // Sort the input list using method mergeSort
int readData(char*); // Read data from file and build list using installData
void showOutput(); // Display sorted list
void showInput(); // Display unsorted list
};
#endif
Private data consists of pointers to the value and object creation
objects that are passed through the constructor, the data
pointer serving the dual role of pointing to the unsorted list before
a sort and the sorted list after the sort, and the sorted
variable of type bool which has value true if and
only if the list is sorted. There are private methods which operate
on Cell objects (described below). The Cell objects
are internal "carriers" of objects and are not available to users.
Private methods include installData which builds all list
objects from the data file and returns a pointer to the resulting list
structure (which is more complex than a singly linked list - see
below), merge which returns a singly linked list that is the
merge of two input, ordered, singly linked lists, mergeSort
which uses merge to sort a given input list, and
showTree which is intended to display an unsorted input list.
Methods available to a user, besides the constructor, are
readData which creates an internal structure from a given
data file name, pointed to by data, and holds a list of
objects to be sorted (uses the private installData method and
unsets sorted), sort which replaces the unsorted
list pointed to by data with a sorted list (sets
sorted and uses the private method mergeSort), and
showInput and showOutput which display the unsorted
and sorted lists, respectively.
The Cell class is protoyped as follows in
mcell.h:
#ifndef _CELL
#define _CELL
#include <iostream>
using namespace std;
class Cell {
friend class MergeSort;
void *object; // Pointer to an object, if terminal
Cell *left, *right; // Pointers to left and right sublists
public:
Cell (Cell*, Cell*); // Called when building intermediate nodes
Cell (void*); // Called when building terminal nodes
};
#endif
The reason for the left and right pointers is to
separate the left half of a list from its right half. The pointers
allow the separation to take place in one step: the merge proceeds on
the two sublists pointed to by these pointers. Details are given in
the next section.
|
