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