Need Help With This

Table 1: Files to be Submitted

Class/FileName

Description

MyList

Interface for ArrayList

MyAbstractList

Abstract Parent for ArrayList

MyArrayList

Program uses 3 ArrayLists:

(1): Deck of Cards

(2): Stacks of Cards on the Table

(3): Linked Lists of Card Subsequences on the Table

MyLinkedList

Each subsequence is in a Linked List

MyStack

Program uses 2 types of Stacks:

(1): Each pile of Cards on the Table

(2): Stack used to reverse Linked Lists of

Card Subsequences

SortCardGame

Main driver of the game

Table

Has 2 Data Structures:

(1): ArrayList of Stacks of Cards

(2): ArrayList of Linked Lists of Card Subsequences

Deck

An ArrayList of 52 Cards

Card

A Comparable Card with suit and rank

SortGameOut.txt

The output of the games.

The Card Game

Take a deck of normal playing cards. The deck is shuffled, cards are turned up one at a time and dealt into piles on the table, according to the following RULES:

Initially, there are no piles. The first card dealt forms a new pile consisting of the single card drawn.

Each new card must be placed on top of the leftmost pile whose top card has a higher value than the new card being added to the piles.

If each of the piles have a top card that is lower than the new card, then the new card must start a new pile to the right of all existing piles. Thus, you can only place a card on top of a card whose value is higher than its value.

When there are no more cards to deal, the game ends.

At each stage of the game, using these rules, the top cards of the piles are increasing from left to right. To recover the shuffled deck in sorted order, repeatedly remove the minimum visible card one of the cards at the top of one of the piles.

In other words, at the end of the game, card 1 is always on top of the leftmost pile. Removing card 1, card 2 is now at the top of some pile; removing card 2, card 3 is now at the top of some pile, and so we have a natural algorithm for manually sorting cards.

Now, the object of the game is to finish with as few piles as possible. To play with real cards, we order first by rank and then by suit within rank, using the bridge-bidding order: Clubs, Diamonds, Hearts, and Spades.

It is natural to ask what a winning game should be. Monte Carlo simulations show how the number of piles varies for an ordinary 52-card deck. The table below shows the results of playing 10,000 games.

# stacks

8

9

10

11

12

13

14

15

16

17

18

frequency

54

525

1746

2791

2503

1518

632

186

33

11

1

The average number of piles is 11.6. Usually there are 10 - 13 final piles. The rules for this Patience Sorting game say you can claim that you win, if you end with 9 piles or fewer. This leads to a ~5% chance of winning. Of course, this game is all luck. There is no strategy, when following all the correct rules.

The Longest Subsequence

Another feature of this card game, besides being a way to sort a deck of cards, is that it can also be enhanced to find a subset of the "longest increasing or decreasing subsequences". As it turns out, the number of piles is the length of a longest subsequence. Proofs for this feature can be found using Google.

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. The longest decreasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, highest to lowest, and in which the subsequence is as long as possible. These subsequences are not necessarily contiguous, or unique. Longest increasing and decreasing subsequences are studied in the context of various disciplines related to mathematics. In our case, the sequence is the randomly ordered Deck of Cards. The Cards making up the subsequences are not contiguous in the Deck, but the Cards are ordered as they appeared in the Deck. The subsequences for this project will be formed by adding the Cards to a linked list, at the same time as they are laid in a pile on the Table.

Example Using Just the 13 Spades:

To illustrate, suppose a shuffled deck of just the thirteen Spades, as shown below. Using these RULES, the piles of cards on the table would be arranged as shown, given Ace is high in this example. (Ace is low in our Project)

The rule is to always place a card on the leftmost possible pile.

(1): So, 6 starts Pile1

(2): Then, 3 is placed on 6: since 3 < 6.

(3): Then, 5 starts Pile2: as 5 > 3

(4): Then, 10 starts Pile3: as 10 > 5

(5): Then, Jack starts Pile4: as Jack > 10

(6): Then, 2 is placed on 3: since 2 < 3

(7): Then, 9 is placed on 10: since 9 < 10

(8): Then, Ace starts Pile5: as Ace > Jack

(9): Then, King is placed on Ace: since King < Ace

(10): Then, 7 is placed on 9: since 7 < 9

(11): Then, 4 is placed on 5: since 4 < 5

(12): Then, 8 is placed on Jack: since 8 < J

(13): Last, Queen is placed on King: since Queen < King

These cards can be picked up in sorted order by examining the top card in each pile and choosing the lowest each time. For the situation shown above, the cards can be retrieved in sorted order by picking the top card of the piles in this order:

2: Pile1, 3: Pile1, 4: Pile2, 5: Pile2, 6: Pile1, 7: Pile3, 8: Pile4,

9: Pile3, 10: Pile3, Jack: Pile4, Queen: Pile5, King: Pile5, Ace: Pile5

