#ifdef __BORLANDC__
#pragma argsused
#endif
/****************************************************************************/
/* Nathan Balon */
/* CIS 350 Data Structures and Algorithms */
/* University of Michigan Dearborn */
/* Programming assignment #1 */
/* BCS ranking program */
/* */
/* created on 1/15/2005 */
/****************************************************************************/
/***************************************************************************
*
* The program is used to calculate a median ranking. One example of the use
* the program is it could rank the top six teams in colllege football from
* the input given the program. Teams are represented by the characters in the
* set {A, B, C, D, E, F}. Each letter would represent a team. Based on the
* input given to the program a median rank would be determined the order these
* teams.
*
* The program will first read in the number of Rankings the program will use
* to calculate the median ranking. Next, the program will read in all of the
* rankings. The program will continue to calculate the median ranking for
* each set of rankings it is given until it reads in a 0 for the number of
* rankings, then the program exits.
*
* A ranking will consists of six characters, from A-F with no
* characters repeated. An example of valid input for the program is ABDCFE.
* The program will terminate when a line that start with 0 is encounterd.
*
* sample of valid input for the program:
* 4
* ABCDEF
* ABDCFE
* ABDCEF
* CDABFE
* 0
*
* After an input set is read into the program, the program will calculate
* what is the median ranking from the rankings given. If there are more then
* one median ranking with the same values then the one that comes first
* aphabetically will be displayed.
*
* An example of valid output of the program is:
* "ABCDEF is the median ranking with value 4"
*
******************************************************************************/
#include
#include
#include
#include
#include
using namespace std;
/* Global Functions */
int getNumberOfRankings();
vector getInputRankings(int rankingLength);
/* Global Variables */
const int MAX_RANKINGS = 10000; // maximum number of ranking allowed
/*****************************************************************************/
/* Ranking is a data structure used to hold a number of rankings. */
/* Rankings provides methods to compute the median ranking and to */
/* display the median ranking. */
/*****************************************************************************/
class Ranking{
public:
Ranking(vector inputRankings);
void calcRank();
void displayMedianRanking() const;
~Ranking();
private:
int calcCandidateRank(const string permutation) const;
int distanceBetweenStrings(const string string1, const string string2) const;
void createPermutationString();
vector* _inputRankings; // A vector to hold all of the string entered
// by user to have the rank calculated
string _initialPermutation; // the initial permutation string used to
// calculate the median ranking.
string _medianRanking; // the string which is the median rank
int _rankingValue; // the value of the median rank
};
/**************************************************************************/
/* Ranking member functions */
/**************************************************************************/
/**
* Ranking creates a new instance of Ranking.
*
* parameter: A vector of strings containing the rankings
* Precondition: inputRanking is a vector of strings containing the rankings.
* inputRankings must not be an empty vector.
* All strings contained in the vector should be the same length.
* Postcondition: A Ranking object is created. The object will be in a consistant
* state and the permutation string will be created.
*/
Ranking::Ranking(vector inputRankings){
_inputRankings = new vector(inputRankings);
createPermutationString();
_medianRanking = "NA";
_rankingValue = 0;
}
/**
* createPermutationString creates a permutation string to be to calculate the
* the median ranking. The function is used by the constructor create the intial
* permutation.
*
* Precondition: The _inputRanking vector was properly initialized.
* The _inputRanking vector is not empty. All strings
* contained in the _inputRanking vector are the same length.
* Postcondition: A string will e created containing the intial permutation
* to use to calculate the median ranking. If the vector hold
* the rankings is empty the program will terminate since it
* is not able to create the intial permutation.
*/
void Ranking::createPermutationString(){
string sampleString; // a string from the vector used to determine the
// length of the strings in the vector
string permutation; // a string to be used for the starting permutation
// check that _inputRanking is not empty
if(_inputRankings->empty()){
cerr << "The rankings must not be empty";
exit(1);
}
// get a sample string to determine the length of the strings contained in the vector
sampleString = _inputRankings->at(0);
// create the intial permutation
for(int i = 0; i < sampleString.length(); i++){
permutation += 'A' + i;
}
_initialPermutation = permutation;
}
/**
* distanceBetweenStrings compares two strings to determine the distance
* between two rankings.
*
* Parameters: string1 and string2, the strings to compare.
* Return value: an int value for the distance between the two rankings
* Precondtion: two strings of equal length are supplied to the method.
* Postcondition: the distance between the two strings is returned.
*/
int Ranking::distanceBetweenStrings(const string string1, const string string2) const{
int total_distance = 0; // the distance between the rankings
int pos_char1 = 0; // the position the first character to be compared found in string2
int pos_char2 = 0; // the position the second character to be compared found in string2
// if the strings are equal return 0 so no char by char comparison is need.
if(string1 == string2){
return 0;
}
for(int i = 0; i < string1.length() - 1; i++){
for(int j = i; j < string1.length() -1; j ++){
pos_char1 = 0;
pos_char2 = 0;
// locate the characters to be compared in the second string
for(int k = 0; k < string2.length(); k++){
if(string2[k] == string1[i]){
pos_char1 = k;
}else if(string2[k] == string1[j+1]){
pos_char2 = k;
}
}
// if pos_char1 is found after pos_char2 increment the total distance
if(pos_char1 > pos_char2){
total_distance++;
}
}
}
return total_distance;
}
/**
* calcCandiateRank is used to sum the distances between the rankings of an
* object and a string.
*
* parameter: permutation ia a string which is used to determine the
* candiate ranking of the string.
* return value: int the sum of all distance of the candidate rank.
* Precondition: an object is initialized with a vector of strings to have
* the candiate ranking of a string calcuated.
* Postcondition: the candidate rank for a string is returned.
*/
int Ranking::calcCandidateRank(const string permutation) const{
int totalDistance = 0; // the total distance
vector::iterator pos; // iterator for the vector
for(pos = _inputRankings->begin(); pos < _inputRankings->end(); pos++){
totalDistance += distanceBetweenStrings(*pos, permutation);
}
return totalDistance;
}
/**
* calcRank calculates the median rank from the of the vector which were
* supplied when a Ranking object was created.
*
* Precondition: a Ranking object is constructed with a vector of rankings to
* be used to calculate the median ranking.
* Postcondition: the values of median rank and rank value are calculated.
*/
void Ranking::calcRank(){
int candidateRank = 0; // the candidate ranking for a permutation
string permutationValue = _initialPermutation; // the string to create permutations from
// calculate the value of the first permutation
_rankingValue = calcCandidateRank(permutationValue);
_medianRanking = permutationValue;
// calculate the medain rank for all permutations of "ABCDEF"
while (next_permutation(permutationValue.begin(), permutationValue.end())){
candidateRank = calcCandidateRank(permutationValue);
// check if the value of the rank is less than or equal to the previous
// medain value that was found
if(candidateRank <= _rankingValue){
if(candidateRank < _rankingValue){
_rankingValue = candidateRank;
_medianRanking = permutationValue;
} else if(permutationValue < _medianRanking){
_medianRanking = permutationValue;
}
}
}
}
/**
* displayMedianRanking diplays the string which is the median ranking and the
* values of the ranking.
*
* Precondition: The median ranking should already be computed by calling the
* method calcRank on the object.
* Postcondition: The median ranking is sent to standard output.
*/
void Ranking::displayMedianRanking() const{
cout << _medianRanking << " is the median ranking with a value of "
<< _rankingValue << endl;
}
/**
* destructor for a Ranking object, used to allocate memory used by the vector
* _inputRankings.
*
* Precondition: An object of the type ranking must have been created.
* Postcondition: Returns the memory allocated for the vector to hold the rankings.
*/
Ranking::~Ranking(){
delete _inputRankings;
}
/*************************************************************************/
/* Global Functions used by main */
/*************************************************************************/
/**
* getNumberOfRankings gets the number of rankings that will be input in the
* set of rankings from standard input.
*
* return value: The number of rankings in the input set.
* Preconditions: none
* PostCondition: The number of rankings in the set will be returned.
* If the number of rankings exceeds the MAX_RANKINGS the
* program will be terminate since it doesn't support
* calculating the ranking for that large of input.
*/
int getNumberOfRankings(){
int numberOfRankings = 0; // the number of rankings in a set of rankings
cin >> numberOfRankings;
// check that the maximum number of ranking to be calculate is not exceeded
if(numberOfRankings > MAX_RANKINGS){
cerr << "Invalid number of ranking, must be less than " << MAX_RANKINGS;
exit(1);
}
return numberOfRankings;
}
/**
* getInputRankings reads in all of the rankings in the set of input and adds
* the input string to a vector.
*
* parameter: rankingLength the number of lines to be read.
* return value: vector a vector contain all the strings read.
* Precondition: the length of the input is determine the number of strings
* to be read in.
* Postcondition: a vector of strings will be populated with the user ranking.
* If all the strings entered were not the same length the
* program will terminate because the input is invalid.
*/
vector getInputRankings(int rankingLength){
vector userRankings; // used to hold the ranking entered by the user
bool firstTimeInLoop = true; // used to indicate the first time in the loop
int perviousLength = 0; // the pervious length of the string read in
string rank; // a ranking to be added to the vector
// read in a rank and add to the vector contain all the rankings
while(rankingLength--){
cin >> rank;
// check that all strings have the same length
if(firstTimeInLoop){
perviousLength = rank.length();
firstTimeInLoop = false;
} else {
if(perviousLength != rank.length()){
cerr << "All strings must have the same length" << endl;
exit(1);
} else {
perviousLength = rank.length();
}
}
// convert the input string to upper case
for (int i = 0; i < rank.length(); ++i){
rank[i] = toupper(rank[i]);
}
// add the string read in to the input vector
userRankings.push_back(rank);
}
return userRankings;
}
/************************************************************************/
/* main - The main entry point to the ranking program. */
/************************************************************************/
int main( int argc, char * argv[] ){
int inputLength = 0; // the number of rankings used to claculate the median
vector inputRankings; // input rankings
// get the input from stdin untill the end of input is found
while((inputLength = getNumberOfRankings()) > 0){
// get the input set of rankings
inputRankings = getInputRankings(inputLength);
// create an object used to calculate the median ranking
Ranking rank(inputRankings);
// calculate the median ranking
rank.calcRank();
// display the median ranking to the user
rank.displayMedianRanking();
// clear the vector for the next set of input
inputRankings.clear();
}
return 0;
}