Available under Creative Commons-ShareAlike 4.0 International License. Download for free at http://cnx.org/contents/402b20ad-c01f-45f1-9743-05eadb1f710e@37.6
Consider the problem of inserting an Integer object in order into a sorted list of Integers. Let us contrast the insert in order algorithms between IList, the immutable list, and LRStruct, the mutable list.
Insert in order using factory |
Insert in order using mutation |
import listFW.*; public class InsertInOrder implements IListAlgo { private IListFactory _fact; public InsertInOrder(IListFactory lf) { _fact = lf; } /** * Simply makes a new non-empty list with the given * parameter n as first. * @param host an empty IList. * @param n n[0] is an Integer to be inserted in order into host. * @return INEList. */ public Object emptyCase(IEmptyList host, Object... n) { return _fact.makeNEList(n[0], host); } /** * Based on the comparison between first and n, * creates a new list or recur! * @param host a non-empty IList. * @param n an Integer to be inserted in order into host. * @return INEList */ public Object nonEmptyCase(INEList host, Object... n) { return (Integer)n[0] < (Integer)host.getFirst() ? _fact.makeNEList(n[0], host): _fact.makeNEList(host.getFirst(), (IList)host.getRest().execute(this, n[0])); } } |
import lrs.*; public class InsertInOrderLRS implements IAlgo { public static final InsertInOrderLRS Singleton = new InsertInOrderLRS(); private InsertInOrderLRS() { } /** * Simply inserts the given parameter n at the front. * @param host an empty LRStruct. * @param n n[0] isan Integer to be inserted in order into host. * @return LRStruct */ public Object emptyCase(LRStruct host, Object... n) { return host.insertFront(n[0]); } /** * Based on the comparison between first and n, * inserts at the front or recurs! * @param host a non-empty LRStruct. * @param n n[0] is an Integer to be inserted in order into host. * @return LRStruct */ public Object nonEmptyCase(LRStruct host, Object... n) { if ((Integer)n[0] < (Integer)host.getFirst()) { return host.insertFront(n[0]); } else { return host.getRest().execute(this, n[0]); } } } |
Note: The insert in order algorithm for LRStruct need not create any new list and thus needs no factory. Download the above
code:
- 1254 reads