Assignment Overview
1. Write a semi-coroutine to sort a set of values into ascending order using a binary-tree insertion method. This method constructs a binary tree of the data values, which can subsequently be traversed to retrieve the values in sorted order. Construct a binary tree without balancing it, so that the values 25, 6, 9, 5, 99, 100, 101, 7 produce a tree.
By traversing the tree in infix order — go left if possible, return value, go right if possible — the values are returned in sorted order. Instead of constructing the binary tree with each vertex having two pointers and a value, build the tree using a coroutine for each vertex. Hence, each coroutine in the tree contains two other coroutines and a value. (A coroutine must be self-contained, i.e., it cannot access any global variables in the program.)
The coroutine has the following interface (you may only add a public destructor and private members): template Coroutine Binsertsort Assume type T has operators == and <= (or <), and public default and copy constructor. Each value for sorting is passed to the coroutine via member sort. When passed the first value, v, the coroutine stores it in variable pivot.
Each subsequent value is compared to pivot. If v <= pivot, a Binsertsort coroutine called less is resumed with v; if v > pivot, a Binsertsort coroutine called greater resumed with v. Each of the two coroutines, less and greater,
creates two more coroutines in turn. The result is a binary tree of identical coroutines. The coroutines less and
greater must not be created by calls to new, i.e., no dynamic allocation is necessary in this coroutine.
2. Write a full coroutine that plays the following card game. If a player is not the only player, they take a number of cards from a deck of cards and pass the remaining deck to the player on the left if the number of remaining cards is odd, or to the right if the number of remaining cards is even. A player must take at least one card and no more than a certain maximum.
After making a play, a player checks to see if they received a deck that is a multiple of 5 (“death deck”); if so, that player must remove themself from the game. The player who takes the last cards or is the only player remaining wins the game. The players routine is called before any players are created to set the total number of players in the game. The constructor is passed a reference to a printer object and an identification number assigned by the main program. (Use values in the range 0 to N −1 for identification values.) To form the circle of players, the start routine is called for each player from uMain::main to pass a reference to the player on the left and right; the start routine also resumes the player coroutine to set uMain as its starter (needed during termination). The play routine receives the deck of cards passed among the players.
