10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
public FilteredList (List
@Override
public Iterator
}
CS 61B Iterators and Iterables Spring 2021 Exam Prep Discussion 5: February 16, 2021
1 Filtered List
We want to make a FilteredList class that selects only certain elements of a List during iteration. To do so, we¡¯re going to use the Predicate interface defined below. Note that it has a method, test that takes in an argument and returns True if we want to keep this argument or False otherwise.
public interface Predicate
}
For example, if L is any kind of object that implements List
standard java.util.List), then writing
FilteredList
gives an iterable containing all items, x, in L for which filter.test(x) is True. Here, filter is of type Predicate. Fill in the FilteredList class below.
import java.util.*;
public class FilteredList
1
2
3
4
5
6
7
8 9}
}
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
2 Iterators and Iterables Solution:
import java.util.*;
class FilteredList
Predicate
public FilteredList(List
this.pred = filter; }
public Iterator
return new FilteredListIterator();
}
private class FilteredListIterator implements Iterator
int index;
public FilteredListIterator() { index = 0;
moveIndex();
}
@Override
public boolean hasNext() {
return index < list.size(); }
@Override
public T next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
T answer = list.get(index); index += 1;
moveIndex();
return answer;
}
private void moveIndex() {
while (hasNext() && !pred.test(list.get(index))) { index += 1;
} }
} }
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
Alternate Solution: Although this solution provides the right functionality, it is not as efficient as the first one. Imagine you only want the first couple items from the iterable. Is it worth processing the entire list in the constructor? It is not ideal in the case that our list is millions of elements long. The first solution is different in that we ¡±lazily¡± evaluate the list, only progressing our index on every call to next and hasNext. However, this solution may be easier to digest.
import java.util.*;
class FilteredList
Predicate
public FilteredList(List
this.pred = filter; }
public Iterator
return new FilteredListIterator();
}
private class FilteredListIterator implements Iterator
public FilteredListIterator() { items = new LinkedList<>(); for (T item: list) {
if (pred.test(item)) { items.add(item);
} }
}
@Override
public boolean hasNext() {
return !items.isEmpty(); }
@Override
public T next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return items.removeFirst(); }
}
Iterators and Iterables 3
4 Iterators and Iterables
2 Iterator of Iterators
Implement an IteratorOfIterators which will accept as an argument a List of Iterator objects containing Integers. The first call to next() should return the first item from the first iterator in the list. The second call to next() should return the first item from the second iterator in the list. If the list contained n iterators, the n+1th time that we call next(), we would return the second item of the first iterator in the list.
Note that if an iterator is empty in this process, we continue to the next iterator. Then, once all the iterators are empty, hasNext should return false. For example, if we had 3 Iterators A, B, and C such that A contained the values [1, 3, 4, 5], B was empty, and C contained the values [2], calls to next() for our IteratorOfIterators would return [1, 2, 3, 4, 5].
1 import java.util.*;
2 public class IteratorOfIterators ______________________________ {
3
4
5 public IteratorOfIterators(List
7
8
9
10
11
12
13 } 14
15 @Override
16 public boolean hasNext() {
17
18
19
20
21 } 22
23
24
25 @Override
26 public Integer next() {
27 28 29 30
31 }
32 }
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
public IteratorOfIterators(List
for (Iterator
if (iterator.hasNext()) { iterators.add(iterator);
} }
@Override
public boolean hasNext() {
return !iterators.isEmpty(); }
@Override
public Integer next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
Iterator
if (iterator.hasNext()) {
iterators.addLast(iterator);
}
return ans; }
}
Solution:
public class IteratorOfIterators implements Iterator
1
2
3
4
5
6
7
8 9}
Iterators and Iterables 5
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
6 Iterators and Iterables
Alternate Solution: Although this solution provides the right functionality, it is
not as efficient as the first one.
public class IteratorOfIterators implements Iterator
public IteratorOfIterators(List
while (!a.isEmpty()) {
} }
Iterator
l.add(curr.next());
a.add(curr);
}
@Override
public boolean hasNext() {
return !l.isEmpty(); }
@Override
public Integer next() {
if(!hasNext()) {
throw new NoSuchElementException();
}
return l.removeFirst(); }
}
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
public class DMSComparator implements __________________________ {
@Override
public int compare(Animal o1, Animal o2) {
int first = o1.speak(new Animal()); int second = o2.speak(new Animal()); int third = o1.speak(new Dog());
int fourth = o2.speak(new Dog());
if (________________________________________________________) { return 0;
} else if (_________________________________________________) { return 1;
} else { return -1;
} }
}
3 DMS Comparator
Implement the Comparator DMSComparator, which compares Animal instances. An Animal instance is greater than another Animal instance if its dynamic type is more specific. See the examples to the right below.
In the second and third blanks in the compare method, you may only use the integer variables predefined (first, second, etc), relational/equality oper- ators (==, >, etc), boolean operators (&& and ||), integers, and parentheses.
As a challenge, use equality operators (== or !=) and no relational operators (>, <=, etc). There may be more than one solution.
class Animal {
int speak(Dog a) { return 1; } int speak(Animal a) { return 2; }
}
class Dog extends Animal {
int speak(Animal a) { return 3; } }
class Poodle extends Dog {
int speak(Dog a) { return 4; }
}
Examples:
Animal animal = new Animal(); Animal dog = new Dog(); Animal poodle = new Poodle();
compare(animal, dog) // negative number
compare(dog, dog) // zero
compare(poodle, dog) // positive number
Iterators and Iterables 7
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18
8 Iterators and Iterables Solution:
public class DMSComparator implements Comparator
@Override
public int compare(Animal o1, Animal o2) {
int first = o1.speak(new Animal()); int second = o2.speak(new Animal()); int third = o1.speak(new Dog());
int fourth = o2.speak(new Dog());
if (first == second && third == fourth) { return 0;
} else if (first > second || third > fourth) { return 1;
} else { return -1;
} }
}
Challenge Solution:
public class DMSComparator implements Comparator
@Override
public int compare(Animal o1, Animal o2) {
int first = o1.speak(new Animal()); int second = o2.speak(new Animal()); int third = o1.speak(new Dog());
int fourth = o2.speak(new Dog());
if (first == second && third == fourth) { return 0;
} else if (third == 4 || (first == 3 && second == 2)) { return 1;
} else { return -1;
} }
}