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