//====================================================================
// Program: Comparing Organizing Lists
// Assignment: 2
// Date: February 9, 2009
//
// Programmer: Nomed Nocaed             
// Course: CSC 221 B                 Professor: Nirre Pluf
//
// Assumptions:
//   Requires CLinkList class with moveSearch() and 
//   transposeSearch() methods
//====================================================================

#include<iostream>  
#include<fstream>  
#include<cmath>  
#include<string>  
#include"clinklist.h"  

int zipf(double alpha, int n);  // function for Zipf's distribution  

int main(int argc, char* argv[])  
{  
   // check for appropriate command line arguments
   if(argc < 3)  
   {  
      cout << "use: " << argv[0] << " numValues numSearch distType \n";  
      cout << " numValues:  number of values in list \n";  
      cout << " numSearch: number of searches \n";  
      cout << " distType:  distribution type, unif or zipf \n";  
      return 1;  
   }  

   int numValues = atoi(argv[1]);  // number of values in list  
   int numSearch = atoi(argv[2]);  // number of seraches to perform   
   bool isZipf   = false;          // search distribution, "norm" default   

   if(argc > 3 && strcmp(argv[3], "zipf") == 0)
      isZipf = true;
   else if(argc == 3 || strcmp(argv[3], "unif"))
      cout << "using normal distribution... \n";  
   
   int temp;         // temporary number to search for
   CLinkList> list;  // original list of values

   // fill list with numbers 0 - (numValues - 1)
   for(int i = 0; i < numValues; i++)  
      list.addToEnd(i);  

   // cout << list << '\n';  

   CLinkList mList = (list);  // list organized using move method
   CLinkList tList = (list);  // list organizex using transpose method 

   int n, nNorm = 0, nMove = 0, nTrans = 0; // counters for number of compares 
   int value;                               // value to search for (random)

   // perform numSearch random searches
   for(int i = 0; i < numSearch; i++)  
   {  
      // determine the random value to search for
      if(!isZipf)  
         value = rand()%(numValues);  
      else  
         value = zipf(1.35, numValues);  

      // search for value and record number of compares  
      if((n = list.search(value))) nNorm += n;    
      if((n = mList.moveSearch(value))) nMove += n;    
      if((n = tList.transposeSearch(value))) nTrans += n;    
   }  

   // output the results   
   cout << "===================================================== \n";  
   cout << "Using " << numValues << " values, " << numSearch << " searches, and "
        << (isZipf?"zipf":"unif") << " distribution \n";   
   cout << "avg number of searches required \n";  
   cout << " original:      " << double(nNorm)/numSearch << '\n';  
   cout << " move to front: " << double(nMove)/numSearch << '\n';  
   cout << " trans list:    " << double(nTrans)/numSearch << '\n';  

   
   return 0;  
}  

//==zipf=====================================================================
// pre:  alpha is the power exponent and n is the value range  
// post: returns a value between zero and (n-1) according to Zipf's distro
//===========================================================================
int zipf(double alpha, int n)
{
  static bool first = true;  // Static first time flag
  static double c = 0;       // Normalization constant
  double z;                  // Uniform random number (0 < z < 1)
  double sum_prob;           // Sum of probabilities
  double zipf_value;         // Computed exponential value to be returned
  int    i;                  // Loop counter

  // Compute normalization constant on first call only
  if (first)
  {
    for (i=1; i<=n; i++)
      c = c + (1.0 / pow((double) i, alpha));
    c = 1.0 / c;
    first = false;
  }

  // Pull a uniform random number (0 < z < 1)
  do
  {
    z = double(rand())/RAND_MAX;
  }
  while ((z == 0) || (z == 1));

  // Map z to the value
  sum_prob = 0;
  for (i=1; i<=n; i++)
  {
    sum_prob = sum_prob + c / pow((double) i, alpha);
    if (sum_prob >= z)
    {
      zipf_value = i;
      break;
    }
  }

  // Assert that zipf_value is between 1 and N
  assert((zipf_value >=1) && (zipf_value <= n));

  return int(zipf_value - 1);
}