1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.functor.example.kata.two;
18
19 import static org.junit.Assert.assertEquals;
20
21 import java.util.Collections;
22 import java.util.List;
23
24 import org.apache.commons.functor.Function;
25 import org.apache.commons.functor.Predicate;
26 import org.apache.commons.functor.Procedure;
27 import org.apache.commons.functor.core.algorithm.RecursiveEvaluation;
28 import org.apache.commons.functor.core.algorithm.UntilDo;
29 import org.apache.commons.functor.generator.util.IntegerRange;
30 import org.junit.Test;
31
32 /**
33 * Examples of binary search implementations.
34 *
35 * A binary search algorithm is the same strategy used in
36 * that number guessing game, where one player picks a number
37 * between 1 and 100, and the second player tries to guess it.
38 * Each time the second player guesses a number, the first player
39 * tells whether the chosen number is higher, lower or equal to
40 * the guess.
41 *
42 * An effective strategy for this sort of game is always guess
43 * the midpoint between what you know to be the lowest and
44 * highest possible number. This will find the number in
45 * log2(N) guesses (when N = 100, this is at most 7 guesses).
46 *
47 * For example, suppose the first player (secretly) picks the
48 * number 63. The guessing goes like this:
49 *
50 * P1> I'm thinking of a number between 1 and 100.
51 * P2> Is it 50?
52 * P1> Higher.
53 * P2> 75?
54 * P1> Lower.
55 * P2> 62?
56 * P1> Higher.
57 * P2> 68?
58 * P1> Lower.
59 * P2> 65?
60 * P1> Lower.
61 * P2> 63?
62 * P1> That's it.
63 *
64 * Dave Thomas's Kata Two asks us to implement a binary search algorithm
65 * in several ways. Here we'll use this as an opportunity to
66 * consider some common approaches and explore
67 * some functor based approaches as well.
68 *
69 * See http://pragprog.com/pragdave/Practices/Kata/KataTwo.rdoc,v
70 * for more information on this Kata.
71 *
72 * @version $Revision: 1171255 $ $Date: 2011-09-15 22:27:39 +0200 (Thu, 15 Sep 2011) $
73 * @author Rodney Waldhoff
74 */
75 @SuppressWarnings("unchecked")
76 public class TestBinaryChop {
77
78 /**
79 * This is Dave's test case, plus
80 * a quick check of searching a fairly large
81 * list, just to make sure the time and space
82 * requirements are reasonable.
83 */
84 private void chopTest(BinaryChop chopper) {
85 assertEquals(-1, chopper.find(3, new int[0]));
86 assertEquals(-1, chopper.find(3, new int[] { 1 }));
87 assertEquals(0, chopper.find(1, new int[] { 1 }));
88
89 assertEquals(0, chopper.find(1, new int[] { 1, 3, 5 }));
90 assertEquals(1, chopper.find(3, new int[] { 1, 3, 5 }));
91 assertEquals(2, chopper.find(5, new int[] { 1, 3, 5 }));
92 assertEquals(-1, chopper.find(0, new int[] { 1, 3, 5 }));
93 assertEquals(-1, chopper.find(2, new int[] { 1, 3, 5 }));
94 assertEquals(-1, chopper.find(4, new int[] { 1, 3, 5 }));
95 assertEquals(-1, chopper.find(6, new int[] { 1, 3, 5 }));
96
97 assertEquals(0, chopper.find(1, new int[] { 1, 3, 5, 7 }));
98 assertEquals(1, chopper.find(3, new int[] { 1, 3, 5, 7 }));
99 assertEquals(2, chopper.find(5, new int[] { 1, 3, 5, 7 }));
100 assertEquals(3, chopper.find(7, new int[] { 1, 3, 5, 7 }));
101 assertEquals(-1, chopper.find(0, new int[] { 1, 3, 5, 7 }));
102 assertEquals(-1, chopper.find(2, new int[] { 1, 3, 5, 7 }));
103 assertEquals(-1, chopper.find(4, new int[] { 1, 3, 5, 7 }));
104 assertEquals(-1, chopper.find(6, new int[] { 1, 3, 5, 7 }));
105 assertEquals(-1, chopper.find(8, new int[] { 1, 3, 5, 7 }));
106
107 List largeList = (List) (new IntegerRange(0, 100001).toCollection());
108 assertEquals(-1, chopper.find(new Integer(-5), largeList));
109 assertEquals(100000, chopper.find(new Integer(100000), largeList));
110 assertEquals(0, chopper.find(new Integer(0), largeList));
111 assertEquals(50000, chopper.find(new Integer(50000), largeList));
112
113 }
114
115 /**
116 * In practice, one would most likely use the
117 * binary search method already available in
118 * java.util.Collections, but that's not
119 * really the point of this exercise.
120 */
121 @Test
122 public void testBuiltIn() {
123 chopTest(new BaseBinaryChop() {
124 public int find(Object seeking, List list) {
125 int result = Collections.binarySearch(list,seeking);
126 //
127 // Collections.binarySearch is a bit smarter than our
128 // "find". It returns
129 // (-(insertionPoint) - 1)
130 // when the value is not found, rather than
131 // simply -1.
132 //
133 return result >= 0 ? result : -1;
134 }
135 });
136 }
137
138 /**
139 * Here's a basic iterative approach.
140 *
141 * We set the lower or upper bound to the midpoint
142 * until there's only one element between the lower
143 * and upper bound. Then the lower bound is where
144 * the element would be found if it existed in the
145 * list.
146 *
147 * We add an additional comparision at the end so
148 * that we can return -1 if the element is not yet
149 * in the list.
150 */
151 @Test
152 public void testIterative() {
153 chopTest(new BaseBinaryChop() {
154 public int find(Object seeking, List list) {
155 int high = list.size();
156 int low = 0;
157 while (high - low > 1) {
158 int mid = (high + low) / 2;
159 if (greaterThan(list,mid,seeking)) {
160 high = mid;
161 } else {
162 low = mid;
163 }
164 }
165 return list.isEmpty() ? -1 : (equals(list,low,seeking) ? low : -1);
166 }
167 });
168 }
169
170 /*
171 * At http://onestepback.org/index.cgi/Tech/Programming/Kata/KataTwoVariation1.rdoc,
172 * Jim Weirich discusses Kata Two from the perspective of loop invariants.
173 *
174 * Loop invariants provide a way of deductive reasoning about loops.
175 *
176 * Let P, Q. and R be predicates and A and B be
177 * procedures. Note that if:
178 * assert(P.test());
179 * A.run();
180 * assert(Q.test());
181 * and
182 * assert(Q.test());
183 * B.run();
184 * assert(R.test());
185 * are both valid, then:
186 * assert(P.test());
187 * A.run();
188 * B.run();
189 * assert(R.test());
190 * is valid as well.
191 *
192 * Similiarly, if INV and TERM are predicates and BODY is a procedure,
193 * then if:
194 * assert(INV.test());
195 * BODY.run();
196 * assert(INV.test());
197 * is valid, then so is:
198 * assert(INV.test());
199 * while(! TERM.test() ) { BODY.run(); }
200 * assert(INV.test());
201 * assert(TERM.test());
202 *
203 * Here INV is an "loop invariant", a statement that is true for every
204 * single iteration through the loop. TERM is a terminating condition,
205 * a statement that is true (by construction) when the loop exits.
206 *
207 * We can use loop invariants to reason about our iterative binary
208 * search loop. In particular, note that:
209 *
210 * // assert that the list is empty, or
211 * // the result index is between
212 * // low (inclusive) and high (exclusive),
213 * // or high is 0 (the list is empty)
214 * Predicate INV = new Predicate() {
215 * public boolean test() {
216 * return high == 0 ||
217 * (low <= result && result < high);
218 * }
219 * };
220 *
221 * is a valid invariant in our binary search, and that:
222 *
223 * Predicate TERM = new Predicate() {
224 * public boolean test() {
225 * return (high - low) <= 1;
226 * }
227 * };
228 *
229 * is a valid terminating condition.
230 *
231 * The BODY in our case simply moves the endpoints
232 * closer together, without violating
233 * our invariant:
234 *
235 * Procedure BODY = new Procedure() {
236 * public void run() {
237 * int mid = (high + low) / 2;
238 * if (greaterThan(list,mid,seeking)) {
239 * high = mid;
240 * } else {
241 * low = mid;
242 * }
243 * }
244 * };
245 *
246 * One could assert our invariant before and after
247 * the execution of BODY, and the terminating condition
248 * at the end of the loop, but we can tell by construction
249 * that these assertions will hold.
250 *
251 * Using the functor framework, we can make these notions
252 * explict. Specifically, the construction above is:
253 *
254 * Algorithms.untildo(BODY,TERM);
255 *
256 * Since we'll want to share state among the TERM and BODY,
257 * let's declare a single interface for the TERM Predicate and
258 * the BODY Procedure. We'll be calculating a result within
259 * the loop, so let's add a Function implementation as well,
260 * as a way of retrieving that result:
261 */
262 interface Loop extends Predicate, Procedure, Function {
263 /** The terminating condition. */
264 boolean test();
265 /** The loop body. */
266 void run();
267 /** The result of executing the loop. */
268 Object evaluate();
269 };
270
271 /*
272 * Now we can use the Algorithms.dountil method to
273 * execute that loop:
274 */
275 @Test
276 public void testIterativeWithInvariants() {
277 chopTest(new BaseBinaryChop() {
278
279 public int find(final Object seeking, final List list) {
280 Loop loop = new Loop() {
281 int high = list.size();
282 int low = 0;
283
284 /** Our terminating condition. */
285 public boolean test() {
286 return (high - low) <= 1;
287 }
288
289 /** Our loop body. */
290 public void run() {
291 int mid = (high + low) / 2;
292 if (greaterThan(list,mid,seeking)) {
293 high = mid;
294 } else {
295 low = mid;
296 }
297 }
298
299 /**
300 * A way of returning the result
301 * at the end of the loop.
302 */
303 public Object evaluate() {
304 return new Integer(
305 list.isEmpty() ?
306 -1 :
307 (BaseBinaryChop.equals(list,low,seeking) ? low : -1));
308 }
309
310 };
311 new UntilDo(loop, loop).run();
312 return ((Number) loop.evaluate()).intValue();
313 }
314 });
315 }
316
317 /*
318 * Jim Weirich notes how Eiffel is very explict about loop invariants:
319 *
320 * from
321 * low := list.lower
322 * high := list.upper + 1
323 * invariant
324 * lower_limit: -- low <= result (this is just a comment)
325 * upper_limit: -- high < result (this is just a comment)
326 * variant
327 * high - low
328 * until
329 * (high - low) <= 1
330 * loop
331 * mid := (high + low) // 2
332 * if list.at(mid) > seeking then
333 * high := mid
334 * else
335 * low := mid
336 * end
337 * end
338 *
339 * We can do that too, using EiffelStyleLoop.
340 */
341 class BinarySearchLoop extends EiffelStyleLoop {
342 BinarySearchLoop(Object aSeeking, List aList) {
343 seeking = aSeeking;
344 list = aList;
345
346 from(new Procedure() {
347 public void run() {
348 low = 0;
349 high = list.size();
350 }
351 });
352
353 invariant(new Predicate() {
354 public boolean test() {
355 return high == 0 || low < high;
356 }
357 });
358
359 variant(new Function() {
360 public Object evaluate() {
361 return new Integer(high - low);
362 }
363 });
364
365 until(new Predicate() {
366 public boolean test() {
367 return high - low <= 1;
368 }
369 });
370
371 loop(new Procedure() {
372 public void run() {
373 int mid = (high + low) / 2;
374 if (BaseBinaryChop.greaterThan(list,mid,seeking)) {
375 high = mid;
376 } else {
377 low = mid;
378 }
379 }
380 });
381 }
382
383 int getResult() {
384 return list.isEmpty() ? -1 : BaseBinaryChop.equals(list,low,seeking) ? low : -1;
385 }
386
387 private int high;
388 private int low;
389 private final Object seeking;
390 private final List list;
391 }
392
393 @Test
394 public void testIterativeWithInvariantsAndAssertions() {
395 chopTest(new BaseBinaryChop() {
396 public int find(Object seeking, List list) {
397 BinarySearchLoop loop = new BinarySearchLoop(seeking,list);
398 loop.run();
399 return loop.getResult();
400 }});
401 }
402
403 /**
404 * A recursive version of that implementation uses
405 * method parameters to track the upper and
406 * lower bounds.
407 */
408 @Test
409 public void testRecursive() {
410 chopTest(new BaseBinaryChop() {
411 public int find(Object seeking, List list) {
412 return find(seeking, list, 0, list.size());
413 }
414
415 private int find(Object seeking, List list, int low, int high) {
416 if (high - low > 1) {
417 int mid = (high + low) / 2;
418 if (greaterThan(list,mid,seeking)) {
419 return find(seeking,list,low,mid);
420 } else {
421 return find(seeking,list,mid,high);
422 }
423 } else {
424 return list.isEmpty() ? -1 : (equals(list,low,seeking) ? low : -1);
425 }
426 }
427 });
428 }
429
430 /**
431 * We can use the Algorithms.recuse method
432 * to implement that as tail recursion.
433 *
434 * Here the anonymous Function implemenation
435 * holds this itermediate state, rather than
436 * the VM's call stack.
437 *
438 * Arguably this is more like a continuation than
439 * tail recursion, since there is a bit of state
440 * to be tracked.
441 */
442 @Test
443 public void testTailRecursive() {
444 chopTest(new BaseBinaryChop() {
445 public int find(final Object seeking, final List list) {
446 return ((Number) new RecursiveEvaluation(new Function() {
447 public Object evaluate() {
448 if (high - low > 1) {
449 int mid = (high + low) / 2;
450 if (greaterThan(list,mid,seeking)) {
451 high = mid;
452 } else {
453 low = mid;
454 }
455 return this;
456 } else {
457 return list.isEmpty() ?
458 BaseBinaryChop.NEGATIVE_ONE :
459 (BaseBinaryChop.equals(list,low,seeking) ?
460 new Integer(low) :
461 BaseBinaryChop.NEGATIVE_ONE);
462 }
463 }
464 int high = list.size();
465 int low = 0;
466 }).evaluate()).intValue();
467 }
468 });
469 }
470
471 /**
472 * One fun functional approach is to "slice" up the
473 * list as we search, looking at smaller and
474 * smaller slices until we've found the element
475 * we're looking for.
476 *
477 * Note that while any given call to this recursive
478 * function may only be looking at a sublist, we
479 * need to return the index in the overall list.
480 * Hence we'll split out a method so that we can
481 * pass the offset in the original list as a
482 * parameter.
483 *
484 * With all of the subList creation, this approach
485 * is probably less efficient than either the iterative
486 * or the recursive implemenations above.
487 */
488 @Test
489 public void testRecursive2() {
490 chopTest(new BaseBinaryChop() {
491 public int find(Object seeking, List list) {
492 return find(seeking,list,0);
493 }
494
495 private int find(Object seeking, List list, int offset) {
496 if (list.isEmpty()) {
497 return -1;
498 } if (list.size() == 1) {
499 return (equals(list,0,seeking) ? offset : -1);
500 } else {
501 int mid = list.size() / 2;
502 if (greaterThan(list,mid,seeking)) {
503 return find(seeking,list.subList(0,mid),offset);
504 } else {
505 return find(seeking,list.subList(mid,list.size()),offset+mid);
506 }
507 }
508 }
509 });
510 }
511
512 /**
513 * We can do that using tail recursion as well.
514 *
515 * Again, the anonymous Function implemenation
516 * holds the "continuation" state.
517 */
518 @Test
519 public void testTailRecursive2() {
520 chopTest(new BaseBinaryChop() {
521 public int find(final Object seeking, final List list) {
522 return ((Number) new RecursiveEvaluation(new Function() {
523 public Object evaluate() {
524 if (sublist.isEmpty()) {
525 return BaseBinaryChop.NEGATIVE_ONE;
526 } if (sublist.size() == 1) {
527 return (BaseBinaryChop.equals(sublist,0,seeking) ?
528 new Integer(offset) :
529 BaseBinaryChop.NEGATIVE_ONE);
530 } else {
531 int mid = sublist.size() / 2;
532 if (greaterThan(sublist,mid,seeking)) {
533 sublist = sublist.subList(0,mid);
534 } else {
535 sublist = sublist.subList(mid,sublist.size());
536 offset += mid;
537 }
538 return this;
539 }
540 }
541 int offset = 0;
542 List sublist = list;
543 }).evaluate()).intValue();
544 }
545 });
546 }
547
548 }