Convince yourself that this algorithm works for sorting the deck of cards. Get out a Deck of Cards and play it.

Next, lets see how we can tweak this algorithm to find a subset of the set of longest decreasing subsequences for the deck of Spades. As each card is placed in one of the piles, give it a reference (pointer) to the top card in the previous pile to its left. If the card is placed in the leftmost pile, then this reference will be null. This reference will always point to a card of lower value.

(1): When 6 and 3 are placed in Pile1, their references are set to null.

(2): When 5 is placed in Pile2, its reference is set to card 3, the top card in Pile1.

(3): When 10 is placed in Pile3, its reference is set to card 5, the top card in Pile2.

(4): When Jack is placed in Pile4, its reference is set to card 10, the top card in Pile3.

(5): When 2 is placed in Pile1, its reference is set to null.

(6): When 9 is placed in Pile3, its reference is set to card 5, the top card in Pile2.

(7): When Ace is placed in Pile5, its reference is set to card Jack, the top card in Pile4.

(8): When King is placed in Pile5, its reference is set to card Jack, the top card in Pile4.

(9): When 7 is placed in Pile3, its reference is set to card 5, the top card in Pile2.

(10): When 4 is placed in Pile2, its reference is set to card 2, the top card in Pile1.

(11): When 8 is placed in Pile4, its reference is set to card 7, the top card in Pile3.

(12): When Queen is placed in Pile5, its reference is set to card 8, the top card in Pile4.

Using each of the cards in the rightmost pile (Pile5), you can follow the card pointers, until you reach null (from Pile5 to Pile1). The linked cards form one of the longest decreasing subsequences of the shuffled deck of cards.

In this project, we will retrieve a subset of the longest subsequences and print them in both increasing and decreasing order. There will be one subsequence for each of the cards in the last pile at the end of the game.

Now, the cards do not contain reference pointers to do the linking. The cards will be linked together by placing them in nodes and adding the nodes to linked lists, as nodes have references to the next node in their linked list. These linked lists will be created by adding each card node to the top of a linked list formed from previously linked cards, being careful to find the correct linked list to add it to. This will require copying some of the previously formed linked lists, as these sequences use some of the same cards.

Seq

Linked

List 0

Seq

Linked

List 1

Seq

Linked

List 2

Seq

Linked

List 3

Seq

Linked

List 4

Seq

Linked

List 5

Using the same spades example, the above linked lists will be formed. In forming these lists, the following linked list copies occur:

(1): When we are placing the 9-S and needing to link it to the 5-S, the Seq Linked List 1 is copied and each card above the 5-S is removed and the 9-S added, forming Seq Linked List 3.

(2): When we are placing the K-S and needing to link it to the J-S, the Seq Linked List 1 is copied again and each card above the J-S is removed and the K-S added, forming Seq Linked List 4.

(3): When we are placing the 7-S and needing to link it to the 5-S, the Seq Linked List 1 is copied again and each card above the 5-S is removed and the 7-S added, forming Seq Linked List 5.

The linked lists with the same number of nodes as the number of piles are the ones containing the longest subsequences. In this example, they are Seq Linked List 1, Seq Linked List 4. And Seq Linked List 5.

Requirements Specification and System Design

You are required to write a program to simulate playing this Patience Sorting card game. It is highly recommended that you obtain a deck of cards and play this game, until you understand how it is played. You will use this game to both produce a sorted Deck from a shuffled one and a subset of the longest subsequences in the shuffled deck. The sorted Deck will be printed, as well as, each of the longest subsequences in both decreasing and increasing order. The rules are stated above under The Card Game and The Longest Subsequence.

Our version of this game uses Aces low (rank=1) and King high (rank=13). The cards will be ordered first by rank and then by suit within the rank. The suit order from lowest to highest: Clubs, Diamonds, Hearts, and Spades. The Card class will implement Comparable, so that you can sort the Cards. You will use the following classes:

MyList: interface for Lists

MyAbstractList: abstract parent class for MyArrayList

MyArrayList: holds the piles (stacks) on the Table and holds the

list of subsequences (linked lists)

MyLinkedList: holds the linked cards for the subsequences

Card: holds the suit and rank and implements Comparable

Deck: inherited from MyArrayList (array of 52 Cards)

MyStack: implements the card piles and is used to reverse LinkedLists Card subsequeces.

Table: the class holding the MyArrayList of MyStack piles

and the MyArrayList of MyLinkedList subsequences

The card game is played from the application program class, SortCardGame. The code for playing the game is divided between the Table class and the SortCardGame application.

Data Definition:

You are to code many of the methods in the Card, Deck, Table and SortCardGame classes. Each of the methods that require implementation will have method-level comments to aid you in coding the method. Please follow the algorithms given in these method-level comments, unless you can justify, to your instructor, a better way to play the game and produce the output given in the txt file.

