/* This program demonstrates
 *  2 dimensional dynamic arrays
 *
 * A 2 dimensional dynamic array is organized as a single dimensional array of 
 * pointers, each of which points to a single "row" of the array - a single
 * dimensional array. 
 * 
 * This needs a 2-level pointer to access it. It also needs to be created and deleted
 * in 2 steps. 
 * 
 * We need to be sure we are within the bounds of the dynamic array. 
 */

#include<iostream>
using namespace std;

/* If we have a dynamic 2D array, we use a 2-level pointer, whether
 * it is as a parameter or as a return type
 */
int ** twoDArrayDemo(int rows, int columns);
int matrixSearch(int ** arr, int r, int cN, int val);

int main()
{

    int r,c;
    cout<<"Enter the number of rows and columns: ";
    cin>>r>>c;

    // We need a 2-level pointer to point to a 2D dynamic array
    int ** mat = twoDArrayDemo(r,c);

    cout<<"The matrix is : \n";
    for(int i=0; i<r; i++)
    {
        for(int j=0; j<c; j++)
            cout<< mat[i][j] <<"\t";
        cout<<endl;
    }

    /* Have the user enter a search column (0-indexed) and then
	 * go through that column, looking for a particular number.
	 */
    int searchCol,val;
    cout<<"Enter the search column: ";
    cin>>searchCol;
    cout<<"Enter the value to search: ";
    cin>>val;
    int found = matrixSearch(mat,r,searchCol,val);
    cout<<"Value was found in row "<< found;

    // delete the 2D array
    // first, delete each individual row
    for(int i=0; i<r; i++)
        delete [] mat[i];

    // delete the array of pointers
    delete [] mat;

    return 0;
}

/* Creating a two dimensional dynamic array.
 * This function accepts 2 parameters - the number of rows and columns in the
 * two dimensional array. It then creates a dynamic two dimensional array
 * using a 2-level pointer. A dynamic 2D array is an array of pointers (as many)
 * as the number of arrays, and then each pointer points to an array, with
 * as many elements as the number of columns.
 * Once we have created the array, we can use it just like a regular 2D array.
 * Both creating and deleting a 2D array needs to go through 2 steps.
 *
 * The function also shows how to return a 2D array from a function
 */
int ** twoDArrayDemo(int rows, int cols)
{
    // create an array of pointers - dynamic
    int **mat= new int*[rows];

    // Use a loop to create each individual row
    for(int i=0; i<rows; i++)
        mat[i] = new int[cols];

    // use it like a regular 2D array
    cout<<"Enter the values in the matrix: ";
    for(int i=0; i<rows; i++)
    {
        for(int j=0; j<cols; j++)
            cin>> mat[i][j];
    }

    /* The max norm of a matrix is the largest balue in th ematrix
     */
    int maxNorm = mat[0][0];
    for(int i=0; i<rows; i++)
    {
        for(int j=0; j<cols; j++)
        {
            if( mat[i][j] > maxNorm)
                maxNorm = mat[i][j];
        }
    }
    cout<<"The max norm is "<< maxNorm<<endl;

    // return the array
    return mat;
}

/* This function will receive a dynamic 2D array as a 2 level pointer parameter
 * It also receives a search value, a column to search and the number of rows
 * and then checks only the given column for the value
 *
 * We need to make sure we are NEVER out of bounds in a 2D array.
 * Unlike 1D arrays, even 1 element out of bounds will result in the program crashing
 * Always check for bounds before dereferencing
 */
int matrixSearch(int **mat, int rows, int cN, int val)
{
    /* Begin at row 0 on the given column, look for the number
      * If the number is found, exit the loop.
      * Make sure we don't go out of bounds*/
    int pos = -1;
    int i =0;
    while ( i < rows && mat[i][cN] != val)
    {
        cout<<"Checked row "<< i <<". Value is "<< mat[i][cN]<<endl;
        i++;
    }

    /* If number were found, we would have exited the loop before
    * we hit the number of rows
    */
    if(i<rows)
        pos = i;
    // returns -1 if element not found in the specified column
    return pos;
}