Comp201: Principles of Object-Oriented Programming I
Spring 2008 -- Mutable List Processing - Exercises on LRStruct

The purpose of this lab is to provide more practice on manipulating the mutable list structure LRStruct. It is always helpful to draw a few pictures to visualize what the list should look like and how it should be manipulated. Use anonymous inner classes whenever you need helpers.

0. Weaving two lists into one list.

Given two lists that do not share any node, write a visitor called Zipper that “zips” them together like a zipper into one list. For example, when you zip (5, 3, 9) together with (-7, 0, 8, -15), the result is the list (5, -7, 3, 0, 9, 8, -15). In the case of LRStruct, we want both LRStruct to become (5, -7, 3, 0, 9, 8, -15). Note that the lists may have different lengths.

To solve this problem, we need to know how to make two LRStruct objects share the same head node. Observe the following:

Given two distinct LRStruct x and y, we can "assign" y to x by performing the following sequence of operations:

x.insertFront (null);
x.setRest (y);
x.removeFront();

x's head is now pointing to y's head. Draw some pictures (as illustrated in lecture #28) to see how x an y share the head node.

We can codify the above as the following visitor.

/**
* Makes the host share the same head node with the input list.
* The input list does not change.
* In the end, both host and the input list share the same head node.
*/
public class Share implements IAlgo {
    public final static Share Singleton = new Share ();
    private Share() {
    }

    /**
     * @param input a LRStruct;
     * @return null
     */
    public Object emptyCase(LRStruct host, Object... input) {
        return assign(host, (LRStruct)input[0]);
    }

    /**
     * @param input a LRStruct;
     * @return null
     */
    public Object nonEmptyCase(LRStruct host, Object... input) {
        return assign(host, (LRStruct)input[0]);
    }

    /**
     * "Assigns the LRStruct on the right-hand-side, rhs, 
     * to the LRStruct on the left-hand-side, lhs, so that
     * in the end, they both share the same head node.
    */
    private Object assign (LRStruct lhs, LRStruct rhs) {
        lhs.insertFront (null);
        lhs.setRest (rhs);
        lhs.removeFront();
        return null;
    }
}

We shall use Share in the algorithm to "weave" two LRStruct together to obtain a single one.

/**
* Weaves ("Zips") together two distinct LRStructs that do not
* share any node to yield a single LRStruct.
* For example, when we zip (5, 3, 9), the host, together
* with (-7, 0, 8, -15), the input parameter, both lists
* become (5, -7, 3, 0, 9, 8, -15).
*/

public class Zipper implements IAlgo {
    public static final Zipper Singleton = new Zipper();
    private Zipper() {
    }

    /**
     * host is empty, so there is nothing to zip with.
     * Just let host become the input list.
     * @param host empty
     * @param input [0] the other LRStruct.
     */
    public Object emptyCase(LRStruct host, Object... input) {
        return host.execute(Share.Singleton, input[0]);
    }

    /**
     * Recursively weave the input LRStruct with host's rest.
     * The result is both input and host'rest share the same
     * head node.  All we need to do next is assign host to
     * input so that input "becomes" the host and share the same
     * head node as host.
     * @param host not empty
     * @param input [0] the other LRStruct.
     */
    public Object nonEmptyCase(LRStruct host, Object input) {
        ((LRStruct)input[0]).execute(this, host.getRest());
        return ((LRStruct)input[0]).execute(Share.Singleton, host);
    }
}

Download the above code here: lab11.zip

Exercise #1: Unzipping a list into two lists.

Given a list, unzip it to obtain two lists. One list contains all the even indexed elements of the original list; the other list contains all the odd-indexed elements of the original list. For LRStruct, we want the host to become the list that contains only the even-indexed elements, and the return Object of the visitor's methods to be the list holding the odd-indexed elements of the original host list.

The key here is to compare the following things:

The mutated rest of the host list, that results from unzipping the un-mutated original rest of the host list.
The returned list from unzipping the rest of the host list.
The desired, mutated rest of the final, mutated host list list after the unzipping process is completely done. Note that this is not necessarily the same as first item above.

Hint: Take an example list, such as {a, b, c, d, e, f}, and use it to compare the above 3 lists. Unzipping {a, b, c, d, e, f} should mutate this host list to {a, c, e} and return {b, d, f}.

Exercise #2: Merging two sorted lists into one list.

Write an LRStruct visitor, called Merge that merges the host and input list into one list sorted in ascending order. Assume the host and input list do not share any node and contain Integer objects sorted in ascending order. Also, they need not have the same length. In the end, both the host and the input list should share the same nodes. The algorithm should not create any new list nodes. For examples, (1 3 8 9) merged with (-5 6 7) will result in both lists becoming (-5 3 6 7 8 9). Use anonymous inner classes whenever appropriate.

Remember that you do not know a priori whether the input list is empty or not. However, your algorithm depends on that fact. Thus you have no choice but to delegate to it since the OOP "rule" is to always delegate to another object if your algorithm depends on what that object is.

If a non-empty host list contains a first which is the smaller between it and some other list's first, what can you say about the placement of that smallest first value in the final merged list? What can you say the host list after the other list has been merged into its rest?

What's the difference between the situation where the first list's first is smaller than the second list's first, vs. where the second list's first is smaller than the first list's first?

Exercise #3: Merge sorting a list.

The following is the pseudo-code to perform merge sort on a list of integers.

Sort Algorithm:

Host list is empty
- Done!
Host list is non-empty:
- Host list has only one element:
  - Done!
- Host list has more than one element:
  - Split the list into two sublists;
  - (Recursively) Sort each of the sublists;
  - Merge the sorted sublists into one list.

Write a visitor to implement the above algorithm to sort an LRStruct containing Integers. You should move the nodes of the LRStruct around and not creating any new nodes.

The differentiation between a non-empty host list having one vs. many elements is crucial because , if omitted, the splitting of a one-element list would result in another one-element list. Thus the list would never get any smaller, never reach a base case and would result in running forever, i.e. a stack overflow error. So, how do you figure out if a list has only one element--without using a conditional, of course?

Hint: use exercises #1 and #2

Exercise #4:

Given an LRStruct ("list") containing Integer objects, write a visitor called AddPairs to replace each pair of consecutive Integers in the host with their sum. For a host with an odd number of elements, the last element is left unchanged. For examples, (1 2 3 4) is transformed into (3 7), and (5 10 20 25 30 –30 17) is transformed into (15 45 0 17). Use anonymous inner classes whenever appropriate

Exercise #5:

Write a LRStruct visitor called SwapEnds to swap the first element and the last element of the host. For example, suppose host = (5, 12, -9, 0) before execution, then after execution, host = (0, 12, -9, 5). Do this with the fewest list traversals as possible. Do not swap the nodes; just swap the contents of the first data node and the last data node. Write all helpers as anonymous inner classes.

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

Comp201: Principles of Object-Oriented Programming I Spring 2008 -- Mutable List Processing - Exercises on LRStruct