rwaldhoff 2003/03/12 13:08:16
Modified: functor/xdocs examples.xml
functor/src/test/org/apache/commons/functor/example
QuicksortExample.java
Log:
some doc enhancements
Revision Changes Path
1.2 +74 -5 jakarta-commons-sandbox/functor/xdocs/examples.xml
Index: examples.xml
===================================================================
RCS file: /home/cvs/jakarta-commons-sandbox/functor/xdocs/examples.xml,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- examples.xml 5 Mar 2003 17:15:50 -0000 1.1
+++ examples.xml 12 Mar 2003 21:08:16 -0000 1.2
@@ -12,14 +12,83 @@
We've begun to develop some example code that demonstrates the use and
utility of the Functor component.
</p>
- <subsection name="Code Reuse Through Composition">
- <p>
- See the <a
href="xref-test/org/apache/commons/functor/example/FlexiMapExample.html#88">FlexiMap</a>
example.
- </p>
+ <p>
+ In order to keep the examples in sync with the rest of the code,
+ each example is written as a <a href="http://junit.org/";>JUnit</a>
+ <code>TestCase</code>. The example programs are executed along with
+ all the other unit tests, and can be invoked via <code>ant test</code>
+ or <code>maven test</code> once you've set up Ant or Maven as described
+ in the <a href="building.html">build instructions</a>.
+ </p>
+ <p>
+ If you're not familiar with JUnit, don't worry. An understanding of
+ JUnit isn't important for an understanding of these examples, and
+ we'll walk you through the relevant bits anyway.
+ </p>
+ <p>
+ Two things you'll want to know about JUnit are (a) all the methods
+ whose names start with "test" will be executed automatically by the
+ test suite and (b) there are various "assert" methods that can be used
+ to make assertions about the Objects being tested. If any assertion
+ fails, the JUnit framework will count (and report) this as a test
+ failure.
+ </p>
+ <p>You can run a specific test case or sub-suite via Ant by invoking</p>
+ <pre>ant -Dtest.entry=<fully-specified-test-case-name> test</pre>
+ <p>or in Maven by invoking</p>
+ <pre>maven -Dtestcase=<fully-specified-test-case-name> test:single</pre>
+ <p>For example, to run the Quicksort example, invoke</p>
+ <pre>ant -Dtest.entry=org.apache.commons.functor.example.QuicksortExample
test</pre>
+ <p>or</p>
+ <pre>maven -Dtestcase=org.apache.commons.functor.example.QuicksortExample
test:single</pre>
+ <p>To run all the examples, invoke:</p>
+ <pre>ant -Dtest.entry=org.apache.commons.functor.example.TestAll test</pre>
+ <p>or</p>
+ <pre>maven -Dtestcase=org.apache.commons.functor.example.TestAll
test:single</pre>
+ <p>
+ Each example is written in something like a literate programming style.
+ In other words, with descriptive prose mixed right in with the source, as
+ <code>/* C++ style */</code> comments.
+ </p>
+ <subsection name="Reuse Through Composition">
+ <p>
+ The Functor package, and more generally, a functional approach
+ to program design, supports a powerful technique for balancing
+ behavior specialization and code reuse.
+ </p>
+ <p>
+ Traditional Object Oriented design suggests inheritence as a
+ mechanism code reuse, and method overloading as a mechanism for
+ specialization. For example, one defines a general purpose, perhaps
+ even abstract class, say <i>AbstractList</i>, and then extend or
+ specialize this parent via subclasses, inheriting some behaviors
+ and overloading others.
+ </p>
+ <p>
+ Functors encourage another, complementary approach to code reuse
+ and behavior specialiazation: composition. Following a compositional
+ design, we create a number of simple objects and then combine them to
+ create more complex behaviors. For example, the
+ <a href="http://jakarta.apache.org/commons/pool/";>Commons Pool</a>
+ component defines an <code>ObjectPool</code> type that maintains
+ a collection of pooled objects, but delegates to a
+ <code>PoolableObjectFactory</code> to create, validate and destroy
+ the objects to be pooled. Arbitrary <code>ObjectPool</code>
+ implementations can be composed with arbitrary
+ <code>PoolableObjectFactory</code>
+ implementations in order to create new types of pools.
+ </p>
+ <p>
+ The
+ <a
href="xref-test/org/apache/commons/functor/example/FlexiMapExample.html#88">FlexiMap</a>
+ example applies this design to <code>java.util.Map</code>,
demonstrating how
+ "pluggable" functors can be applied to a generic <code>Map</code>
structure in order
+ to introduce new behaviors.
+ </p>
</subsection>
<subsection name="A Functional Quicksort Implementation">
<p>
- See the <a
href="xref-test/org/apache/commons/functor/example/Quicksort.html#79">Quicksort</a>
example.
+ See the <a
href="xref-test/org/apache/commons/functor/example/QuicksortExample.html#79">Quicksort</a>
example.
</p>
</subsection>
</section>
1.2 +142 -135
jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example/QuicksortExample.java
Index: QuicksortExample.java
===================================================================
RCS file:
/home/cvs/jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example/QuicksortExample.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- QuicksortExample.java 12 Mar 2003 00:12:44 -0000 1.1
+++ QuicksortExample.java 12 Mar 2003 21:08:16 -0000 1.2
@@ -82,14 +82,11 @@
*/
/*
- * Here's an example of the QuicksortExample sorting algorithm, implemented using
- * commons-functor.
+ * Here's an example of the Quicksort sorting algorithm, implemented using
+ * Commons Functor.
*
- * We'll write this quicksort implementation in a literate programming style,
- * (in other words, with descriptive prose mixed right in with the source).
- *
- * For convenience, and to make sure this example stays up to date,
- * we'll implement our quicksort example as a JUnit TestCase.
+ * See http://jakarta.apache.org/commons/sandbox/functor/examples.html
+ * for additional examples.
*/
/**
@@ -117,28 +114,15 @@
return new TestSuite(QuicksortExample.class);
}
-
-/*
- * If you're not familiar with JUnit, don't worry. An understanding of JUnit
- * isn't important for an understanding of this example, and we'll walk you
- * through the relevant bits anyway.
- *
- * Two things you'll want to know about JUnit are (a) all the methods
- * whose names start with "test" will be executed automatically by the
- * test suite and (b) there are various "assert" methods that can be used
- * to make assertions about the Objects being tested. If any assertion
- * fails, the JUnit framework will count this as a test failure.
- */
-
/*
* ----------------------------------------------------------------------------
* UNIT TESTS:
* ----------------------------------------------------------------------------
*/
-
+
/*
* In "test first" style, let's start with the some functional descriptions
- * of what'd we'd like our QuicksortExample to do, expressed as unit tests.
+ * of what'd we'd like our Quicksort to do, expressed as unit tests.
*
* In our tests, we'll use a "quicksort" method which takes a List and
* returns a (new) sorted List. We'll define that method a bit later.
@@ -152,11 +136,8 @@
public void testSortEmpty() {
List empty = Collections.EMPTY_LIST;
List result = quicksort(empty);
- assertTrue(
- "Sorting an empty list should produce an empty list.",
- result.isEmpty()
- );
- }
+ assertTrue("Sorting an empty list should produce an empty list.",
result.isEmpty());
+ }
/*
* Similarly, sorting a List composed of a single element
@@ -166,20 +147,18 @@
public void testSortSingleElementList() {
List list = new ArrayList();
list.add("element");
-
+
List sorted = quicksort(list);
-
+
assertTrue(
- "The quicksort() method should return a distinct list.",
- list != sorted
- );
-
+ "The quicksort() method should return a distinct list.",
+ list != sorted);
+
assertEquals(
- "Sorting a single-element list should produce an equivalent list",
+ "Sorting a single-element list should produce an equivalent list",
list,
- sorted
- );
- }
+ sorted);
+ }
/*
* Finally, sorting a List composed of multiple copies
@@ -188,19 +167,18 @@
public void testSortSingleValueList() {
List list = new ArrayList();
- for(int i=0;i<10;i++) {
+ for(int i = 0; i < 10; i++) {
list.add("element");
}
List sorted = quicksort(list);
-
+
assertTrue(
- "The quicksort() method should return a distinct list.",
- list != sorted
- );
-
+ "The quicksort() method should return a distinct list.",
+ list != sorted);
+
assertEquals(list, sorted);
- }
-
+ }
+
/*
* So far so good.
*
@@ -210,23 +188,21 @@
*/
public void testSortSorted() {
List list = new ArrayList();
- for(int i=0;i<10;i++) {
+ for(int i = 0; i < 10; i++) {
list.add(new Integer(i));
}
-
+
List sorted = quicksort(list);
-
+
assertTrue(
- "The quicksort() method should return a distinct list.",
- list != sorted
- );
-
+ "The quicksort() method should return a distinct list.",
+ list != sorted);
+
assertEquals(
- "Sorting an already sorted list should produce an equivalent list",
+ "Sorting an already sorted list should produce an equivalent list",
list,
- sorted
- );
- }
+ sorted);
+ }
/*
* Sorting a reverse-order list (finally, a test case that requires something
@@ -235,7 +211,7 @@
public void testSortReversed() {
List expected = new ArrayList();
List tosort = new ArrayList();
- for(int i=0;i<10;i++) {
+ for(int i = 0; i < 10; i++) {
/*
* The "expected" list contains the integers in order.
*/
@@ -245,25 +221,24 @@
*/
tosort.add(new Integer(9 - i));
}
-
- assertEquals(expected, quicksort(tosort));
- }
+ assertEquals(expected, quicksort(tosort));
+ }
/*
* Just for fun, let's add some randomness to the tests, first by shuffling:
*/
public void testSortShuffled() {
List expected = new ArrayList();
- for(int i=0;i<10;i++) {
+ for(int i = 0; i < 10; i++) {
expected.add(new Integer(i));
}
List tosort = new ArrayList(expected);
Collections.shuffle(tosort);
-
+
assertEquals(expected, quicksort(tosort));
- }
-
+ }
+
/*
* and then using random values:
*/
@@ -271,9 +246,9 @@
Random random = new Random();
/*
* populate a list with random integers
- */
+ */
List tosort = new ArrayList();
- for(int i=0;i<10;i++) {
+ for(int i = 0; i < 10; i++) {
tosort.add(new Integer(random.nextInt(10)));
}
/*
@@ -284,7 +259,7 @@
Collections.sort(expected);
assertEquals(expected, quicksort(tosort));
- }
+ }
/*
* Finally, while this quicksort implementation is intended to
@@ -292,78 +267,81 @@
* let's output some timings just to demonstrate that the
* performance is adequate.
*/
-
+
private static final int SIZE = 1000;
private static final int COUNT = 100;
-
+
public void testTimings() {
/*
* We'll need the total elapsed time:
*/
long elapsed = 0L;
-
+
/*
* and a source for random integers:
*/
Random random = new Random();
-
+
/*
* Repeat this COUNT times:
*/
- for(int i=0;i<COUNT;i++) {
+ for(int i = 0; i < COUNT; i++) {
/*
* Create a List of size SIZE, and
* populate it with random integers:
*/
List tosort = new ArrayList(SIZE);
- for(int j=0;j<SIZE;j++) {
+ for(int j = 0; j < SIZE; j++) {
tosort.add(new Integer(random.nextInt(SIZE)));
}
-
+
/*
* Start the timer.
*/
- long start = System.currentTimeMillis();
-
+ long start = System.currentTimeMillis();
+
/*
* Sort the list.
* (We'll ignore the returned value here.)
*/
quicksort(tosort);
-
+
/*
* Stop the timer.
*/
- long stop = System.currentTimeMillis();
-
- /*
- * Add the elapsed time to our total.
- */
- elapsed += stop - start;
+ long stop = System.currentTimeMillis();
+
+ /*
+ * Add the elapsed time to our total.
+ */
+ elapsed += stop - start;
}
-
/*
* Whew, that was a lot of processing. Now figure out
* how long it took on average (per list):
*/
- double avgmillis = ((double)elapsed)/((double)COUNT);
-
+ double avgmillis = ((double)elapsed) / ((double)COUNT);
+
/*
* and print a simple summary.
*/
- System.out.println();
+ System.out.println();
System.out.println(
- "QuicksortExample Example: Sorted " + COUNT +
- " lists of " + SIZE +
- " elements in " + elapsed + " millis (" +
- avgmillis +
- " millis, or " +
- (avgmillis/1000D) +
- " seconds on average).");
- System.out.println();
- }
-
+ "Quicksort Example: Sorted "
+ + COUNT
+ + " lists of "
+ + SIZE
+ + " elements in "
+ + elapsed
+ + " millis ("
+ + avgmillis
+ + " millis, or "
+ + (avgmillis / 1000D)
+ + " seconds on average).");
+ System.out.println();
+ }
+
/*
* BUILDING BLOCKS:
* ----------------------------------------------------------------------------
@@ -371,21 +349,44 @@
* Let's save ourselves some casting and error checking by defining
* functor subclasses that deal with java.util.List.
*
- * Let ListFunction be a UnaryFunction that operates on Lists :
- */
-
+ * Let ListFunction be a UnaryFunction that operates on Lists:
+ */
+
public abstract class ListFunction implements UnaryFunction {
public abstract Object evaluate(List list);
-
+
public Object evaluate(Object obj) {
- if(null == obj) {
+ if(obj instanceof List) {
+ return evaluate((List)obj);
+ } else if(null == obj) {
throw new NullPointerException("The argument must not be null.");
- } else if(!(obj instanceof List)) {
+ } else {
throw new ClassCastException(
"The argument must be a List, found " +
obj.getClass().getName());
- } else {
- return evaluate((List)obj);
+ }
+ }
+ }
+
+/*
+ * Let ObjectListFunction be a BinaryFunction that operates on
+ * an Object, List pair:
+ */
+
+ public abstract class ObjectListFunction implements BinaryFunction {
+ public abstract Object evaluate(Object head, List tail);
+
+ public Object evaluate(Object left, Object right) {
+ if(left != null && right instanceof List) {
+ return evaluate(left, (List)right);
+ } else if(null == left) {
+ throw new NullPointerException("The left argument must not be
null.");
+ } else if(null == right) {
+ throw new NullPointerException("The right argument must not be
null.");
+ } else {
+ throw new ClassCastException(
+ "The right argument must be a List, found " +
+ right.getClass().getName());
}
}
}
@@ -415,13 +416,13 @@
/*
* Let's define functors for the operations we'll need.
*
- * Given a List, we want to be able to break it into its head:
+ * Given a List, we need to be able to break it into its head:
*/
private UnaryFunction head = new ListFunction() {
public Object evaluate(List list) {
return list.get(0);
- }
+ }
};
/*
@@ -429,59 +430,65 @@
*/
private UnaryFunction tail = new ListFunction() {
public Object evaluate(List list) {
- return list.size() < 2 ? Collections.EMPTY_LIST :
list.subList(1,list.size());
- }
+ return list.size() < 2 ?
+ Collections.EMPTY_LIST :
+ list.subList(1, list.size());
+ }
};
-
+
/*
* Given a List in head/tail form, we should be able to find
- * the List of elements in the tail less than the head:
+ * the list of elements in the tail less than the head.
+ * We can simply apply the select algorithm here, using
+ * a predicate identifying elements less than the head.
*/
- private BinaryFunction lesserTail = new BinaryFunction() {
- public Object evaluate(Object head, Object tail) {
+ private BinaryFunction lesserTail = new ObjectListFunction() {
+ public Object evaluate(Object head, List tail) {
return CollectionAlgorithms.select(
- ((List)tail).iterator(),
+ tail.iterator(),
RightBoundPredicate.bind(
- IsLessThan.getIsLessThan(),
- head));
+ IsLessThan.getIsLessThan(),
+ head));
}
};
/*
- * and we should be able to find the List of elements in
- * the tail greater than the head:
+ * We must also be able to find the List of elements in
+ * the tail greater than (or equal to) the head. This
+ * is similar to the lesserTail approach.
*/
private BinaryFunction greaterTail = new BinaryFunction() {
public Object evaluate(Object head, Object tail) {
return CollectionAlgorithms.select(
((List)tail).iterator(),
RightBoundPredicate.bind(
- IsGreaterThanOrEqual.getIsGreaterThanOrEqual(),
- head));
+ IsGreaterThanOrEqual.getIsGreaterThanOrEqual(),
+ head));
}
};
/*
* With these building blocks, our quicksort function is a
- * straightfoward application of the description above:
+ * straightfoward application of the description above.
*/
- private UnaryFunction quicksort = new ConditionalUnaryFunction(
+ private UnaryFunction quicksort = new ConditionalUnaryFunction(
IsEmpty.getIsEmpty(), /* If the list is empty, */
new ConstantFunction(Collections.EMPTY_LIST), /* then return an empty
list, */
new ListFunction() { /* else, split and recurse */
- public Object evaluate(List list) {
- List result = new ArrayList(list.size());
- Object h = head.evaluate(list);
- Object t = tail.evaluate(list);
- result.addAll((List)quicksort.evaluate(lesserTail.evaluate(h,t)));
- result.add(h);
- result.addAll((List)quicksort.evaluate(greaterTail.evaluate(h,t)));
- return result;
- }
+ public Object evaluate(List list) {
+ List result = new ArrayList(list.size());
+ Object h = head.evaluate(list);
+ Object t = tail.evaluate(list);
+ result.addAll((List)quicksort.evaluate(lesserTail.evaluate(h, t)));
+ result.add(h);
+ result.addAll((List)quicksort.evaluate(greaterTail.evaluate(h, t)));
+ return result;
}
- );
-
+ });
+/*
+ * Finally, our quicksort method simply invokes the UnaryFunction:
+ */
public List quicksort(List list) {
return (List)(quicksort.evaluate(list));
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
