1 /* 2 * Copyright 2013, Google Inc. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * * Redistributions in binary form must reproduce the above 12 * copyright notice, this list of conditions and the following disclaimer 13 * in the documentation and/or other materials provided with the 14 * distribution. 15 * * Neither the name of Google Inc. nor the names of its 16 * contributors may be used to endorse or promote products derived from 17 * this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 package org.jf.util; 33 34 import com.google.common.collect.Lists; 35 import com.google.common.collect.Ordering; 36 import junit.framework.Assert; 37 import org.junit.Test; 38 39 import java.util.List; 40 41 public class LinearSearchTest { 42 @Test testLinearSearch()43 public void testLinearSearch() { 44 List<Integer> list = Lists.newArrayList(0, 1, 3, 4); 45 46 doTest(list, 5, 10); 47 doTest(list, 5, 4); 48 doTest(list, 5, 3); 49 doTest(list, 5, 2); 50 doTest(list, 5, 1); 51 doTest(list, 5, 0); 52 53 doTest(list, 4, 10); 54 doTest(list, 4, 4); 55 doTest(list, 4, 3); 56 doTest(list, 4, 2); 57 doTest(list, 4, 1); 58 doTest(list, 4, 0); 59 60 doTest(list, 3, 10); 61 doTest(list, 3, 4); 62 doTest(list, 3, 3); 63 doTest(list, 3, 2); 64 doTest(list, 3, 1); 65 doTest(list, 3, 0); 66 67 doTest(list, 2, 10); 68 doTest(list, 2, 4); 69 doTest(list, 2, 3); 70 doTest(list, 2, 2); 71 doTest(list, 2, 1); 72 doTest(list, 2, 0); 73 74 doTest(list, 1, 10); 75 doTest(list, 1, 4); 76 doTest(list, 1, 3); 77 doTest(list, 1, 2); 78 doTest(list, 1, 1); 79 doTest(list, 1, 0); 80 81 doTest(list, 0, 10); 82 doTest(list, 0, 4); 83 doTest(list, 0, 3); 84 doTest(list, 0, 2); 85 doTest(list, 0, 1); 86 doTest(list, 0, 0); 87 88 doTest(list, -1, 10); 89 doTest(list, -1, 4); 90 doTest(list, -1, 3); 91 doTest(list, -1, 2); 92 doTest(list, -1, 1); 93 doTest(list, -1, 0); 94 } 95 doTest(List<Integer> list, int key, int guess)96 private void doTest(List<Integer> list, int key, int guess) { 97 int expectedIndex = Ordering.natural().binarySearch(list, key); 98 99 Assert.assertEquals(expectedIndex, LinearSearch.linearSearch(list, Ordering.<Integer>natural(), key, guess)); 100 } 101 } 102