11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2010 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in compliance with the License. You may obtain a copy of the License at 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software distributed under the 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * express or implied. See the License for the specific language governing permissions and 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtIncompatible; 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Function; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Functions; 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.SortedLists.KeyAbsentBehavior; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.SortedLists.KeyPresentBehavior; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.testing.NullPointerTester; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport junit.framework.TestCase; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.List; 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Tests for SortedLists. 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(emulated = true) 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic class SortedListsTest extends TestCase { 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final ImmutableList<Integer> LIST_WITH_DUPS = 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableList.of(1, 1, 2, 4, 4, 4, 8); 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final ImmutableList<Integer> LIST_WITHOUT_DUPS = ImmutableList.of(1, 2, 4, 8); 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert void assertModelAgrees(List<Integer> list, Integer key, int answer, 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert KeyPresentBehavior presentBehavior, KeyAbsentBehavior absentBehavior) { 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (presentBehavior) { 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case FIRST_PRESENT: 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (list.contains(key)) { 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(list.indexOf(key), answer); 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return; 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case LAST_PRESENT: 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (list.contains(key)) { 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(list.lastIndexOf(key), answer); 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return; 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case ANY_PRESENT: 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (list.contains(key)) { 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(key, list.get(answer)); 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return; 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case FIRST_AFTER: 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (list.contains(key)) { 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(list.lastIndexOf(key) + 1, answer); 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return; 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case LAST_BEFORE: 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (list.contains(key)) { 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(list.indexOf(key) - 1, answer); 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return; 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert default: 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new AssertionError(); 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // key is not present 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int nextHigherIndex = list.size(); 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = list.size() - 1; i >= 0 && list.get(i) > key; i--) { 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert nextHigherIndex = i; 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (absentBehavior) { 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case NEXT_LOWER: 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(nextHigherIndex - 1, answer); 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return; 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case NEXT_HIGHER: 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(nextHigherIndex, answer); 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return; 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case INVERTED_INSERTION_INDEX: 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(-1 - nextHigherIndex, answer); 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return; 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert default: 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new AssertionError(); 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testWithoutDups() { 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (KeyPresentBehavior presentBehavior : KeyPresentBehavior.values()) { 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (KeyAbsentBehavior absentBehavior : KeyAbsentBehavior.values()) { 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int key = 0; key <= 10; key++) { 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertModelAgrees(LIST_WITHOUT_DUPS, key, 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedLists.binarySearch(LIST_WITHOUT_DUPS, key, presentBehavior, absentBehavior), 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert presentBehavior, absentBehavior); 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testWithDups() { 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (KeyPresentBehavior presentBehavior : KeyPresentBehavior.values()) { 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (KeyAbsentBehavior absentBehavior : KeyAbsentBehavior.values()) { 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int key = 0; key <= 10; key++) { 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertModelAgrees(LIST_WITH_DUPS, key, 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedLists.binarySearch(LIST_WITH_DUPS, key, presentBehavior, absentBehavior), 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert presentBehavior, absentBehavior); 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("NullPointerTester") 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testNulls() throws Exception { 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert NullPointerTester tester = new NullPointerTester(); 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault(Function.class, Functions.identity()); 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault(List.class, LIST_WITH_DUPS); 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault(Comparable.class, 2); 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault(KeyPresentBehavior.class, KeyPresentBehavior.ANY_PRESENT); 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.setDefault(KeyAbsentBehavior.class, KeyAbsentBehavior.NEXT_HIGHER); 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.testAllPublicStaticMethods(SortedLists.class); 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 132