public class Deck {
    Card[] cards;

    public Deck (int n) {
	cards = new Card[n];
    }

    public static void main (String[] args) {
	Deck deck = buildDeck ();
	shuffleDeck (deck);
	deck = mergeSort (deck);
	printDeck (deck);

	// create a weird card that's not in the deck
	Card card = new Card (1, 15);

	System.out.println (findBisect (deck, deck.cards[17], 0, 51));
	System.out.println (findBisect (deck, card, 0, 51));
    }

    public static int findCard (Deck deck, Card card) {
	for (int i = 0; i< deck.cards.length; i++) {
	    if (deck.cards[i].equals (card)) return i;
	}
	return -1;
    }

    public static int findBisect (Deck deck, Card card, int low, int high) {
	System.out.println (low + ", " + high);

	if (high < low) return -1;

	int mid = (high + low) / 2;
	int comp = Card.compareCards (deck.cards[mid], card);

	if (comp == 0) {
	    return mid;
	} else if (comp > 0) {
	    return findBisect (deck, card, low, mid-1);
	} else {
	    return findBisect (deck, card, mid+1, high);
	}
    }

    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;
    }

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

    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);
	}
    }

    public static int randInt (int low, int high) {
	while (true) {
	    int x = (int)(Math.random() * (high-low+1) + low);
	    if (x >= low && x <= high) return x;
	} 
    }

    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);
	}
    }

    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;
    }

    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;
    }

    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;
    }

  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;
  }
	
  public static Deck mergeSort (Deck deck) {
    if (deck.cards.length == 1) return deck;
    int mid = deck.cards.length / 2;

    // divide the deck roughly in half
    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);
  }
}


class Card
{
    int suit, rank;

    public Card () { 
	this.suit = 0;  this.rank = 0;
    }

    public Card (int suit, int rank) { 
	this.suit = suit;  this.rank = rank;
    }

    public static void printCard (Card c) {
	String[] suits = { "Clubs", "Diamonds", "Hearts", "Spades" };
	String[] ranks = { "narf", "Ace", "2", "3", "4", "5", "6",
			   "7", "8", "9", "10", "Jack", "Queen", "King" };

	System.out.println (ranks[c.rank] + " of " + suits[c.suit]);
    }

    public static int compareCards (Card c1, Card c2) {
	if (c1.suit > c2.suit) return 1;
	if (c1.suit < c2.suit) return -1;
	if (c1.rank > c2.rank) return 1;
	if (c1.rank < c2.rank) return -1;    
	return 0;
    }
	
    public static boolean sameCard (Card c1, Card c2) {
	return (c1.suit == c2.suit && c1.rank == c2.rank);
    }
}