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 15 package com.google.common.collect; 16 17 import com.google.common.annotations.GwtCompatible; 18 import com.google.common.annotations.GwtIncompatible; 19 import com.google.common.collect.SortedLists.KeyAbsentBehavior; 20 import com.google.common.collect.SortedLists.KeyPresentBehavior; 21 import com.google.common.testing.NullPointerTester; 22 23 import junit.framework.TestCase; 24 25 import java.util.List; 26 27 /** 28 * Tests for SortedLists. 29 * 30 * @author Louis Wasserman 31 */ 32 @GwtCompatible(emulated = true) 33 public class SortedListsTest extends TestCase { 34 private static final ImmutableList<Integer> LIST_WITH_DUPS = 35 ImmutableList.of(1, 1, 2, 4, 4, 4, 8); 36 37 private static final ImmutableList<Integer> LIST_WITHOUT_DUPS = ImmutableList.of(1, 2, 4, 8); 38 39 void assertModelAgrees(List<Integer> list, Integer key, int answer, 40 KeyPresentBehavior presentBehavior, KeyAbsentBehavior absentBehavior) { 41 switch (presentBehavior) { 42 case FIRST_PRESENT: 43 if (list.contains(key)) { 44 assertEquals(list.indexOf(key), answer); 45 return; 46 } 47 break; 48 case LAST_PRESENT: 49 if (list.contains(key)) { 50 assertEquals(list.lastIndexOf(key), answer); 51 return; 52 } 53 break; 54 case ANY_PRESENT: 55 if (list.contains(key)) { 56 assertEquals(key, list.get(answer)); 57 return; 58 } 59 break; 60 case FIRST_AFTER: 61 if (list.contains(key)) { 62 assertEquals(list.lastIndexOf(key) + 1, answer); 63 return; 64 } 65 break; 66 case LAST_BEFORE: 67 if (list.contains(key)) { 68 assertEquals(list.indexOf(key) - 1, answer); 69 return; 70 } 71 break; 72 default: 73 throw new AssertionError(); 74 } 75 // key is not present 76 int nextHigherIndex = list.size(); 77 for (int i = list.size() - 1; i >= 0 && list.get(i) > key; i--) { 78 nextHigherIndex = i; 79 } 80 switch (absentBehavior) { 81 case NEXT_LOWER: 82 assertEquals(nextHigherIndex - 1, answer); 83 return; 84 case NEXT_HIGHER: 85 assertEquals(nextHigherIndex, answer); 86 return; 87 case INVERTED_INSERTION_INDEX: 88 assertEquals(-1 - nextHigherIndex, answer); 89 return; 90 default: 91 throw new AssertionError(); 92 } 93 } 94 95 public void testWithoutDups() { 96 for (KeyPresentBehavior presentBehavior : KeyPresentBehavior.values()) { 97 for (KeyAbsentBehavior absentBehavior : KeyAbsentBehavior.values()) { 98 for (int key = 0; key <= 10; key++) { 99 assertModelAgrees(LIST_WITHOUT_DUPS, key, 100 SortedLists.binarySearch(LIST_WITHOUT_DUPS, key, presentBehavior, absentBehavior), 101 presentBehavior, absentBehavior); 102 } 103 } 104 } 105 } 106 107 public void testWithDups() { 108 for (KeyPresentBehavior presentBehavior : KeyPresentBehavior.values()) { 109 for (KeyAbsentBehavior absentBehavior : KeyAbsentBehavior.values()) { 110 for (int key = 0; key <= 10; key++) { 111 assertModelAgrees(LIST_WITH_DUPS, key, 112 SortedLists.binarySearch(LIST_WITH_DUPS, key, presentBehavior, absentBehavior), 113 presentBehavior, absentBehavior); 114 } 115 } 116 } 117 } 118 119 @GwtIncompatible("NullPointerTester") 120 public void testNulls() { 121 new NullPointerTester().testAllPublicStaticMethods(SortedLists.class); 122 } 123 } 124