Skip to content

Commit 97e5091

Browse files
AllenDowneyAllenDowney
committed
Adding code for chapters 13-14
1 parent c9b1805 commit 97e5091

File tree

10 files changed

+702
-0
lines changed

10 files changed

+702
-0
lines changed

‎ch13/Card.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
../ch12/Card.java

‎ch13/Deck.java

Lines changed: 197 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,197 @@
1+
import java.util.Arrays;
2+
import java.util.Random;
3+
4+
/**
5+
* A deck of playing cards (of fixed size).
6+
*/
7+
public class Deck {
8+
9+
// This is a class variable so we don't have to create
10+
// a new Random object every time we call randomInt.
11+
private static Random random = new Random();
12+
13+
private Card[] cards;
14+
15+
/**
16+
* Constructs a standard deck of 52 cards.
17+
*/
18+
public Deck() {
19+
this.cards = new Card[52];
20+
int index = 0;
21+
for (int suit = 0; suit <= 3; suit++) {
22+
for (int rank = 1; rank <= 13; rank++) {
23+
this.cards[index] = new Card(rank, suit);
24+
index++;
25+
}
26+
}
27+
}
28+
29+
/**
30+
* Constructs a deck of n cards (null).
31+
*/
32+
public Deck(int n) {
33+
this.cards = new Card[n];
34+
}
35+
36+
/**
37+
* Gets the internal cards array.
38+
*/
39+
public Card[] getCards() {
40+
return this.cards;
41+
}
42+
43+
/**
44+
* Returns a string representation of the deck.
45+
*/
46+
public String toString() {
47+
return Arrays.toString(this.cards);
48+
}
49+
50+
/**
51+
* Swaps the cards at indexes i and j.
52+
*/
53+
public void swapCards(int i, int j) {
54+
Card temp = this.cards[i];
55+
this.cards[i] = this.cards[j];
56+
this.cards[j] = temp;
57+
}
58+
59+
/**
60+
* Chooses a random number between low and high, including both.
61+
*/
62+
public int randomInt(int low, int high) {
63+
int range = high - low + 1;
64+
return low + random.nextInt(range);
65+
}
66+
67+
/**
68+
* Randomly permutes the array of cards.
69+
*/
70+
public void shuffle() {
71+
for (int i = 0; i < this.cards.length - 1; i++) {
72+
int j = this.randomInt(i, this.cards.length - 1);
73+
this.swapCards(i, j);
74+
}
75+
}
76+
77+
/**
78+
* Finds the index of the lowest card
79+
* between low and high inclusive.
80+
*/
81+
public int indexLowest(int low, int high) {
82+
int index = low;
83+
Card minCard = this.cards[low];
84+
for (int i = low + 1; i <= high; i++) {
85+
Card card = this.cards[i];
86+
if (card.compareTo(minCard) < 0) {
87+
index = i;
88+
minCard = card;
89+
}
90+
}
91+
return index;
92+
}
93+
94+
/**
95+
* Sorts the cards (in place) using selection sort.
96+
*/
97+
public void selectionSort() {
98+
int high = this.cards.length - 1;
99+
for (int i = 0; i < this.cards.length; i++) {
100+
int j = this.indexLowest(i, high);
101+
this.swapCards(i, j);
102+
}
103+
}
104+
105+
/**
106+
* Returns a subset of the cards in the deck.
107+
*/
108+
public Deck subdeck(int low, int high) {
109+
Deck sub = new Deck(high - low + 1);
110+
for (int i = 0; i < sub.cards.length; i++) {
111+
sub.cards[i] = this.cards[low + i];
112+
}
113+
return sub;
114+
}
115+
116+
/**
117+
* Combines two previously sorted subdecks.
118+
*/
119+
public static Deck merge(Deck d1, Deck d2) {
120+
Card[] c1 = d1.cards;
121+
Card[] c2 = d2.cards;
122+
Deck result = new Deck(c1.length + c2.length);
123+
Card[] c3 = result.cards;
124+
int i = 0; // index in c1
125+
int j = 0; // index in c2
126+
127+
// for each index in the result
128+
for (int k = 0; k < c3.length; k++) {
129+
int choice;
130+
131+
// determine which card to merge next
132+
if (i >= c1.length) {
133+
choice = 2; // c1 is empty
134+
} else if (j >= c2.length) {
135+
choice = 1; // c2 is empty
136+
} else if (c1[i].compareTo(c2[j]) < 0) {
137+
choice = 1; // c1 is lower
138+
} else {
139+
choice = 2; // c2 is lower
140+
}
141+
142+
// store the chosen card in the result
143+
if (choice == 1) {
144+
c3[k] = c1[i];
145+
i++;
146+
} else {
147+
c3[k] = c2[j];
148+
j++;
149+
}
150+
}
151+
return result;
152+
}
153+
154+
/**
155+
* Returns a sorted copy of the deck using merge sort.
156+
*/
157+
public Deck mergeSort() {
158+
159+
// 0 or 1 cards, already sorted
160+
int len = this.cards.length;
161+
if (len < 2) {
162+
return this;
163+
}
164+
165+
// cut the deck about in half
166+
int mid = len / 2;
167+
Deck d1 = this.subdeck(0, mid - 1);
168+
Deck d2 = this.subdeck(mid, len - 1);
169+
170+
// sort each half and merge
171+
d1 = d1.mergeSort();
172+
d2 = d2.mergeSort();
173+
return merge(d1, d2);
174+
}
175+
176+
/**
177+
* Reorders the cards (in place) using insertion sort.
178+
*/
179+
public void insertionSort() {
180+
for (int i = 1; i < this.cards.length; i++) {
181+
Card card = this.cards[i];
182+
this.insert(card, i);
183+
}
184+
}
185+
186+
/**
187+
* Helper method for insertion sort.
188+
*/
189+
private void insert(Card card, int i) {
190+
int j = i;
191+
while (j > 0 && card.compareTo(this.cards[j - 1]) < 0) {
192+
this.cards[j] = this.cards[j - 1];
193+
j--;
194+
}
195+
this.cards[j] = card;
196+
}
197+
}

