pa01 : Card game using Binary Search Trees

num ready? description assigned due
pa01 true Card game using Binary Search Trees Fri 04/25 09:00AM Fri 05/16 11:59PM

Collaboration policy

Introduction

Goal of this assignment

Instructions

In this lab you will implement a game in two different ways: one that uses the STL set container class and another that uses your custom implementation of a BST (based on the code your wrote for lab02)

Starter code and required files

Refer to lab01 for instructions on how to set up a GitHub repository and pull the starter code for this lab. Obtain the starter code from this repo: https://github.com/ucsb-cs24-w24/STARTER-lab05

Check that you have the following files:

Common files for both implementations of the game

Implemenation 1: implementation of the game using std::set

Implementation 2: implementation of the game using your custom BST

Note: The files main_set.cpp and main.cpp should read in the cards of the two players from input files and put everything together to play the game. The key difference is that main_set.cpp only makes use of the STL std::set container class and the definitions in card.h/cpp to code the game (described later) while main.cpp uses definitions in card.h/cpp and card_list.h/cpp which contain your implementation of a BST (from lab01) modified for the purposes of this assignment. Implement main_set.cpp first!

Create the following files:

The game

Alice and Bob are playing a game a bit like Go Fish, although neither of them is very good at it. The players are dealt two sets of cards which are provided in two separate files as inputs to your program. Although the cards in each player’s hand is unique, duplicates exist in the other player’s hand.

Once you have the sets of cards, the game begins. Alice and Bob take turns playing the game. Alice iterates forward through her hand in increasing order of the card values (see next section on how cards are ordered), checking whether Bob has that card. Once a matching card is found, your program should print the line “Alice picked matching card <card value as a number/character>". The card should then be removed from both players hands.

The process then repeats, except this time, Bob looks through his cards starting with the largest card and working towards the smallest card. This means that while the first card Alice finds should be the first shared card (in order), the first card Bob finds should be the last shared card (in order). The game ends once they do not have any cards in common and you should print out the final hands of both players. Note that players do not draw any new cards during this process.

The ordering of cards is described in the next section.

Card ordering

The ordering of cards is determined first by its suit and then by the value:

  1. The ordering least to greatest is: clubs, diamonds, spades, hearts. Thus a club of any value is less than a diamond of any value.

  2. The ordering within each suit is determined by the value from least to greatest as follows: ace, 2, 3, . . . 10, jack, queen, king.

Based on the above two rules, the ordering of the following cards

h 9, c k, s 3, c a, h j, d 3

from smallest to largest would be

c a, c k, d 3, s 3, h 9, h j

Your approach for the set-based implementation of the game

At the start of the program, you will read in Alice and Bob’s starting hands from two files. The names of these files are provided as command line arguments with Alice’s file in argv[1] and Bob’s in argv[2]. The starter code opens the files for you as ifstream objects, which you can treat much like cin. You should read Alice and Bob’s cards into two binary search trees. In your first implementation of the game in (main_set.cpp), you should use std::set to store each players hand. Define a class and associated operators needed to represent a single card in card.h/cpp. When you run make, you should get an executable game_set that you can test with the text files available to you.

After you have a correct implementation that is based on std::set, test your program with the given input files

Example run of the program

Contents of alice_cards.txt:

h 3
s 10
c a
c 3
s 5
h 10
d a

Contents of bob_cards.txt:

c 2
d a
h 10
c 3
d j
s 10
h a

Correct output after running make and then running ./game_set alice_cards.txt bob_cards.txt:

Alice picked matching card c 3
Bob picked matching card h 10
Alice picked matching card d a
Bob picked matching card s 10

Alice's cards:
c a
s 5
h 3

Bob's cards:
c 2
d j
h a

Note: a=ace, k=king, q=queen, j=jack

Approach for the custom BST implementation of the game

In your second implementation of the game, you must implement the binary search trees yourself in card_list.h and card_list.cpp. Don’t worry about balancing the binary search trees (though you can try and optimize this if you like). Your binary search tree class should obey the card ordering rules given above. While implementing this, you may find it helpful to overload the operators ==, <, and > on your card class so that you can easily choose which branches to go down on your binary tree. Note that you need to correctly handle the case of cards with the value 10 (which has two characters) and separately compare the value and suit, so storing the cards as strings is probably not the best approach.

