Imagine a world of ants that live in a one-dimensional space. A queen ant can make a bunch of worker ants. Each time she gives birth to a worker ant, she gives it a name. A worker ant can always tell what its name is. A worker ant from a particular colony can always calculate its distance from its queen. A worker ant can also move its queen to a different location. Wherever the queen moves to, ALL of her workers always know their relative distance from her. We want to keep track of all the ants in our ant world and all the ants in each of the existing colonies. We want to model the fact that each queen produces its own worker ants, each one which can move its queen around without telling the other ants in the same colony, yet ALL of the ants in the same colony would know where their queen is.
The above can be modeled by a Queen class with an abstract
Worker inner class as shown below. This example illustrates the
differences between static and non-static fields, methods and embedded classes.
/**
* Models ants living in a 1-dimensional world
*
*
* The Worker inner objects have direct access to the location of its outer
* Queen object.
*
* @author A.L. Cox
* @author D.X. Nguyen
* @author S.B. Wong
* @since 02/06/2005
*/
public class Queen {
/**
* The total number of ants (queens and workers for all the queens) that
* currently exist in our ant world.
*
* Why is this field static?
*/
private static int _ants;
/**
* The location of this Queen object with respect to 0.
*
* Why is this field non-static?
*/
private int _origin;
/**
* The total numbers of living worker ants produced by this Queen object.
*
* Why is this field non-static?
*/
private int _workers;
/**
* Is part of a Queen instance, just like the origin field and the
* makeWorker() method are parts of a Queen instance.
* Any concrete implementation of Worker must implement the getName()
* method to return the name given by its Queen at birth time.
*
* Why can't this class be static?
*/
public abstract class Worker {
/**
* The location of this Worker object.
*/
private int _location;
/**
* Increments _ants and _workers because every time a Worker is
* instantiated, a new ant is added to our ant world, a new worker ant
* is added to the colony of this outer Queen object.
* @param loc the starting location of this Worker object.
*/
public Worker(int loc) {
_location = loc;
_ants++; // The worker is an ant.
_workers++;
}
/**
* @return the relative distance between this Worker and its outer Queen
* object.
*/
public int calcDist() {
return _location - _origin;
}
/**
* The name will be given at birth. The code cannot be written at
* this point and thus must be abstract.
* @return name of the worker
*/
public abstract String getName();
/**
* Our worker has been stepped on! (No one holds a reference
* to this object anymore. It's being garbage collected.)
*/
protected void finalize() {
_ants--; // The worker is an ant.
_workers--;
}
/**
* Changes the location of this Worker object to a new location.
* @param loc the new location for this Worler object.
*/
public void moveTo(int loc) {
_location = loc;
}
/**
* Changes the origin of the outer Queen object to a new location.
* @param org the new origin for the outer Queen object.
*/
public void moveQueen(int org) {
moveTo(org);
_origin = org;
}
}
/**
* Initializes the origin of this Queen object to a given location.
* Increments _ants since this new Queen object is an ant.
* @param org the starting origin of this Queen object.
*/
public Queen(int org) {
_ants++; // The queen is an ant.
_origin = org;
}
/**
* Return the total number of all ants, including all of the
* queens and their respective workers.
*
* Why is this method static?
* Can it be non-static?
*/
public static int countAllAnts() {
return _ants;
}
/**
* @return the total number of workers that belong to this Queen object
*
* Why isn't this method static?
*/
public int countMyWorkers() {
return _workers;
}
/**
* Factory method: relegate the task of manufacturing concrete
* Worker objects to the Queen object because the Queen object
* intrinsically "knows" how to make its inner objects.
* @param name The name of the Worker.
*/
public Worker makeWorker(final String name) {
// Anonymously create a Worker object by overriding getName().
return new Worker(_origin) {
public String getName() {
return name; // requires the parameter name to be final.
}
};
}
}
Write a JUnit test program for the Queen and Worker classes.
In the above Queen example, the locations of a Queen object and its Worker objects are subject to change. Every time a Worker ant moves its Queen, it has the side effect of changing the Queen's origin. The Queen object remains the "same". This seems like a reasonable thing to have. In the functional programming paradigm, the move the Queen, the Worker ant would have to instantiate a new Queen object with a new location and find a way to associate itself to this new Queen, which does not seem to model the "real" ant world very well. By allowing our objects to change their internal states in appropriate situations, our programming model becomes more "realistic", more efficient, and in many cases "simpler".
Consider the problem of moving the minimum element of a list of integers to the front of the list. Since the current IList model is immutable, we can only solve the problem by returning a copy of the original list with its minimum at the front. Below is an algorithm to solve the problem that makes use of an accumulator to accumulate the current minimum and internally updates it as the list is being traversed.
package listFW.visitor;
import listFW.*;
/**
* Moves the minimum element from a list of Integer to the front.
* Uses SIDE-EFFECT to accumulate minimum: non-functional programming!!!
* @author Dung X. Nguyen
* @since Copyright: Copyright (c) 2005 by DXN - All rights reserved
*/
public class MinFront2 implements IListAlgo {
private Integer _accMin; // accumulated min.
private IListFactory _fact;
public MinFront2(IListFactory f) {
_fact = f;
}
public Object emptyCase(IEmptyList L, Object... inp) {
return L;
}
public Object nonEmptyCase(INEList L, Object... inp) {
// We assign _accMin the first of L as a candidate for minimum:
_accMin = (Integer)L.getFirst();
/**
* Let us consider the set S of all elements in L that precede L.
* S is clearly empty. At this point we have established the following:
* _accMin is an element of L and is smaller than all elements of S.
* We now call on an anonymous helper to operate on L in order to find
* the minimum and remove it from L. This helper will recursively
* traverse L to the end in order to obtain the minimum, save it in
* _accMin and reconstruct the host list L without the minimum on its way
* back from the recursive list traversal.
*/
IList withoutMin = (IList)L.execute(new IListAlgo() {
/**
* Note: when L executes this helper, this case is called since L is
* not empty. Thus for the first call to this method, h is L.
* We update _accMin to ensure that it is an element of L and is the
* minimum of all elements in L that precedes the rest of the host
* parameter h. Then we recursively call this helper on h.getRest()
* to save the minimum in _accMin and create a copy of h.getRest()
* that does not contain _accMin.
*/
public Object nonEmptyCase(INEList h, Object... nu) {
Integer first = (Integer)h.getFirst();
if (first < _accMin) {
_accMin = first;
}
/**
* At this point, we have established the following invariant:
* _accMin is an element of L and is the minimum of all elements
* in L that precedes h.getRest().
*/
IList accList = (IList)h.getRest().execute(this);
/**
* By induction, _accMin is now the minimum of the whole outer
* host list L, and accList is a copy of h.getRest() that does
* not contain _accMin.
*/
if (!first.equals(_accMin)) {
accList = _fact.makeNEList(first, accList);
}
// accList is now a copy of the host h without _accMin.
return accList;
/**
* As noted earlier, L.execute(...) calls nonEmptyCase() since
* L is not empty. Thus the first call to nonEmptyCase() is the
* call with L as the value for the host parameter h. So, when
* we return from this first call, accList is a copy of L without
* the minimum stored in _accMin.
*/
}
/**
* This method is only called from inside of the nonEmptyCase()
* method. The empty host parameter h marks the end of the outer
* host list L.
* _accmin is thus the minimum. The empty list is thus a copy of
* the outer host list L from the current list (empty) to the end
* that does not contain _accMin.
*/
public Object emptyCase(IEmptyList h, Object... nu) {
return h;
}
});
/**
* "Cons" the minimum to the front of the copy of the host that does not
* contain this minimum.
*/
return _fact.makeNEList(_accMin, withoutMin);
}
}
In the above, the comments are longer than the code. The above code and comments can be greatly simplified if the list is mutable. What does it mean for a list to be mutable?