CODE METHOD IN JAVA, /** * Add a card to the end of this pile/hand. O(1) * @param c card to add, must not be null or in a group already. * @throws IllegalArgumentException if the card is in a group already. */ public void add(Card c) { // TODO // No loops or special cases allowed! // (Use "if" only to check errors) // Make sure to test invariant at start and before returning. }

USING CLASSES

public class Card { public enum Suit { CLUB, DIAMOND, HEART, SPADE }; public enum Rank { ACE(1), DEUCE(2), THREE(3), FOUR(4), FIVE(5), SIX(6), SEVEN(7), EIGHT (8), NINE(9), TEN(10), JACK(11), QUEEN(12), KING(13);

private final int rank; private Rank(int r) { rank = r; }

public int asInt() { return rank; } }

private final Suit suit; private final Rank rank; private Card prev, next;

private Card() { rank = null; suit = null; } public Card(Rank r, Suit s) { if (r == null || s == null) throw new IllegalArgumentException("Not a legal card"); rank = r; suit = s; }

// getters for all fields:

public Suit getSuit() { return suit; }

public Rank getRank() { return rank; }

public Card getPrevious() { if (prev == null || prev.suit == null) return null; return prev; }

public Card getNext() { if (next == null || next.suit == null) return null; return next; }

// no setters!

@Override /** Return true if the suit and rank are the same. * Caution: do not use this method to check if you have the same card! */ public boolean equals(Object x) { if (!(x instanceof Card)) return false; Card other = (Card)x; return suit == other.suit && rank == other.rank; }

@Override public String toString() { return rank + " of " + suit + "S"; }

/** * An endogenous DLL of card objects. */ public static class Group { private Card dummy;

private Group(boolean ignored) {} // do not change private static boolean reportErrors = true; // do not change private boolean report(String s) { if (reportErrors) System.err.println("Invariant error: " + s); return false; } private boolean wellFormed() { // Invariant: // (1) dummy is not null, but has null suit and rank. if (dummy == null || dummy.suit != null || dummy.rank != null) { return report("Dummy is not well-formed"); } // (2) the cards are linked in a cycle starting and ending // at the dummy. Card tortoise = dummy; Card hare = dummy;

do { if (hare == null || hare.next == null) { return report("Cycle does not start and end at dummy"); } hare = hare.next.next; tortoise = tortoise.next; } while (hare != tortoise); // (3) Whenever c1.next == c2 is in the cycle, the c2.prev == c1 tortoise = dummy; hare = hare.next; while (hare != dummy) { if (hare.prev != tortoise) { return report("Cards are not linked correctly in the cycle"); } hare = hare.next; tortoise = tortoise.next; } // (4) no cards except the dummy have null suit or rank. Card current = dummy.next; while (current != dummy) { if (current.suit == null || current.rank == null) { return report("Card has null suit or rank"); } current = current.next; } // TODO: Implement the invariant: // This code must terminate and must not crash even if there are problems. return true; }

/** * Create an empty group. */ public Group() { // TODO: initialize empty group dummy = new Card(); assert wellFormed() : "Group initialized wrong"; }

public Card getFirst() { return dummy.getNext(); } public Card getLast() { return dummy.getPrevious(); }

/** * Return true if there are no cards, * that is, if and only if getFirst() == null. O(1) */ public boolean isEmpty() { assert wellFormed() : "invariant false on entry to isEmpty()"; if (getFirst() == null) { return true; } else { return false; } // TODO }

/** * Return the number of cards in this pile. O(n) */ public int count() { assert wellFormed() : "invariant false on entry to count()"; int count = 0; for (Card p = getFirst(); p != null; p = p.next) { count++; } return count; // TODO (a loop will be necessary) }