In either case, send dxnguyen@rice.edu and swong@rice.edu an e-mail to notify your submission. We will reply to confirm your submission.
Pledge of Honor |
1. 25 pts | 2. 20 pts + 5 pts extra | 3. 30 pts + 5 pts extra | 4. 25 pts | Total 100 pts + 10 pts extra |
Below is an implementation of IList using array. Some of the methods are stubbed out. Your task is to complete all the stubbed code. For your convenience, we have written a JUnit test class called TestList. Click here to download the jar file that contains all the stubbed out code and all source code needed to compile and test your solution. Note: ArrayListFactory.java is in the subdirectory listFW/factory.
To extract files from a jar file, enter the command: jar -xfv jarFileName.
package listFW.factory; import listFW.*; import listFW.visitor.Length; // to compute the number of elements in an IList. /** * Manufactures concrete IEmptyList and INEList objects as arrays of Objects. * @author Dung X. Nguyen * @since Copyright 2003 by DXN - All rights reserved */ public class ArrayListFactory implements IListFactory { /** * NOTE the use of multiple interface inheritance below! */ private static class ArrayList implements IEmptyList, INEList { static final ArrayList MTList = new ArrayList(); // the empty list! private Object[] _elts; // the data elements in this ArrayList. private int _firstIdx; // the index of the first element in this ArrayList. /** * Anonymous inner object to copy an Ilist to the array _elts starting from a given * index, idx, assuming there is enough room left in _elts to hold the data in _elts. */ private IListAlgo copy2array = new IListAlgo() { public Object emptyCase(IEmptyList host, Object idx) { return null; } /** * Example: suppose _elts = {a, b, c, d, e, f, g}, host = (x y z) and idx = 2. * After copying, _elts = {a, b, x, y, z, f, g}. */ public Object nonEmptyCase(INEList host, Object idx) { // STUDENTS TO WRITE THE CODE. 7pts } }; /** * Initializes _elts to an empty array of Objects and _firstIdx to 0. */ private ArrayList() { _elts = new Object[0]; _firstIdx = 0; } /** * Initializes _elts to reference the given array of Objects elts * and _fitstIdx to the given index start. */ private ArrayList(Object[] elts, int start) { _elts = elts; _firstIdx = start; } /** * Initializes this ArrayList to contain the given Object dat as the first element, * and the rest of this ArrayList to contain the elements of the given IList tail. */ public ArrayList(Object dat, IList tail) { // STUDENTS TO WRITE THE CODE. 8 pts // HINT: USE THE Length VISITOR AND copy2array. } /** * Returns the fist data Object in this ArrayList. * Throws an Exception if this ArrayList is empty. */ final public Object getFirst() { // STUDENTS TO WRITE THE CODE. 2 pts } /** * Returns an ArrayList representing the rest of this ArrayList. * Throws a NoSuchElementException if this ArrayList is empty. */ final public IList getRest() { // STUDENTS TO WRITE THE CODE. 3 pts } /** * An emtpty ArrayList will call alog.emptyCase, while a non-empty ArrayList will call * algo.nonEmptyCase. */ final public Object execute(IListAlgo algo, Object inp) { // STUDENTS TO WRITE THE CODE. 5 pts } /** * The unique instance of this class. */ public static final ArrayListFactory Singleton = new ArrayListFactory(); private ArrayListFactory() { } /** * Creates an empty list. * @return an IEmptyList object. */ public IEmptyList makeEmptyList() { return ArrayList.MTList; } /** * Creates a non-empty list containing a given first and a given rest. * @param first a data object. * @param tail != null, the rest of the non-empty list to be manufactured. * @return an INEList object containing first and tail * @exception IllegalArgumentException if tail == null. */ public INEList makeNEList(Object first, IList tail) { if (null == tail) { throw new IllegalArgumentException("tail is null!"); } return new ArrayList(first, tail); } }
In this problem we will build a model of cars and remote entry key fobs – the little things on a key chain used to remotely lock or unlock a car. In our model we have
· factories that make cars (ICarFactory) with a given color,
· cars (ICar) that have unique vehicle identification numbers (VIN) and can make their associated key fobs.
· key fobs (IKeyFob) have a single button on it (i.e. a single method of no parameters) that controls a single car.
You are to write the code for two ICarFactorys: SaturnFactory and MercedesFactory. The ICars made by these factories should have these behaviors when the button on their associated key fobs is pressed:
Action: |
Saturn |
Mercedes |
When car is initially created: |
Unlocked |
Unlocked |
After first time IKeyFob.pressBtn()
is called: |
Locked |
Locked, but
security system is unarmed. |
After second time IKeyFob.pressBtn()
is called: |
Unlocked |
Locked and
security system armed. |
After third time IKeyFob.pressBtn()
is called: |
Locked |
Unlocked |
After fourth time IKeyFob.pressBtn()
is called: |
Unlocked |
Locked, but
security system is unarmed. |
Etc. |
… |
… |
Note that the Saturn undergoes a two-click cycle, but the
Mercedes undergoes a three-click cycle.
To simplify matters, we will simply have the car do a System.out.println(…) with enough information to tell what car was affected (i.e. make, color and VIN), and what the effect of pressing the key fob’s button was (i.e. locked, unlocked, unarmed, armed).
Your task is write
the SaturnFactory and MercedesFactory
classes such that the above behaviors are replicated and the following
conditions are met (20 pts):
5 pts Extra Credit: Include the ability for a car to identify exactly which key fob is controlling it.
To facilitate testing, we have supplied you with the CarDealer class which instantiates 2 Saturns, one of which has two key fobs, and 2 Mercedes. It then randomly picks from a single key fob from the 5 key fobs and presses its button. It repeats this 15 times. CLICK HERE TO DOWNLOAD THE JAR FILE CONTAINING THE SOURCE CODE FOR THE INTERFACES AND TEST CODE.
A typical output from running the main(..) method of CarDealer is:
CarDealer:
KeyFob #2 picked.
The
blue Mercedes with VIN #2661678 is now locked but unarmed!
CarDealer:
KeyFob #0 picked.
The
blue Saturn with VIN #23328673 is now locked by key fob ID#29744585!
CarDealer:
KeyFob #1 picked.
The
red Saturn with VIN #13655059 is now locked by key fob ID#28472268!
CarDealer:
KeyFob #4 picked.
The
blue Saturn with VIN #23328673 is now unlocked by key fob ID#22927632!
CarDealer:
KeyFob #3 picked.
The
red Mercedes with VIN #12206609 is now locked but unarmed!
CarDealer:
KeyFob #4 picked.
The
blue Saturn with VIN #23328673 is now locked by key fob ID#22927632!
CarDealer:
KeyFob #2 picked.
Beep! Beep! The blue Mercedes with VIN #2661678 is now locked and armed!
CarDealer:
KeyFob #3 picked.
Beep!
Beep! The red Mercedes with VIN #12206609 is now locked and armed!
CarDealer:
KeyFob #2 picked.
The
blue Mercedes with VIN #2661678 is now unlocked, unarmed and has adjusted the
seats just for you!
CarDealer:
KeyFob #4 picked.
The
blue Saturn with VIN #23328673 is now unlocked by key fob ID#22927632!
CarDealer:
KeyFob #4 picked.
The
blue Saturn with VIN #23328673 is now locked by key fob ID#22927632!
CarDealer:
KeyFob #2 picked.
The
blue Mercedes with VIN #2661678 is now locked but unarmed!
CarDealer:
KeyFob #4 picked.
The
blue Saturn with VIN #23328673 is now unlocked by key fob ID#22927632!
CarDealer:
KeyFob #3 picked.
The
red Mercedes with VIN #12206609 is now unlocked, unarmed and has adjusted the
seats just for you!
CarDealer: KeyFob #0 picked.
The
blue Saturn with VIN #23328673 is now locked by key fob ID#29744585!
In the above printout, the Saturns include the extra credit behavior of being able to identify their individual key fobs. You are not required to replicate the exact wording above, just the included information.
“Higher order” functions on a list are operations on
lists that take other functions as input parameters.
The following should be familiar to those die-hard Scheme-heads:
Foldr(empty,
b , f) = b
and
Foldr(aList,
b, f) = f(first, Foldr(rest, b, f)
For example, suppose
aList =
(x_{n}, x_{n-1}, x_{n-2}, … x_{2}, x_{1},
x_{0})
then
foldr(aList,
b, f) = f(x_{n}, f(x_{n-1}, f(x_{n-2}, …f(x_{2},
f(x_{1}, f(x_{0}, b)))…)))
Thus, we see that
b = a base case value
and
f= an inductive case function which calculates the next recursive result, given an element (first) of a list and the current recursive result.
That is, f(x,
current_rr) = next_rr
Foldr is the same as
“natural recursion” or “reverse accumulation”.
Foldl(empty,
b , f) = b
and
Foldl(aList,
b, f) = Foldl(rest, f(first, b) ,f)
Again, for example using the same definition of aList
as above,
Foldl(aList,
b, f) = f(x_{0}, f(x_{1}, f(x_{2}, …f(x_{n-2},
f(x_{n-1}, f(x_{n}, b)))…)))
where b
and f are define exactly as above.
Note once again that if the list is empty, the result of Foldl is simply b.
Notice also that the order of the calculation using Foldl
is the reverse of that for Foldr.
Foldl is the same as “forward accumulation”.
Filter(empty, pred) = empty_{ }
and
Filter(aList,
pred) = { x_{i} | pred(x_{i})
= true} where x_{i} is an
element of aList
That is, the result of filtering
the list with the predicate is the list of elements from aList
for which the predicate function, pred,
is true when applied to each of those
elements.
Given the interface IFoldInp,
which encapsulates the base case value and the inductive case function (see the
source file for complete documentation), you are to write
And, given the interface ILambda,
which can be used to represent a predicate function, you are to write
5 pts Extra credit: Using a either a new class, FoldFilter that implements IFoldInp, or a new method, IFoldInp makeFoldFilter(ILambda pred), of the supplied test class, HigherOrderTests, create an IFoldInp that utilizes a given ILambda predicate to create a filtering operation using either Foldr or Foldl. One difference will be that this filtering will need to create a new LRStruct and not modify the original host.
When the main(…)
method of HigherOrderTests is run, the following output should be obtained:
lrs
= (1 2 3 4 5 6 7 8 9 10)
add
foldr on lrs = 55
add
foldrl on lrs = 55
mult
foldr on lrs = 3628800
mult
foldrl on lrs = 3628800
cons
foldr on lrs = (1 2 3 4 5 6 7 8 9 10)
cons
foldrl on lrs = (10 9 8 7 6 5 4 3 2 1)
filter
all multiples of two on lrs = (2 4 6 8 10)
filter
all non-multiples of two on lrs = (1 3 5 7 9)
filter
range 3 < x < 7 on lrs = (4 5 6)
filter range !(3 < x < 7) on lrs = (1 2 3 7 8 9 10)
//
The following is the output of the extra credit:
foldr-filter
all multiples of two on lrs = (2 4 6 8 10)
foldl-filter
all multiples of two on lrs = (10 8 6 4 2)
foldr-filter
all non-multiples of two on lrs = (1 3 5 7 9)
foldl-filter
all non-multiples of two on lrs = (9 7 5 3 1)
The following is the code for a heap implementation of an IRAContainer that is a priority queue containing Comparable. Your task is to complete the stubbed out code.
HINT: You may find it useful to call on the siftUp and siftDown method of the Heapifier. Click here to download the source code for all required classes (including the JUnit test class).
package rac; import listFW.*; /** * Uses the Heap structure to implement a priority queue. * Assume the container only contains Comparable elements. */ public class PQArrayContainer implements IRAContainer { private Comparable _elts[]; private int _insertIdx; // next available index for insertion. public PQArrayContainer(int size) { _elts = new Comparable[size]; _insertIdx = 0; } /** * Empty the container. * NOTE: This implies a state change. * This behavior can be achieved by repeatedly removing elements from this IRAContainer. * It is specified here as a convenience to the client. */ public void clear() { _insertIdx = 0; } /** * Return TRUE if the container is empty; otherwise, return * FALSE. */ public boolean isEmpty() { // STUDENT TO COMPLETE; 2 pts } /** * Return TRUE if the container is full; otherwise, return * FALSE. */ public boolean isFull() { // STUDENT TO COMPLETE; 3 pts } /** * Return an immutable list of all elements in the container in the same order as the _elts array. * @param fact for manufacturing an IList. */ public IList elements(IListFactory fact) { // STUDENT TO COMPLETE; 5 pts } /** * Remove the next item from the container and return it in log(n) time. * NOTE: This implies a state change. * @throw an Exception if this IRAContainer is empty. */ public Object get() { // STUDENT TO COMPLETE; 7 pts } /** * Add an item to the container in log(n) time. * NOTE: This implies a state change. * @param input the Object to be added to this IRAContainer. * @throw an Exception if this IRAContainer is full. */ public void put(Object input) { // STUDENT TO COMPLETE; 8 pts } /** * Return the next element in this IRAContainer withour removing it. * @throw an Exception if this IRAContainer is empty. */ public Object peek() { return _elts[0]; } }