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.assertEqualInOrder;
020import static com.google.common.collect.testing.Helpers.copyToList;
021import static com.google.common.collect.testing.Helpers.entryComparator;
022import static com.google.common.collect.testing.features.CollectionSize.ONE;
023import static com.google.common.collect.testing.features.CollectionSize.SEVERAL;
024import static com.google.common.collect.testing.features.CollectionSize.ZERO;
025import static java.util.Collections.sort;
026import static org.junit.Assert.assertThrows;
027
028import com.google.common.annotations.GwtCompatible;
029import com.google.common.collect.testing.AbstractMapTester;
030import com.google.common.collect.testing.features.CollectionSize;
031import java.util.Comparator;
032import java.util.Iterator;
033import java.util.List;
034import java.util.Map.Entry;
035import java.util.NoSuchElementException;
036import java.util.SortedMap;
037
038/**
039 * A generic JUnit test which tests operations on a SortedMap. Can't be invoked directly; please see
040 * {@code SortedMapTestSuiteBuilder}.
041 *
042 * @author Jesse Wilson
043 * @author Louis Wasserman
044 */
045@GwtCompatible
046public class SortedMapNavigationTester<K, V> extends AbstractMapTester<K, V> {
047  @SuppressWarnings("unchecked")
048  private static final Comparator<Object> NATURAL_ORDER =
049      (o1, o2) -> ((Comparable<Object>) o1).compareTo(o2);
050
051  private SortedMap<K, V> navigableMap;
052  private Entry<K, V> a;
053  private Entry<K, V> c;
054
055  @Override
056  public void setUp() throws Exception {
057    super.setUp();
058    navigableMap = (SortedMap<K, V>) getMap();
059    List<Entry<K, V>> entries =
060        copyToList(
061            getSubjectGenerator()
062                .getSampleElements(getSubjectGenerator().getCollectionSize().getNumElements()));
063    sort(entries, entryComparator(navigableMap.comparator()));
064
065    // some tests assume SEVERAL == 3
066    if (entries.size() >= 1) {
067      a = entries.get(0);
068      if (entries.size() >= 3) {
069        c = entries.get(2);
070      }
071    }
072  }
073
074  @CollectionSize.Require(ZERO)
075  public void testEmptyMapFirst() {
076    assertThrows(NoSuchElementException.class, () -> navigableMap.firstKey());
077  }
078
079  @CollectionSize.Require(ZERO)
080  public void testEmptyMapLast() {
081    assertThrows(NoSuchElementException.class, () -> assertNull(navigableMap.lastKey()));
082  }
083
084  @CollectionSize.Require(ONE)
085  public void testSingletonMapFirst() {
086    assertEquals(a.getKey(), navigableMap.firstKey());
087  }
088
089  @CollectionSize.Require(ONE)
090  public void testSingletonMapLast() {
091    assertEquals(a.getKey(), navigableMap.lastKey());
092  }
093
094  @CollectionSize.Require(SEVERAL)
095  public void testFirst() {
096    assertEquals(a.getKey(), navigableMap.firstKey());
097  }
098
099  @CollectionSize.Require(SEVERAL)
100  public void testLast() {
101    assertEquals(c.getKey(), navigableMap.lastKey());
102  }
103
104  @CollectionSize.Require(absent = ZERO)
105  public void testHeadMapExclusive() {
106    assertFalse(navigableMap.headMap(a.getKey()).containsKey(a.getKey()));
107  }
108
109  @CollectionSize.Require(absent = ZERO)
110  public void testTailMapInclusive() {
111    assertTrue(navigableMap.tailMap(a.getKey()).containsKey(a.getKey()));
112  }
113
114  public void testHeadMap() {
115    List<Entry<K, V>> entries =
116        copyToList(
117            getSubjectGenerator()
118                .getSampleElements(getSubjectGenerator().getCollectionSize().getNumElements()));
119    sort(entries, entryComparator(navigableMap.comparator()));
120    for (int i = 0; i < entries.size(); i++) {
121      assertEqualInOrder(
122          entries.subList(0, i), navigableMap.headMap(entries.get(i).getKey()).entrySet());
123    }
124  }
125
126  public void testTailMap() {
127    List<Entry<K, V>> entries =
128        copyToList(
129            getSubjectGenerator()
130                .getSampleElements(getSubjectGenerator().getCollectionSize().getNumElements()));
131    sort(entries, entryComparator(navigableMap.comparator()));
132    for (int i = 0; i < entries.size(); i++) {
133      assertEqualInOrder(
134          entries.subList(i, entries.size()),
135          navigableMap.tailMap(entries.get(i).getKey()).entrySet());
136    }
137  }
138
139  public void testSubMap() {
140    List<Entry<K, V>> entries =
141        copyToList(
142            getSubjectGenerator()
143                .getSampleElements(getSubjectGenerator().getCollectionSize().getNumElements()));
144    sort(entries, entryComparator(navigableMap.comparator()));
145    for (int i = 0; i < entries.size(); i++) {
146      for (int j = i + 1; j < entries.size(); j++) {
147        assertEqualInOrder(
148            entries.subList(i, j),
149            navigableMap.subMap(entries.get(i).getKey(), entries.get(j).getKey()).entrySet());
150      }
151    }
152  }
153
154  @CollectionSize.Require(SEVERAL)
155  public void testSubMapIllegal() {
156    assertThrows(IllegalArgumentException.class, () -> navigableMap.subMap(c.getKey(), a.getKey()));
157  }
158
159  @CollectionSize.Require(absent = ZERO)
160  public void testOrderedByComparator() {
161    Comparator<? super K> comparator = navigableMap.comparator();
162    if (comparator == null) {
163      comparator = NATURAL_ORDER;
164    }
165    Iterator<Entry<K, V>> entryItr = navigableMap.entrySet().iterator();
166    Entry<K, V> prevEntry = entryItr.next();
167    while (entryItr.hasNext()) {
168      Entry<K, V> nextEntry = entryItr.next();
169      assertTrue(comparator.compare(prevEntry.getKey(), nextEntry.getKey()) < 0);
170      prevEntry = nextEntry;
171    }
172  }
173}