/* This program demonstrates
 * 1. Sorting an array
 * 2. Multi-dimensional array
 *
 * So far, we have looked at single dimensional arrays, where we have only one
 * "row" of elements. However, C++ allows us the create arrays with as many
 * dimensions as we would like. It is pretty common to see 2, 3 or 4 dimensions,
 * but it gets harder to keep them straight in our heads after that.
 * For this course, you need to know higher dimensional arrays can exist. But
 * we will only learn about 2-dimensional arrays in detail.
 *
 * Address calculation:
 * C++ stores arrays in row major order. That means the lower dimensional
 * elements under the same higher dimension will be stored together. So, all
 * the columns of each row are stored together. So, C++ stores all the array
 * elements continuously. Row 0 first, row 1 next, row 2 next and so on.
 * Consider the element at row r, column c.
 * Since both rows and columns are 0 indexed, to get to row 'r', we would have
 * to move past 'r' complete rows, and then 'c' columns.
 * The size of each row is the number of columns in the row. So,
 * address = Starting Address + ((row_number * number_of_columns) + column_number)*type_size
 * address = SA + ((r*number_of_columns) + c) * type_size
 *
 * This program now demonstrates
 * 1. Declaring a 2 D array
 * 2. Using set notation to initialize a 2D array
 * 3. Passing a 2D array into a function
 * 4. Iterating through a 2D array to read values, print values and search
 *    through a 2D array.
 */

#include<iostream>
#include<cmath>
using namespace std;

/* Declare the functions here
 * when we pass an array into the function, we don't have to mention the size
 * the array. Mentioning it won't result in an error, but it is not necessary.
 * However, we have to specify it is an array, by using the []
 *
 * Function names are self-descriptive here. They are described while being defined.
 */
void sort(double arr[], int size);

void matrixSearch( const double mat[][3], double key, int row, int col, int &rpos, int & cpos);
int main()
{
    double arr[10];     // declare the array
    const int NUM = 10;
    //accept array values from the user
    cout<<"\nEnter values for the array: ";
    for(int i=0; i<10; i++)
    {
        cin>>arr[i];
    }

    sort(arr, NUM);
    cout<<"\nAfter sorting:\n";
    for(int i=0; i< 10; i++)
    {
        cout<< arr[i]<<"\t";
    }

    /* Declaring a 2 dimensional array. We need to specify the number of rows
    * and the number of columns, instead of just the number of values.
    * The first dimension is the number of rows. The second dimension is the
    * the number of columns.
    * All the rules that applied to single dimensional arrays also apply to
    * multi dimensional arrays.
    * We can use set notation to initialize the array, where each row gets its
    * own set of {}. Any values we leave out are automatically filled out with 0's
    */
    double mat[5][4] = { {1, 3.2, 5, 9.1}, {12, 45, 6.1, 18}, {19, -6}, {87} };

    cout<<"Array contents:\n";
    for(int i=0;i<5; i++)
    {
        for(int j=0; j<4; j++)
        {
            cout<<mat[i][j]<<"\t";
        }
        cout<<endl;
    }

    cout<<"Enter matrix values: ";
    for(int i=0; i<5; i++)
    {
        for(int j=0; j<4; j++)
            cin>> mat[i][j];
    }

    double searchVal;
    int foundRow, foundCol;
    cout<<"Enter the search value: ";
    cin>>searchVal;

    /* We can only return one value from a function. But the position needs 2
    * values - row and column, so we use reference variables instead.
    */

    //call the function, the postion markers will be saved in foundRow and foundCol;
    matrixSearch(mat, searchVal, 5,4,foundRow, foundCol);
     if( foundRow == -1)
        cout<<"The element is not in the array"<<endl;
    else cout<<"The element was found in row "<<foundRow<< " column "<<foundCol<<endl;


    return 0;
}

/* function sort
 * parameters - array and its size
 * returns nothing
 *
 * Sorts the array elements in ascending order
 * Naive Bubble Sort
 *
 * 10 98 27 -6 41 5 - size 6
 * N-1 iterations
 * Iteration 0: elements 0 through 5
 * Comparisons: 10 & 98, 98 & 27 swap, 98 & -6 swap, 98 & 41 swap, 98 & 5 swap (N-1 comparisons)
 * 10 27 -6 41 5 98
 * 98 is in the right spot
 *
 * Iteration1: elements 0 through 4
 * Comparisons: 10 & 27, 27 & -6 swap, 27 & 41, 41 & 5 swap ( N - 1 -1 comparisons)
 * 10 -6 27 5 41  | 98
 * 41 and 98 are in the right spots
 *
 * Iteration 2: elements 0 through 3
 * Comparisons: 10 & -6 swap, 10 & 27, 27 & 5 swap (N -1 -2 comparisons)
 * -6 10 5 27 | 41 98
 * 27, 41 and 98 are in the right spots
 *
 * Iteration 3: elements 0 through 2
 * Comparions: -6 & 10, 10 & 5 swap  (N -1 - 3 comparisons)
 * -6 5 10 | 27 41 98
 * 10, 27, 41 and 98 are in the right spots
 *
 * Iteration 4: elements 0 through 1 (N -1 - 4 comparisons)
 * Comparisons: -6 & 5
 * -6 5 | 10 27 41 98
 *
 * Array is sorted
 *
 * N-1 iterations
 * For each iteration, N-1 - iteration no. of comparisons
 * If numbers are out of order, swap them
 */
void sort(int arr[], int size)
{
    for(int i=0; i< size-1; i++)
    {
        for(int j=0; j< size -1 - i; j++)
        {
            if(arr[j] > arr[j+1])
            {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

/* Function matrix search - 6 parameters, returns nothing
 * Parameters - integer matrix - 5 rows, 3 columns
 * integer search key, number of rows and columns,
 * 2 reference parameters marking positions if found
 *
 * Method is same as linear search - look through entire array,
 * if element found, mark the spot.
 * Set spot to (-1,-1) as initial value.
 *
 * This is extending the linear search idea to cover 2D arrays. We still iterate
 * through the array, and check each element to see if that's the value we're
 * looking for.
 * We use reference variables here because we need to return the row and the
 * column where the element was found.
 */
void matrixSearch( const int mat[][3], int key, int row, int col, int &rpos, int &cpos)
{
    rpos = -1;
    cpos = -1;

    for(int i=0; i<row; i++)
    {
        for(int j=0; j<col; j++)
        {
            if( mat[i][j] == key)
            {
                rpos = i;
                cpos = j;
            }
        }
    }


}