Author: Porter Jones
We've had some practice with collections throughout the quarter, but thought there were a few important points that were worth reiterating as we begin to revisit collections problems in preparation for the final.
As a reminder, for-each loops are very useful when performing read-only operations on collections. They also tend to be much nicer for readability than a typical index-based for loop. For example, imagine we want to write a method printValues that prints out all the values in a given Set of numbers. The following method is an excellent example of when to use a for-each loop:
public static void printValues(Set<Integer> s) {
for (int number : s) {
System.out.println(number);
}
}Remember that a for-each loop iterates over the values in an order determined by the collection (e.g. sorted order for TreeSet and an order that looks random for HashSet), so if I passed a TreeSetto printValues with the values [1, 4, 6, 30, 143] then the output would be
1
4
6
30
143
Now let's try writing a method for a slightly adjusted version of the problem, this time removing multiples of three from a given Set. Following the above example, we might try:
public static void removeMultiplesOfThree(Set<Integer> s) {
for (int number : s) {
if (number % 3 == 0) {
s.remove(number);
}
}
}While the above code seems like it might work, it does not. Java will throw a ConcurrentModificationException when trying to run the above code. As was stated above, for-each loops can only be used for read-only operations, you are not allowed to modify a collection while for-eaching over it. So knowing that a for-each loop is no longer viable for writing removeMultiplesOfThree, what tool should we use to solve the problem? It may seem tempting to try to use an index-based for loop and call get(index), but remember that a Set is not an index-based collection, and thus there is no get(index) method for a Set.
The answer to our problem is that we need to use an Iterator. Remember that we first create an iterator, then we can use the following Iterator functions:
Iterator<Type> itr = collection.iterator()to create the iterator object wherecollectionis a data structure that holds values of typeTypeitr.next()to get the next item in a collectionitr.hasNext()to determine if there are any more elements left to iterate overitr.remove()to remove the last item retrieved with .next()
Below is an example of a proper working solution for removeMultiplesOfThree that uses an Iterator:
public static void removeMultiplesOfThree(Set<Integer> s) {
Iterator<Integer> itr = s.iterator();
while (itr.hasNext()) {
int number = itr.next();
if (number % 3 == 0) {
itr.remove(); // Must remove using the iterator, not s.remove(number)
}
}
}To recap, for-each loops are great for read-only operations over collections, but if we actually want to modify a collection, we cannot use a for-each loop and must use another tool such as an Iterator. It's also worth pointing out that not every Object implements the Iterable interface which guarantees implementing classes have an iterator method, so it is not applicable in all sitations.
This quarter we've talked about Java's HashSet and TreeSet and briefly mentioned some differences between the two. As a reminder, a HashSet offers slightly better performance than a TreeSet in operations like contains(value), add(value), and remove(value). But a TreeSet is nice because it stores the values in sorted order, which could be useful to clients, whereas there is no guarantee about the ordering of a HashSet. To reiterate these points, if someone asked you to retrieve things efficiently, a HashSet would be the better choice, but if someone asked for values to be sorted, then a TreeSet would be the better choice.
There is a slightly more nuanced example that sometimes guides us when deciding between a HashSet and a TreeSet. Imagine we want to write a function onXAxis that takes a Set of Java's Point objects and returns a new Set of all the points on the x-axis (with y == 0). We might try:
public static Set<Point> onXAxis(Set<Point> points) {
Set<Point> result = new TreeSet<Point>();
for (Point point : points) {
if (point.y == 0) {
result.add(point);
}
}
return result;
}This seems fairly simple, however upon running our code we notice Java gives us the following error:
Exception in thread "main" java.lang.ClassCastException: java.desktop/java.awt.Point cannot be cast to java.base/java.lang.ComparableThis is basically a very long way of saying that Point does not implement the Comparable interface. Because of this we can't create sorted collections of Point objects (such as TreeSet<Point>) because there is no way for Java to compare two Point objects. To solve our problem, we must use a HashSet because it does not require its items to be Comparable. A revised solution is below, note that it is exactly the same as the above attempt except for the use of the HashSet implementation.
public static Set<Point> onXAxis(Set<Point> points) {
Set<Point> result = new HashSet<Point>();
for (Point point : points) {
if (point.y == 0) {
result.add(point);
}
}
return result;
}This issue doesn't necessarily come up too often, but it is definitely something to be thinking of when both designing/implementing classes and when acting as clients of already defined classes.
From this example, it is also easy to see how the Comparable interface can be very useful in Java. All we have to do when creating a class is define the ordering of our objects (by writing a compareTo method and implementing the Comparable interface) and then our class can be used in scenarios with already predefined sorting/ordering functionality (for example using TreeSets/TreeMaps or Collections.sort).