1/* 2 * Copyright (C) 2010 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the 10 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 11 * express or implied. See the License for the specific language governing permissions and 12 * limitations under the License. 13 */ 14 15package com.google.common.collect; 16 17import com.google.common.annotations.GwtCompatible; 18import com.google.common.annotations.GwtIncompatible; 19import com.google.common.base.Function; 20import com.google.common.base.Functions; 21import com.google.common.collect.SortedLists.KeyAbsentBehavior; 22import com.google.common.collect.SortedLists.KeyPresentBehavior; 23import com.google.common.testing.NullPointerTester; 24 25import junit.framework.TestCase; 26 27import java.util.List; 28 29/** 30 * Tests for SortedLists. 31 * 32 * @author Louis Wasserman 33 */ 34@GwtCompatible(emulated = true) 35public class SortedListsTest extends TestCase { 36 private static final ImmutableList<Integer> LIST_WITH_DUPS = 37 ImmutableList.of(1, 1, 2, 4, 4, 4, 8); 38 39 private static final ImmutableList<Integer> LIST_WITHOUT_DUPS = ImmutableList.of(1, 2, 4, 8); 40 41 void assertModelAgrees(List<Integer> list, Integer key, int answer, 42 KeyPresentBehavior presentBehavior, KeyAbsentBehavior absentBehavior) { 43 switch (presentBehavior) { 44 case FIRST_PRESENT: 45 if (list.contains(key)) { 46 assertEquals(list.indexOf(key), answer); 47 return; 48 } 49 break; 50 case LAST_PRESENT: 51 if (list.contains(key)) { 52 assertEquals(list.lastIndexOf(key), answer); 53 return; 54 } 55 break; 56 case ANY_PRESENT: 57 if (list.contains(key)) { 58 assertEquals(key, list.get(answer)); 59 return; 60 } 61 break; 62 case FIRST_AFTER: 63 if (list.contains(key)) { 64 assertEquals(list.lastIndexOf(key) + 1, answer); 65 return; 66 } 67 break; 68 case LAST_BEFORE: 69 if (list.contains(key)) { 70 assertEquals(list.indexOf(key) - 1, answer); 71 return; 72 } 73 break; 74 default: 75 throw new AssertionError(); 76 } 77 // key is not present 78 int nextHigherIndex = list.size(); 79 for (int i = list.size() - 1; i >= 0 && list.get(i) > key; i--) { 80 nextHigherIndex = i; 81 } 82 switch (absentBehavior) { 83 case NEXT_LOWER: 84 assertEquals(nextHigherIndex - 1, answer); 85 return; 86 case NEXT_HIGHER: 87 assertEquals(nextHigherIndex, answer); 88 return; 89 case INVERTED_INSERTION_INDEX: 90 assertEquals(-1 - nextHigherIndex, answer); 91 return; 92 default: 93 throw new AssertionError(); 94 } 95 } 96 97 public void testWithoutDups() { 98 for (KeyPresentBehavior presentBehavior : KeyPresentBehavior.values()) { 99 for (KeyAbsentBehavior absentBehavior : KeyAbsentBehavior.values()) { 100 for (int key = 0; key <= 10; key++) { 101 assertModelAgrees(LIST_WITHOUT_DUPS, key, 102 SortedLists.binarySearch(LIST_WITHOUT_DUPS, key, presentBehavior, absentBehavior), 103 presentBehavior, absentBehavior); 104 } 105 } 106 } 107 } 108 109 public void testWithDups() { 110 for (KeyPresentBehavior presentBehavior : KeyPresentBehavior.values()) { 111 for (KeyAbsentBehavior absentBehavior : KeyAbsentBehavior.values()) { 112 for (int key = 0; key <= 10; key++) { 113 assertModelAgrees(LIST_WITH_DUPS, key, 114 SortedLists.binarySearch(LIST_WITH_DUPS, key, presentBehavior, absentBehavior), 115 presentBehavior, absentBehavior); 116 } 117 } 118 } 119 } 120 121 @GwtIncompatible("NullPointerTester") 122 public void testNulls() throws Exception { 123 NullPointerTester tester = new NullPointerTester(); 124 tester.setDefault(Function.class, Functions.identity()); 125 tester.setDefault(List.class, LIST_WITH_DUPS); 126 tester.setDefault(Comparable.class, 2); 127 tester.setDefault(KeyPresentBehavior.class, KeyPresentBehavior.ANY_PRESENT); 128 tester.setDefault(KeyAbsentBehavior.class, KeyAbsentBehavior.NEXT_HIGHER); 129 tester.testAllPublicStaticMethods(SortedLists.class); 130 } 131} 132