guava

1
/*
2
 * Copyright (C) 2010 The Guava Authors
3
 *
4
 * Licensed under the Apache License, Version 2.0 (the "License");
5
 * you may not use this file except in compliance with the License.
6
 * You may obtain a copy of the License at
7
 *
8
 * http://www.apache.org/licenses/LICENSE-2.0
9
 *
10
 * Unless required by applicable law or agreed to in writing, software
11
 * distributed under the License is distributed on an "AS IS" BASIS,
12
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13
 * See the License for the specific language governing permissions and
14
 * limitations under the License.
15
 */
16

17
package com.google.common.collect.testing.testers;
18

19
import static com.google.common.collect.testing.features.CollectionSize.ONE;
20
import static com.google.common.collect.testing.features.CollectionSize.SEVERAL;
21
import static com.google.common.collect.testing.features.CollectionSize.ZERO;
22
import static com.google.common.collect.testing.features.MapFeature.SUPPORTS_REMOVE;
23
import static org.junit.Assert.assertThrows;
24

25
import com.google.common.annotations.GwtIncompatible;
26
import com.google.common.collect.testing.AbstractMapTester;
27
import com.google.common.collect.testing.Helpers;
28
import com.google.common.collect.testing.features.CollectionSize;
29
import com.google.common.collect.testing.features.MapFeature;
30
import java.util.ArrayList;
31
import java.util.Collections;
32
import java.util.List;
33
import java.util.Map.Entry;
34
import java.util.NavigableMap;
35
import org.junit.Ignore;
36

37
/**
38
 * A generic JUnit test which tests operations on a NavigableMap. Can't be invoked directly; please
39
 * see {@code NavigableMapTestSuiteBuilder}.
40
 *
41
 * @author Jesse Wilson
42
 * @author Louis Wasserman
43
 */
