Home | History | Annotate | Download | only in collect 
      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