10888a09821a98ac0680fad765217302858e70fa4Paul Duffin/* 20888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Copyright (C) 2010 The Guava Authors 30888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 40888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 50888a09821a98ac0680fad765217302858e70fa4Paul Duffin * in compliance with the License. You may obtain a copy of the License at 60888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 70888a09821a98ac0680fad765217302858e70fa4Paul Duffin * http://www.apache.org/licenses/LICENSE-2.0 80888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 90888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Unless required by applicable law or agreed to in writing, software distributed under the 100888a09821a98ac0680fad765217302858e70fa4Paul Duffin * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 110888a09821a98ac0680fad765217302858e70fa4Paul Duffin * express or implied. See the License for the specific language governing permissions and 120888a09821a98ac0680fad765217302858e70fa4Paul Duffin * limitations under the License. 130888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 140888a09821a98ac0680fad765217302858e70fa4Paul Duffin 150888a09821a98ac0680fad765217302858e70fa4Paul Duffinpackage com.google.common.collect; 160888a09821a98ac0680fad765217302858e70fa4Paul Duffin 170888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.annotations.GwtCompatible; 180888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.collect.SortedLists.KeyAbsentBehavior; 190888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.collect.SortedLists.KeyPresentBehavior; 200888a09821a98ac0680fad765217302858e70fa4Paul Duffin 210888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport junit.framework.TestCase; 220888a09821a98ac0680fad765217302858e70fa4Paul Duffin 230888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.List; 240888a09821a98ac0680fad765217302858e70fa4Paul Duffin 250888a09821a98ac0680fad765217302858e70fa4Paul Duffin/** 260888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Tests for SortedLists. 270888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 280888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @author Louis Wasserman 290888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 300888a09821a98ac0680fad765217302858e70fa4Paul Duffin@GwtCompatible(emulated = true) 310888a09821a98ac0680fad765217302858e70fa4Paul Duffinpublic class SortedListsTest extends TestCase { 320888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final ImmutableList<Integer> LIST_WITH_DUPS = 330888a09821a98ac0680fad765217302858e70fa4Paul Duffin ImmutableList.of(1, 1, 2, 4, 4, 4, 8); 340888a09821a98ac0680fad765217302858e70fa4Paul Duffin 350888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final ImmutableList<Integer> LIST_WITHOUT_DUPS = ImmutableList.of(1, 2, 4, 8); 360888a09821a98ac0680fad765217302858e70fa4Paul Duffin 370888a09821a98ac0680fad765217302858e70fa4Paul Duffin void assertModelAgrees(List<Integer> list, Integer key, int answer, 380888a09821a98ac0680fad765217302858e70fa4Paul Duffin KeyPresentBehavior presentBehavior, KeyAbsentBehavior absentBehavior) { 390888a09821a98ac0680fad765217302858e70fa4Paul Duffin switch (presentBehavior) { 400888a09821a98ac0680fad765217302858e70fa4Paul Duffin case FIRST_PRESENT: 410888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (list.contains(key)) { 420888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(list.indexOf(key), answer); 430888a09821a98ac0680fad765217302858e70fa4Paul Duffin return; 440888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 450888a09821a98ac0680fad765217302858e70fa4Paul Duffin break; 460888a09821a98ac0680fad765217302858e70fa4Paul Duffin case LAST_PRESENT: 470888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (list.contains(key)) { 480888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(list.lastIndexOf(key), answer); 490888a09821a98ac0680fad765217302858e70fa4Paul Duffin return; 500888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 510888a09821a98ac0680fad765217302858e70fa4Paul Duffin break; 520888a09821a98ac0680fad765217302858e70fa4Paul Duffin case ANY_PRESENT: 530888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (list.contains(key)) { 540888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(key, list.get(answer)); 550888a09821a98ac0680fad765217302858e70fa4Paul Duffin return; 560888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 570888a09821a98ac0680fad765217302858e70fa4Paul Duffin break; 580888a09821a98ac0680fad765217302858e70fa4Paul Duffin case FIRST_AFTER: 590888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (list.contains(key)) { 600888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(list.lastIndexOf(key) + 1, answer); 610888a09821a98ac0680fad765217302858e70fa4Paul Duffin return; 620888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 630888a09821a98ac0680fad765217302858e70fa4Paul Duffin break; 640888a09821a98ac0680fad765217302858e70fa4Paul Duffin case LAST_BEFORE: 650888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (list.contains(key)) { 660888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(list.indexOf(key) - 1, answer); 670888a09821a98ac0680fad765217302858e70fa4Paul Duffin return; 680888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 690888a09821a98ac0680fad765217302858e70fa4Paul Duffin break; 700888a09821a98ac0680fad765217302858e70fa4Paul Duffin default: 710888a09821a98ac0680fad765217302858e70fa4Paul Duffin throw new AssertionError(); 720888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 730888a09821a98ac0680fad765217302858e70fa4Paul Duffin // key is not present 740888a09821a98ac0680fad765217302858e70fa4Paul Duffin int nextHigherIndex = list.size(); 750888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (int i = list.size() - 1; i >= 0 && list.get(i) > key; i--) { 760888a09821a98ac0680fad765217302858e70fa4Paul Duffin nextHigherIndex = i; 770888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 780888a09821a98ac0680fad765217302858e70fa4Paul Duffin switch (absentBehavior) { 790888a09821a98ac0680fad765217302858e70fa4Paul Duffin case NEXT_LOWER: 800888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(nextHigherIndex - 1, answer); 810888a09821a98ac0680fad765217302858e70fa4Paul Duffin return; 820888a09821a98ac0680fad765217302858e70fa4Paul Duffin case NEXT_HIGHER: 830888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(nextHigherIndex, answer); 840888a09821a98ac0680fad765217302858e70fa4Paul Duffin return; 850888a09821a98ac0680fad765217302858e70fa4Paul Duffin case INVERTED_INSERTION_INDEX: 860888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertEquals(-1 - nextHigherIndex, answer); 870888a09821a98ac0680fad765217302858e70fa4Paul Duffin return; 880888a09821a98ac0680fad765217302858e70fa4Paul Duffin default: 890888a09821a98ac0680fad765217302858e70fa4Paul Duffin throw new AssertionError(); 900888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 910888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 920888a09821a98ac0680fad765217302858e70fa4Paul Duffin 930888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void testWithoutDups() { 940888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (KeyPresentBehavior presentBehavior : KeyPresentBehavior.values()) { 950888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (KeyAbsentBehavior absentBehavior : KeyAbsentBehavior.values()) { 960888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (int key = 0; key <= 10; key++) { 970888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertModelAgrees(LIST_WITHOUT_DUPS, key, 980888a09821a98ac0680fad765217302858e70fa4Paul Duffin SortedLists.binarySearch(LIST_WITHOUT_DUPS, key, presentBehavior, absentBehavior), 990888a09821a98ac0680fad765217302858e70fa4Paul Duffin presentBehavior, absentBehavior); 1000888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1010888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1020888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1030888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1040888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1050888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void testWithDups() { 1060888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (KeyPresentBehavior presentBehavior : KeyPresentBehavior.values()) { 1070888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (KeyAbsentBehavior absentBehavior : KeyAbsentBehavior.values()) { 1080888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (int key = 0; key <= 10; key++) { 1090888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertModelAgrees(LIST_WITH_DUPS, key, 1100888a09821a98ac0680fad765217302858e70fa4Paul Duffin SortedLists.binarySearch(LIST_WITH_DUPS, key, presentBehavior, absentBehavior), 1110888a09821a98ac0680fad765217302858e70fa4Paul Duffin presentBehavior, absentBehavior); 1120888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1130888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1140888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1150888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1160888a09821a98ac0680fad765217302858e70fa4Paul Duffin} 1170888a09821a98ac0680fad765217302858e70fa4Paul Duffin 118