Comp201: Principles of Object-Oriented Programming I
Spring 2008 -- Lab 15: Writing Loops and Processing Arrays   

To kill two birds with one stone, we will first go over the sorting portion of last year's Exam 3 as it involves both array processing with loops and template pattern-based sorting.

In this lab, we will practice writing loops to process arrays.

The big problem with arrays is that they just don't quite have enough intelligence. We need a smarter array, one that can automatically resize itself to add more elements, will shrink when elements are removed, and supports various odd and sundry other features that might be handy. In everyday Java parlance, we want to create a "vector" (see the Java documentation for java.util.Vector for comparison).

Creating a Smarter Array

Download the supplied lab code: lab15.zip

Basically, if we want to give an array more intelligence we have to "wrap" it in another class. We cannot subclass the array because all arrays are final and thus not able to be subclassed. But actually, composing with an array gives us the ability to achieve the dynamic reclassification-type behavior needed to make the array grow and shrink.

SmartArray holds an array that is at least as large as is presented to the outside world (an apparent array). Internally, it keeps a maximum allowable index value, _next, which tells it where the end of the apparent working array is located within the larger storage array, _data. So long as _next <=_data.length then the apparant array can grow and shrink at will.

If _next exceeds _data.length, then we simply need to replace _data with a new array that is twice as large and copy all the data over to the new storage array. Whenever we need to increase the size of the array, it is important that we increase by a constant multiplicative factor that is greater than one, as opposed to increasing it by a fixed additive constant. In doing so, the cost for increasing the size is amortized over time, and we can prove that the cost for adding an element to the array is bounded by a fixed constant. That's a lot of fancy words that means: if you double the size of the array every time you need to increase its size, after you add lots and lots of new elements, you find that total expense of copying the array over when necessary becomes a fixed cost on a per element basis.

Study the code for SmartArray to see how the following methods work:

• int size() -- returns the size of the apparent array
• Object get(int ix) -- returns the ix'th element if ix is a valid index of the apparent array
• void set(int ix, Object elt) -- sets the ix'th element to the given value if ix is a valid index of the apparent array
• void checkBounds(ix) -- throws an exception if the given index is not a valid index of the apparent array.

Notice how the index bounds have to be checked over and over again. No polymorphism to help us out here!

Write the code for the methods with missing bodies, in this recommended order:

1. SmartArray toSmartArray(Object[] source)-- need to write the loop to copy the input array. Returns a new SmartArray.
2. String toString(Object[] elts) -- Watch these situations: length = 0 and the last element in the array.
3. String toString() -- this shows you the entire storage array plus the value of _next.
4. void add(Object elt)-- if the storage array (_data) is too small, create a new one that is twice as large and copy all the old and the one new element over to it. Set _next appropriately. See the test case for example details.
5. boolean contains(Object x) -- returns true if x is somewhere, at least once, in the apparent  array.   Try writing this method using the standard "counted" for loop as well as the "for each" loop style. 
   • Be careful that a for-each loop will automatically process the entire array which is not what you want.
   • Consider the utility method, System.arrayCopy(), which can be found in the main Java API docs.   This is a highly optimized array copy routing.
6. Object remove(int ix)-- Check that ix is valid. Write a loop to shift the elements over to fill the empty spot. Which elements need to be shifted. Set _next appropriately. Study the test case carefully to make sure you understand the actual behavior of remove!
7. Object[] toArray()-- copy only the relevant storage array elements into a new array.
8. SmartArray remDup()-- For each element, remove any duplicates of it in the array.
   • Write a loop that goes through every element of the list.
   • Inside that loop, write a loop that removes any duplicates of the current element in the outer loop.
   • Which direction should the inner loop traverse the array? From where to where? Think about which element isreferenced by an index after you remove that index.
   • Write the algorithm without the return SmartArray first, then add that feature in. How do you insure that any duplicate is only recorded once?
9. SmartArray unzip() -- If you remove an element, what is the next element to process?
10. void zip(SmartArray other)-- tricky in spots--be careful and consider all the possibilities!
    • Best bet is to create a new storage array.
    • Which SmartArray is larger? How can you remember which is the larger vs the smaller array?
    • What do you about any "leftover" elements?
    • How can you keep from duplicating code?

Don't you miss polymorphism now? Do you see why it's better to let the objects take care of themselves than to have to check everything all the time?

Additional Exercises:

1. Create a class called util.ArrayUtil with the following method:
   1. public static boolean equals(Object[] x, Object[] y) -- takes 2 arrays of Objects and returns a boolean true if they are equal, which means that
      • x and y are the same length.
      • for all valid indices, i, x[i].equals(y[i[) returns true
      • if x[i] is null, then y[i] is null as well.
      • These specifications match those of the Sun-supplied java.util.Arrays.equals(Object[] x, Object[] y) method.
      • To test your code, substitute ArrayUtil.equals() in the body of the arrayEquals() method in the test class.
2. The remDup method your wrote above traverses the array way too many times if there are multiple duplicates in the array. This is because remove will traverse the entire array for each element removed. Write another version called remDupBetter that doesn't use remove but instead incorporates the shifting of elements itself. This new implementation should traverse the array only once per duplicate found.
   • If you haven't found a duplicate yet, how much do you shift the elements by?
   • What if you've found one duplicate? Two duplicates?
   • How does the amount of shifting affect the new value of _next?
   • Should this algorithm traverse the array in the same directions as the original algorithm?
   • To test, copy the test_remDup method in the test class and use your new method.
3. Likewise, if you used remove in your unzip method, that can algorithm probably be improved by writing your own custom loops for this situation. Try writing an unzipBetter which only traverses the list once. This is a tough algorithm. If you can do this one, you will be a pro at loops and arrays!
   • I recommend that you sit down with some blocks and work out the algorithm before you try to code it.
   • Since you are treating every other element in the array differently, how much should you increment your loop index every time?
   • Watch out for accessing something beyond the end of the apparent array (>_next)!!
   • How much do you need to shift any given element over by? Compare this to your remDupBetter algorithm.
   • What is _next when you are done?
   • To test, copy the test_unzip method in the test class and use your new method.
4. Try writing the for loops above as while loops.

Last Revised Thursday, 03-Jun-2010 09:50:28 CDT

©2008 Stephen Wong and Dung Nguyen