COMPLETE THE MISSING CODE. Follow commented directions throughout code and type missing lines. ONLY Card.java and Deck.java need to be modified.

I. Complete the missing imlementation of the Card class Implement Card(int,int), one of the constructors in the Card class so that they can handle exceptions (as outlined in the beginning file Deck.java). Complete the missing code in the member functions (as outlined in the beginning file Deck.java). Run test1 to demonstrate your implementation is correct.

II. Create and manipulate a stack/queue of Card objects Follow the instructions given from the starting file Deck.java, complete the missing code for test2 and test3.

III. Use appropriate data structures to simulate card manipulation Follow the instructions given from the starting file Deck.java, complete the missing code for test4.

/** * File: Card.java

**/

// DO NOT MODIFY the following import statement import java.util.concurrent.ThreadLocalRandom; // for the function myRandInt

/* Instructions: * Follow the guidelines given in the comments, complete the implementation * of the Card class **/

public class Card { private int rank; // the rank of the Card private int suit; // the suit of the Card /** * Construct a valid playing Card * @param aRank * the rank of the Card * @param aSuit * the suit of the Card * precondition * aRank must be in the range from 0 to 12 (both inclusive) * aSuit must be in the range from 0 to 3 (both inclusive) * postcondition * The Card has been initialized with a valid rank and a valid suit * @exception IllegalArgumentException * Indicates that rank is outside the given range when applicable * Indicates that suit is outside the given range when applicable **/

public Card (int aRank, int aSuit) throws IllegalArgumentException { rank=0; suit=0; // remove this line when implementing this constructor // ADD CODE HERE } /** * constructor which assign valid rank and suit in a * `random' manner, using the function myRandInt * **/ public Card () { rank = myRandInt(0,12); suit = myRandInt(0,3); } /** * A getter function * @return * the suit of the Card **/ public int getSuit(){ return 0; // change this to return the suit of the given card } /** * A getter function * @return * the rank of the Card **/ public int getRank(){ return 0; // change this to return the suit of the given card } /** * Display the Card * postcondition : * the rank and the suit of the Card are displayed to screen, * for example: ACES / SPADES **/ public void display(){ // ADD code here } /** * @param * c1 is a Card * @param * c2 is a Card * preconditions: * first must be non-negative and first must be less than or equal to last * @return * an int randomly chosen from first (inclusive) to last (inclusive) * * needs to add the line import java.util.concurrent.ThreadLocalRandom; **/ public static boolean same (Card c1, Card c2) { return true; // Remove this line and add your code } /** * @param first * an int, the beginning of the range (inclusive) * @param last * an int, the end of the range (inclusive) * @precondition * 0 <= first <= last * @return * an int randomly chosen from first (inclusive) to last (inclusive) * @require * needs to add the line import java.util.concurrent.ThreadLocalRandom; **/ // DO NOT MODIFY THIS FUNCTION private int myRandInt(int first, int last){ return ThreadLocalRandom.current().nextInt(first, last + 1); } // end myRandInt } // end class Card

import java.util.concurrent.ThreadLocalRandom; // to use use randPermute

/* File: Deck.java

* Tests for the ArrayStack and ArrayQueue classes from Morin

* Tests for a Card class

*/ public class Deck { /* Define Global constants */ static final int SHORT = 4; static final int LONG = 13; static final int ALL = 52; public static void main (String [] argv) { // The following shows how to create a stack (and queue) via Morin's code // Add the line below to create an empty stack of Cards via Morin's // ArrayStack stackA = new ArrayStack(Card.class); // Add the line below to create an empty queue of Cards via Morin's // ArrayQueue queueA = new ArrayQueue(Card.class); // Initialize // create a standard deck of cards Card [] standard = new Card[ALL]; // Create a standard deck of cards for (int i=0; i standard[i] = new Card(i%13,i%4); // standard[i].display(); // uncomment this line to show the standard deck } // create a shuffled deck of cards int [] randIndex = randPermute(ALL); // Generate a random permutation of the array [0, .., ALL] Card [] shuffled = new Card[ALL]; // Create a shuffled deck of cards from the standard deck for (int i=0; i shuffled[i] = new Card ((randIndex[i]%13),(randIndex[i]%4)); // shuffled[i].display(); // uncomment this line to show the shuffled deck } // end of initialize // carry out the test test1(); test2(standard, shuffled, ALL, SHORT); test3(shuffled, standard, ALL, SHORT); test4(standard, shuffled, ALL, SHORT); } // end of Main

// test1 is for testing the constructor of Card class // and other member functions with missing implementation // (eg. same) in the Card class // DO NOT MODIFY this function public static void test1() { System.out.println(" Begin of test 1: "); Card [] test1 = new Card [SHORT]; for (int i=0; i test1[i] = new Card (i+10,i+2); } if (Card.same(test1[0],test1[1])) System.out.println("test1[0] and test1[1] are the same."); else System.out.println("test1[0] and test1[1] are different."); if (Card.same(test1[2],test1[3])) System.out.println("test1[2] and test1[3] are the same."); System.out.println(" End of test 1: "); } // End of test1 // Follow the instructions given in the comments to implement test2 public static void test2 (Card [] fulldeck1, Card [] fulldeck2, int len, int sample) { // len is the no of cards in fulldeck1 (and also fulldeck2, since each fulldeck has // the same number of cards) System.out.println(" Begin of test 2: "); // Create an empty stack of Cards via Morin's ArrayStack class (done)

ArrayStack stackA = new ArrayStack(Card.class);

// Create an empty queue of Cards via Morin's ArrayQueue class (done) ArrayQueue queueA = new ArrayQueue(Card.class); // push the Cards fulldeck[0], ... , fulldeck[sample-1] to an empty stack // enqueue the Card fulldeck[0], ... , fulldeck[sample-1] to an empty queue // print something like // "Display a sample of the first stack of cards from top to bottom:" // when displaying the stack and queue in the steps below // Display the stack of cards formed from top to bottom // Display the queue of cards formed from front to end // Repeat the same procedure above from the deck fulldeck2 System.out.println(" End of test 2. "); } public static void test3 (Card [] fulldeck1, Card [] fulldeck2, int len, int sample){ System.out.println(" Begin of test 3: "); // Create q1, an empty queue of Cards via Morin's ArrayQueue class // Create q2, an empty queue of Cards via Morin's ArrayQueue class // put fulldeck1 into q1 in the same order // put fulldeck2 into q2 in the same order // Remove all the non-face cards from q1 // keep only the face cards (JACK, QUEEN, KING only) with suit spade in q1, maintain the original order // keep only the aces in q2, maintain the original order // display q1, from front to end, with the given heading System.out.println("*** Display q1 ***"); // ADD code here // display q2, from front to end, with the given heading System.out.println("*** Display q2 ***"); // ADD code here System.out.println(" end of test 3: "); } public static void test4 (Card [] fulldeck1, Card [] fulldeck2, int len, int sample){ System.out.println(" Begin of test 4: part 1 "); // Create s1, an empty stack of Cards via Morin's ArrayStack class // Create s2, an empty stack of Cards via Morin's ArrayStack class // Create s3, an empty stack of Cards via Morin's ArrayStack class // Create s4, an empty stack of Cards via Morin's ArrayStack class // Distribute the cards in fulldeck1 to s1, s2, s3, s4 in the round robin fashion // `push' each card on the top of the corresponding stack // when it is done, show the top card from each stack in the order s1, s2, s3, s4 // ADD code here System.out.print(" The top card from stack s1 is: "); // ADD code here System.out.print(" The top card from stack s2 is: ");

// ADD code here System.out.print(" The top card from stack s3 is: ");

// ADD code here System.out.print(" The top card from stack s4 is: ");

// ADD code here System.out.println (" End of test 4: part 1 "); System.out.println (" Begin of test 4: part 2 "); // Repeat the same procedure for the fulldeck2. That is: // Reset s1, s2, s3 and s4 to empty stacks of Cards via Morin's ArrayStack class // Distribute the cards in fulldeck2 to s1, s2, s3, s4 in the round robin fashion // `push' each card on the top of the corresponding stack // when it is done, show the top card from each stack in the order s1, s2, s3, s4 // ADD code here System.out.print(" The top card from stack s1 is: "); // ADD code here System.out.print(" The top card from stack s2 is: "); // ADD code here System.out.print(" The top card from stack s3 is: "); // ADD code here System.out.print(" The top card from stack s4 is: ");

// ADD code here

System.out.println(" End of test 4: part 2 "); System.out.println(" End of test 4. "); } // end test4

// DO NOT MODIFY THE CODE BELOW public static int [] randPermute (int n) { // n must be non-negative int [] answer = new int[n]; for (int i=0; i answer[i] =i; int len = n; while (len > 1){ swap(answer, getRandomIndex(0,len-1),len-1); len--;} // end while return answer; } // end of randPermute

public static void swap(int [] a, int s, int t) {// 0<=s<=t int temp = -1; temp = a[s]; a[s] = a[t]; a[t] = temp; } // end of swap public static int getRandomIndex(int r, int s){ // requires 0 <= r <= s // needs to add the line import java.util.concurrent.ThreadLocalRandom; return ThreadLocalRandom.current().nextInt(r, s + 1); } // end getRandomIndex

} // end of Class Deck

// ArrayStack.java

// package ods;

import java.util.AbstractList; import java.util.Collection;

/** * This is a copy of the JCF class ArrayList. It implements the List * interface as a single array a. Elements are stored at positions * a[0],...,a[size()-1]. Doubling/halving is used to resize the array * a when necessary. * @author morin * * @param the type of objects stored in the List */ public class ArrayStack extends AbstractList { /** * keeps track of the class of objects we store */ Factory f; /** * The array used to store elements */ T[] a; /** * The number of elements stored */ int n; /** * Resize the internal array */ protected void resize() { T[] b = f.newArray(Math.max(n*2,1)); for (int i = 0; i < n; i++) { b[i] = a[i]; } a = b; }

/** * Resize the internal array */ protected void resize(int nn) { T[] b = f.newArray(nn); for (int i = 0; i < n; i++) { b[i] = a[i]; } a = b; }

/** * Constructor * @param t0 the type of objects that are stored in this list */ public ArrayStack(Class t) { f = new Factory(t); a = f.newArray(1); n = 0; }

public T get(int i) { if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException(); return a[i]; } public int size() { return n; } public T set(int i, T x) { if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException(); T y = a[i]; a[i] = x; return y; } public void add(int i, T x) { if (i < 0 || i > n) throw new IndexOutOfBoundsException(); if (n + 1 > a.length) resize(); for (int j = n; j > i; j--) a[j] = a[j-1]; a[i] = x; n++; } public T remove(int i) { if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException(); T x = a[i]; for (int j = i; j < n-1; j++) a[j] = a[j+1]; n--; if (a.length >= 3*n) resize(); return x; }

// The following methods are not strictly necessary. The parent // class, AbstractList, has default implementations of them, but // our implementations are more efficient - especially addAll /** * A small optimization for a frequently used method */ public boolean add(T x) { if (n + 1 > a.length) resize(); a[n++] = x; return true; } /** * We override addAll because AbstractList implements it by * repeated calls to add(i,x), which can take time * O(size()*c.size()). This happens, for example, when i = 0. * This version takes time O(size() + c.size()). */ public boolean addAll(int i, Collection c) { if (i < 0 || i > n) throw new IndexOutOfBoundsException(); int k = c.size(); if (n + k > a.length) resize(2*(n+k)); for (int j = n+k-1; j >= i+k; j--) a[j] = a[j-k]; for (T x : c) a[i++] = x; n += k; return true; } /** * We override this method because AbstractList implements by * repeated calls to remove(size()), which takes O(size()) time. * This implementation runs in O(1) time. */ public void clear() { n = 0; resize(); } }

// ArrayQueue.java

// package ods;

import java.util.AbstractQueue; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Queue;

/** * An implementation of the Queue interface using an array * * All operations takes constant amortized time. * @author morin * * @param */ public class ArrayQueue extends AbstractQueue { /** * The class of elements stored in this queue */ protected Factory f; /** * Array used to store elements */ protected T[] a; /** * Index of next element to de-queue */ protected int j; /** * Number of elements in the queue */ protected int n; /** * Grow the internal array */ protected void resize() { T[] b = f.newArray(Math.max(1,n*2)); for (int k = 0; k < n; k++) b[k] = a[(j+k) % a.length]; a = b; j = 0; } /** * Constructor */ public ArrayQueue(Class t) { f = new Factory(t); a = f.newArray(1); j = 0; n = 0; } /** * Return an iterator for the elements of the queue. * This iterator does not support the remove operation */ public Iterator iterator() { class QueueIterator implements Iterator { int k; public QueueIterator() { k = 0; }

public boolean hasNext() { return (k < n); } public T next() { if (k > n) throw new NoSuchElementException(); T x = a[(j+k) % a.length]; k++; return x; } public void remove() { throw new UnsupportedOperationException(); } } return new QueueIterator(); }

public int size() { return n; }

public boolean offer(T x) { return add(x); }

public boolean add(T x) { if (n + 1 > a.length) resize(); a[(j+n) % a.length] = x; n++; return true; } public T peek() { T x = null; if (n > 0) { x = a[j]; } return x; }

public T remove() { if (n == 0) throw new NoSuchElementException(); T x = a[j]; j = (j + 1) % a.length; n--; if (a.length >= 3*n) resize(); return x; }

public T poll() { return n == 0 ? null : remove(); } public static void main(String args[]) { int m = 10000, n = 50; Queue q = new ArrayQueue(Integer.class); for (int i = 0; i < m; i++) { q.add(new Integer(i)); if (q.size() > n) { Integer x = q.remove(); assert(x == i - n); } } Iterator i = q.iterator(); while (i.hasNext()) { System.out.println(i.next()); } } }

// Factory.java

// package ods;

import java.lang.reflect.Array;

/** * An ugly little class for allocating objects and arrays of generic * type T. This is needed to work around limitations of Java generics. */ public class Factory { Class t; /** * Return the type associated with this factory * @return */ public Class type() { return t; } /** * Constructor - creates a factory for creating objects and * arrays of type t(=T) * @param t0 */ public Factory(Class t0) { t = t0; } /** * Allocate a new array of objects of type T. * @param n the size of the array to allocate * @return the array allocated */ @SuppressWarnings({"unchecked"}) protected T[] newArray(int n) { return (T[])Array.newInstance(t, n); }

/** * * @return */ public T newInstance() { T x; try { x = t.newInstance(); } catch (Exception e) { x = null; } return x; } }