/* This program demonstrates
 * 1. Dynamic Memory
 * 2. Dynamic Arrays
 * 3. 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;

/* When we want to return an array from a function, the return type has to be
 * a pointer of the type of the array that we're returning.
 */
int* readDynArray(int count);
int* insert(int *arr, int size, int val, int pos);

/* 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 *intArr = nullptr;

    int size;
    cout<<"Enter the number of elements: ";
    cin>>size;
	
	 intArr = readDynArray(size);

    cout<<"\nPrinting from main: \n";
    for(int i=0; i<size; i++)
        cout<<intArr[i] <<"\t";
    cout<<endl;
    
    int pos, num;
    cout<<"Enter the number to be inserted: ";
    cin>>num;
    cout<<"Enter the position: ";
    cin>>pos;
    
    // Call the insert function and then store the returned array in the same pointer
    intArr = insert(intArr,size,num,pos);
    size++; // we have 1 more element
    
    cout<<"\nArray after insert:\n";
    for(int i=0; i<size; i++)
        cout<<intArr[i] <<"\t";
    cout<<endl;
    
    // delete the array
    delete [] intArr;
	
	 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;
}

/* We dynamically create an array of the given size
 * We create a pointer (which can point to arrays) and the use the "new" operator
 * to create the array.
 * We can then use the pointer like a regular array variable.
 * Finally, we can just return that pointer.
 * This array will be active and accessible in mian until it is deleted.
 */
int* readDynArray(int count)
{
    int *array = new int[count];
    cout<<"Enter the values: ";
    for(int i=0; i<count; i++)
        cin>>array[i];

    cout<<"Printing from the function:\n";
    for(int i=0; i<count; i++)
        cout<<array[i]<<"\t";
    cout<<endl;

    //cout<<"Value at element -5: "<< array[-5] << endl; // out of bounds in a dynamic array - segfault

    return array;
}

/* This function inserts an element into the dynamic array.
 * The function accepts a dynamic array and its size as a parameter and returns an
 * array, as a pointer. We follow the algorithm below.
 * 1. Get position and value
 * 2. Declare a new array of size+1 elements
 * 3. Copy all elements from location 0 until position -1
 * 4. Write the new element in
 * 5.Copy all elements from location position to size-1
 * 6. Delete old array
 * 7. Pretend new array was the old array all this time and return it
 */
int* insert(int *arr, int size, int val, int pos)
{
    int *newArr = new int[size+1];

    for(int i=0; i<pos; i++)
        newArr[i] = arr[i];

    newArr[pos] = val;

    for(int i = pos+1; i<=size; i++)
        newArr[i] = arr[i-1];

    delete [] arr;
    return newArr;
}


/* 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;
}