// ---------------------------------------------------------------
// --- Demonstrates the Card Shuffling Algorithm
// --- 
// --- Test Results: (using time <exe>)
// ---    With generation of Ordered Deck each time -> 0.28 for 10000 decks
// ---    With memcpy gen of Ordered Deck each time -> 0.27 for 10000 decks
// ---------------------------------------------------------------

#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>      // for srand() and rand()

const int dump_deck = 0;       // set to 1 to see deck info
const int dump_gen_deck = 0;   // set to 1 to see sorted deck info
const int dump_to_file = 0;    // set to 1 to see deck by number

const int do_analysis = 1;
const int style1 = 0;

// const int shuffles = 10;
const int shuffles = 520000;
// const int shuffles = 10400000;


// --- Demonstrate the "Card Shuffling" algorithm

typedef char Cards;  // -- since 1-11  can safely be held in 8 bits
const int MIN_CARD = 0;
const int MAX_CARD = 51;

const int MAX_CARDS_IN_DECK = MAX_CARD + 1;

const int MAX_SUIT = 4;    // 4 suits
const int MAX_FACE = 13;   // 13 cards per suit

char SuitMask [MAX_SUIT] = { 'S', 'H', 'D', 'C' };
Cards CardValue [MAX_FACE] = 
        { 11, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 10, 10 }; 
char CardFace [MAX_FACE] = 
        { 'A', '2', '3', '4', '5', '6', '7',
          '8', '9', 'T', 'J', 'Q', 'K' };

typedef struct tag_NamedDeckStruct
{
  char card_id [3];   // [1-9,J,Q,K] [S,H,D,C] [/0]  ie a card string
  Cards card_val;      // 1 to 10 (NOTE: Aces are special)
} NamedDeckStruct; 

typedef struct tag_CardDeck
{
  int CardArray [MAX_CARDS_IN_DECK];   // index into m_NDSBaseDeck
  int NextCard;                   // the next card IN deck
} CardDeck;



