commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From rwaldh...@apache.org
Subject cvs commit: jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example QuicksortExample.java
Date Wed, 12 Mar 2003 21:08:16 GMT
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=&lt;fully-specified-test-case-name&gt; test</pre>
  +      <p>or in Maven by invoking</p>
  +      <pre>maven -Dtestcase=&lt;fully-specified-test-case-name&gt; 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: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message