public class Deck {
    Card[] cards;

    // basic constructor (allocates just the deck, no cards)
    public Deck (int n) {
	cards = new Card[n];
    }

    // buildDeck: allocates a 52-card deck and populates it with cards
    public static Deck buildDeck () {
	Deck deck = new Deck (52);

	int index = 0;
	for (int suit = 0; suit <= 3; suit++) {
	    for (int rank = 1; rank <= 13; rank++) {
		deck.cards[index] = new Card (suit, rank);
		index++;
	    }
	}
	return deck;
    }

    // printDeck: speaks for itself
    public static void printDeck (Deck deck) {
	for (int i=0; i<deck.cards.length; i++) {
	    Card.printCard (deck.cards[i]);
	}
    }

    // shuffleDeck: random permutation of the cards (swaps references)
    public static void shuffleDeck (Deck deck) {
	for (int i=0; i<deck.cards.length; i++) {
	    int j = randInt (i, deck.cards.length-1);
	    swapCards (deck, i, j);
	}
    }

    // randInt: returns a random number between low and high,
    // including both endpoints
    public static int randInt (int low, int high) {
	// the while loop is necessary to cover the
	// possibility that random returns exactly 1.0
	while (true) {
	    int x = (int)(Math.random() * (high-low+1) + low);
	    if (x >= low && x <= high) return x;
	} 
    }

    // sortDeck: this is the simple selection sort
    public static void sortDeck (Deck deck) {
	for (int i=0; i<deck.cards.length; i++) {
	    int j = findLowestCard (deck, i, deck.cards.length-1);
	    swapCards (deck, i, j);
	}
    }

    // swapCards: swaps the references to the cards, not the
    // contents of the cards
    public static void swapCards (Deck deck, int i, int j) {
	Card temp = deck.cards[i];
	deck.cards[i] = deck.cards[j];
	deck.cards[j] = temp;
    }

    // findLowestCard: traverses the given index range of the
    // deck and finds the card with the lowest rank
    public static int findLowestCard (Deck deck, int low, int high) {
	int winner = low;
	for (int i=low+1; i<=high; i++) {
	    if (Card.compareCards (deck.cards[i], deck.cards[winner]) < 0) {
		winner = i;
	    }
	}
	return winner;
    }

    // subDeck: allocates a new deck and copies references from
    // the given index range into it.  The cards are aliased by
    // the old and the new deck.
    public static Deck subdeck (Deck deck, int low, int high) {
	Deck sub = new Deck (high-low+1);
	
	for (int i = 0; i<sub.cards.length; i++) {
	    sub.cards[i] = deck.cards[low+i];
	}
	return sub;
    }

    // merge: takes two decks and merges them into a new deck.
    // the cards from the old decks are aliased by the new deck
    // precondition--the old decks must be sorted
    // postcondition--the new deck is sorted
    public static Deck merge (Deck d1, Deck d2) {
	// create the new deck
	Deck result = new Deck (d1.cards.length + d2.cards.length);
		
	int choice;    // records the winner (1 means d1, 2 means d2)
	int i = 0;     // traverses the first input deck
	int j = 0;     // traverses the second input deck
		
	// k traverses the new (merged) deck
	for (int k = 0; k<result.cards.length; k++) {
	    choice = 1;
			
	    // if d1 is empty, d2 wins; if d2 is empty, d1 wins; otherwise,
	    // compare the two cards
	    if (i == d1.cards.length)
		choice = 2;
	    else if (j == d2.cards.length)
		choice = 1;
	    else if (Card.compareCards (d1.cards[i], d2.cards[j]) == 1)
		choice = 2;
	    
	    // make the new deck refer to the winner card
	    if (choice == 1) {
		result.cards[k] = d1.cards[i];  i++;
	    } else {
		result.cards[k] = d2.cards[j];  j++;
	    }			
	}
	return result;
    }

    // mergeSort: takes a deck of cards and returns a new deck that
    // contains references to to the same set of cards, but in order
    public static Deck mergeSort (Deck deck) {
	// base case is a deck with one card
	if (deck.cards.length == 1) return deck;
	
	// divide the deck roughly in half
	int mid = deck.cards.length / 2;
	Deck d1 = subdeck (deck, 0, mid-1);
	Deck d2 = subdeck (deck, mid, deck.cards.length-1);
	
	// sort the halves 
	d1 = mergeSort (d1);
	d2 = mergeSort (d2);
		
	// merge the two halves and return the result
	// (d1 and d2 get garbage collected)
	return merge (d1, d2);
    }
}