Assignment #6 Playing with Inheritance: Pairing Hands

Due

Thursday, March 11th at NOON

Overview

For this project you will implement the stable marriage problem to pair hands. Every left hand needs a right hand pair. You will write a high up "Hand" class that contains the functionality of all Hands. You will also have 2 derived classes, "LeftHand" and "RightHand" that contain the functionality that each needs to extend from the base class. In a main program, you will read in from an input file a test case that says the number of Hands to create, and specifies each Hand's (both Left and Right) preferences for the other kind of Hand. Then you will implement the stable marriage algorithm to pair your Hands so they live happily ever after. You will also create a Makefile to compile all your C++ files.

The stable marriage problem is a problem of finding a stable matching between 2 matched sets. Given n left hands and n right hands, where each hand has ranked all members of the opposite kind of hand with a unique number between 1 and n in order of preference, match the left and right hands such that there are no 2 hands of opposite kinds who would both rather have each other than their current partners. If there are no such hands, the marriages are "stable".

Here is the algorithm for creating a stable pairing:

 

function stableMatching {
    Initialize all l in L and r in R to free
    while exists free left l who still has a right r to propose to {
       r = l's highest ranked such right
       if r is free
         (l, r) become engaged
       else some pair (l', r) already exists
         if r prefers l to l'
           (l, r) become engaged
           l' becomes free
         else
           (l', r) remain engaged
    }
}

Instructions

1. Prompt the user for a filename which will be your input file. Your input file format is thus: The first line is the number of cases (number of times you will do the stable marriage problem). Each case follows with a blank line before the case. For each case, the first line indicates the number of hands (left and right). Say there are n. The following 2n lines will have the preferences for the n left hands, then the n right hands. The preferences for each left hand will be for the n right hands, with the highest preferred first. Same for right hands. So the following:
   2
   1 2
   1 2
   1 2
   1 2
   is translated as 2 hands, the first left hand prefers right hand 1, then 2. The second left hand has the same preferences. The first right hand prefers left hand 1, then 2. The second right has the same preferences.
2. For output, output the stable hand-marriage solution (n left-right pairs), such as this . You can just output to the screen using cout . The output should be in ascending order of the left hands (id the lefties in the order in which the input is provided and output in the same order). Print nothing else but the ids involved in each pairing, and list each pairing on its own line, then separate cases with a blank line.
3. You need to define the Hand class (in Hand.h and Hand.cpp) that is the base class for the LeftHand and RightHand classes. The Hand class contains the functionality common to both Left and Right Hand classes. You will also define the LeftHand and RightHand classes (each with a .h and .cpp file) that derive from the Hand class and are more specialized. There should be some difference between the Left and Right Hands! (don't make them empty classes).
4. You will write a file testSMPHand.cpp that implements the stable marriage algorithm several times over based on the input file - for each case, pairing Left and Right hands based on their preference. Generate output as specified above (no need to write explicitly to a file in your main function).
5. You will need a Makefile that compiles your Hand class, your LeftHand class, your RightHand class, and testSMPHand.cpp, and creates an executable "testHand" file to run your program. You can pattern your Makefile after the example one used in class that is available in the cs105/code directory. Make sure the lines after the rule: line starts with a tab! (Not spaces)
6. Compile and run your code:

     computer% make clean
     computer% make
     computer% ./testHand
   

I recommend using the CS department linux machines. Make sure to test your code on the CS department machines before turning the assignment in!
7. When you're happy with your code (and there are no warnings!), use the turnin program to submit your files: Hand.h, Hand.cpp, LeftHand.h, LeftHand.cpp, RightHand.h, RightHand.cpp, testSMPHand.cpp, and Makefile. MAKE SURE YOUR NAME IS ON THE TOP OF EACH FILE (except the Makefile)! Use jbsartor as the grader and assign6 ( assign6Mulligan if it is late) as the assignment name.

     computer% turnin --submit jbsartor assign6 Hand.h Hand.cpp LeftHand.h LeftHand.cpp RightHand.h RightHand.cpp testSMPHand.cpp Makefile
   

   You can turn in your files as many times as you want - I will only take the last one submitted.