Ch14 G1

//Gheorghe and Yeon-Soo

class Deck {
    Card[] cards;
    public Deck(int n) {
        this.cards = new Card[n];
    }
    public Deck() {
        this.cards = new Card [52];
    int index = 0;
    for (int suit = 0; suit <= 3; suit++) {
        for (int rank = 1; rank <= 13; rank++) {
        this.cards[index] = new Card(suit, rank);
        index++;
        }
    }
    }
    public static void printDeck(Deck deck) {
    for (int i=0; i<deck.cards.length; i++) {
        Card.printCard(deck.cards[i]);
    }
    }

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

    public static int findBisect(Deck deck, Card card, int low, int high) {
    if (high < low) return -1;
    int mid = (high + low) / 2;
    int comp = Card.compareCards(card, deck.cards[mid]);
    if (comp == 0) {
        return mid;
    } else if (comp < 0) {
        // card is less than deck.cards[mid]; search the first half
        return findBisect(deck, card, low, mid-1);
    } else {
        return findBisect(deck, card, mid+1, high);
    }
    }

    public static int randomInt(int low, int high){
    return (int)(low + (high - low) * Math.random());
    }

    public static void swapCards(Deck deck, int i, int j){
        Card card = new Card();
        card = deck.cards[i];
        deck.cards[i] = deck.cards[j];
        deck.cards[j] = card;
    }

    public static int indexLowestCard(Deck deck, int lowIndex, int highIndex){
        int result = lowIndex;
        for(int i = lowIndex; i < highIndex; i++){
            if(Card.compareCards(deck.cards[result], deck.cards[i]) > 0) result = i;
        }
        return result;
    }

    public static void shuffleDeck(Deck deck){
        for(int i = 0; i < deck.cards.length; i++) {
            swapCards(deck, i, randomInt(i, deck.cards.length - 1));
        }
    }

    /*
     * Sorts a deck from low to high.
     */
    public static void sortDeck(Deck deck){
        for(int i = 0; i < deck.cards.length; i++){
            swapCards(deck, i, indexLowestCard(deck, i, deck.cards.length));
        }
    }

    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) {
        Deck result = new Deck (d1.cards.length + d2.cards.length);
        int flag;
        for(int i = 0, j = 0, k = 0; k < result.cards.length; k++) {
            flag = 1;
            if (i == d1.cards.length)
                flag = 2;
            else if (j == d2.cards.length)
                flag = 1;
            else if (Card.compareCards(d1.cards[i], d2.cards[j]) > 0)
                flag = 2;

            if (flag == 1) {
                result.cards[k] = d1.cards[i];  i++;
            } else {
                result.cards[k] = d2.cards[j];  j++;
            }
        }
        return result;
    }

    public static Deck mergeSort(Deck deck) {
        Deck a = Deck.subdeck(deck, 0, deck.cards.length/2);
        Deck b = Deck.subdeck(deck, deck.cards.length/2, deck.cards.length - 1);
        sortDeck(a);
        sortDeck(b);

        deck = merge(a, b);
        return deck;
    }
    public static Deck recMergeSort(Deck deck){
        if(deck.cards.length <= 1) return deck;

        Deck a = subdeck(deck, 0, (deck.cards.length-1) / 2);
        Deck b = subdeck(deck, (deck.cards.length-1) / 2 + 1, deck.cards.length - 1);
        a = mergeSort(a);
        b = mergeSort(b);
        return merge(a, b);
    }
}