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