/* This program demonstrates two different techniques of creating random
   integers without duplicates.  The first technique is a tree-based method
   designed to minimize the number of calls to the rand () function.  It is
   a tree based algorithm and is well suited when calls to rand () are
   computationally expensive or when there is a very large number of
   random numbers to generated.
   
   The second technique is simpler and uses a boolean array to keep track of what
   numbers have been selected already.  If a random number is generated that has
   occurred before, a new one is generated.  With very large arrays, there will be
   a lot of repeat random number generation, so the first technique tends to be more
   efficient for large sets, though the timings of the two techniques are much closer
   than I anticipated.  I had expected the first technique to vastly outperform the
   second on tasks like generating generating all numbers from 1 to 20,000 exactly once,
   but that doesn't appear to be the case.
   
   The example below is a much smaller example, shuffling playing cards, so you are only
   dealing with 52 numbers.
*/
 
#include <iostream>
#include <string>
#include <ctime>
#include <iomanip>
using namespace std;
 
struct node
{
    int value;    // radomly produced integer value
    node* left;   // pointer to right child
    node* right;  // pointer to left child
    int leftSize; // yourself + number of descendants in left tree
                  // keep track of this so you don't have to keep
                  // recalculating by traversing
};
 
void GenerateRandomIntegers1 (int min, int max, int* array, int arraySize);
void GenerateRandomIntegers2 (int min, int max, int* array, int arraySize);
void Display (int array[], int arraySize);
 
 
string card[] = {"Ace", "2", "3", "4", "5", "6", "7", "8", "9", "10",
                 "Jack", "Queen", "King"};
string suit[] = {"Spades", "Hearts", "Clubs", "Diamonds"};
 
 
int main ()
{
    srand (time (NULL));
 
    int min = 0;
    int max = 51;
    int arraySize = max - min + 1;
    int* array = new int[arraySize];
 
    cout << "First method - Shuffle\n\n";
    GenerateRandomIntegers1 (min, max, array, arraySize);    
    Display (array, arraySize);
    cout << "\n\nSecond method - Shuffle\n\n";
    GenerateRandomIntegers2 (min, max, array, arraySize);    
    Display (array, arraySize);
 
    cin.get ();  // pause screen    
    return 0;
}
 
 
void GenerateRandomIntegers1 (int min, int max, int array[], int arraySize)
// a tree-oriented method.  Random numbers never have to be regenerated.  Random
// number is generated out of a range of the number of empty slots remaining.
// If the number 3 is generated, the number selected will be 4th smallest
// (add 1 to 3 since 0 is smallest) as-of-yet-unpicked number.
// node->leftSize is the number of nodes less than that node that are children
// have been picked already (includes itself).  This is needed in order to know
// how much to adjust a random number. 
{     
     node* tempNodes = new node[arraySize];
     node* headNode = &tempNodes[0];
     int range = max - min + 1;
     headNode->value = rand () % range + min;
     headNode->left = NULL;
     headNode->right = NULL;
     headNode->leftSize = 1;
 
     array[0] = headNode->value;  // pick first/top node
     node* treeTop;
     node* nodeToInsert;
     bool inserted;     
 
     for (int i = 1; i < arraySize; i++)
     {
         range--;  // decrement random number range each time since one fewer
                   // value is available.
         tempNodes[i].leftSize = 1;
         tempNodes[i].left = NULL;
         tempNodes[i].right = NULL;
         int positionAmongUnpicked = rand () % range;
         // insert at positionAmongUnpicked spot in list of unpicked numbers.
         // (i.e. if remaining unpicked numbers are {6, 12, 14, 17, 20} and
         // positionAmongUnpicked is 3, the value will end up being 17).
         tempNodes[i].value = positionAmongUnpicked + min; 
         inserted = false;
         treeTop = headNode;
         nodeToInsert = &tempNodes[i];
 
         // insert node
         do
         {
             if (nodeToInsert->value + treeTop->leftSize > treeTop->value)
             // check whether to insert right or left
             {
                  // go right.  There are treeTop->leftSize smaller nodes already,
                  // so increment by that number.
                  nodeToInsert->value = nodeToInsert->value + treeTop->leftSize; 
                  if (treeTop->right == NULL)
                  {
                       treeTop->right = nodeToInsert;
                       inserted = true;
                  }
                  else
                      treeTop = treeTop->right;
             }
             else
             {
                 // go left
                 treeTop->leftSize++;
                 if (treeTop->left == NULL)
                 {
                      treeTop->left = nodeToInsert;
                      inserted = true;
                 }                
                 else
                      treeTop = treeTop->left;                
             }             
         }
         while (!inserted);
 
         array[i] = nodeToInsert->value; 
     } 
 
     delete []tempNodes; // clean by deleting nodes.
}
 
 
void GenerateRandomIntegers2 (int min, int max, int array[], int arraySize)
// this method will generate repeated random numbers.  boolean array
// keeps track of what numbers have been picked.  Generates another if
// this number has already been picked.
{
     int range = max - min + 1;
     bool* picked =  new bool[range];
     // initialize all to unpicked
     for (int i = 0; i < range; i++)
         picked[i] = false;
 
     int value;
 
     for (int i = 0; i < arraySize; i++)
     {
         value = rand () % range;
         if (picked[value])
             i--;  // already picked.  for-loop increments, so decrement here
         else
         {
             array[i] = value + min;
             picked[value] = true; // hasn't been picked yet.  Assign to array,
                                   // flag as picked.
         }
     }
 
     delete [] picked; // clean up. delete boolean array
}
 
 
void Display (int array[], int arraySize)
{
     for (int i = 0; i < arraySize; i++)
     {
         cout << left << setw(6) << card[array[i] % 13] << " of " <<
                 suit[array[i] % 4] << endl;
     }
}