// Introduction to Algorithms
// Template for Shift
// <put your name, login name & student number here>

/****************************************************************************

The problem is to shift a segment of an array, leaving "the rest"
of the array as it is.   The segment is of length "len", starting
at "source" and is to be moved to start at "dest".

	---------------------------------------------------------
	|		|	|   copy this 	|		|
	---------------------------------------------------------
	 ^			 ^		 ^		 ^
	 0			 source		 source+len	 size

	---------------------------------------------------------
	|		|    to here	|	|		|
	---------------------------------------------------------
	 ^		 ^		 ^			 ^
	 0		 dest		 dest+len		 size

*****************************************************************************/

public class Shift implements Shifting {
  
    public void shift (int[] array, int source, int dest, int len) {
	int size = array.length;
    
	// This is one of the exercises -
	// please write the main code before
	// you look at this bit.
	if ( false ) {
	    throw new IllegalArgumentException ("shift out of range");
	}

	// the obvious way only sometimes works
	if ( true ) {
	    // initialise the loop
	    int j=0;

	    // the precondition goes here
	    //	---------------------------------------------------------
	    //	|		|	|		|		|
	    //	---------------------------------------------------------
	    //	 ^			 ^		 ^		 ^
	    //	 0			 source		 source+len	 size

	    // show the initial state of the loop
	    Trace.printarray (array,   );
	    
	    // the loop itself
	    while (      ) {

		// the loop invariant goes here --- 
		// adapt the diagram for the precondition
		// to show that part of the array has been shifted
		
		// show the state at the top of the loop body
	      Trace.printarray (array,     );
		
		// the body of the loop goes here

	    }

	    // the postcondition goes here
	    //	---------------------------------------------------------
	    //	|		|		|	|		|
	    //	---------------------------------------------------------
	    //	 ^		 ^		 ^			 ^
	    //	 0		 dest		 dest+len		 size
	    
	    // the loop has finished: show the final state
	    Trace.printarray (array, source+j, source+len, dest+j, dest+len);
	    
	} else /* (       ) */ {

	    // if the obvious way doesn't work,
	    // copy it and modify it to make it work.
	    // remember what you learned about symmetry
	    // from the right-to-left search


	}
	
	//return array;
    }
}

/*****************************************************************************

What arithmetical relationships must hold amongst source, dest, len
and size for this to make sense?

Replace the "false" condition for "throw new IllegalArgumentException()"
with a test for these relationships.  The Java for "or" is || (like &&).

You don't need to declare that the method "throws IllegalArgumentException",
so you can make a habit of inserting tests like this in your programs for
the validity of the precondition,  without incurring additional Java
bureaucracy.    NEVER try or catch this Exception: it indicates a BUG
that you (or your caller) must FIX.

*****************************************************************************/