4.5: Subdecks

Last updated
Save as PDF

Page ID: 15295

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

The first step of merge sort is to split the deck into two subdecks, each with about half the cards. So we might want a method, subdeck, that takes a deck and a range of indexes. It returns a new deck that contains the specified subset of the cards:

public Deck subdeck(int low, int high) {
    Deck sub = new Deck(high - low + 1);
    for (int i = 0; i < sub.cards.length; i++) {
        sub.cards[i] = this.cards[low + i];
    }
    return sub;
}

The first line creates an unpopulated subdeck. Inside the for loop, the subdeck gets populated with copies of references from the deck.

The length of the subdeck is high - low + 1, because both the low card and the high card are included. This sort of computation can be confusing, and forgetting the + 1 often leads to “off-by-one” errors. Drawing a picture is usually the best way to avoid them.

Figure 13.5.1 is a state diagram of a subdeck with low = 0 and high = 4. The result is a hand with five cards that are shared with the original deck; that is, they are aliased.

State diagram showing the effect of subdeck. — Figure \(\PageIndex{1}\): State diagram showing the effect of `subdeck`.

Aliasing might not be a good idea, because changes to shared cards would be reflected in multiple decks. But since Card objects are immutable, this kind of aliasing is not a problem at all.