public class stackheap
{
/*     UNDERSTANDING POINTERS, STACK AND HEAP MEMORY USAGE
    
A rather standard way that memory is used by a program (not just a
java program) is to partition it into a RUNTIME STACK segment and a
GLOBAL HEAP segment.  Let's first talk about the stack.

When you call a function such as the 'power' function below, the execution
of the function has certain memory requirements.  Namely, it requires space
to store its local variables.  In the case of the power function, it
requires memory to store x, n, ax, and pn  (4 32-bit ints total 16 bytes).
Where are these bytes located?  They are placed on the *runtime stack*.
Each call to power PUSHES a "stack frame" containing the 16 bytes associated
with a set of local copies of x,n,ax,pn.  When the function exits (returns),
the stack frame is POPPED which means the memory is deallocated.  
*/

 int power(int x, int n) // calculates x**n in log(n) steps
  {
    int ax = 1, pn = n;
    while (n>0)
    {
	if (n%2==1) ax *= pn;
        pn = pn*pn;
        n = n/2;
    }
    return ax;
  }//power

/*
It's important to understand that a new stack frame is created for
each CALL to the function.  This is especially important for
understanding how recursive functions work.  The fact (factorial)
function below is recursive.  
*/
int fact(int n)
  { 
      if (n<2) return 1; else return n*fact(n-1);
  }
/*
This function contains only one local variable (n).  Each time fact is
called, a new frame with n is created and pushed on top of the stack.
For example, when we call fact(4), we push a frame with n=4 on the
stack.  This call in turn calls fact(3), which pushes another n=3 on
top of the existing stack frame.  This in turn calls fact(2), with
another frame with n=2.  A final recursive call is made fact(1).  At
this point, our runtime stack looks like the following:

n = 1
-----
n = 2
-----
n = 3
-----
n = 4

Now fact(1) returns 1: this results in the top frame being popped. This
means that now "n" is 2.  so the n*fact(n-1) here returns 2*1=2: this is
what's returned by the call to fact(2).  Now the next frame is popped and
n is now 3, so n*fact(n-1) is 3*2=6: this is what's returned by fact(3).
The frame with n=3 is then popped and now n=4, so the final value of
n*fact(n-1) is 4*6 =24.  This value is returned by fact(4), and all memory
for this computation will be reclaimed by the last pop.  As you can 
see, the more recursive calls are nested on top of each other, the
higher the stack will grow.  So there could be a stack overflow unless
we can guarantee that the growth is within control - such as when it's 
bounded by a constant or log(n). 'fact' is not a good example of recursion.


                         HEAP AND POINTERS

Now the story gets more complicated. Memory for primitive built-in types 
such as int, double, long, boolean are allocated directly on the stack as
shown above.  However, everything else in Java is an *Object* and memory
is allocated in another part of memory called the *heap*.  This includes
arrays, Strings, and instances of all classes. In such a situation,
what's allocated on the stack is a reference, or pointer, to the heap
memory location containing the object: it's basically a memory address.  
Consider the following, simple, O(n*n) sorting function:
*/
    void swapsort(int[] A)
    {
	for(int i=0;i<A.length-1;i++)
	    {
		int min = i; // find index of ith smallest value
		for(int k=i+1;k<A.length;k++) 
		    if (A[k]<A[min]) min = k;
		int tmp = A[i]; A[i]=A[min]; A[min]=tmp; //swap A[i] with A[min]
	    }
    }//sorts array A.

/*
  This function contains local variables i, k, min, tmp and A.  The
first four are all integers and are treated the same way as before
(although i and k are only visible inside their respective loops,
they're allocated in the same stack frame).  But what about the array?
A is a *local* variable, so memory for it is allocated on the stack.  But
if the contents of the array is inside the stack frame, then it would be
*popped* when the function exits, which means that all the swapping we've
done would be useless! 
*/
    void sortingtest() // test if the swapsort function works
    {
        int[] B = {5,3,4,1}; // definitely not sorted
	swapsort(B);   // will this sort B or just a local copy of B?
        for(int x:B) System.out.print(x+" ");  
	System.out.println(" is it sorted?"); 
    }
/*
Do you expect B to be sorted after the call to swapsort?  It WILL be sorted,
even though A is clearly a local variable inside the function.  How do you
explain this?  

Because A is not the array {5,3,4,1} itself, but a *pointer* to the array.
The array itself is allocated on the heap.  Both A in swapsort and B in
sortingtest are pointers.  And *they point to the same array*.  When
we pass B to swapsort, only the pointer is passed, which means only the
location of the array is copied to A. When we swap A[i] with A[min], however,
it is the *contents* of the array that's being swapped.  When swapsort
terminates, only the *pointer* A is popped off of the stack.  The memory
containing the array on the heap stays intact.  Since B in sortingtest still
refers to the same memory location, it now refers to a sorted array.  Please
try to understand this clearly.  

If you think you understand it, answer the following question:
 */
    void swapstuff(int x, int y, int[] A, int[] B)
    {
        int[] Tmp = A;  A = B;  B = Tmp; // swap A and B
        x = x+y;  y = x-y;  x = x-y;  // swaps x and y without a temp.
    }
/*
    If you passed this function two different ints, and two different arrays,
    would you expect anything to be swapped?

    int x = 2, y = 4;
    int[] A = {1,3,5};  int[] B = {2,4,6};
    swapstuff(x,y,A,B);
    // what are x, y, A, B now, after the function call?


    ANSWER: absolutely nothing gets swapped.  x,y,A,B outside the
    function are completely unaffected.  x,y,A,B are all local
    variables.  When we swapped A and B inside the function, we
    swapped a pair of pointers.  But A,B outside the function still had
    the same values as before:  The CONTENTS of the arrays that they point
    to were never affected.  Contrast this with swapsort: there we swapped
    the CONTENTS of the array (A[i] and A[min]), not the pointers themselves.
    Be sure you understand this: A and B are pointers, but they're still
    local variables.
*/
    public static void main(String[] av)
    {
        // we need an instance of the class to call non-static methods:
        stackheap app = new stackheap();
        app.sortingtest();
        int x = 2, y = 4;
        int[] A = {1,3,5};  int[] B = {2,4,6};
        app.swapstuff(x,y,A,B);
        System.out.println(x+" and "+y);
        System.out.println(A[0]+" and "+B[0]);
        //app.fact(1000000); // this will overflow the runtime stack
    }//main
}//stackheap class