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 #13) to see how x an y share the head node.
We can codify the above as the following visitor.
/**
* Assigns the input list to the host.
* host thus "becomes" the input list.
* In the end, both host and the input list share the same head node.
*/
public class Becomes implements IAlgo {
public final static Becomes Singleton = new Becomes ();
private Becomes() {
}
/**
* @param input a LRStruct;
* @return null
*/
public Object emptyCase(LRStruct host, Object input) {
return assign(host, (LRStruct)input);
}
/**
* @param input a LRStruct;
* @return null
*/
public Object nonEmptyCase(LRStruct host, Object input) {
return assign(host, (LRStruct)input);
}
final private Object assign (LRStruct lhs, LRStruct rhs) {
lhs.insertFront (null);
lhs.setRest (rhs);
lhs.removeFront();
return null;
}
}
We shall use Becomes 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 the other LRStruct.
*/
public Object emptyCase(LRStruct host, Object input) {
return host.execute(Becomes.Singleton, input);
}
|
/**
* 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 the other LRStruct.
*/
public Object nonEmptyCase(LRStruct host, Object input) {
((LRStruct)input).execute(this, host.getRest());
return ((LRStruct)input).execute(Becomes.Singleton, host);
}
}
|
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 becomes 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.
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.
The following is the pseudo-code to perform merge sort on a list of integers.
Sort Algorithm:
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.
Hint: use exercises #1 and #2
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
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.