public class cs151 {

  public static void main (String[] args) {
    Card[] deck = Card.buildDeck ();
    Card.shuffleDeck (deck);
    Card.sortDeck (deck);
    Card.printDeck (deck);

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

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

class Card
{
  public 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);
  }

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

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

    if (high < low) return -1;

    int mid = (high + low) / 2;
    int comp = compareCards (deck[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 Card[] buildDeck () {
    Card[] deck = new Card [52];

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

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

  public static void shuffleDeck (Card[] deck) {
    for (int i=0; i<deck.length; i++) {
      int j = randInt (i, deck.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 (Card[] deck) {
    for (int i=0; i<deck.length; i++) {
      int j = findLowestCard (deck, i, deck.length-1);
      swapCards (deck, i, j);
    }
  }

  public static void swapCards (Card[] deck, int i, int j) {
    Card temp = deck[i];
    deck[i] = deck[j];
    deck[j] = temp;
  }

  public static int findLowestCard (Card[] deck, int low, int high) {
    int winner = low;
    for (int i=low+1; i<=high; i++) {
      if (compareCards (deck[i], deck[winner]) < 0) {
        winner = i;
      }
    }
    return winner;
  }

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