The cards used for this game are objects of the Card class. The Card class implements Comparable.

The Card class has two private instance variables:

int rank: (1-13), where Ace = 1, Jack = 11, Queen = 12, King = 13

int suit: (1-4), where Club=1, Diamond=2, Heart=3, and Spade=4

There are static instance variables used for printing: each is an array of Strings, one for printing the ranks and the other for printing the suits:

public static String[] RANKS =

{

" A", " 2", " 3", " 4", " 5", " 6", " 7",

" 8", " 9", "10", " J", " Q", " K"

};

public static String[] SUITS =

{

"-C", "-D", "-H", "-S"

};

The Card instance methods include:

Card () default constructor initializing the Card to the Ace of Clubs: (rank = 1 and suit = 1)

Card (int rank, int suit) - constructor initializing the Card to the two parameters.

Card (Card otherCard) copy constructor initializing the Card to the corresponding instance variables of passed in otherCard.

int compareTo (Card someCard) returns a positive number, if this card is greater than the parameter someCard or a negative number if this card is less than the parameter someCard and zero, if they are equal. Must compare rank and then suit within rank.

boolean equals (Object obj) returns true, if this card has the same rank and suit as the parameter obj. The obj must be cast to a Card.

String toString() See the Sample output to see how to code a String representation of a Card.

There are 52 cards in a deck of cards. The Deck class extends (inherits from) MyArrayList holding the 52 Cards. It does not have any additional instance variables. The list of additional methods includes:

Deck () default constructor initializing the 52-card array. It passes the number 52 to the parent constructor to create a MyArrayList of only 52 Cards. It calls generateDeck () to initialize the array.

void generateDeck () initializes the Cards, using the Card two-parameter constructor - Card (int rank, int suit).

void shuffle () It shuffles the Deck of Cards. See Lesson 2 slides and source code for an algorithm for shuffling a card deck of course, it must be modified somewhat for this program.

String toString () See the Sample output to see how to code the String representation of the Deck.

The Table class constructs the piles of Cards using the rules of the game and the lists of ordered Card subsequences. The piles of Cards are stacks contained in an array list: MyArrayList>. It manages these Cards as the game is played. The Table class also holds the linked lists of Card subsequences contained in an array list: MyArrayList>. The longest increasing and decreasing subsequences are printed and the Cards are retrieved in sorted order from the piles of Cards.

The Table class has three private instance variables:

MyArrayList > piles

int numPiles

MyArrayList > subSeqs

The Table instance methods include:

Table () default constructor

void constructCardPiles (Deck deck): This method creates the piles (stacks) from the Deck of Cards, according to the following rules:

Initially, there are no piles. The first Card dealt forms a new pile consisting of the first Card.

Each new Card picked from the Deck must be placed on top of the leftmost pile (lowest MyArrayList index), whose top Card has a value higher than the new Card's value.

If there are only piles with top Cards that are lower in value than the new Card's value, then use the new Card to start a new pile to the right of all the existing piles (at end of MyArrayList of MyStack piles)

Save card in ArrayList of LinkedList subsequences (See below)

The game ends when all the cards have been dealt.

Dealing the cards in this way provides us a way of retrieving a subset of the longest increasing and decreasing subsequences.

The number of piles is the length of a longest subsequence.

For each new Card, add a copy of that card to the list of

subsequences and link it to the top Card in the previous pile to the left of this pile - the one with the lower ArrayList index - By design, the pile's top Card has a lower value than the value of the new Card.

void printCardPiles (PrintWriter writer) Use the passed in PrintWriter to print each pile (stacks) on the MyArrayList of MyStacks.

void printLongestSeqs (PrintWriter writer) - Use the passed in PrintWriter to print each of the longest decreasing subsequences stored in the MyArrayList of MyLinkedLists. Then reverse each of these subsequences using a MyStack and print them in increasing order.

void makeSortedDeck (Deck deck) Builds a sorted Deck by looking at the top Card on each pile (stack) and grabbing the card with the lowest value and placing on the new sorted Deck.

void addCardToSubSeq (Card currentCard, Card previousCard) - Adds the currentCard to one of the subsequences in the subsequence list. The correct subsequence on which to add the currrentCard is the one on which the previousCard currently resides.

MyLinkedList findSubSeq (Card card) - Find the first subsequence in the ArrayList of LinkedList subsequences that contains the Card passed in as a parameter.

MyLinkedList copySubSeq (MyLinkedList subSeq)- Make a copy of the subsequence LinkedList passed in as a parameter by copying each Card and adding the new copy to the new subsequence.

MyLinkedList reverseSubSeq (MyLinkedList subSeq) - Reverse the subsequence LinkedList passed in as a parameter using a stack.

The SortCardGame class is the main driver for the game. You will be given the code for the main method and the algorithm for the playGame method. The main method creates the output file and PrintWriter object passing it to the playGame method who calls the Deck and Table methods to play the game. See the Java file for the algorithm. The SortGameOut.txt has a sample run of 5 games.

