//
//  main.cpp
//  randomizer
//
//  Created by Brandon on 8/16/16.
//  Copyright © 2016 Shogun3D. All rights reserved.
//

#include <iostream>
#include <map>
#include <vector>
#include <time.h>


/*
 * Name: get_unique_number_count
 * Desc: Returns the number of unique numbers generated from 100k numbers
 *       between 1 and 500k.
 */
int get_unique_number_count()
{
    // Seed the random number generator
    srand( (unsigned) time( NULL ) );

    // Hash map used to store random numbers
    std::map<int,int> numbers;
    int unique_numbers = 0;

    // Generate 100k random numbers and store their occurrences in the map
    for( int i = 0; i < 100000; i++ )
    {
        // Generate a number between 1 and 500000
        int n = 1+(rand()%499999);

        // Update the number of occurences of this particular number in the map
        // then save the number of the previous value to minimize the need to read
        // the hash map twice.
        int occurence = numbers[n]++;

        // If this number was never added to the list before, the value should be
        // zero and initially count it as a unique number.  If it was added before,
        // the value should be one as it was already counted, then subtract from the
        // number of unique numbers, essentially disqualifying it.
        if( occurence == 0 )
            unique_numbers++;
        else if( occurence == 1 )
            unique_numbers--;
    }

    return unique_numbers;
}


/*
 * Name: get_most_frequent_numbers
 * Desc: Returns the list of numbers most frequently generated out of
 *       100k numbers between 1 and 500k.
 */
void get_most_frequent_numbers( std::vector<int>& most_frequent )
{
    // Seed the random number generator
    srand( (unsigned) time( NULL ) );

    // Hash map used to store random numbers
    std::map<int,int> numbers;
    int highest_occurence = 2;

    // Generate 100k random numbers and store their occurrences in the map
    for( int i = 0; i < 100000; i++ )
    {
        // Generate a number between 1 and 500000
        int n = 1+(rand()%499999);

        // Update the number of occurences of this particular number in the map
        // then save the number of the previous value to minimize the need to read
        // the hash map twice.
        int occurence = ++numbers[n];

        // Save the number that has the highest occurence.  If the previous number has
        // been surpassed, then empty the vector of the previous number(s) and give
        // the new number priority.
        if( occurence > highest_occurence )
        {
            highest_occurence = occurence;
            most_frequent.clear();
            most_frequent.push_back(n);
        }
        // If this number is tied with the number of highest occurence, save it also.
        else if( occurence == highest_occurence )
        {
            most_frequent.push_back(n);
        }
    }
}

int main(int argc, const char * argv[]) {
    std::vector<int> mf;
    int un = get_unique_number_count();
    get_most_frequent_numbers( mf );

    std::cout << "Unique numbers: " << un << " out of 100000" << std::endl;
    std::cout << "Most frequent numbers: ";

    std::vector<int>::iterator i = mf.begin();
    while( i != mf.end() )
    {
        std::cout << (*i) << " ";
        ++i;
    }

    std::cout << std::endl;

    return 0;
}