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
17package com.google.common.collect.testing.testers;
18
19import static com.google.common.collect.testing.features.CollectionSize.ONE;
20import static com.google.common.collect.testing.features.CollectionSize.SEVERAL;
21import static com.google.common.collect.testing.features.CollectionSize.ZERO;
22import static com.google.common.collect.testing.features.MapFeature.SUPPORTS_REMOVE;
23
24import com.google.common.collect.testing.AbstractMapTester;
25import com.google.common.collect.testing.Helpers;
26import com.google.common.collect.testing.features.CollectionSize;
27import com.google.common.collect.testing.features.MapFeature;
28
29import java.util.ArrayList;
30import java.util.Collections;
31import java.util.List;
32import java.util.Map.Entry;
33import java.util.NavigableMap;
34import java.util.NoSuchElementException;
35
36/**
37 * A generic JUnit test which tests operations on a NavigableMap. Can't be
38 * invoked directly; please see {@code MapTestSuiteBuilder}.
39 *
40 * @author Jesse Wilson
41 * @author Louis Wasserman
42 */
43public class MapNavigationTester<K, V> extends AbstractMapTester<K, V> {
44
45  private NavigableMap<K, V> navigableMap;
46  private List<Entry<K, V>> entries;
47  private Entry<K, V> a;
48  private Entry<K, V> b;
49  private Entry<K, V> c;
50
51  @Override public void setUp() throws Exception {
52    super.setUp();
53    navigableMap = (NavigableMap<K, V>) getMap();
54    entries = Helpers.copyToList(getSubjectGenerator().getSampleElements(
55        getSubjectGenerator().getCollectionSize().getNumElements()));
56    Collections.sort(entries, Helpers.<K, V>entryComparator(navigableMap.comparator()));
57
58    // some tests assume SEVERAL == 3
59    if (entries.size() >= 1) {
60      a = entries.get(0);
61      if (entries.size() >= 3) {
62        b = entries.get(1);
63        c = entries.get(2);
64      }
65    }
66  }
67
68  /**
69   * Resets the contents of navigableMap to have entries a, c, for the
70   * navigation tests.
71   */
72  @SuppressWarnings("unchecked") // Needed to stop Eclipse whining
73  private void resetWithHole() {
74    Entry<K, V>[] entries = new Entry[] {a, c};
75    super.resetMap(entries);
76    navigableMap = (NavigableMap<K, V>) getMap();
77  }
78
79  @CollectionSize.Require(ZERO)
80  public void testEmptyMapFirst() {
81    assertNull(navigableMap.firstEntry());
82    try {
83      navigableMap.firstKey();
84      fail();
85    } catch (NoSuchElementException e) {
86    }
87  }
88
89  @MapFeature.Require(SUPPORTS_REMOVE)
90  @CollectionSize.Require(ZERO)
91  public void testEmptyMapPollFirst() {
92    assertNull(navigableMap.pollFirstEntry());
93  }
94
95  @CollectionSize.Require(ZERO)
96  public void testEmptyMapNearby() {
97    assertNull(navigableMap.lowerEntry(samples.e0.getKey()));
98    assertNull(navigableMap.lowerKey(samples.e0.getKey()));
99    assertNull(navigableMap.floorEntry(samples.e0.getKey()));
100    assertNull(navigableMap.floorKey(samples.e0.getKey()));
101    assertNull(navigableMap.ceilingEntry(samples.e0.getKey()));
102    assertNull(navigableMap.ceilingKey(samples.e0.getKey()));
103    assertNull(navigableMap.higherEntry(samples.e0.getKey()));
104    assertNull(navigableMap.higherKey(samples.e0.getKey()));
105  }
106
107  @CollectionSize.Require(ZERO)
108  public void testEmptyMapLast() {
109    assertNull(navigableMap.lastEntry());
110    try {
111      assertNull(navigableMap.lastKey());
112      fail();
113    } catch (NoSuchElementException e) {
114    }
115  }
116
117  @MapFeature.Require(SUPPORTS_REMOVE)
118  @CollectionSize.Require(ZERO)
119  public void testEmptyMapPollLast() {
120    assertNull(navigableMap.pollLastEntry());
121  }
122
123  @CollectionSize.Require(ONE)
124  public void testSingletonMapFirst() {
125    assertEquals(a, navigableMap.firstEntry());
126    assertEquals(a.getKey(), navigableMap.firstKey());
127  }
128
129  @MapFeature.Require(SUPPORTS_REMOVE)
130  @CollectionSize.Require(ONE)
131  public void testSingletonMapPollFirst() {
132    assertEquals(a, navigableMap.pollFirstEntry());
133    assertTrue(navigableMap.isEmpty());
134  }
135
136  @CollectionSize.Require(ONE)
137  public void testSingletonMapNearby() {
138    assertNull(navigableMap.lowerEntry(samples.e0.getKey()));
139    assertNull(navigableMap.lowerKey(samples.e0.getKey()));
140    assertEquals(a, navigableMap.floorEntry(samples.e0.getKey()));
141    assertEquals(a.getKey(), navigableMap.floorKey(samples.e0.getKey()));
142    assertEquals(a, navigableMap.ceilingEntry(samples.e0.getKey()));
143    assertEquals(a.getKey(), navigableMap.ceilingKey(samples.e0.getKey()));
144    assertNull(navigableMap.higherEntry(samples.e0.getKey()));
145    assertNull(navigableMap.higherKey(samples.e0.getKey()));
146  }
147
148  @CollectionSize.Require(ONE)
149  public void testSingletonMapLast() {
150    assertEquals(a, navigableMap.lastEntry());
151    assertEquals(a.getKey(), navigableMap.lastKey());
152  }
153
154  @MapFeature.Require(SUPPORTS_REMOVE)
155  @CollectionSize.Require(ONE)
156  public void testSingletonMapPollLast() {
157    assertEquals(a, navigableMap.pollLastEntry());
158    assertTrue(navigableMap.isEmpty());
159  }
160
161  @CollectionSize.Require(SEVERAL)
162  public void testFirst() {
163    assertEquals(a, navigableMap.firstEntry());
164    assertEquals(a.getKey(), navigableMap.firstKey());
165  }
166
167  @MapFeature.Require(SUPPORTS_REMOVE)
168  @CollectionSize.Require(SEVERAL)
169  public void testPollFirst() {
170    assertEquals(a, navigableMap.pollFirstEntry());
171    assertEquals(entries.subList(1, entries.size()),
172        Helpers.copyToList(navigableMap.entrySet()));
173  }
174
175  @MapFeature.Require(absent = SUPPORTS_REMOVE)
176  public void testPollFirstUnsupported() {
177    try {
178      navigableMap.pollFirstEntry();
179      fail();
180    } catch (UnsupportedOperationException e) {
181    }
182  }
183
184  @CollectionSize.Require(SEVERAL)
185  public void testLower() {
186    resetWithHole();
187    assertEquals(null, navigableMap.lowerEntry(a.getKey()));
188    assertEquals(null, navigableMap.lowerKey(a.getKey()));
189    assertEquals(a, navigableMap.lowerEntry(b.getKey()));
190    assertEquals(a.getKey(), navigableMap.lowerKey(b.getKey()));
191    assertEquals(a, navigableMap.lowerEntry(c.getKey()));
192    assertEquals(a.getKey(), navigableMap.lowerKey(c.getKey()));
193  }
194
195  @CollectionSize.Require(SEVERAL)
196  public void testFloor() {
197    resetWithHole();
198    assertEquals(a, navigableMap.floorEntry(a.getKey()));
199    assertEquals(a.getKey(), navigableMap.floorKey(a.getKey()));
200    assertEquals(a, navigableMap.floorEntry(b.getKey()));
201    assertEquals(a.getKey(), navigableMap.floorKey(b.getKey()));
202    assertEquals(c, navigableMap.floorEntry(c.getKey()));
203    assertEquals(c.getKey(), navigableMap.floorKey(c.getKey()));
204  }
205
206  @CollectionSize.Require(SEVERAL)
207  public void testCeiling() {
208    resetWithHole();
209    assertEquals(a, navigableMap.ceilingEntry(a.getKey()));
210    assertEquals(a.getKey(), navigableMap.ceilingKey(a.getKey()));
211    assertEquals(c, navigableMap.ceilingEntry(b.getKey()));
212    assertEquals(c.getKey(), navigableMap.ceilingKey(b.getKey()));
213    assertEquals(c, navigableMap.ceilingEntry(c.getKey()));
214    assertEquals(c.getKey(), navigableMap.ceilingKey(c.getKey()));
215  }
216
217  @CollectionSize.Require(SEVERAL)
218  public void testHigher() {
219    resetWithHole();
220    assertEquals(c, navigableMap.higherEntry(a.getKey()));
221    assertEquals(c.getKey(), navigableMap.higherKey(a.getKey()));
222    assertEquals(c, navigableMap.higherEntry(b.getKey()));
223    assertEquals(c.getKey(), navigableMap.higherKey(b.getKey()));
224    assertEquals(null, navigableMap.higherEntry(c.getKey()));
225    assertEquals(null, navigableMap.higherKey(c.getKey()));
226  }
227
228  @CollectionSize.Require(SEVERAL)
229  public void testLast() {
230    assertEquals(c, navigableMap.lastEntry());
231    assertEquals(c.getKey(), navigableMap.lastKey());
232  }
233
234  @MapFeature.Require(SUPPORTS_REMOVE)
235  @CollectionSize.Require(SEVERAL)
236  public void testPollLast() {
237    assertEquals(c, navigableMap.pollLastEntry());
238    assertEquals(entries.subList(0, entries.size() - 1),
239        Helpers.copyToList(navigableMap.entrySet()));
240  }
241
242  @MapFeature.Require(absent = SUPPORTS_REMOVE)
243  @CollectionSize.Require(SEVERAL)
244  public void testPollLastUnsupported() {
245    try {
246      navigableMap.pollLastEntry();
247      fail();
248    } catch (UnsupportedOperationException e) {
249    }
250  }
251
252  @CollectionSize.Require(SEVERAL)
253  public void testDescendingNavigation() {
254    List<Entry<K, V>> descending = new ArrayList<Entry<K, V>>();
255    for (Entry<K, V> entry : navigableMap.descendingMap().entrySet()) {
256      descending.add(entry);
257    }
258    Collections.reverse(descending);
259    assertEquals(entries, descending);
260  }
261}
262