CSC300: Lecture 8 (Elementary Sorts, Objects as Data: Comparable, Objects as Functions: Comparator (1.2, 2.1, 2.5))

Contents [0/6]

Homework [1/6]
XSortCards0 [2/6]
XCardSimple [3/6]
XSortCards1 [4/6]
XCard [5/6]
XSortCards2 [6/6]

Homework [1/6]

XSortCards0 [2/6]

file:XSortCards0.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package algs21;
import stdlib.*;
import java.util.Comparator;

public class XSortCards0 {
  public static void show (String[] d) {
    for (int i=0; i<4; i++) {
      for (int j=0; j<13; j++) {
        StdOut.format ("%3s ", d[i*13+j]);
      }
      StdOut.println ();
    }
    StdOut.println ();
  }
  private static class CardComparator implements Comparator<String> {
    private static char suit (String s) {
      return s.charAt (s.length () - 1);
    }
    private static int rank (String s) {
      char rank = s.charAt (0);
      switch (rank) {
      case '1' : return 10;
      case 'J' : return 11;
      case 'Q' : return 12;
      case 'K' : return 13;
      case 'A' : return 14;
      default: return rank - '0';
      }
    }
    public int compare (String c1, String c2) {
      if (rank(c1) < rank(c2)) return -1;
      if (rank(c1) > rank(c2)) return +1;
      if (suit(c1) < suit(c2)) return -1;
      if (suit(c1) > suit(c2)) return +1;

      return 0;
    }
  }
  public static void main (String[] args) {
    String[] d =  {
        "2C", "3C", "4C", "5C", "6C", "7C", "8C", "9C", "10C", "JC", "QC", "KC", "AC",
        "2D", "3D", "4D", "5D", "6D", "7D", "8D", "9D", "10D", "JD", "QD", "KD", "AD",
        "2H", "3H", "4H", "5H", "6H", "7H", "8H", "9H", "10H", "JH", "QH", "KH", "AH",
        "2S", "3S", "4S", "5S", "6S", "7S", "8S", "9S", "10S", "JS", "QS", "KS", "AS" };
    show (d);
    StdRandom.shuffle (d);
    show (d);
    Insertion.sort (d);
    show (d);
    Insertion.sort (d, new CardComparator ());
    show (d);


    String c1 = "@E";
    d[0] = c1;
    StdRandom.shuffle (d);
    Insertion.sort (d, new CardComparator ());
    show (d);


  }
}

XCardSimple [3/6]

file:XCardSimple.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package algs12;
import stdlib.*;

public class XCardSimple implements Comparable<XCardSimple> {
  public static enum Rank { TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING, ACE }
  public static enum Suit { CLUBS, DIAMONDS, HEARTS, SPADES }

  public final Rank rank;
  public final Suit suit;
  public XCardSimple (Rank r, Suit s) { this.rank = r; this.suit = s; }
  public String toString () { return rank + " of " + suit; }
  public int compareTo (XCardSimple that) {
    if (this.suit.compareTo (that.suit) < 0) return -1;
    if (this.suit.compareTo (that.suit) > 0) return +1;
    if (this.rank.compareTo (that.rank) < 0) return -1;
    if (this.rank.compareTo (that.rank) > 0) return +1;
    return 0;
  }
  public boolean equals (Object that) {
    if (that == null)
      return false;
    if (this.getClass() != that.getClass())
      return false;
    // This does the right thing but is inefficient.
    // Since equals may be used more than compareTo, there is usually a separate implementation.
    return 0 == this.compareTo ((XCardSimple) that);
  }

  public static void main (String[] args) {
    Suit s1 = Suit.CLUBS;
    //Suit s2 = new Suit();

    XCardSimple c1 = new XCardSimple(Rank.ACE, Suit.SPADES);
    XCardSimple c2 = new XCardSimple(Rank.ACE, Suit.SPADES);
    StdOut.println (c1 + (c1.equals(c2) ? " equals " : " does not equal ") + c2);
  }
}