‎ch13/Test.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
/**
2+
* Test sorting algorithms for decks of cards.
3+
*/
4+
public class Test {
5+
6+
/**
7+
* Checks that the deck is sorted.
8+
*/
9+
public static void checkSorted(Deck deck) {
10+
Card[] cards = deck.getCards();
11+
for (int i = 0; i < cards.length - 1; i++) {
12+
if (cards[i].compareTo(cards[i + 1]) >= 0) {
13+
System.out.println("Card #" + i + " not sorted!");
14+
}
15+
}
16+
}
17+
18+
/**
19+
* Demonstrates how to call the sorting methods.
20+
*/
21+
public static void main(String[] args) {
22+
Deck deck;
23+
24+
System.out.println("Testing selection...");
25+
deck = new Deck();
26+
deck.shuffle();
27+
deck.selectionSort();
28+
checkSorted(deck);
29+
30+
System.out.println("Testing mergesort...");
31+
deck = new Deck();
32+
deck.shuffle();
33+
deck = deck.mergeSort();
34+
checkSorted(deck);
35+
36+
System.out.println("Testing insertion...");
37+
deck = new Deck();
38+
deck.shuffle();
39+
deck.insertionSort();
40+
checkSorted(deck);
41+
}
42+
}

‎ch14/Card.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
../ch12/Card.java

‎ch14/CardCollection.java

Lines changed: 129 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,129 @@
1+
import java.util.ArrayList;
2+
import java.util.Random;
3+
4+
/**
5+
* A collection of playing cards.
6+
*/
7+
public class CardCollection {
8+
9+
private String label;
10+
private ArrayList<Card> cards;
11+
12+
/**
13+
* Constructs an empty collection.
14+
*/
15+
public CardCollection(String label) {
16+
this.label = label;
17+
this.cards = new ArrayList<Card>();
18+
}
19+
20+
/**
21+
* Returns the label.
22+
*/
23+
public String getLabel() {
24+
return label;
25+
}
26+
27+
/**
28+
* Returns the number of cards.
29+
*/
30+
public int size() {
31+
return cards.size();
32+
}
33+
34+
/**
35+
* True if the collection is empty, false otherwise.
36+
*/
37+
public boolean empty() {
38+
return cards.size() == 0;
39+
}
40+
41+
/**
42+
* Randomly permute the cards.
43+
*/
44+
public void shuffle() {
45+
Random random = new Random();
46+
for (int i = size() - 1; i > 0; i--) {
47+
int j = random.nextInt(i);
48+
swapCards(i, j);
49+
}
50+
}
51+
52+
/**
53+
* Swaps the cards at indexes i and j.
54+
*/
55+
public void swapCards(int i, int j) {
56+
Card temp = cards.get(i);
57+
cards.set(i, cards.get(j));
58+
cards.set(j, temp);
59+
}
60+
61+
/**
62+
* Moves n cards from this collection to the given collection.
63+
*/
64+
public void deal(CardCollection that, int n) {
65+
for (int i = 0; i < n; i++) {
66+
Card card = popCard();
67+
that.addCard(card);
68+
}
69+
}
70+
71+
/**
72+
* Moves all remaining cards to the given collection.
73+
*/
74+
public void dealAll(CardCollection that) {
75+
int n = size();
76+
deal(that, n);
77+
}
78+
79+
/**
80+
* Adds the given card to the collection.
81+
*/
82+
public void addCard(Card card) {
83+
cards.add(card);
84+
}
85+
86+
/**
87+
* Returns the card with the given index.
88+
*/
89+
public Card getCard(int i) {
90+
return cards.get(i);
91+
}
92+
93+
/**
94+
* Returns the last card.
95+
*/
96+
public Card last() {
97+
int i = size() - 1;
98+
return cards.get(i);
99+
}
100+
101+
/**
102+
* Removes and returns the card with the given index.
103+
*/
104+
public Card popCard(int i) {
105+
return cards.remove(i);
106+
}
107+
108+
/**
109+
* Removes and returns the last card.
110+
*/
111+
public Card popCard() {
112+
int i = size() - 1;
113+
return popCard(i);
114+
}
115+
116+
/**
117+
* Returns a string representation of the card collection.
118+
*/
119+
public String toString() {
120+
return label + ": " + cards.toString();
121+
}
122+
123+
/**
124+
* Gets the internal cards array (should only be used for testing).
125+
*/
126+
public Card[] getCards() {
127+
return (Card[]) cards.toArray();
128+
}
129+
}

‎ch14/Deck.java

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
/**
2+
* A deck of playing cards.
3+
*/
4+
public class Deck extends CardCollection {
5+
6+
/**
7+
* Constructs a standard deck of 52 cards.
8+
*/
9+
public Deck(String label) {
10+
super(label);
11+
12+
for (int suit = 0; suit <= 3; suit++) {
13+
for (int rank = 1; rank <= 13; rank++) {
14+
addCard(new Card(rank, suit));
15+
}
16+
}
17+
}
18+
}

0 commit comments

Comments
 (0)