In general, since we are ignoring the "generics" features of Java, DrJava will occasionally complain with an "unchecked type warning" (or something similar).   Ignore these warnings -- they can be permanently suppressed by un-checking the appropriate box under "Preferences/Compiler Options" in DrJava.)

Problem 2.b (15 pts):  Use a for loop to write the code for the method copyArray as specified by the Javadoc comments below and by the JUnit test method test_copyArray in the JUnit test class TestArrayUtils.

Hints:

• The negation (i.e. exact logical opposite) of
     0 <= srcLo <= src.length - 1
  is
     srcLo < 0 OR srLo > src.length - 1. 
  In Java, this is written as
     (srcLo < 0) || (srLo > src.length - 1) 
  The notation for OR in Java is ||.
• Use the method Math.min (provided by Java) to compute the minimum of two integers.  For example, Math.min(4, -35) = -35.  What is Math.min(-55, Math.min(4, -35))?  The interactions pane of DrJava should come in handy here!

public class ArrayUtils {
    public static final ArrayUtils Singleton = new ArrayUtils();
    private ArrayUtils() {
    }

    /**
     * Copy a number of consecutive elements from a 1-dimensional array starting
     * from a given index to another 1-dimensional array starting at a given index.
     *
     * @param src != null, the source array.
     *
     * @param srcLo the starting index of in the src array from where the copying begins; 
     * 0 <= srcLo <= src.length - 1 must be true, otherwise, 
     * throw an IllegalArgumentException.
     *
     * @param maxElts >=0, the maximum number of elements in the src array to 
     * be copied to the dest array at dstLo. The actual number of elements 
     * copied is the minimum of maxElts, the number of elements remaining 
     * in src starting at srcLo, and the number of elements remaining in dest 
     * starting at dstLo.  If maxElts < 0 do nothing.
     *
     * @param dest !=null, the destination array.
     *
     * @param dstLo the starting index of the dest array.
     * 0 <= dstLo <= dst.length - 1 must be true, otherwise, 
     * throw an IllegalArgumentException.
     *
     * @exception IllegalArgumentException whenever any of the conditions of srcLo 
     * and dstLo as stated in the above are violated.
     */
    public void copyArray(Object[] src, int srcLo, int maxElts, 
                          Object[] dest, int dstLo) {
	//STUDENT TO COMPLETE

    }
    

// OTHER METHODS ELIDED
}

Problem 2.c (15 pts):  Use a for loop to write the code for the method matrix2array as specified by the Javadoc comments below and by the JUnit test method test_matrix2array in the JUnit test class TestArrayUtils.

Hints:

• Use the countElements method to find the correct size for the resultant array.
• Use the copyArray method to copy the source matrix to the resultant array one row at a time.  You will need to find a way to keep track of the starting index in the resultant array, as it will increase after each time you copy a row to it.
• Do you need to do anything when a given row in the matrix is empty?
• Do not assume that the 2-dimensional array is rectangular!!

package array;

public class ArrayUtils {
    public static final ArrayUtils Singleton = new ArrayUtils();
    private ArrayUtils() {
    }
    // OTHER METHODS ELIDED...
    

    /**
     * Converts a 2-dimensional array m to a 1-dimensional array whose size is
     * the number of elements in the input matrix m.
     * @param m != null.
     * @return a 1-dimensional array that is the concatenation of all the row arrays
     * in the matrix from the lowest row index to the highest row index.
     */
    public Object[] matrix2array(Object[][] m) {
	// STUDENT TO COMPLETE

    }
}

Problem 3:  RACs and Binary Tree Traversals (25 pts total +  15 pts extra credit)

RAC's are essentially memory devices.  They store information and retrieve it later on.    The order in which the data is "remembered" depends on what type of RAC is used.  

A tree traversal is a process that traces a path through the tree (see Lab #13).  The elements of the tree are processed in the order that they are encountered during the traversal process.   Thus we can talk about a tree traversal in terms of processing the elements of the tree in some "remembered" order through the tree.

RAC's and tree traversals are made for each other.

Consider the following BiTree visitor, called RACTraverse, that expresses a tree traversal process using a RAC as the input parameter:

Empty Case:

1. Return the given RAC

Non-Empty Case:

1. Put the root data into the given RAC.
2. Recur to the left.
3. Recur to the right.
4. Return the given RAC.

The data collected in the RAC during the traversal process can be retrieved either one element at a time or by using its elements method, which returns a list of its elements in their proper order.    We will be considering the net effect on the order of the data as it is retrieved from the RAC.

Problem 3.a (10 pts):  Stacks vs. Queues Discussion

What do you think the difference will be when a stack vs. a queue is used as the RAC in the above traversal algorithm?     That is, what is the difference in order of the data retrieved from the RAC after the traversal is completed?

• Describe your answer in terms of in-order, pre-order and/or post-order traversals.
• Justify your answer in terms of the behavior of a stack vs. a queue.

Write your answer as a comment at the top of the RACTraverse.java file.

Problem 3.b (15 pts):  Implementation of RACTraverse

Finish the implementation of  RACTraverse as per the above description.     The test code has been provided.

Once you have completed the regular portion of the exam, you may take an additional 30 minutes beyond the 4 hour limit to complete the following extra credit problems.

Problem 3.c (5 pts extra):  Tree traversal in order with respect to value -- discussion of theory

Assume that the BiTree contains objects which are either Comparable or for which a Comparator can be defined (that is, a binary comparison can be used to define a total ordering).   How would you go about creating a tree traversal such that the elements of the tree came out in order with respect to their values, not their positions in the tree?

Write you answer as a comment at the top of the Test_RACTraversal_Extra.java file.

Problem 3.c (10 pts extra):  Tree traversal in order with respect to value -- implementation of code

Write any code necessary to implement your theory on how to produce a traversal of a tree ordered in terms of value (either "lowest" to "highest" or "highest" to "lowest").     Write the test code to thoroughly test you algorithm in the Test_RACTraversal_Extra.java file.   You will be graded on the completeness and thoroughness of your test code.

Note:  Integers, Doubles and Strings are all Comparable objects.