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.collect.SortedLists.KeyAbsentBehavior;
20import com.google.common.collect.SortedLists.KeyPresentBehavior;
21import com.google.common.testing.NullPointerTester;
22
23import junit.framework.TestCase;
24
25import java.util.List;
26
27/**
28 * Tests for SortedLists.
29 *
30 * @author Louis Wasserman
31 */
32@GwtCompatible(emulated = true)
33public 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