#include "picture.h"


//****************************************************************************
//
// Function:   Picture
//
// Purpose:    C-tor
//
// Parameters: argv - holds which algorithm to use and what neighborhood size
//
// Calls:      atoi, static_cast, floor
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//****************************************************************************


Picture::Picture(char **argv)
{
   if(argv[1][1] == 'a')
   {
      algorithm = atoi(argv[2]);
      neighborhood = atoi(argv[4]);
   }
   if(argv[1][1] == 'n')
   {
      neighborhood = atoi(argv[2]);
      algorithm = atoi(argv[4]);
   }

   switch(algorithm)
   {
      case 1: algorithm = 2; break;
      case 2: algorithm = 4; break;
      case 3: algorithm = 10; break;
      default: exit(EXIT_FAILURE); break;
   }
   
   border = static_cast<size_t>(floor(neighborhood/2.0));
   neighborhood_squared = (neighborhood * neighborhood);
   position = (neighborhood_squared) - static_cast<int>
              (floor(((neighborhood_squared) + 1) / algorithm * 1.0));
}


//****************************************************************************
//
// Function:   ~Picture
//
// Purpose:    X-tor
//
// Parameters: none
//
// Calls:      get, getline, new, exit, push_back
//
// Time Comp:  O(h) h = height of picture
//
// Space Com:  O(1)
//
//****************************************************************************


Picture::~Picture()
{
   for(size_t i(0); i < height; ++i)
   {
      delete [] original_pic[i];
      delete [] filtered_pic[i];
   }
   delete [] original_pic;
   delete [] filtered_pic;
}


//****************************************************************************
//
// Function:   read_info
//
// Purpose:    Retrieve header info of picture
//
// Parameters: none
//
// Calls:      peek, getline, get, new
//
// Time Comp:  O(h) h = height of image
//
// Space Com:  O(h * w) h = height of image
//                   w = width of image
//
//****************************************************************************


void Picture::read_info()
{
   getline(cin, format);
   while(cin.peek() == '#')
   {
      getline(cin, comment);
   }
   cin >> width  >> height >> max_value;
   cin.get();

   original_pic = new unsigned char* [height];
   filtered_pic = new unsigned char* [height];
   for(size_t h(0); h < height; ++h)  //create dynamic matrix
   {
      original_pic[h] = new unsigned char[width];
      filtered_pic[h] = new unsigned char[width];
   }
   
   height_minus_border = ((height - 1) - border);
   width_minus_border = ((width - 1) - border);
}


//****************************************************************************
//
// Function:   read_data
//
// Purpose:    Read in the original image
//
// Parameters: none
//
// Calls:      get
//
// Time Comp:  O(h * w) h = height of image
//                   w = width of image
//
// Space Com:  O(1)
//
//****************************************************************************


void Picture::read_data()
{
   for(size_t i(0); i < height; ++i)
   {
      for(size_t j(0); j < width; ++j)
      {
         original_pic[i][j] = cin.get();
      }
   }
}


//****************************************************************************
//
// Function:   filter
//
// Purpose:    Chooses which filter algorithm to use
//
// Parameters: none
//
// Calls:      filter_sort, filter_median
//
// Time Comp:  O(h * w * n^2)  h = height
//                             w = width
// Space Com:  O(n^2)          n = neighborhood
//
//****************************************************************************


void Picture::filter()
{
   if(algorithm == 10)  //filter_median works best for algorithm 3
   {
      filter_median();
   }
   if(height * width > 350000)  //works best with large input
   {
      filter_median();
   }
   else  //this filter works best with small input
   {
      filter_sort();
   }
}


//****************************************************************************
//
// Function:   output_filtered_picture
//
// Purpose:    Output the new filtered image
//
// Parameters: none
//
// Calls:      size, 
//
// Time Comp:  O(h * w) h = height of image
//                   w = width of image
//
// Space Com:  O(1)
//
//****************************************************************************


void Picture::output_filtered_picture()
{
   cout << format << endl;
   if(comment.size() != 0)
   {
      cout << comment << endl;
   }
   cout << (width - 2 * border)
        << ' '
        << (height - 2 * border)
        << endl
        << max_value 
        << endl;

   for(size_t i = border; i <= height_minus_border; ++i)
   {
      for(size_t j = border; j <= width_minus_border; ++j)
      {
         cout << filtered_pic[i][j];
      }
   }
}