// -----------------------------------------------------------------------
main ()
{
  // --- Define master card list (make sure initialization loads it)
  // --- There are undoubtedly structure dependencies...
  NamedDeckStruct m_NDSBaseDeck [MAX_CARDS_IN_DECK];

  int card;
  int suit;
  int index;

  // --- Generate A LOT of decks and store card frequencies
  // --- first index is for card location, second is for value at that location
  int CardsDealt [MAX_CARDS_IN_DECK][MAX_CARDS_IN_DECK];
  int card_loc, card_value;

  for (card_loc = 0; card_loc < MAX_CARDS_IN_DECK; card_loc++) {
    for (card_value = 0; card_value < MAX_CARDS_IN_DECK; card_value++) {
      CardsDealt [card_loc][card_value] = 0;
    }
  }

  // ---- First Initialize
  index = 0;    // -- which card we are loading
  for (card = 0; card < MAX_FACE; card++) {
    if (dump_deck) {
      cout << "Setting card " << card << " with value ";
      cout << (int) CardValue[card] << endl;
    }

    for (suit = 0; suit < MAX_SUIT; suit++) {
      m_NDSBaseDeck[index].card_val = CardValue[card];
      m_NDSBaseDeck[index].card_id[0] = CardFace[card];
      m_NDSBaseDeck[index].card_id[1] = SuitMask[suit];
      m_NDSBaseDeck[index].card_id[2] = '\0';     // -- null terminate

      index++;   // --- increment to NEXT card
    }
  }
  if (dump_deck) {
    cout << " ==== DUMP CARDS ===" << endl;
    for (index = 0; index < (MAX_SUIT * MAX_FACE); index++) {
      cout << "Card " << index << " -- " <<  m_NDSBaseDeck[index].card_id;
      cout << "  - with value of " << (int) m_NDSBaseDeck[index].card_val << endl;
    }
  }

  // -- Set seed for the random # generator
//  srand (1234567); 
  srand (1234568); 
  // -- In real life:   srand(time(NULL) + getpid() * passed in seed?); 
  // --- Now generate a deck (randomly)
  CardDeck MasterOrderedDeck;
  CardDeck ShuffledDeck;  

  int card_index;
  for (card_index = MIN_CARD; card_index <= MAX_CARD; card_index++) {
     MasterOrderedDeck.CardArray[card_index] = card_index;
  }
  MasterOrderedDeck.NextCard = -100;


  cout << "Starting to shuffle " << shuffles << " decks " << endl;
  for (int decks_gen = 0; decks_gen < shuffles; decks_gen++) {

    // --- Copy the MasterOrderedDeck over the OrderedDeck
    memcpy (&ShuffledDeck, &MasterOrderedDeck, sizeof(CardDeck));

    if (dump_gen_deck) {
      for (card_index = MIN_CARD; card_index <= MAX_CARD; card_index++) {
        cout << ShuffledDeck.CardArray[card_index] << endl;
      }
      cout << "------------" << endl;
    }

    int new_index;
    int counter = 0; 
    int temp_card;

    // --- Do the algorithm CORRECTLY

    for (card_index = MAX_CARD; card_index >= MIN_CARD; card_index--) 
    {
      // -- generate a new random card location 
      // --- from our location down
      new_index = rand() % (card_index + 1);
      if ((MIN_CARD > new_index) || (MAX_CARD < new_index)) {
        cout << "Bad Index generated? " << new_index << endl;
      }

      // -- swap cards
      temp_card = ShuffledDeck.CardArray[card_index];
      ShuffledDeck.CardArray[card_index] = 
               ShuffledDeck.CardArray[new_index];
      ShuffledDeck.CardArray[new_index] = temp_card;
    }

    if (dump_to_file) {
       // --- Dump cards to file
       for (card_index = MIN_CARD; card_index <= MAX_CARD; card_index++) {
          cout << ShuffledDeck.CardArray[card_index] << " ";
       }
       cout << endl;
    }

    if (dump_gen_deck) {
      for (card_index = MIN_CARD; card_index <= MAX_CARD; card_index++) {
        cout << ShuffledDeck.CardArray[card_index] << endl;
      }
    } 

    // --- Mark which cards actually ended up where
    for (card_loc = 0; card_loc < MAX_CARDS_IN_DECK; card_loc++) {
       CardsDealt [card_loc][ShuffledDeck.CardArray[card_loc]]++;
    }
    
  }   // --- End of generating LOTS of DECKS

  // --- Now dump results of Deals
  int cards_dealt;

  for (card_loc = 0; card_loc < MAX_CARDS_IN_DECK; card_loc++) {
     
    cards_dealt = 0;
   
    for (card_value = 0; card_value < MAX_CARDS_IN_DECK; card_value++) {
      cards_dealt += CardsDealt [card_loc][card_value]; 
    }

    // --- Check for incompletely dealt rows
    if (cards_dealt != shuffles) {
      cout << "ERROR: Row " << card_loc << " had " << cards_dealt << endl;
    }
  }

  if (do_analysis) {
    // --- We will see what happens in a given location:
    int expected_cards = shuffles / MAX_CARDS_IN_DECK; 
    int flag_error = (int) (expected_cards * 0.03);     // -- allow 3% error
    int flag_error_inv = -flag_error;
    int the_delta = 0;
    cout << "There should be " << expected_cards << " per hand" << endl;
    for (card_loc = 0; card_loc < MAX_CARDS_IN_DECK; card_loc++) {
      for (card_value = 0; card_value < MAX_CARDS_IN_DECK; card_value++) {
        the_delta = CardsDealt[card_loc][card_value] - expected_cards;
        if (style1) {
          cout << setw (3) << card_value << " : ";
          cout << setw (7) << CardsDealt[card_loc][card_value] << " -- ";
          cout << setw (7) << the_delta;
          if ((the_delta > flag_error) || (the_delta < flag_error_inv)) {
             cout << "  ***";
          } 
          cout << endl;
        }
        else {
          if ((the_delta > flag_error) || (the_delta < flag_error_inv)) {
            cout << setw(2) << card_loc << " : ";
            cout << setw(2) << card_value << "  -- ";
            cout << setw (7) << the_delta << endl;
          }
        }
      }
    } 
  }

/* ----------------------------------- TESTS RANDOM GENERATION
  int DeckCount[MAX_CARDS_IN_DECK];
  for (card_index = MIN_CARD; card_index <= MAX_CARD; card_index++) {
    DeckCount [card_index] = 0;
  }

  for (int ix = 0; ix < 104000; ix++) {
    new_index = rand() % (MAX_CARDS_IN_DECK);
    if ((new_index >= 0) && (new_index < MAX_CARDS_IN_DECK)) {
      DeckCount[new_index]++;
    }
  }
 
  for (card_index = MIN_CARD; card_index <= MAX_CARD; card_index++) {
    cout << card_index << " - " << DeckCount [card_index] << endl; 
  }
-------------------------------------------------- */ 
}