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/kata/two TestBinaryChop.java BaseBinaryChop.java
Date Mon, 01 Dec 2003 19:22:41 GMT
rwaldhoff    2003/12/01 11:22:41

  Modified:    functor/src/test/org/apache/commons/functor/example/kata/two
                        TestBinaryChop.java BaseBinaryChop.java
  Log:
  revised kata two examples
  
  Revision  Changes    Path
  1.5       +240 -113  jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example/kata/two/TestBinaryChop.java
  
  Index: TestBinaryChop.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example/kata/two/TestBinaryChop.java,v
  retrieving revision 1.4
  retrieving revision 1.5
  diff -u -r1.4 -r1.5
  --- TestBinaryChop.java	1 Dec 2003 16:40:11 -0000	1.4
  +++ TestBinaryChop.java	1 Dec 2003 19:22:41 -0000	1.5
  @@ -56,6 +56,7 @@
    */
   package org.apache.commons.functor.example.kata.two;
   
  +import java.util.Collections;
   import java.util.List;
   
   import junit.framework.Test;
  @@ -67,6 +68,42 @@
   import org.apache.commons.functor.generator.util.IntegerRange;
   
   /**
  + * Examples of binary search implementations.
  + * 
  + * A binary search algorithm is the same strategy used in
  + * that number guessing game, where one player picks a number
  + * between 1 and 100, and the second player tries to guess it.
  + * Each time the second player guesses a number, the first player
  + * tells whether the chosen number is higher, lower or equal to
  + * the guess.
  + * 
  + * An effective strategy for this sort of game is always guess
  + * the midpoint between what you know to be the lowest and 
  + * highest possible number.  This will find the number in
  + * log2(N) guesses (when N = 100, this is at most 7 guesses).
  + * 
  + * For example, suppose the first player (secretly) picks the
  + * number 63.  The guessing goes like this:
  + * 
  + * P1> I'm thinking of a number between 1 and 100. 
  + * P2> Is it 50?
  + * P1> Higher. 
  + * P2> 75?
  + * P1> Lower.
  + * P2> 62?
  + * P1> Higher.
  + * P2> 68?
  + * P1> Lower.
  + * P2> 65?
  + * P1> Lower.
  + * P2> 63?
  + * P1> That's it.
  + *
  + * Dave Thomas's Kata Two asks us to implement a binary search algorithm
  + * in several ways.  Here we'll use this as an opportunity to 
  + * consider some common approaches and explore 
  + * some functor based approaches as well. 
  + *  
    * See http://pragprog.com/pragdave/Practices/Kata/KataTwo.rdoc,v
    * for more information on this Kata.
    * 
  @@ -81,146 +118,236 @@
       public static Test suite() {
           return new TestSuite(TestBinaryChop.class);
       }
  -        
  -    public void setUp() throws Exception {
  -        super.setUp();
  -    }
  -    
  -    public void tearDown() throws Exception {
  -        super.tearDown();
  -    }
  -    
  +
  +    /**
  +     * This is Dave's test case, plus 
  +     * a quick check of searching a fairly large
  +     * list, just to make sure the time and space 
  +     * requirements are reasonable. 
  +     */
       private void chopTest(BinaryChop chopper) {
           assertEquals(-1, chopper.find(3, new int[0]));
           assertEquals(-1, chopper.find(3, new int[] { 1 }));
  -        assertEquals(0,  chopper.find(1, new int[] { 1 }));
  +        assertEquals(0, chopper.find(1, new int[] { 1 }));
   
  -        assertEquals(0,  chopper.find(1, new int[] { 1, 3, 5 }));
  -        assertEquals(1,  chopper.find(3, new int[] { 1, 3, 5 }));
  -        assertEquals(2,  chopper.find(5, new int[] { 1, 3, 5 }));
  +        assertEquals(0, chopper.find(1, new int[] { 1, 3, 5 }));
  +        assertEquals(1, chopper.find(3, new int[] { 1, 3, 5 }));
  +        assertEquals(2, chopper.find(5, new int[] { 1, 3, 5 }));
           assertEquals(-1, chopper.find(0, new int[] { 1, 3, 5 }));
           assertEquals(-1, chopper.find(2, new int[] { 1, 3, 5 }));
           assertEquals(-1, chopper.find(4, new int[] { 1, 3, 5 }));
           assertEquals(-1, chopper.find(6, new int[] { 1, 3, 5 }));
   
  -        assertEquals(0,  chopper.find(1, new int[] { 1, 3, 5, 7 }));
  -        assertEquals(1,  chopper.find(3, new int[] { 1, 3, 5, 7 }));
  -        assertEquals(2,  chopper.find(5, new int[] { 1, 3, 5, 7 }));
  -        assertEquals(3,  chopper.find(7, new int[] { 1, 3, 5, 7 }));
  +        assertEquals(0, chopper.find(1, new int[] { 1, 3, 5, 7 }));
  +        assertEquals(1, chopper.find(3, new int[] { 1, 3, 5, 7 }));
  +        assertEquals(2, chopper.find(5, new int[] { 1, 3, 5, 7 }));
  +        assertEquals(3, chopper.find(7, new int[] { 1, 3, 5, 7 }));
           assertEquals(-1, chopper.find(0, new int[] { 1, 3, 5, 7 }));
           assertEquals(-1, chopper.find(2, new int[] { 1, 3, 5, 7 }));
           assertEquals(-1, chopper.find(4, new int[] { 1, 3, 5, 7 }));
           assertEquals(-1, chopper.find(6, new int[] { 1, 3, 5, 7 }));
           assertEquals(-1, chopper.find(8, new int[] { 1, 3, 5, 7 }));
  -        
  -        List largeList = (List)(new IntegerRange(0,100001).toCollection());
  -        assertEquals(-1, chopper.find(new Integer(-5),largeList));
  -        assertEquals(100000, chopper.find(new Integer(100000),largeList));
  -        assertEquals(0, chopper.find(new Integer(0),largeList));
  -        assertEquals(50000, chopper.find(new Integer(50000),largeList));
  -        
  -     }
   
  +        List largeList = (List) (new IntegerRange(0, 100001).toCollection());
  +        assertEquals(-1, chopper.find(new Integer(-5), largeList));
  +        assertEquals(100000, chopper.find(new Integer(100000), largeList));
  +        assertEquals(0, chopper.find(new Integer(0), largeList));
  +        assertEquals(50000, chopper.find(new Integer(50000), largeList));
  +
  +    }
  +
  +    /**
  +     * In practice, one would most likely use the 
  +     * binary search method already available in 
  +     * java.util.Collections, but that's not 
  +     * really the point of this exercise.
  +     */
  +    public void testBuiltIn() {
  +        chopTest(new BaseBinaryChop() {
  +            public int find(Object seeking, List list) {
  +                int result = Collections.binarySearch(list,seeking);
  +                //
  +                // Collections.binarySearch is a bit smarter than our
  +                // "find". It returns 
  +                //  (-(insertionPoint) - 1)
  +                // when the value is not found, rather than
  +                // simply -1.
  +                //
  +                return result >= 0 ? result : -1; 
  +            }
  +        });
  +    }
  +
  +    /**
  +     * Here's a basic iterative approach.
  +     * 
  +     * We set the lower or upper bound to the midpoint
  +     * until there's only one element between the lower
  +     * and upper bound.  Then the lower bound is where
  +     * the element would be found if it existed in the
  +     * list.
  +     * 
  +     * We add an additional comparision at the end so
  +     * that we can return -1 if the element is not yet
  +     * in the list.
  +     */
       public void testIterative() {
  -        chopTest(
  -            new BaseBinaryChop() {
  -                public int find(Object seeking, List list) {
  -                    int high = list.size();
  -                    int low = 0;
  -                    int cur = 0;
  -                    while(low < high) {
  -                        cur = (high+low)/2;
  -                        int comp = ((Comparable)(list.get(cur))).compareTo(seeking);
  -                        if(comp == 0) { 
  -                            return cur;
  -                        } else if(comp < 0) {
  -                            if(low == cur) { cur++; }
  -                            low = cur;
  -                        } else {                                
  -                            high = cur;
  -                        }
  +        chopTest(new BaseBinaryChop() {
  +            public int find(Object seeking, List list) {
  +                int high = list.size();
  +                int low = 0;
  +                while (high - low > 1) {
  +                    int mid = (high + low) / 2;
  +                    if(greaterThan(list,mid,seeking)) {
  +                        high = mid;
  +                    } else {
  +                        low = mid;
                       }
  -                    return -1;
                   }
  -            });    
  +                return list.isEmpty() ? -1 : (equals(list,low,seeking) ? low : -1);
  +            }
  +        });
       }
   
  +    /**
  +     * A recursive version of that implementation uses 
  +     * method parameters to track the upper and 
  +     * lower bounds. 
  +     */
       public void testRecursive() {
  -        chopTest(
  -            new BaseBinaryChop() {
  -                public int find(Object seeking, List list) {                    
  -                    if(list.size() == 0) {
  -                        return -1;
  +        chopTest(new BaseBinaryChop() {
  +            public int find(Object seeking, List list) {
  +                return find(seeking, list, 0, list.size());
  +            }
  +            
  +            private int find(Object seeking, List list, int low, int high) {
  +                if(high - low > 1) {
  +                    int mid = (high + low) / 2;
  +                    if(greaterThan(list,mid,seeking)) {
  +                        return find(seeking,list,low,mid);
                       } else {
  -                        int pivot = list.size()/2;
  -                        int offset = 0;
  -                        int comp = ((Comparable)(list.get(pivot))).compareTo(seeking);
  -                        if(comp == 0) { 
  -                            return pivot;
  -                        } else if(comp < 0) {
  -                            offset = find(seeking,list.subList(Math.max(pivot,1),list.size()));
  -                        } else {                                
  -                            offset = find(seeking,list.subList(0,pivot));
  -                        }
  -                        return -1 == offset ? -1 : (comp == 1) ? offset : pivot+offset;
  +                        return find(seeking,list,mid,high);
                       }
  +                } else {
  +                    return list.isEmpty() ? -1 : (equals(list,low,seeking) ? low : -1);
                   }
  -            });    
  +            }
  +        });
       }
   
  +    /**
  +     * We can use the Algorithms.recuse method 
  +     * to implement that as tail recursion.
  +     * 
  +     * Here the anonymous Function implemenation
  +     * holds this itermediate state, rather than
  +     * the VM's call stack.
  +     * 
  +     * Arguably this is more like a continuation than
  +     * tail recursion, since there is a bit of state
  +     * to be tracked.
  +     */
  +    public void testTailRecursive() {
  +        chopTest(new BaseBinaryChop() {
  +            public int find(final Object seeking, final List list) {
  +                return ((Number)Algorithms.recurse(new Function() {
  +                    public Object evaluate() {
  +                        if(high - low > 1) {
  +                            int mid = (high + low) / 2;
  +                            if(greaterThan(list,mid,seeking)) {
  +                                high = mid;
  +                            } else {
  +                                low = mid;
  +                            }
  +                            return this;
  +                        } else {
  +                            return list.isEmpty() ? 
  +                                BaseBinaryChop.NEGATIVE_ONE : 
  +                                (BaseBinaryChop.equals(list,low,seeking) ? 
  +                                    new Integer(low) : 
  +                                    BaseBinaryChop.NEGATIVE_ONE);
  +                        }
  +                    }
  +                    int high = list.size();
  +                    int low = 0;
  +                })).intValue();
  +            }
  +        });
  +    }
  +
  +    /**
  +     * One fun functional approach is to "slice" up the 
  +     * list as we search,  looking at smaller and 
  +     * smaller slices until we've found the element 
  +     * we're looking for.
  +     *
  +     * Note that while any given call to this recursive 
  +     * function may only be looking at a sublist, we
  +     * need to return the index in the overall list.
  +     * Hence we'll split out a method so that we can
  +     * pass the offset in the original list as a 
  +     * parameter.
  +     *  
  +     * With all of the subList creation, this approach
  +     * is probably less efficient than either the iterative
  +     * or the recursive implemenations above.
  +     */
       public void testRecursive2() {
  -        chopTest(
  -            new BaseBinaryChop() {
  -                public int find(Object seeking, List list) { 
  -                    return find(seeking,list,0,list.size());
  -                }
  -                
  -                private int find(Object seeking, List list, int low, int high) {
  -                    if(low >= high) {
  -                        return -1;
  +        chopTest(new BaseBinaryChop() {
  +            public int find(Object seeking, List list) {
  +                return find(seeking,list,0);
  +            }
  +            
  +            private int find(Object seeking, List list, int offset) {
  +                if(list.isEmpty()) {
  +                    return -1;
  +                } if(list.size() == 1) {
  +                    return (equals(list,0,seeking) ? offset : -1);
  +                } else {
  +                    int mid = list.size() / 2;
  +                    if(greaterThan(list,mid,seeking)) {
  +                        return find(seeking,list.subList(0,mid),offset);
                       } else {
  -                        int cur = (high+low)/2;
  -                        int comp = ((Comparable)(list.get(cur))).compareTo(seeking);
  -                        if(comp == 0) { 
  -                            return cur;
  -                        } else if(comp < 0) {
  -                            if(low == cur) { cur++; }
  -                            return find(seeking,list,cur,high);
  -                        } else {                                
  -                            return find(seeking,list,low,cur);
  -                        }
  +                        return find(seeking,list.subList(mid,list.size()),offset+mid);
                       }
                   }
  -            });    
  -    }    
  -    public void testTailRecursive() {
  -        chopTest(
  -            new BaseBinaryChop() {
  -                public int find(final Object seeking, final List list) { 
  -                    return ((Number)Algorithms.recurse(
  -                        new Function() {
  -                            public Object evaluate() {
  -                                if(low < high) {
  -                                    int mid = (high+low)/2;                           
    
  -                                    int comp = ((Comparable)(list.get(mid))).compareTo(seeking);
  -                                    if(comp == 0) { 
  -                                        return new Integer(mid);
  -                                    } else if(comp < 0) {
  -                                        if(mid == low) { mid++; }
  -                                        low = mid;
  -                                        return this;
  -                                    } else {  
  -                                        high = mid;
  -                                        return this;                              
  -                                    }
  -                                } else {
  -                                    return new Integer(-1);
  -                                }
  +            }
  +        });
  +    }
  +
  +    /**
  +     * We can do that using tail recursion as well.
  +     * 
  +     * Again, the anonymous Function implemenation
  +     * holds the "continuation" state.
  +     */
  +    public void testTailRecursive2() {
  +        chopTest(new BaseBinaryChop() {
  +            public int find(final Object seeking, final List list) {
  +                return ((Number)Algorithms.recurse(new Function() {
  +                    public Object evaluate() {
  +                        if(sublist.isEmpty()) {
  +                            return BaseBinaryChop.NEGATIVE_ONE;
  +                        } if(sublist.size() == 1) {
  +                            return (BaseBinaryChop.equals(sublist,0,seeking) ? 
  +                                new Integer(offset) : 
  +                                BaseBinaryChop.NEGATIVE_ONE);
  +                        } else {
  +                            int mid = sublist.size() / 2;
  +                            if(greaterThan(sublist,mid,seeking)) {
  +                                sublist = sublist.subList(0,mid);
  +                            } else {
  +                                sublist = sublist.subList(mid,sublist.size());
  +                                offset += mid;
                               }
  -                            int high = list.size();
  -                            int low = 0;
  -                        })).intValue();
  -                }                   
  -            });    
  -    }    
  +                            return this;
  +                        }
  +                    }
  +                    int offset = 0;
  +                    List sublist = list;
  +                })).intValue();
  +            }
  +        });
  +    }
  +
   }
  
  
  
  1.2       +16 -2     jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example/kata/two/BaseBinaryChop.java
  
  Index: BaseBinaryChop.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example/kata/two/BaseBinaryChop.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- BaseBinaryChop.java	1 Dec 2003 07:30:24 -0000	1.1
  +++ BaseBinaryChop.java	1 Dec 2003 19:22:41 -0000	1.2
  @@ -79,5 +79,19 @@
           return find(seeking, Arrays.asList(in));
       }
       
  +    protected static int compare(List list, int index, Object obj) {
  +        return ((Comparable)list.get(index)).compareTo(obj);
  +    }
  +
  +    protected static boolean greaterThan(List list, int index, Object obj) {
  +        return compare(list,index,obj) > 0;
  +    }
  +
  +    protected static boolean equals(List list, int index, Object obj) {
  +        return compare(list,index,obj) == 0;
  +    }
  +    
  +    protected static Integer NEGATIVE_ONE = new Integer(-1);
  +    
       public abstract int find(Object seeking, List in);
   } 
  
  
  

---------------------------------------------------------------------
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