Managing a Sorted STL List (C++)

OPTION A (Basic): A Sorted Card List

Understand the Problem

An stl list application

In the lectures we instantiated an stl list of floats and, above it, built some insert() and remove() methods on the client side that managed the list in increasing sorted order. In this assignment we will do the same for Card objects, using a natural ordering and a random Card generator that will be provided at the end of this document.

You will provide global scope insert(), remove() and removeAll() like in the lessons. They take an stl list of Cards (first parameter) and a Card (second parameter). This is very much like the iTunes example that follows the float example, so you'll want to study that.

Part 1: STL list Spec

There are very few changes you'll need to make to the overall design of what you saw:

bool removeAll(CardList &myList, Card &x) - Notice that this method returns a bool which should be true if x was in the list, and false if it was not.

For Cards, there is no < operator. Use compareTo() in your insert() and/or remove() methods, as needed.

Nothing should be changed in any of the classes or methods brought in from the earlier assignments. Everything you do should be added as client scope code.

Client Notes for Part 1

Instantiate about five to ten cards randomly, but produce duplicates of every card in the list: every card you generate goes into your list twice. Display the list immediately after you build it. (Note, you might have four, not two, of some cards because of generateRandomCard(), and that's fine. (Maybe even six or eight or ... .)

Display the list.

Next, pick up to half of the cards you inserted for removal, but do it as follows. If you instantiated five cards initially and put them into the list twice, then your list has 10 cards. Pick, say, two (or three or all five) distinct cards from your initial five and remove() all traces of each of those two cards. I don't want you to use removeAll() for this step. Instead use remove(), which only removes one instance of a card. So you'll have to use remove() on the same card repeatedly. I.e., if 3 of diamonds is a card, remove all copies of 3 of Diamonds, not just the first. Don't rely on any knowledge you might have about how many copies of the 3 of diamonds are in the list, but use an intelligent loop to keep remove()-ing it until the return value of remove() tells you the loop is done.

Display the list and confirm that it looks right after the removal.

Finally, test removeAll()'s return value somehow after the above test.

Submit an entire source and run.

OPTION B-1 (Intermediate)

Encapsulate the global insert(), remove(), removeAll() machinery into a CardList class.

OPTION B-2 (Intermediate)

Expand the compareTo() so that there are three choices for a single order ranking. One I have supplied in the additional Card class members/methods below: card values are dominant over card suits, yet both are integrated into a single compareTo(). A second new ordering will be based purely on Card values (and ignore Card suits). A third, and new, ordering will be based on Card suits (and ignores Card values). With this idea, we could have three different compareTo()results, depending on which order criterion is desired. To make this work, you'll need give the client a setSortType() method. And to do this, you need the full multi-key machinery from the modules. Derive the new class from Card and call it CardWMultiOrders.

Resources for All Options

Here are the additional Card class members and a new global scope random Card generator that you will need. Add this to the existing Card class (mine or yours) from Assignment #1 and test it out with the provided main() to be sure it works. Then you can use this as a basis for this week's assignment.

// required includes #include  #include  #include  #include  using namespace std; class Card { // to existing members, add: public: // if not already symbolized, use consts static const int NUM_CARD_VALS = 13; static const int NUM_CARD_SUITS = 4; public: // comparison members and methods const static char valueRanks[NUM_CARD_VALS]; const static Suit suitRanks[NUM_CARD_SUITS]; int compareTo(Card &other); static int getSuitRank(Suit st); static int getValueRank(char val); } // global scope method prototypes typedef list CardList; void showList(CardList &myList); void insert(CardList &myList, Card &x); bool remove(CardList &myList, Card &x); bool removeAll(CardList &myList, Card &x); // for easy comparisons int operator==(Card first, Card other) { return first.compareTo(other) == 0; } // for client Card generation Card generateRandomCard(); char Card::DEFAULT_VAL = 'A'; Card::Suit Card::DEFAULT_SUIT = Card::spades; // for comparisons -- ordering values and ranks const char Card::valueRanks[NUM_CARD_VALS] // const forces correct # initializers = { '2', '3', '4', '5', '6', '7', '8', '9', 'T', 'J', 'Q', 'K', 'A'}; const Card::Suit Card::suitRanks[NUM_CARD_SUITS] = {Card::clubs, Card::diamonds, Card::hearts, Card::spades}; // main to test comparison mechanism and random card generation int main() { int k; Card card1, card2; srand(time(NULL)); // or not, if you want repetition cout << "should all be 0: "; card1.set('A', Card::spades); card2.set('A', Card::spades); cout << card1.compareTo( card2 ) << endl; card1.set('4', Card::hearts); card2.set('4', Card::hearts); cout << card1.compareTo( card2 ) << endl; card1.set('T', Card::clubs); card2.set('T', Card::clubs); cout << card1.compareTo( card2 ) << endl; cout << "should all be < 0 : "; card1.set('A', Card::clubs); card2.set('A', Card::spades); cout << card1.compareTo( card2 ) << endl;; card1.set('4', Card::hearts); card2.set('5', Card::hearts); cout << card1.compareTo( card2 ) << endl; card1.set('9', Card::hearts); card2.set('T', Card::clubs); cout << card1.compareTo( card2 ) << endl; cout << "should all be > 0 : "; card1.set('A', Card::clubs); card2.set('K', Card::clubs); cout << card1.compareTo( card2 ) << endl; card1.set('6', Card::hearts); card2.set('5', Card::spades); cout << card1.compareTo( card2 ) << endl; card1.set('K', Card::diamonds); card2.set('K', Card::clubs); cout << card1.compareTo( card2 ) << endl; cout << " Some random cards: "; for ( k = 0; k < 50; k++ ) { cout << generateRandomCard().toString() << " "; } cout << endl << endl; return 0; } // new global scope method ------------------------------------------- Card generateRandomCard() { Card::Suit suit; char val; suit = (Card::Suit) ( rand() % Card::NUM_CARD_SUITS ); val = Card::valueRanks[ rand() % Card::NUM_CARD_VALS ]; return Card(val, suit); } // Card comparison method definitions ------------------------------------------- int Card::compareTo(Card &other) { if (this->value == other.value) return ( getSuitRank(this->suit) - getSuitRank(other.suit) ); // else return getValueRank(this->value) - getValueRank(other.value) ; } int Card::getSuitRank(Suit st) { int k; for (k = 0; k < NUM_CARD_SUITS; k++) if (suitRanks[k] == st) return k; // should not happen return 0; } int Card::getValueRank(char val) { int k; for (k = 0; k < NUM_CARD_VALS; k++) if (valueRanks[k] == val) return k; // should not happen return 0; } /* ---------------------- run Card compareTo() test ------------------ should all be 0: 0 0 0 should all be < 0 : -3 -1 -1 should all be > 0 : 1 1 1 Some random cards: K of Diamonds 6 of Diamonds Q of Hearts 5 of Clubs A of Clubs 9 of Spades 5 of Spades J of Clubs K of Clubs Q of Spades T of Clubs K of Spades 2 of Clubs Q of Clubs 7 of Spades 3 of Clubs T of Hearts K of Spades 5 of Diamo nds A of Diamonds 4 of Spades 9 of Spades 3 of Clubs A of Clubs 9 of Diamo nds 6 of Diamonds 5 of Clubs 9 of Spades A of Clubs Q of Diamonds 2 of Spa des 7 of Diamonds K of Hearts 8 of Spades 3 of Diamonds 8 of Spades 6 of S pades 7 of Hearts 6 of Clubs 6 of Diamonds Q of Diamonds A of Diamonds Q o f Clubs 2 of Hearts 6 of Diamonds 9 of Diamonds 5 of Clubs 6 of Spades 7 o f Diamonds Q of Clubs Press any key to continue . . . --------------------------------- */ 

That's it.