Your card_list.h and card_list.cpp must include a bidirectional iterator for the BST to allow traversal of cards in both forward (inorder, smallest to largest) and reverse (reverse inorder, largest to smallest) directions.

Iterator Requirements:

Implement a bidirectional Iterator class that supports forward traversal using the getSuccessorNode method (via operator++) and reverse traversal using the getPredecessorNode method (via operator–). Provide begin(), end(), rbegin(), and rend() methods in the bst class. begin() and end() return iterators for forward traversal starting at the smallest card and the end, respectively. rbegin() and rend() return iterators for reverse traversal starting at the largest card and the end, respectively. Use Iterator with operator++ in the printDeck method to print cards in sorted order. Ensure iterators are const-correct, returning const Node* for read-only access in printDeck and parts of the game logic, and encapsulate Node details to prevent direct pointer access outside the bst class.

Example Usage of iterators

bst alice, bob;
// Call to insert to add cards to each hand
for (bst::Iterator it = alice.begin(); it != alice.end(); ++it) {
    std::cout << it->out << std::endl; // Prints "c a", then "d 3"
}
for (bst::Iterator it = bob.rbegin(); it != bob.rend(); --it) {
    std::cout << it->out << std::endl; // Prints "d 3"
}
playGame(alice, bob); // Plays the game, printing matches and modifying hands

Game Logic Requirements:

Implement a free function playGame(bst& alice, bst& bob) in card_list.cpp to manage the game logic, using only public methods of the bst class (insert, remove, contains, printDeck, begin, end, rbegin, rend) and the Iterator class. In playGame, use Iterator with operator++ for Alice’s turn to traverse her hand forward and operator– for Bob’s turn to traverse his hand backward. Do not access Node pointers directly; rely on the iterator’s operator-> to access card data (e.g., it->info, it->out) and public bst methods for all operations. Ensure main.cpp calls playGame(alice, bob) to execute the game, integrating with the file reading and output logic. Your logic for this program should be very similar to main_set.cpp except you should not use std::set and use your custom BST implementation instead.

Testing Requirements:

In tests.cpp, include test cases that provide the following coverage:

  1. BST Public Methods: Include at least 5 test cases for each public member function of the bst class, including at a minimum insert(), remove(), contains(), printDeck(), getSuccessorNode(), and getPredecessorNode(). Test cases should cover:
    • Empty tree (e.g., verify contains() returns false).
    • Single node (e.g., verify correct insertion and retrieval).
    • Multiple nodes (e.g., verify correct ordering and removal).
    • Edge cases (e.g., removing a non-existent card, inserting duplicates).
    • Correct memory management (e.g., no leaks after remove() or clear()).
  2. Include at least 5 test cases for the Iterator class, covering:
    • Empty tree (verify begin() == end() and rbegin() == rend()).
    • Single node (verify correct node is returned and increment/decrement reaches end).
    • Multiple nodes (verify correct inorder sequence with ++ and reverse inorder sequence with –).
    • Incrementing past the end and decrementing past the reverse end (verify safe behavior).
    • Iterator comparison (verify == and != work correctly).
  3. Include at least 3 test cases for the playGame function in tests.cpp, covering:
    • Both players with common cards (verify correct matches and removals).
    • One empty hand (verify early exit).
    • No common cards (verify loop termination).

Correct output after running make and then running ./game alice_cards.txt bob_cards.txt should produce the exact same output as before (when you ran game_set with the given input files).

You should write these tests BEFORE implementing the full game to ensure that your binary search tree works correctly. Debugging one set of code is much easier than debugging two at the same time. This will also ensure that your are correctly separating your binary tree class from the rest of your program logic.

Requirements

For this lab, you will have flexibility in your implementation, but your mentor will check for the following requirements when reviewing your code. Ensure your solution meets these criteria:

Submission instructions

You and your partner only need to make a single submission. Add your partner to Gradescope before you submit (or before the deadline). Submit your code on Gradescope. You must organize your program in the files: main_set.cpp, main.cpp, card.cpp, tests.cpp, card.h, card_list.cpp and card_list.h, Makefile