You are here

Example

6 June, 2016 - 14:38
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: