using namespace std;
#include<iostream>

/* Utilities for static and dynamic two-dimensional arrays in C++ 

 Static arrays:  Stored as blocks in memory in "row-major" order.
 That is, given int A[3][3], the data is laid out in memory as:
 A[0][0], A[0][1], A[0][2], A[1][0], A[1][1], etc ...
 You need to be aware of this when making pointer calculations.

 "Static" means that memory for the array is allocated at compile
 time - you must know the dimensions of your array when declaring them.
 You can only use constants or macros for constants when stating the
 sizes of arrays.  In a single-dimensional array, the memory location
 of A[i] is simply A+i. However, when given the 2D coordinates of a cell, 
 such as A[i][j], calculating the memory address entails knowing the size
 of each row.  That is, A[i][j] == *(A + (i*rowsize) + j)

 Static arrays can be more efficient than dynamically allocated arrays
 because one can treat a static array as a contiguous block of memory.
 But there are some issues that you need to be aware of.  Consider the
 following function, which tries to print any 2d array passed to it:

    void print2d(int A[][], int r, int c)
    {
      int i, j;
      for(i=0;i<r;i++) 
      { for (j=0;j<c;j++) cout << A[i][j] << "\t";
        cout << "\n";
      }
    }

The compiler will not accept this function, becasue as explained above,
to calculate a 2d coordinate, it must know the size (number of columns)
of each row of the array.  It has no idea what the "r" and "c" variables
are for, and in any case it can't know their values at compile time.  To
Write such a function, one needs to at least specify the number of 
columns in the type declaration:

    void print2d(int A[][5], int r, int c)
    ....

This is OK, but obviously very limited in its use.  To get around this
problem, we can use a macro instead of a function:
*/

/* macro definition */
#define PRINTM(A,r,c) { \
  int i, j; \
  for(i=0;i<r;i++) \
    { for (j=0;j<c;j++) cout << A[i][j] << "\t"; \
      cout << "\n"; \
    } \
}

/*
The macro is written out before compilation, so this is just an advanced
form of copying and pasting.  Notice, however, that the i and j variables
are still local by virtue of the enclosing {} braces.   We can use the
macro as in :

int A[4][5];
//
PRINTM(A,4,5)  // no semicolon here - this is just shorthand.

Please don't get carried away with macros however.  Use them only when
appropriate.


 Another thing to remember is that very large arrays should not be
 allocated on the stack, as that will overflow the stack.  That is,
 instead of 

  {
     double A[1000][1000];

 Do instead:

     static double A[1000][1000];

 Or, if this is the principal structure of your program, you can declare
 it as a global (but don't get carried away with globals!).  Declaring 
 the variable static means that all manifestations of the current scope
 (function call) will share the same variable.  This use of "static" extends
 that found in the context of object oriented programming.  When a variable
 inside a function is declared static, it means that it will retain its value
 across different calls to the function.  The memory for the structure is
 allocated in a special global space that's permanently attached to the source
 code of the program (if you've done assembler programming, such varibles
 are like those that you define as part of the code section.)  


 Dynamic Arrays: 


A 2D array is a 1D array in which each element is a pointer to another
array.  A dynamic array is thus larger than a static array, and the
data is not contiguous.  It's larger because a separate row is used
for storing the pointers, and not contiguous because the pointers can
point anywhere.

*/

// The following funtion creates a dynamic array of doubles:
double **make2d(int r, int c)
{ int i;
  double **m;
  m = new double*[r]; 
  for (i=0;i<r;i++) 
    m[i] = new double[c];
  return m;
}

// double** can be replaced by double*[]

// deallocation : EVERY call to "new" requires a corresponding "delete"
void free2d(double ** M, int r)
{ int i;
  if (!M) return;
  for(i=0;i<r;i++) delete(M[i]);
  delete(M);
}

/*
Calculating the address of cells for such an array is now just a matter
of calculating the addresses of two one-dimensional arrays, with a 
pointer dereference in between.  It is thus possible to write the following:
*/

// only works for dynamic arrays: 
void printdy(int **A, int r, int c)
{
  int i, j;
  for(i=0;i<r;i++) 
    { for (j=0;j<c;j++) cout << A[i][j] << "\t";
      cout << "\n";
    }
}

/*
However, in the following example the advantage goes to static arrays.  The
built-in "memcpy" functions allows us to copy an entire block of memory
from one location to another.  Given a pair of static 2D arrays:

  double A[4][5];
  double B[4][5];

we can copy the entire contents of A to B using:

   #include <string.h>  /* at the top of program */
   ...
   memcpy(B,A,160);  // 160 == 4*5*8 == size of array in bytes
 
You can type "man memcpy" on any unix/linux prompt to understand how it
works.  The first argument is the destination address, the second is the 
source, and the third argument is the number of bytes to copy over.  The 
total size of the array is multiplied by 8 since there are 8 bytes (64 bits) 
for each double.

Functions like memcpy, however, cannot be used on dynamic 2D arrays, 
because the arrays are scattered all over memory space.  You must write a 
loop to copy individual values separately.
*/


///////////////test program:

/* Testing multi-dimensional arrays */

int main()
{
  // statically allocated array:
  static int A[5][4];    // what's static mean?  - not a stack variable
  PRINTM(A,5,4);  cout << endl;

  // dynamically allocated 2-d array;
  int **B;  int n =4;  n++;
  //  B = (int **) malloc(5*sizeof(int*));
  B = new int*[n];
  for (int i=0;i<5;i++) B[i] = new int[4];
  for (int i=0;i<4;i++) B[i][i] = 98;

  printdy(B,5,4); cout << endl;

  //  B = new int[3][4];  Not valid

  // memory deallocation:  every new needs a delete
  for (int i=0;i<5;i++) delete(B[i]);
  delete(B);

  return 0;
}