44
@GwtIncompatible
45
@Ignore // Affects only Android test runner, which respects JUnit 4 annotations on JUnit 3 tests.
46
public class NavigableMapNavigationTester<K, V> extends AbstractMapTester<K, V> {
47

48
  private NavigableMap<K, V> navigableMap;
49
  private List<Entry<K, V>> entries;
50
  private Entry<K, V> a;
51
  private Entry<K, V> b;
52
  private Entry<K, V> c;
53

54
  @Override
55
  public void setUp() throws Exception {
56
    super.setUp();
57
    navigableMap = (NavigableMap<K, V>) getMap();
58
    entries =
59
        Helpers.copyToList(
60
            getSubjectGenerator()
61
                .getSampleElements(getSubjectGenerator().getCollectionSize().getNumElements()));
62
    Collections.sort(entries, Helpers.<K, V>entryComparator(navigableMap.comparator()));
63

64
    // some tests assume SEVERAL == 3
65
    if (entries.size() >= 1) {
66
      a = entries.get(0);
67
      if (entries.size() >= 3) {
68
        b = entries.get(1);
69
        c = entries.get(2);
70
      }
71
    }
72
  }
73

74
  /** Resets the contents of navigableMap to have entries a, c, for the navigation tests. */
75
  @SuppressWarnings("unchecked") // Needed to stop Eclipse whining
76
  private void resetWithHole() {
77
    Entry<K, V>[] entries = (Entry<K, V>[]) new Entry<?, ?>[] {a, c};
78
    super.resetMap(entries);
79
    navigableMap = (NavigableMap<K, V>) getMap();
80
  }
81

82
  @CollectionSize.Require(ZERO)
83
  public void testEmptyMapFirst() {
84
    assertNull(navigableMap.firstEntry());
85
  }
86

87
  @MapFeature.Require(SUPPORTS_REMOVE)
88
  @CollectionSize.Require(ZERO)
89
  public void testEmptyMapPollFirst() {
90
    assertNull(navigableMap.pollFirstEntry());
91
  }
92

93
  @CollectionSize.Require(ZERO)
94
  public void testEmptyMapNearby() {
95
    assertNull(navigableMap.lowerEntry(k0()));
96
    assertNull(navigableMap.lowerKey(k0()));
97
    assertNull(navigableMap.floorEntry(k0()));
98
    assertNull(navigableMap.floorKey(k0()));
99
    assertNull(navigableMap.ceilingEntry(k0()));
100
    assertNull(navigableMap.ceilingKey(k0()));
101
    assertNull(navigableMap.higherEntry(k0()));
102
    assertNull(navigableMap.higherKey(k0()));
103
  }
104

105
  @CollectionSize.Require(ZERO)
106
  public void testEmptyMapLast() {
107
    assertNull(navigableMap.lastEntry());
108
  }
109

110
  @MapFeature.Require(SUPPORTS_REMOVE)
111
  @CollectionSize.Require(ZERO)
112
  public void testEmptyMapPollLast() {
113
    assertNull(navigableMap.pollLastEntry());
114
  }
115

116
  @CollectionSize.Require(ONE)
117
  public void testSingletonMapFirst() {
118
    assertEquals(a, navigableMap.firstEntry());
119
  }
120

121
  @MapFeature.Require(SUPPORTS_REMOVE)
122
  @CollectionSize.Require(ONE)
123
  public void testSingletonMapPollFirst() {
124
    assertEquals(a, navigableMap.pollFirstEntry());
125
    assertTrue(navigableMap.isEmpty());
126
  }
127

128
  @CollectionSize.Require(ONE)
129
  public void testSingletonMapNearby() {
130
    assertNull(navigableMap.lowerEntry(k0()));
131
    assertNull(navigableMap.lowerKey(k0()));
132
    assertEquals(a, navigableMap.floorEntry(k0()));
133
    assertEquals(a.getKey(), navigableMap.floorKey(k0()));
134
    assertEquals(a, navigableMap.ceilingEntry(k0()));
135
    assertEquals(a.getKey(), navigableMap.ceilingKey(k0()));
136
    assertNull(navigableMap.higherEntry(k0()));
137
    assertNull(navigableMap.higherKey(k0()));
138
  }
139

140
  @CollectionSize.Require(ONE)
141
  public void testSingletonMapLast() {
142
    assertEquals(a, navigableMap.lastEntry());
143
  }
144

145
  @MapFeature.Require(SUPPORTS_REMOVE)
146
  @CollectionSize.Require(ONE)
147
  public void testSingletonMapPollLast() {
148
    assertEquals(a, navigableMap.pollLastEntry());
149
    assertTrue(navigableMap.isEmpty());
150
  }
151

152
  @CollectionSize.Require(SEVERAL)
153
  public void testFirst() {
154
    assertEquals(a, navigableMap.firstEntry());
155
  }
156

157
  @MapFeature.Require(SUPPORTS_REMOVE)
158
  @CollectionSize.Require(SEVERAL)
159
  public void testPollFirst() {
160
    assertEquals(a, navigableMap.pollFirstEntry());
161
    assertEquals(entries.subList(1, entries.size()), Helpers.copyToList(navigableMap.entrySet()));
162
  }
163

164
  @MapFeature.Require(absent = SUPPORTS_REMOVE)
165
  public void testPollFirstUnsupported() {
166
    assertThrows(UnsupportedOperationException.class, () -> navigableMap.pollFirstEntry());
167
  }
168

169
  @CollectionSize.Require(SEVERAL)
170
  public void testLower() {
171
    resetWithHole();
172
    assertEquals(null, navigableMap.lowerEntry(a.getKey()));
173
    assertEquals(null, navigableMap.lowerKey(a.getKey()));
174
    assertEquals(a, navigableMap.lowerEntry(b.getKey()));
175
    assertEquals(a.getKey(), navigableMap.lowerKey(b.getKey()));
176
    assertEquals(a, navigableMap.lowerEntry(c.getKey()));
177
    assertEquals(a.getKey(), navigableMap.lowerKey(c.getKey()));
178
  }
179

180
  @CollectionSize.Require(SEVERAL)
181
  public void testFloor() {
182
    resetWithHole();
183
    assertEquals(a, navigableMap.floorEntry(a.getKey()));
184
    assertEquals(a.getKey(), navigableMap.floorKey(a.getKey()));
185
    assertEquals(a, navigableMap.floorEntry(b.getKey()));
186
    assertEquals(a.getKey(), navigableMap.floorKey(b.getKey()));
187
    assertEquals(c, navigableMap.floorEntry(c.getKey()));
188
    assertEquals(c.getKey(), navigableMap.floorKey(c.getKey()));
189
  }
190

191
  @CollectionSize.Require(SEVERAL)
192
  public void testCeiling() {
193
    resetWithHole();
194
    assertEquals(a, navigableMap.ceilingEntry(a.getKey()));
195
    assertEquals(a.getKey(), navigableMap.ceilingKey(a.getKey()));
196
    assertEquals(c, navigableMap.ceilingEntry(b.getKey()));
197
    assertEquals(c.getKey(), navigableMap.ceilingKey(b.getKey()));
198
    assertEquals(c, navigableMap.ceilingEntry(c.getKey()));
199
    assertEquals(c.getKey(), navigableMap.ceilingKey(c.getKey()));
200
  }
201

202
  @CollectionSize.Require(SEVERAL)
203
  public void testHigher() {
204
    resetWithHole();
205
    assertEquals(c, navigableMap.higherEntry(a.getKey()));
206
    assertEquals(c.getKey(), navigableMap.higherKey(a.getKey()));
207
    assertEquals(c, navigableMap.higherEntry(b.getKey()));
208
    assertEquals(c.getKey(), navigableMap.higherKey(b.getKey()));
209
    assertEquals(null, navigableMap.higherEntry(c.getKey()));
210
    assertEquals(null, navigableMap.higherKey(c.getKey()));
211
  }
212

213
  @CollectionSize.Require(SEVERAL)
214
  public void testLast() {
215
    assertEquals(c, navigableMap.lastEntry());
216
  }
217

218
  @MapFeature.Require(SUPPORTS_REMOVE)
219
  @CollectionSize.Require(SEVERAL)
220
  public void testPollLast() {
221
    assertEquals(c, navigableMap.pollLastEntry());
222
    assertEquals(
223
        entries.subList(0, entries.size() - 1), Helpers.copyToList(navigableMap.entrySet()));
224
  }
225

226
  @MapFeature.Require(absent = SUPPORTS_REMOVE)
227
  @CollectionSize.Require(SEVERAL)
228
  public void testPollLastUnsupported() {
229
    assertThrows(UnsupportedOperationException.class, () -> navigableMap.pollLastEntry());
230
  }
231

232
  @CollectionSize.Require(SEVERAL)
233
  public void testDescendingNavigation() {
234
    List<Entry<K, V>> descending = new ArrayList<>(navigableMap.descendingMap().entrySet());
235
    Collections.reverse(descending);
236
    assertEquals(entries, descending);
237
  }
238

239
  @CollectionSize.Require(absent = ZERO)
240
  public void testHeadMapExclusive() {
241
    assertFalse(navigableMap.headMap(a.getKey(), false).containsKey(a.getKey()));
242
  }
243

244
  @CollectionSize.Require(absent = ZERO)
245
  public void testHeadMapInclusive() {
246
    assertTrue(navigableMap.headMap(a.getKey(), true).containsKey(a.getKey()));
247
  }
248

249
  @CollectionSize.Require(absent = ZERO)
250
  public void testTailMapExclusive() {
251
    assertFalse(navigableMap.tailMap(a.getKey(), false).containsKey(a.getKey()));
252
  }
253

254
  @CollectionSize.Require(absent = ZERO)
255
  public void testTailMapInclusive() {
256
    assertTrue(navigableMap.tailMap(a.getKey(), true).containsKey(a.getKey()));
257
  }
258
}
259