//
//  hw3.h
//  project3
//
//  Created by Joel Hayashi on 2019/05/02.
//  Copyright © 2019 Joel Hayashi. All rights reserved.
//
//  Joel Hayashi
//  May 6, 2019
//
//  Program implements the file average_complexity ( int ) which does a linear search for a random number in a vector of ints that are randomly aligned and returns a double which indicates the average running time of the linear search based on its number of comparisons
//
//
//  This program has a running time of T = O ( N^2 ), theoretically. Experimentally, it has a running time of T = O ( N )

#ifndef hw3_h
#define hw3_h

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>


/**template< class RandomIt >                               //This is the implementation of std::random_shuffle from the internet...only one for loop so theoretically, O ( N )
 void random_shuffle( RandomIt first, RandomIt last )
 {
 typename std::iterator_traits<RandomIt>::difference_type i, n;
 n = last - first;
 for (i = n-1; i > 0; --i) {
 using std::swap;
 swap(first[i], first[std::rand() % (i+1)]);
 // rand() % (i+1) isn't actually correct, because the generated number
 // is not uniformly distributed for most values of i. A correct implementation
 // will need to essentially reimplement C++11 std::uniform_int_distribution,
 // which is beyond the scope of this example.
 }
 }
 */

double average_complexity( int x ){
    std::vector<int> randomVector;

    double prevRunningTime = 0.0;            //For comparison purposes
    double avgRunningTime = 0.0;

    for (int i = 1; i <= x; i++){randomVector.push_back(i);}     //Line up all numbers from 1 to x in vector
    std::random_shuffle(randomVector.begin(), randomVector.end());    //Randomly shuffle the elements in the vector

    //Initiate iterations to search for random numbers within the vector
    long int operationNum = 0;   //Keeps track of number of operations done
    int randomNums;         //Number to be searched

    for (double j = 1; j <= x; j++) {           //First stopping condition is the number of loops which is the int passed to average_complexity
        randomNums = 1 + rand() % x;
        for (int k = 0; k < randomVector.size(); k++) {        //Looking through each entry
            if (randomVector[k] == randomNums){
                operationNum += (k + 1);                //Must add k + 1 since k starts from 0
                break;
            }
        }

        //This nested for loop would indicate an O ( N^2 ), which takes precedence over the O ( N ) in random_shuffle

        if (j > 1) {prevRunningTime = avgRunningTime;}           //Update prevRunningTime to last avgRunningTime
        avgRunningTime = operationNum / j;              //Update avgRunningTime per run

        if (avgRunningTime >= (1 - 0.005) * prevRunningTime && avgRunningTime <= (1 + 0.005) * prevRunningTime && j >= 500) {break;}  //Final stopping condition is when the difference in running time is marginal, within +/- 0.5% of the previously recording avg running time
    }
    return avgRunningTime;
}



#endif /* hw3_h */

// Test runs
// int const MAX_N = 8192000; // 405 sec , 485 sec , 418 sec
// int const MAX_N = 4096000; // 224 sec , 220 sec , 215 sec , 216 sec
// int const MAX_N = 2048000; // 104 sec , 97 sec , 109 sec , 102 sec
// int const MAX_N = 1024000; // 52 sec , 52 sec , 51 sec , 47 sec , 52 sec
// int const MAX_N = 512000; // 26 sec , 26 sec , 25 sec , 24 sec
// int const MAX_N = 256000; // 14 sec , 13 sec , 12 sec , 13 sec
// int const MAX_N = 128000; // 6 sec , 6 sec , 7 sec , 6 sec
// int const MAX_N = 64000; // 2 sec , 3 sec , 3 sec , 3 sec
// int const MAX_N = 32000; // 2 sec , 1 sec , 1 sec , 1 sec
// int const MAX_N = 16000; // 0 sec , 0 sec , 0 sec
// int const MAX_N = 8000; // 0 sec , 0 sec , 0 sec
// int const MAX_N = 4000; // 0 sec , 0 sec , 0 sec