This tutorial consists of several exercises on writing list algorithms on LRStruct as visitors IAlgo. It serves to re-enforce your understanding of the framework for writing algorithms that mutate the list structure, without creating new lists. Contrasting these algorithms against their counterparts in the immutable list framework (IList) will enhance your understanding the two list frameworks.
To compile and test your algorithms, you will need to download the file lrs.jar from the following link:
http://www.owlnet.rice.edu/~comp212/02-fall/dataStructures/list/lrs/
lrs.jar contains the binary class files for the LRStruct framework discussed in lecture 12.
The link http://www.owlnet.rice.edu/~comp212/02-fall/dataStructures/list/lrs/doc/ contains the full javadoc documentation for LRStruct.
To compile your code, use the command:
javac -classpath .:lrs.jar your-source-code.java
To run your test program, use the command:
java -classpath .:lrs.jar your-test-program
Consider the problem of removing the last element from an LRStruct. The following shows the algorithm and the actual code.
Object-Oriented Algorithm (OOA) |
Object-Oriented Coding (OOC) |
| An algorithm to remove the last element from an LRStruct is a concrete IAlgo visitor. |
public class RemLast implements IAlgo {
// Singleton
|
| When the LRStruct host is empty, throw an exception as specified. The code on the right simply expresses such an action. |
public Object emptyCase(LRStruct host, Object inp) {
throw new java.util.NoSuchElementException("Empty list has no data.");
}
|
|
When the LRStruct host is not empty, ask the host's
rest for help in determining whether or not the host is holding the last
element, passing the host as a parameter just in case this is true and the
last element needs to be removed. |
public Object nonEmptyCase(LRStruct host, Object inp) {
return host.getRest().execute(RemLastHelp.Singleton, host);
}
}
|
| The algorithm for a host LRStruct to help remove the last element from the preceding LRStruct, p, is a concrete IAlgo visitor whose input parameter is p. |
public class RemLastHelp implements IAlgo {
// Singleton
|
| The empty LRStruct tells the preceding LRStruct to remove its first. |
/**
* @param inp the LRStruct preceding host.
*/
public Object emptyCase(LRStruct host, Object inp) {
return ((LRStruct)inp).removeFront();
}
|
| A non-empty LRStruct asks its rest for help to remove its last element passing itself as a parameter. |
/**
* The last element of the (non-empty) host is the
* last element of inp, the LRStruct preceding host.
*/
public Object nonEmptyCase(LRStruct host, Object inp) {
return host.getRest().execute(this, host);
}
}
|
|
RemLastHelp can be defined and instantiated anonymously inside of the RemLast.nonEmtpyCase(...) as follows. public class RemLast implements IAlgo {
// other methods elided...
public Object nonEmptyCase(LRStruct host, Object inp) {
return host.getRest().execute(new IAlgo() { // Anonymous inner class!
public Object emptyCase(LRStruct h, Object p) {
return ((LRStruct)p).removeFront();
}
public Object nonEmptyCase(LRStruct h, Object p) {
return h.getRest().execute(this, h);
}
}, host);
}
}
In the above, note how the parameters of the anonymous inner class are renamed in order to avoid masking the parameter names in the outer object. Also note how the algorithm has the side-effect of removing the last element from a non-empty LRStruct host.
|
|
Use the format of the above example to write the following algorithms on
LRStruct. It is convenient to package the algorithms in a package named lrs.visitor.
Be sure to create the appropriate subdirectories to match your package
name. You may want to review the counterparts of these algorithms for the
immutable list, listFW.IList at the following
link:
http://www.owlnet.rice.edu/~comp212/02-fall/dataStructures/list/listFW/visitor/.
Concatenate the LRStruct host with another LRStruct. Return
null. After the execution of this algorithm, the host should be the
original host concatenated with the input parameter.
Algorithm Description |
Algorithm Code |
| An algorithm to concatenate an LRStruct host with another LRStruct, inp, is a concrete IAlgo visitor, which takes as input parameter the LRStruct inp. |
public class ReverseLRS implements IAlgo {
// Singleton
|
| When the LRStruct host is empty, what should we
do? We need to turn the host into the input parameter itself.
A simple assignment will not do (why?).
Try the following: insert null to the front of the host. This mutates the host to a non-empty list. Now set the rest of the host to the input parameter inp. This makes inp the tail of the host. Now remove the front element from the host. What do we get? |
/**
* @param inp an LRStruct to be concatenated to the host.
*/
public Object emptyCase(LRStruct host, Object inp) {
// Code to fill out;
}
|
|
When the LRStruct host is not empty, recur on the rest! |
public Object nonEmptyCase(LRStruct host, Object inp) {
// code to fill out;
}
}
|
Reverse an LRStruct host. Return null. The algorithm should
have the side-effect of reversing the host that executes this algorithm.
Algorithm Description |
Algorithm Code |
| An algorithm to reverse an LRStruct is a concrete IAlgo visitor. |
public class ReverseLRS implements IAlgo {
// Singleton
|
| When the LRStruct host is empty, what should we do? |
public Object emptyCase(LRStruct host, Object inp) {
// Code to fill out;
}
|
|
When the LRStruct host is not empty, ask the host's rest for help, passing the host as the input parameter! |
public Object nonEmptyCase(LRStruct host, Object inp) {
return host.getRest().execute(ReverseHelp.Singleton, host);
}
}
|
| The algorithm for a host LRStruct to help reverse the
enclosing LRStruct, p, is a concrete IAlgo
visitor whose input parameter is p itself.
The following invariant holds: the elements from p to host is the reverse of the original list so far. |
public class ReverseHelp implements IAlgo {
// Singleton
|
| This marks the end of the enclosing list p. From the invariant property, p is the reverse of the original list. Is there anything to do here?. |
/**
* @param inp the enclosing LRStruct.
*/
public Object emptyCase(LRStruct h, Object inp) {
// code to fill out;
}
|
| How can we advance in the list and re-establish the
invariant here?
Remove the first element from the host and insert it to the front of the enclosing list, the input parameter, and recur! |
/**
*/
public Object nonEmptyCase(LRStruct h, Object inp) {
// code to fill out;
return h.execute(this, inp);
}
}
|
ReverseHelp can be defined and instantiated anonymously inside of the ReverseLRS.nonEmtpyCase(...). As an inner class, ReversHelp has access to the enclosing host, so there is no need to pass host to this helper. However, we need to declare the enclosing host as final in the parameter list of the calling method. public class ReverseLRS implements IAlgo {
// other methods elided...
public Object nonEmptyCase(final LRStruct host, Object inp) {
return host.getRest().execute(new IAlgo() { // Anonymous inner class!
public Object emptyCase(LRStruct h, Object p) {
// ???;
}
public Object nonEmptyCase(LRStruct h, Object p) {
// code to fill out here;
// ???;
return h.execute(this, null);
}
}, null);
}
}
I
|
|