XSortCards1 [4/6]

file:XSortCards1.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package algs21;
import stdlib.*;
import algs12.XCard;

public class XSortCards1 {
  public static void show (XCard[] d) {
    for (int i=0; i<4; i++) {
      for (int j=0; j<13; j++) {
        StdOut.format ("%3s ", d[i*13+j]);
      }
      StdOut.println ();
    }
    StdOut.println ();
  }
  public static void main (String[] args) {
    XCard[] d = XCard.newDeck ();
    show (d);
    StdRandom.shuffle (d);
    show (d);
    Insertion.sort (d);
    show (d);
  }
}

XCard [5/6]

file:XCard.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package algs12;
import stdlib.*;

public class XCard implements Comparable<XCard> {
  public static enum Rank {
    TWO("2"),
    THREE("3"),
    FOUR("4"),
    FIVE("5"),
    SIX("6"),
    SEVEN("7"),
    EIGHT("8"),
    NINE("9"),
    TEN("10"),
    JACK("J"),
    QUEEN("Q"),
    KING("K"),
    ACE("A");

    private final String name;
    private Rank (String name) { this.name = name; }
    public String toString () { return name; }
  }
  public static enum Suit {
    CLUBS("C"),
    DIAMONDS("D"),
    HEARTS("H"),
    SPADES("S");

    private final String name;
    private Suit (String name) { this.name = name; }
    public String toString () { return name; }
  }

  public final Rank rank;
  public final Suit suit;
  private XCard (Rank r, Suit s) { this.rank = r; this.suit = s; }
  public String toString () { return rank.toString () + suit.toString (); }
  public int compareTo (XCard that) {
    if (this.suit.compareTo (that.suit) < 0) return -1;
    if (this.suit.compareTo (that.suit) > 0) return +1;
    if (this.rank.compareTo (that.rank) < 0) return -1;
    if (this.rank.compareTo (that.rank) > 0) return +1;
    return 0;
  }

  private static XCard[] protoDeck = new XCard[52];
  static { // This is how you run a loop to initialize a static variable.
    int i = 0;
    for (Suit s : Suit.values ())
      for (Rank r : Rank.values ()) {
        protoDeck[i] = new XCard (r, s);
        i++;
      }
  }
  public static XCard[] newDeck () {
    XCard[] deck = new XCard[protoDeck.length];
    for (int i = 0; i<protoDeck.length; i++)
      deck[i] = protoDeck[i];
    return deck;
  }

  public static void main (String[] args) {
    XCard[] d1 = XCard.newDeck ();  final XCard c1 = d1[51];
    XCard[] d2 = XCard.newDeck ();  final XCard c2 = d2[51];
    StdOut.println (c1 + (c1.equals(c2) ? " equals " : " does not equal ") + c2);
  }
}

XSortCards2 [6/6]

file:XSortCards2.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package algs21;
import stdlib.*;
import algs12.XCard;
import java.util.Comparator;

public class XSortCards2 {
  public static void show (XCard[] d) {
    for (int i=0; i<4; i++) {
      for (int j=0; j<13; j++) {
        StdOut.format ("%3s ", d[i*13+j]);
      }
      StdOut.println ();
    }
    StdOut.println ();
  }
  private static class RankFirstComparator implements Comparator<XCard> {
    public int compare (XCard c1, XCard c2) {
      if (c1.rank.compareTo (c2.rank) < 0) return -1;
      if (c1.rank.compareTo (c2.rank) > 0) return +1;
      if (c1.suit.compareTo (c2.suit) < 0) return -1;
      if (c1.suit.compareTo (c2.suit) > 0) return +1;
      return 0;
    }
  }
  public static void main (String[] args) {
    XCard[] d = XCard.newDeck ();
    show (d);
    StdRandom.shuffle (d);
    show (d);
    Insertion.sort (d);
    show (d);
    Insertion.sort (d, new RankFirstComparator ());
    show (d);
  }
}

Revised: 2008/03/17 13:01