/* This program demonstrates
 * 1. Dynamic Memory
 * 2. Dynamic Arrays
 *
 * Dynamic Arrays:
 * So far, we have been declaring arrays in stack space. These arrays need to have
 * their size decided BEFORE COMPILING. That is why we had to use integer literals
 * or constant integers for size while declaring the arrays. We decided this size
 * hoping that it would be "large enough" to hold all the data the user is going
 * to put in.
 *
 * Also, we cannot create arrays in one function (that is not main) and use it in
 * other functions.
 *
 * Dynamic memory solves both of these problems.
 * 1. Declaration
 * We declare dynamic memory using the keyword "new".
 * When we declare a variable/array dynamically, the variable/array is created in
 * a completely different area of memory called the heap. This happens at RUNTIME.
 * So, we can use a variable to specify the size of the array.
 * 2. Access
 * We can access variables/arrays created in heap memory ONLY through a pointer.
 * 3. Deleting
 * Since we create this memory in runtime, this is not automatically deleted when
 * we return from a function. This is useful because we can create arrays in a
 * function and return it. However, we should take care to delete the memory we
 * created before we exit the program. To delete memory we created, we use the
 * keyword "delete". Please note that deleting doesn't have to be done in the
 * same function that created the 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* readArray(int count);
int* readDynArray(int count);
int* insert(int *arr, int size, int val, int pos);

int main()
{

    /* If we create a stack-space array in a function, it would be destroyed
    * when we return from the function. So, if we try to access that array from
    * main, it would either print junk values or crash with a segmentation fault
    */
    int *intArr = nullptr;

    int size;
    cout<<"Enter the number of elements: ";
    cin>>size;

    intArr = readArray(size);
    // The previous line will retrun an invalid reference, which would crash if we used it

    /* Instead of using the readArray function that creates an in-stack array
    * and returns an array that is subsequently destroyed, we can create a dynamic
    * array in the function, retrun it, use it in main, and delete it when it
    * is no longer required.
    */

    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;
    return 0;
}

/* This function creates an in-stack array of the given size
 * and reads some values in, and then returns the array.
 * This will compile, and run, but crash or print wrong values
 * if we try and access the returned array in main.
 * This is because the array is destroyed when we return from
 * the function, and the returned address is pointing
 * to memory that technically is unallocated.
 */
int* readArray(int count)
{
    int array[100];
    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, but will print junk

    return array;
}

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