//****************************************************************************
//
// Function:   filter_sort
//
// Purpose:    Filter image using a sort to find the correct pixel value
//
// Parameters: none
//
// Calls:      floor, static_cast, new, sort
//
// Time Comp:  O(h * w * n^2) h = height of image
//                            w = width of image
//                            n = neighborhood 
//
// Space Com:  O(n^2) n = neighborhood size
//
//****************************************************************************


void Picture::filter_sort()
{
   size_t count;
   double int_border = (floor(neighborhood/2.0));
   int neg_border = static_cast<int>(-floor(neighborhood/2.0));

   unsigned char* A = new unsigned char[(neighborhood_squared)];

   for(size_t i = border; i <= height_minus_border; ++i)
   {  //O(h) h = height of image
      for(size_t j = border; j <= width_minus_border; ++j)
      {  //O(w) w = width of image
         count = 0;
         for(int k = neg_border; k <= int_border; ++k)
         {  //O(n) n = neighborhood
            for(int l = neg_border; l <= int_border; ++l)
            {  //O(n) n = neighborhood
               A[count] = original_pic[i + k][j + l];
               ++count;
            }
         }
         sort(A, A + (neighborhood_squared));  //O(n^2) n = neighborhood
         filtered_pic[i][j] = A[position];
      }
   }
   delete [] A;
}


//****************************************************************************
//
// Function:   filter_median
//
// Purpose:    Filter the image using a median algorithm to find correct
//
// Parameters: none
//
// Calls:      floor, static_cast, new, select
//
// Time Comp:  O(h * w * n^2) h = height
//                            w = width
//                            n = neighborhood
//
// Space Com:  O(n^2) n = neighborhood
//
//****************************************************************************


void Picture::filter_median()
{
   size_t count;
   double int_border = (floor(neighborhood/2.0));
   int neg_border = static_cast<int>(-floor(neighborhood/2.0));

   unsigned char* A = new unsigned char[(neighborhood_squared)];

   for(size_t i = border; i <= height_minus_border; ++i)
   {  //O(h) h = height of image
      for(size_t j = border; j <= width_minus_border; ++j)
      {  //O(w) w = width of image
         count = 0;
         for(int k = neg_border; k <= int_border; ++k)
         {  //O(n) n = neighborhood size
            for(int l = neg_border; l <= int_border; ++l)
            {  //O(n) n = neighborhood size
               A[count] = original_pic[i + k][j + l];
               ++count;
            }
         }
         filtered_pic[i][j] =
         select(A, 0, neighborhood_squared - 1, position);  //O(n^2)
      }
   }
   delete [] A;
}


//****************************************************************************
//
// Function:   select
//
// Purpose:    Choose the ith element from the array
//
// Parameters: A - array of unsigned char
//             start - first position in A
//             finish - end position of A
//             ith_smallest - position of char we want to get
//
// Calls:      partition, select
//
// Time Comp:  O(n^2) n = neighborhood
//
// Space Com:  O(n^2) n = neighborhood
//
//****************************************************************************


unsigned char Picture::select
(unsigned char A[], size_t start, size_t finish, size_t ith_smallest)
{
   if(start == finish)
   {
      return A[start];
   }

   size_t q = partition(A, start, finish);  //O(n^2) n = neighborhood
   size_t k = q - start + 1;
   if(ith_smallest == k)
   {
      return A[q];
   }
   else if(ith_smallest < k)
   {
      return select(A, start, q - 1, ith_smallest);  //O(n^2)
   }
   else
   {
      return select(A, q + 1, finish, ith_smallest - k);  //O(n^2)
   }
}


//****************************************************************************
//
// Function:   partition
//
// Purpose:    Partition the array
//
// Parameters: A - array of unsigned chars
//             start - first position in A
//             finish - ending position of A
//
// Calls:      rand
//
// Time Comp:  O(n^2) n = neighborhood
//
// Space Com:  O(1)
//
//****************************************************************************


size_t Picture::partition(unsigned char A[], size_t start, size_t finish)
{
   unsigned char temp;
   size_t in = rand() % (finish - start + 1) + start;
   temp = A[in];
   A[in] = A[finish];
   A[finish] = temp;

   unsigned char x = A[finish];
   
   size_t i = start - 1;
   
   for(size_t j = start; j < finish; ++j)
   {  //O(n^2) n = neighborhood
      if(A[j] <= x)
      {  //move everything <= x to the left of x
         ++i;
         temp = A[i];
         A[i] = A[j];
         A[j] = temp;
      }
   }
   temp = A[i + 1];
   A[i + 1] = A[finish];
   A[finish] = temp;
   return i + 1;
}