The MyStack objects are used to represent the piles of Cards on the Table as stacks and they are also used to reverse a Card subsequence contained in a LinkedList. The MyStack class is changed up slightly from the textbook. It needs to implement Comparable, so that it can be a contained in an array list, a MyArrayList of MyStack objects. Thus, it must also implement a compareTo (MyStack st) method, which compares the stacks using their size: getSize(). This class is given to you.

The MyLinkedList objects are used to store a subsequence of Cards representing one of the decreasing or increasing subsequence of the randomly ordered Deck of Cards. The MyLinkedList class is changed up slightly from the textbook. It needs to implement Comparable, so that it can be a contained in an array list, a MyArrayList of MyLinkedList objects. Thus, it must also implement a compareTo (MyLinkedList list) method, which compares the linked lists using their size: getSize(). This class is given to you.

The MyArrayList objects are used to store the piles of Cards on the Table. Each pile is a MyStack object containing the Cards. The MyArrayList objects are also used to store the decreasing or increasing subsequences of the randomly ordered Deck of Cards. This class is given to you.

public class Card implements Comparable { // For printing the card rank

public static String[] RANKS = { " A", " 2", " 3", " 4", " 5", " 6", " 7", " 8", " 9", "10", " J", " Q", " K" };

// For printing the card suit

public static String[] SUITS = { "-C", "-D", "-H", "-S" }; // private instance variables

private int rank; private int suit;

// Default Constructor: initialize to Ace of Clubs public Card() { // code todo }

// Two-Param Constructor : initialize rank and suit public Card (int initRank, int initSuit) { // code todo }

// Copy constructor: Copies a Card from another Card public Card (Card otherCard) { // code todo } // Returns relative position of this Card to someCard. // This compares the Cards, first by rank: Aces low, King High // then Suit within rank: CLUB=1, DIAMOND=2, HEART=3, SPADE=4 public int compareTo (Card someCard) { // code todo }

// Determines whether this Card has the same rank and suit // as another Card passed in - Note cast of obj to Card @Override public boolean equals (Object obj) { Card someCard = (Card) obj; return (someCard.compareTo (this) == 0); }

// Print the card's rank and suit using the static // String arrays defined about public String toString() { String printString = RANKS[rank - 1] + SUITS[suit - 1]; return printString; } }

public class Deck extends MyArrayList

{

// Default Constructor: Create a deck of 52 cards

// by passing 52 to the MyArrayList constructor

// and then calling the generateDeck method

public Deck()

{

// code todo

}

// Generates the 52 Cards and adds them to the Deck

// Use a nested loop: Rank: 1-13 and Suit: 1-4

public void generateDeck()

{

// code todo

}

// Shuffle the 52 Cards:

// See Lesson2 Source Code DeckOfCards for Hint

// Loop through each card in the Deck:

// a. Generate a random index (0-51)

// b. Swap the card with the one at the random index

public void shuffle()

{

// code todo

}

// Print the Deck: 13 cards per line

// Call the Card's toString

@Override

public String toString()

{

String deckStr = "";

for (int c = 0; c < size(); c++)

{

deckStr = deckStr + get (c).toString() +

((((c+1) % 13) == 0) ? ' ' : ' ');

}

return deckStr;

}

}

public interface MyList> extends java.lang.Iterable { // Add a new element at the end of this list public void add (E e);

// Add a new element at specified index in this list public void add (int index, E e);

// Return true if this list contains the element public boolean contains (E e);

// Return the element at the specified index public E get (int index);

// Return the index of the first matching element // Return -1 if no match. public int indexOf (E e);

// Return the index of the last matching element // Return -1 if no match. public int lastIndexOf (E e);

// Return true if this list contains no elements public boolean isEmpty();

// Clear the list public void clear();

// Remove the first occurrence of the element // Shift any subsequent elements to the left. // Return true if the element is removed. public boolean remove (E e);

// Remove the element at the specified position // Shift any subsequent elements to the left. // Return the element that was removed from the list. public E remove (int index);

// Replace the element at the specified position // with the specified element and returns the new set. public Object set (int index, E e);

// Return the number of elements in this list public int size(); }

public class MyStack> implements Comparable>

{

private MyArrayList list = new MyArrayList();

// Use this to find top of stack and to compare Stacks

public int getSize()

{

return list.size();

}

// Look at top of stack, without removing it

public E peek()

{

return list.get (getSize() - 1);

}

// Place a new element on the stack

public void push (E e)

{

list.add (e);

}

// Remove the top element from the stack

public E pop()

{

E e = list.get (getSize() - 1);

list.remove (getSize() - 1);

return e;

}

public boolean isEmpty()

{

return list.isEmpty();

}

public int compareTo (MyStack e)

{

return (getSize() - e.getSize());

}

public MyArrayList getList()

{

return list;

}

@Override

public String toString()

{

return "Stack: " + list.toString();

}

}

public class SortCardGame

{

private static final String OUTPUT_FILE = "./src/SortGameOut.txt";

public static void main(String[] args) throws Exception

{

int runs = 5; // number of games to play,

// Create an output File writer

File outFile = new File (OUTPUT_FILE);

PrintWriter writer = new PrintWriter (outFile);

// Display number of runs

System.out.println ("Playing " + runs + " games.");

// Loop to play the game for the number of specified runs

// Display the Begin Game and End Game messages

for (int run = 1; run <= runs; run++)

{

writer.println(" =========== Begin Game " + run + " ==========");

playGame (writer); // Play the Game

writer.println("=========== End Game " + run + " ==========");

}

writer.close();

System.out.println ("Simulation complete.");

return;

}

// Simulates playing the sort card game and finding longest subsequences:

// 1. As each Card is placed on the correct stack on the Table, it is

// also placed correctly in a linked list of Cards forming an

// ordered longest subsequence.

// 2. Prints a longest decreasing and increasing subsequence for

// each Card in last stack

// 3. After the Cards have all been placed on the Table in their

// correct stack, they are picked back up in sorted ordrer.

//

// Algorithm:

// 1.Create the Table and Deck objects

// 2.Print the Deck before shuffling

// 3.Shuffle the deck 7 times, calling the Deck shuffle method

// 4.Print the Deck after shuffling

// 5.Construct the card piles on the Table, calling the

// Table constructCardPiles method

// 6.Print the card piles before doing the sort

// calling the Table printCardPiles method

// 7.Print the longest subsequences, calling

// the Table printLongestSubSeqs method

// 8.Use the piles on the Table to make a sorted Deck,

// calling the Table makeSortedDeck method

// 9.Display the sorted Deck

public static void playGame (PrintWriter writer)

{

// code todo

}

}

public class Table

{

// Holds the stacks of cards in an ArrayList of Card Stacks

private MyArrayList> piles;

// Holds a list of sequences in an ArrayList of Card Linked Lists

private MyArrayList> subSeqs;

// The number of Stacks of Cards in the ArrayList

private int numPiles;

// Constructor: initialize instance variables

public Table()

{

// code todo

}

// This method creates the piles (stacks) from the Deck of Cards,

// according to the following rules:

// A. Initially, there are no piles. The first Card dealt

// forms a new pile consisting of the first Card.

// B. Each new Card picked from the Deck must be placed on top

// of the leftmost pile (lowest MyArrayList index), whose

// top Card has a value higher than the new Card's value.

// C. If there are only piles with top Cards that are lower

// in value than the new Card's value, then use the new

// Card to start a new pile to the right of all the

// existing piles (at end of MyArrayList of MyStack piles)

// D. Save card in ArrayList of LinkedList subsequences (See below)

// E. The game ends when all the cards have been dealt.

//

// Dealing the cards in this way provides us a way of retrieving

// a subset of the longest increasing and decreasing subsequences.

// A. The number of piles is the length of a longest subsequence.

// B. For each new Card, add a copy of that card to the list of

// subsequences and link it to the top Card in the previous

// pile to the left of this pile - the one with the lower

// ArrayList index - By design, the pile's top Card has a

// lower value than the value of the new Card.

//

// The Algorithm:

// Loop retrieving each card in the Deck

// 1. Retrieve the card from the Deck: cardFromDeck

// 2. Set a flag to indicate if we placed the

// cardFromDeck in an existing pile

// 3. Loop through each pile starting from the

// leftmost pile - ArrayList index 0 - to find

// the correct one on which to place the cardFromDeck

// a. Retrieve top Card on the Stack using peek

// b. If there exists a pile whose top Card is

// is higher than the cardFromDeck, then

// i. Set flag to say we have found a pile on

// which to place the cardFromDeck

// ii. Retrieve a reference to the top Card

// on the previous pile - the one to the

// left of where you just placed the

// cardFromDeck: (one less index value

// in ArrayList)

// iii. Add the cardFromDeck to the list of

// subsequences using the addCardToSubSeq method

// iv. Push the cardFromDeck onto the pile

// 4. Check the flag:

// If we haven't found a place for the cardFromDeck

// in an existing pile, then

// a. Create a new pile (in ArrayList of Stacks)

// b. Retrieve a reference to the top Card on the

// previous pile, - the one to the left of where

// you just placed the cardFromDeck: (one less

// index value in ArrayList), unless this first

// card from the Deck: numPiles equal 0

// c. Add the cardFromDeck to the list of

// subsequences using the addCardToSubSeq method

// d. Add the cardFromDeck onto the pile

// e. Increment the pile count

public void constructCardPiles (Deck deck)

{

// code todo

}

// Use the passed in PrintWriter to print each pile

// on the ArrayList of Card Stacks

public void printCardPiles (PrintWriter writer)

{

// code todo

}

// Use the passed in PrintWriter to print each of the decreasing

// and increasing subsequences

//

// The Algorithm:

// 1. Loop through the subsequence list and obtain each

// subsequence whose size equals the number of piles -

// the longest subsequences - Use the PrintWriter to

// print each of these subsequence

// 2. Loop through the subsequence list again and obtain

// each subsequence whose size equals the number of piles

// - this time reverse the subsequence and use the

// PrintWriter to print it

public void printLongestSubSeqs (PrintWriter writer)

{

// code todo

}

// Builds a sorted Deck by looking at the top Card of each pile

// (stack) and grabbing the card with the lowest value; thus,

// Cards are picked up in sorted order and added to the new Deck

//

// Algorithm:

// Loop for each card in the deck

// 1. Keep an index to the pile with the lowest card, so far

// 2. Keep the lowest Card found so far - initialize it to

// the highest card for starters

// 3. Walk across the piles - skipping empty ones - and find

// the ArrayList index of the Stack with smallest card by

// comparing the top card in the pile to the current

// lowest card by using the Card compareTo method -

// Dont' pop the card yet; it may not be the overall

// lowest - Update the the lowest Card and its ArrayList

// index along the way

// 4. Now that we have exited the walk of the piles, we know

// the index of the stack with the lowest Card - pop that

// Card from the stack and put it on the new sorted Deck

public void makeSortedDeck (Deck deck)

{

// code todo

}

// Adds a copy of the currentCard to one of the subsequences

// in the subsequence list. The correct subsequence on which to

// add the currrentCard is the one on which the previousCard

// currently resides.

//

// The Algorithm:

// 1. Make a copy of the currentCard, using Card's copy

// constructor.

// 2. Find the subsequence containing the previousCard

// by calling the findSubSeq method

// 3. If there is no subsequence (null), create a new

// subsequence LinkedList and add the copy of the

// currentCard to the new subsequence and add the new

// subsequence to the ArrayList of LinkedList of subsequences

// 4. If there was a subsequence containing the previousCard,

// then check to see if the previousCard is at the front

// of the subsequence LinkedList:

// a. If the previousCard is at the head, then just add the

// the copy of the currentCard to the front of the

// subsequence LinkedList, thus linking the two Cards

// b. If the previousCard is not at the head,

// then we must

// i. Copy the subsequence containing the previousCard

// by calling the copySubSeq method

// ii. Add the copied subsequence to the ArrayList of

// subsequences

// iii. Traverse the copied subsequence from the head,

// removing each Card that is not the previousCard.

// Break out of the loop when finding the previousCard.

// - Hint: You can use a FOR EACH loop

// iv. Now, the previousCard is at the front of the

// subsequence, so we can add the copy of the

// currentCard to the front of the subsequence,

// thus linking the two Cards

private void addCardToSubSeq (Card currentCard, Card previousCard)

{

// code todo

}

// Find the first subsequence in the ArrayList of

// subsequences that contains the Card passed in

// The Algorithm:

// 1. Make sure the card passed in is not null,

// if so return null.

// 2. Traverse the ArrayList of subsequence LinkedLists,

// checking to see if the subsequence contains the

// card passed in - Hint: You can use a FOR EACH loop

// 3. Return the subsequence when found

private MyLinkedList findSubSeq (Card card)

{

// code todo

}

// Make a copy of a subsequence LinkedList by copying each Card

// and adding the new copy to the new subsequence.

//

// The Algorithm:

// 1. Create a new LinkedList to hold the new subsequence

// 2. Traverse the passed in LinkedList, create a new Card from

// each Card using the Card copy constructor and then add

// each new Card to the end of the new subsequence LinkedList

// Hint: You can use a FOR EACH loop

// 3. Return the new subsequence.

private MyLinkedList copySubSeq (MyLinkedList subSeq)

{

// code todo

}

// Reverse the given subsequence using a stack

//

// The Algorithm:

// 1. Create a new LinkedList to hold the new subsequence

// 2. Create a Stack to use to do the reversing

// 3. Traverse the passed in LinkedList and place each

// Card on the Stack - Hint: You can use a FOR EACH loop

// 4. Loop through the Stack, popping off the Cards and

// adding them to the end of the new subsequence LinkedList

// 5. Return the new subsequence.

public MyLinkedList reverseSubSeq (MyLinkedList subSeq)

{

// code todo

}

}

public abstract class MyAbstractList> implements MyList { protected int size = 0; // The size of the list

protected MyAbstractList() { } // Create a default list

// Create a list from an array of objects protected MyAbstractList (E[] objects) { for (int i = 0; i < objects.length; i++) { add (objects[i]); } }

// Add a new element at the end of this list @Override public void add (E e) { add (size, e); }

// Return true if this list contains no elements @Override public boolean isEmpty() { return size == 0; }

// Return the number of elements in this list @Override public int size() { return size; }

// Remove the first occurrence of the element e // Shift any subsequent elements to the left. // Return true if the element is removed. @Override public boolean remove (E e) { if (indexOf (e) >= 0) { remove (indexOf(e)); return true; } else { return false; } } }

public class MyArrayList> extends MyAbstractList

{

public static final int INITIAL_CAPACITY = 16;

private E[] data = null;

public int capacity;

// Create a default list of 16 elements

public MyArrayList()

{

data = (E[]) new Comparable[INITIAL_CAPACITY]; // array

capacity = INITIAL_CAPACITY;

}

// Create a list of capacity elements

public MyArrayList (int capacity)

{

data = (E[]) new Comparable[capacity]; // array

}

// Create a list from an array of objects

public MyArrayList (E[] objects)

{

for (int i = 0; i < objects.length; i++)

{

add (objects[i]); // Warning: dont use super(objects)!

}

}

// Add a new element at the specified index

@Override

public void add (int index, E e)

{

// Doubles array, if not big enough

ensureCapacity();

// Move the elements to the right after the specified index

for (int i = size - 1; i >= index; i--)

{

data[i + 1] = data[i];

}

// Insert new element to data[index] and increase size

data[index] = e;

size++;

}

// Create a new larger array, double the current size + 1

private void ensureCapacity()

{

if (size >= data.length)

{

E[] newData = (E[]) (new Comparable[size * 2 + 1]);

System.arraycopy (data, 0, newData, 0, size);

data = newData;

}

}

// Return true if this list contains the element

@Override

public boolean contains (E e)

{

for (int i = 0; i < size; i++)

{

if (e.equals(data[i]))

{

return true;

}

}

return false;

}

// Return the element at the specified index

@Override

public E get (int index)

{

checkIndex (index);

return data[index];

}

// Throws IndexOutOfBoundsException, if needed

private void checkIndex (int index)

{

if (index < 0 || index >= size)

{

throw new IndexOutOfBoundsException

("Index: " + index + ", Size: " + size);

}

}

// Return the index of the first matching element

// Return -1 if no match.

@Override

public int indexOf(E e)

{

for (int i = 0; i < size; i++)

{

if (e.equals (data[i]))

{

return i;

}

}

return -1;

}

// Return the index of the last matching element

// Return -1 if no match.

@Override

public int lastIndexOf (E e)

{

for (int i = size - 1; i >= 0; i--)

{

if (e.equals (data[i]))

{

return i;

}

}

return -1;

}

// Remove the element at the specified position

// Shift any subsequent elements to the left.

// Return the element that was removed from the list.

@Override

public E remove(int index)

{

checkIndex (index);

E old = data[index];

// Shift data to the left

for (int j = index; j < size - 1; j++)

{

data[j] = data[j + 1];

}

data[size - 1] = null; // This element is now null

size--; // Decrement size

return old;

}

// Replace the element at the specified position

// with the specified element.

@Override

public E set (int index, E e)

{

checkIndex (index);

E old = data[index];

data[index] = e;

return old;

}

// Return a string representation of the array

@Override

public String toString()

{

StringBuilder result = new StringBuilder("[");

for (int i = 0; i < size; i++)

{

result.append (data[i]);

if (i < size - 1)

{

result.append (", ");

}

}

return result.toString() + "]";

}

// Trims the capacity of the array to the current size

// If size == capacity, no need to trim

public void trimToSize()

{

if (size != data.length)

{

E[] newData = (E[]) (new Comparable[size]);

System.arraycopy (data, 0, newData, 0, size);

data = newData;

}

}

// Clear the array: create a new empty one

@Override

public void clear()

{

data = (E[]) new Comparable[INITIAL_CAPACITY];

size = 0;

}

// Override iterator() defined in Iterable

@Override

public java.util.Iterator iterator()

{

return new ArrayListIterator();

}

// Private iterator class for myArrayList class

private class ArrayListIterator implements java.util.Iterator

{

private int current = 0; // Current index

// Return true when there are more elements past current

@Override

public boolean hasNext()

{

return(current < size);

}

// Return the element at current

@Override

public E next()

{

return data[current++];

}

// Remove the element at current

@Override

public void remove()

{

MyArrayList.this.remove(current);

}

}

}

public class MyLinkedList> extends MyAbstractList

implements Comparable>

{

private Node head, tail; // head and tail pointers

// Create a default list

public MyLinkedList()

{

}

// Need this for implementing Comparable

public int compareTo (MyLinkedList e)

{

return (size() - e.size());

}

// Create a list from an array of objects

public MyLinkedList (E[] objects)

{

super(objects); // Passes the array up to abstract parent

}

// Return the head element in the list

public E getFirst()

{

if (size == 0)

{

return null;

}

else

{

return head.element;

}

}

// Return the last element in the list

public E getLast()

{

if (size == 0)

{

return null;

}

else

{

return tail.element;

}

}

// Add an element to the beginning of the list

public void addFirst (E e)

{

// Create a new node for element e

Node newNode = new Node(e);

newNode.next = head; // link the new node with the head

head = newNode; // head points to the new node

size++; // Increase list size

if (tail == null) // new node is only node

{

tail = head;

}

}

// Add an element to the end of the list

public void addLast (E e)

{

// Create a new node for element e

Node newNode = new Node(e);

if (tail == null)

{

head = tail = newNode; // new node is only node

}

else

{

tail.next = newNode; // Link the new with the last node

tail = tail.next; // tail now points to the last node

}

size++; // Increase size

}

// Remove the head node and

// return the object from the removed node

public E removeFirst()

{

if (size == 0)

{

return null;

}

else

{

Node temp = head;

head = head.next;

size--;

if (head == null)

{

tail = null;

}

return temp.element;

}

}

// Remove the last node and return the object from it

public E removeLast()

{

if (size == 0)

{

return null;

}

else if (size == 1)

{

Node temp = head;

head = tail = null;

size = 0;

return temp.element;

}

else

{

Node current = head;

for (int i = 0; i < size - 2; i++)

{

current = current.next;

}

Node temp = tail;

tail = current;

tail.next = null;

size--;

return temp.element;

}

}

// Remove the element at the specified position

// Return the element that was removed from the list.

@Override

public E remove (int index)

{

if (index < 0 || index >= size)

{

return null;

}

else if (index == 0)

{

return removeFirst();

}

else if (index == size - 1)

{

return removeLast();

}

else

{

Node previous = head;

for (int i = 1; i < index; i++)

{

previous = previous.next;

}

Node current = previous.next;

previous.next = current.next;

size--;

return current.element;

}

}

// Return a String representation of the linked list elements

@Override

public String toString()

{

StringBuilder result = new StringBuilder("[");

Node current = head;

for (int i = 0; i < size; i++)

{

result.append (current.element);

current = current.next;

if (current != null)

{

result.append (", "); // Separate elements with a comma

}

else

{

result.append ("]"); // Insert the ] in the string

}

}

return result.toString();

}

// Clear the list

@Override

public void clear()

{

size = 0;

head = tail = null;

}

@Override

// Add a new element at specified index in this list

public void add(int index, E e)

{

if (index == 0)

{

addFirst (e);

}

else if (index == size)

{

addLast (e);

}

else

{

checkIndex (index);

// Create a new node for element e

Node newNode = new Node(e);

Node previous = head;

for (int i = 1; i < index; i++)

{

previous = previous.next;

}

newNode.next = previous.next;

previous.next = newNode;

size++; // Increase size

}

}

// Return true if this list contains the element e

@Override

public boolean contains(E e)

{

Node current = head;

while (current != null)

{

if (e.equals(current.element))

{

return true;

}

current = current.next;

}

return false;

}

// Return the element at the specified index

@Override

public E get (int index)

{

Node current = head;

for (int i = 0; i < index; i++)

{

current = current.next;

}

return current.element;

}

// Return the index of the first matching element

// Return -1 if no match

@Override

public int indexOf (E e)

{

Node current = head;

for (int i = 0; i < size; i++)

{

if (e.equals (current.element))

{

return i;

}

current = current.next;

}

return -1;

}

// Return the index of the last matching element

// Return -1 if no match.

@Override

public int lastIndexOf (E e)

{

int lastIndex = -1;

Node current = head;

for (int i = 0; i < size; i++)

{

if (e.equals (current.element))

{

lastIndex = i;

}

current = current.next;

}

return lastIndex;

}

// Replace the element at the specified position

// with the specified element

@Override

public E set (int index, E e)

{

Node current = head;

for (int i = 0; i < index; i++)

{

current = current.next;

}

E old = current.element;

current.element = e;

return old;

}

// Override iterator() defined in Iterable

@Override

public java.util.Iterator iterator()

{

return new LinkedListIterator();

}

// Throws IndexOutOfBoundsException, if needed

private void checkIndex (int index)

{

if (index < 0 || index >= size)

{

throw new IndexOutOfBoundsException

("Index: " + index + ", Size: " + size);

}

}

// The Node class

private static class Node

{

E element;

Node next;

public Node (E element)

{

this.element = element;

}

}

// Private iterator class for myArrayList class

private class LinkedListIterator implements java.util.Iterator

{

private Node current = head; // Current index

@Override

public boolean hasNext()

{

return(current != null);

}

@Override

public E next()

{

E e = current.element;

current = current.next;

return e;

}

@Override

public void remove()

{

MyLinkedList.this.remove (current.element);

}

}

}