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