001/*
002 * Copyright (C) 2010 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect.testing.testers;
018
019import static com.google.common.collect.testing.Helpers.copyToList;
020import static com.google.common.collect.testing.Helpers.entryComparator;
021import static com.google.common.collect.testing.features.CollectionSize.ONE;
022import static com.google.common.collect.testing.features.CollectionSize.SEVERAL;
023import static com.google.common.collect.testing.features.CollectionSize.ZERO;
024import static com.google.common.collect.testing.features.MapFeature.SUPPORTS_REMOVE;
025import static java.util.Collections.sort;
026import static org.junit.Assert.assertThrows;
027
028import com.google.common.annotations.GwtIncompatible;
029import com.google.common.collect.testing.AbstractMapTester;
030import com.google.common.collect.testing.features.CollectionSize;
031import com.google.common.collect.testing.features.MapFeature;
032import java.util.ArrayList;
033import java.util.Collections;
034import java.util.List;
035import java.util.Map.Entry;
036import java.util.NavigableMap;
037
038/**
039 * A generic JUnit test which tests operations on a NavigableMap. Can't be invoked directly; please
040 * see {@code NavigableMapTestSuiteBuilder}.
041 *
042 * @author Jesse Wilson
043 * @author Louis Wasserman
044 */
045@GwtIncompatible
046public class NavigableMapNavigationTester<K, V> extends AbstractMapTester<K, V> {
047
048  private NavigableMap<K, V> navigableMap;
049  private List<Entry<K, V>> entries;
050  private Entry<K, V> a;
051  private Entry<K, V> b;
052  private Entry<K, V> c;
053
054  @Override
055  public void setUp() throws Exception {
056    super.setUp();
057    navigableMap = (NavigableMap<K, V>) getMap();
058    entries =
059        copyToList(
060            getSubjectGenerator()
061                .getSampleElements(getSubjectGenerator().getCollectionSize().getNumElements()));
062    sort(entries, entryComparator(navigableMap.comparator()));
063
064    // some tests assume SEVERAL == 3
065    if (entries.size() >= 1) {
066      a = entries.get(0);
067      if (entries.size() >= 3) {
068        b = entries.get(1);
069        c = entries.get(2);
070      }
071    }
072  }
073
074  /** Resets the contents of navigableMap to have entries a, c, for the navigation tests. */
075  @SuppressWarnings("unchecked") // Needed to stop Eclipse whining
076  private void resetWithHole() {
077    Entry<K, V>[] entries = (Entry<K, V>[]) new Entry<?, ?>[] {a, c};
078    super.resetMap(entries);
079    navigableMap = (NavigableMap<K, V>) getMap();
080  }
081
082  @CollectionSize.Require(ZERO)
083  public void testEmptyMapFirst() {
084    assertNull(navigableMap.firstEntry());
085  }
086
087  @MapFeature.Require(SUPPORTS_REMOVE)
088  @CollectionSize.Require(ZERO)
089  public void testEmptyMapPollFirst() {
090    assertNull(navigableMap.pollFirstEntry());
091  }
092
093  @CollectionSize.Require(ZERO)
094  public void testEmptyMapNearby() {
095    assertNull(navigableMap.lowerEntry(k0()));
096    assertNull(navigableMap.lowerKey(k0()));
097    assertNull(navigableMap.floorEntry(k0()));
098    assertNull(navigableMap.floorKey(k0()));
099    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()), 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(entries.subList(0, entries.size() - 1), copyToList(navigableMap.entrySet()));
223  }
224
225  @MapFeature.Require(absent = SUPPORTS_REMOVE)
226  @CollectionSize.Require(SEVERAL)
227  public void testPollLastUnsupported() {
228    assertThrows(UnsupportedOperationException.class, () -> navigableMap.pollLastEntry());
229  }
230
231  @CollectionSize.Require(SEVERAL)
232  public void testDescendingNavigation() {
233    List<Entry<K, V>> descending = new ArrayList<>(navigableMap.descendingMap().entrySet());
234    Collections.reverse(descending);
235    assertEquals(entries, descending);
236  }
237
238  @CollectionSize.Require(absent = ZERO)
239  public void testHeadMapExclusive() {
240    assertFalse(navigableMap.headMap(a.getKey(), false).containsKey(a.getKey()));
241  }
242
243  @CollectionSize.Require(absent = ZERO)
244  public void testHeadMapInclusive() {
245    assertTrue(navigableMap.headMap(a.getKey(), true).containsKey(a.getKey()));
246  }
247
248  @CollectionSize.Require(absent = ZERO)
249  public void testTailMapExclusive() {
250    assertFalse(navigableMap.tailMap(a.getKey(), false).containsKey(a.getKey()));
251  }
252
253  @CollectionSize.Require(absent = ZERO)
254  public void testTailMapInclusive() {
255    assertTrue(navigableMap.tailMap(a.getKey(), true).containsKey(a.getKey()));
256  }
257}