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