1 /* 2 * Copyright (C) 2008 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; 18 19 import static com.google.common.collect.Iterators.peekingIterator; 20 import static com.google.common.collect.testing.IteratorFeature.MODIFIABLE; 21 import static com.google.common.collect.testing.IteratorFeature.UNMODIFIABLE; 22 import static java.util.Collections.emptyList; 23 24 import com.google.common.annotations.GwtCompatible; 25 import com.google.common.collect.testing.IteratorTester; 26 27 import junit.framework.TestCase; 28 29 import java.util.Collection; 30 import java.util.Collections; 31 import java.util.Iterator; 32 import java.util.List; 33 import java.util.NoSuchElementException; 34 35 /** 36 * Unit test for {@link PeekingIterator}. 37 * 38 * @author Mick Killianey 39 */ 40 @SuppressWarnings("serial") // No serialization is used in this test 41 @GwtCompatible(emulated = true) 42 public class PeekingIteratorTest extends TestCase { 43 44 /** 45 * Version of {@link IteratorTester} that compares an iterator over 46 * a given collection of elements (used as the reference iterator) 47 * against a {@code PeekingIterator} that *wraps* such an iterator 48 * (used as the target iterator). 49 * 50 * <p>This IteratorTester makes copies of the master so that it can 51 * later verify that {@link PeekingIterator#remove()} removes the 52 * same elements as the reference's iterator {@code #remove()}. 53 */ 54 private static class PeekingIteratorTester<T> extends IteratorTester<T> { 55 private Iterable<T> master; 56 private List<T> targetList; 57 58 public PeekingIteratorTester(Collection<T> master) { 59 super(master.size() + 3, MODIFIABLE, master, 60 IteratorTester.KnownOrder.KNOWN_ORDER); 61 this.master = master; 62 } 63 @Override protected Iterator<T> newTargetIterator() { 64 // make copy from master to verify later 65 targetList = Lists.newArrayList(master); 66 Iterator<T> iterator = targetList.iterator(); 67 return Iterators.peekingIterator(iterator); 68 } 69 @Override protected void verify(List<T> elements) { 70 // verify same objects were removed from reference and target 71 assertEquals(elements, targetList); 72 } 73 } 74 75 private <T> void actsLikeIteratorHelper(final List<T> list) { 76 // Check with modifiable copies of the list 77 new PeekingIteratorTester<T>(list).test(); 78 79 // Check with unmodifiable lists 80 new IteratorTester<T>(list.size() * 2 + 2, UNMODIFIABLE, list, 81 IteratorTester.KnownOrder.KNOWN_ORDER) { 82 @Override protected Iterator<T> newTargetIterator() { 83 Iterator<T> iterator = Collections.unmodifiableList(list).iterator(); 84 return Iterators.peekingIterator(iterator); 85 } 86 }.test(); 87 } 88 89 public void testPeekingIteratorBehavesLikeIteratorOnEmptyIterable() { 90 actsLikeIteratorHelper(Collections.emptyList()); 91 } 92 93 public void testPeekingIteratorBehavesLikeIteratorOnSingletonIterable() { 94 actsLikeIteratorHelper(Collections.singletonList(new Object())); 95 } 96 97 // TODO(cpovirk): instead of skipping, use a smaller number of steps 98 99 public void testPeekOnEmptyList() { 100 List<?> list = Collections.emptyList(); 101 Iterator<?> iterator = list.iterator(); 102 PeekingIterator<?> peekingIterator = Iterators.peekingIterator(iterator); 103 104 try { 105 peekingIterator.peek(); 106 fail("Should throw NoSuchElementException if nothing to peek()"); 107 } catch (NoSuchElementException e) { /* expected */ } 108 } 109 110 public void testPeekDoesntChangeIteration() { 111 List<?> list = Lists.newArrayList("A", "B", "C"); 112 Iterator<?> iterator = list.iterator(); 113 PeekingIterator<?> peekingIterator = 114 Iterators.peekingIterator(iterator); 115 116 assertEquals("Should be able to peek() at first element", 117 "A", peekingIterator.peek()); 118 assertEquals("Should be able to peek() first element multiple times", 119 "A", peekingIterator.peek()); 120 assertEquals("next() should still return first element after peeking", 121 "A", peekingIterator.next()); 122 123 assertEquals("Should be able to peek() at middle element", 124 "B", peekingIterator.peek()); 125 assertEquals("Should be able to peek() middle element multiple times", 126 "B", peekingIterator.peek()); 127 assertEquals("next() should still return middle element after peeking", 128 "B", peekingIterator.next()); 129 130 assertEquals("Should be able to peek() at last element", 131 "C", peekingIterator.peek()); 132 assertEquals("Should be able to peek() last element multiple times", 133 "C", peekingIterator.peek()); 134 assertEquals("next() should still return last element after peeking", 135 "C", peekingIterator.next()); 136 137 try { 138 peekingIterator.peek(); 139 fail("Should throw exception if no next to peek()"); 140 } catch (NoSuchElementException e) { /* expected */ } 141 try { 142 peekingIterator.peek(); 143 fail("Should continue to throw exception if no next to peek()"); 144 } catch (NoSuchElementException e) { /* expected */ } 145 try { 146 peekingIterator.next(); 147 fail("next() should still throw exception after the end of iteration"); 148 } catch (NoSuchElementException e) { /* expected */ } 149 } 150 151 public void testCantRemoveAfterPeek() { 152 List<String> list = Lists.newArrayList("A", "B", "C"); 153 Iterator<String> iterator = list.iterator(); 154 PeekingIterator<?> peekingIterator = Iterators.peekingIterator(iterator); 155 156 assertEquals("A", peekingIterator.next()); 157 assertEquals("B", peekingIterator.peek()); 158 159 /* Should complain on attempt to remove() after peek(). */ 160 try { 161 peekingIterator.remove(); 162 fail("remove() should throw IllegalStateException after a peek()"); 163 } catch (IllegalStateException e) { /* expected */ } 164 165 assertEquals("After remove() throws exception, peek should still be ok", 166 "B", peekingIterator.peek()); 167 168 /* Should recover to be able to remove() after next(). */ 169 assertEquals("B", peekingIterator.next()); 170 peekingIterator.remove(); 171 assertEquals("Should have removed an element", 2, list.size()); 172 assertFalse("Second element should be gone", list.contains("B")); 173 } 174 175 static class ThrowsAtEndException extends RuntimeException { /* nothing */ } 176 177 /** 178 * This Iterator claims to have more elements than the underlying 179 * iterable, but when you try to fetch the extra elements, it throws 180 * an unchecked exception. 181 */ 182 static class ThrowsAtEndIterator<E> implements Iterator<E> { 183 Iterator<E> iterator; 184 public ThrowsAtEndIterator(Iterable<E> iterable) { 185 this.iterator = iterable.iterator(); 186 } 187 @Override 188 public boolean hasNext() { 189 return true; // pretend that you have more... 190 } 191 @Override 192 public E next() { 193 // ...but throw an unchecked exception when you ask for it. 194 if (!iterator.hasNext()) { 195 throw new ThrowsAtEndException(); 196 } 197 return iterator.next(); 198 } 199 @Override 200 public void remove() { 201 iterator.remove(); 202 } 203 } 204 205 public void testPeekingIteratorDoesntAdvancePrematurely() throws Exception { 206 /* 207 * This test will catch problems where the underlying iterator 208 * throws a RuntimeException when retrieving the nth element. 209 * 210 * If the PeekingIterator is caching elements too aggressively, 211 * it may throw the exception on the (n-1)th element (oops!). 212 */ 213 214 /* Checks the case where the first element throws an exception. */ 215 216 List<Integer> list = emptyList(); 217 Iterator<Integer> iterator = 218 peekingIterator(new ThrowsAtEndIterator<Integer>(list)); 219 assertNextThrows(iterator); 220 221 /* Checks the case where a later element throws an exception. */ 222 223 list = Lists.newArrayList(1, 2); 224 iterator = peekingIterator(new ThrowsAtEndIterator<Integer>(list)); 225 assertTrue(iterator.hasNext()); 226 iterator.next(); 227 assertTrue(iterator.hasNext()); 228 iterator.next(); 229 assertNextThrows(iterator); 230 } 231 232 private void assertNextThrows(Iterator<?> iterator) { 233 try { 234 iterator.next(); 235 fail(); 236 } catch (ThrowsAtEndException expected) { 237 } 238 } 239 } 240 241