Enhancing Aggregate Data Structures with Selection Iterators
Selection iterators traverse the elements in aggregate data structures such as lists, maps, and trees, and return only those elements that meet a particular criteria. The element selection criteria is encapsulated in a selection object which separates the decision to return an element from the order in which that decision is made. Selection iterators promote cleaner iteration loop code by moving the test for the required elements into the iterator. Aggregate data structures can also be enhanced by using selection iterators to create sub-collections.
1. Introduction
Objects that follow the Iterator design pattern provide sequential access to the elements of aggregate data structures, or collections, such as lists, maps, and trees (Gamma et al. 1995). Iterators are used to perform common tasks such as the application of an operation to each element in a list or for retrieving each element for use in a calculation. The following code shows a typical example of iterating through the elements of a list in Java.
for (Iterator i = list.iterator(); i.hasNext();) {
System.out.println(i.next());
}The list object returns an iterator with a call to iterator(). The iterator’s hasNext() method determines whether there are more elements to return and controls when the iteration loop terminates. The iterator’s next() method returns the next element in the list.
Iterators return each element in the collection. In some cases, only a subset of the elements are required. For example, when iterating through a list of numeric and non-numeric elements, only the numeric elements are required to calculate the numeric total. Each element must be tested to ensure it is a numeric object before calling a method to obtain its numeric value. The following Java code iterates over a list that contains numeric and non-numeric elements to calculate the numeric total.
double total = 0;
for (Iterator i = list.iterator(); i.hasNext();) {
Object o = i.next();
if (o instanceof Number) {
Number n = (Number)o;
total += n.doubleValue();
}
}Before obtaining the floating point value of each numeric element with a call to doubleValue(), each element is tested to ensure that it is numeric by checking that its super-class is Number.
Testing each element to ensure it meets some criteria—in this case, being numeric—before using it clutters the iteration loop. A better solution is to iterate over only the required elements—in this case, only the numeric elements.
2. Selection Iterators
Selection iterators traverse the elements in an aggregate data structure such as a list and return only those elements that meet a particular criteria. Gamma et al. (1995, p. 269) describe an abstract internal list iterator class that performs an operation on each element that satisfies some criteria. The criteria is implemented in concrete sub-classes by overriding the method that performs the test.
Selection iterators are generic external iterators that return elements using a selection criteria. The criteria for returning an element is encapsulated in an object that implements the Selector interface.
public boolean select(Object o);This encapsulation separates the decision to return an element from the order in which that decision is made. The Selector interface has one method, select(Object o), that returns true if its parameter meets the criteria.
Aggregate data structures that provide iterators can be extended to provide selection iterators by adding an iterator(Selector s) method. This method returns a selection iterator that uses the selector object to determine which elements will be returned. An example selection iterator is shown below for the class SelectionArrayList, a sub-class of the standard Java ArrayList class.
Using a selection iterator to iterate over only the required elements makes iteration loop code cleaner. The following code implements the same iteration loop for calculating the total of the numeric elements but uses a selection iterator to ensure that only numeric elements are returned.
double total = 0;
Selector s = new NumberSelector();
for (Iterator i = list.iterator(s); i.hasNext();) {
Number n = (Number)i.next();
total += n.doubleValue();
}The NumberSelector object implements the Selector interface and returns true if the element passed into its select(Object o) method is a sub-class of Number. The iteration loop is now cleaner because only the calculation is mentioned; the test for a numeric element does not clutter the code.
Selection iterators can have a slight performance disadvantage: any calculations or tests performed by a selector object to determine whether an element meets its criteria cannot be reused in the iteration loop.
The examples in this article highlight traversal through the elements of a list from beginning to end. Selection iterators can be implemented for back to front list traversal, and for data structures with non-linear traversal such as trees. Because the choice to return an element is encapsulated in selection objects, they can be reused in other selection iterators.
3. Creating Sub-Collections
Aggregate data structures can be further extended to use selection iterators to produce sub-collections. Lists, for example, often have a method for returning a sub-list of the elements stored between two indices, such as: List subList(int from, int to). A more powerful sub-list method can be implemented that uses a selector object to determine which elements are added to the sub-list: List subList(Selector s). The following code shows the implementation of such a method for a List class in Java. Variants of this method can be implemented to apply the selector object to the elements between two indices, for example.
public List subList(Selector s) {
ArrayList subList = new ArrayList(size());
for (Iterator i = iterator(s); i.hasNext();) {
subList.add(i.next());
}
subList.trimToSize();
return subList;
}4. An Example Selection Iterator
The SelectionArrayList class is an example of a selection iterator.
public class SelectionArrayList extends ArrayList {
public Iterator iterator(Selector s) {
return new SelectionIterator(s);
}
private class SelectionIterator implements Iterator {
/**
* The Selector object that determines the object to be returned by
* the next call to next().
*/
private Selector selector;
/**
* Index of the element to be returned by the next call to next().
*/
int cursor = -1;
/**
* The modCount value that the iterator believes that the backing
* List should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
int expectedModCount = modCount;
protected SelectionIterator(Selector s) {
selector = s;
cursor = getNextCursor();
}
public boolean hasNext() {
/**
* getNextCursor() forwards the cursor to the end of the list
* when there are no more elements that match the criteria of
* the selector.
*/
return (cursor != size());
}
public Object next() {
checkForComodification();
Object next = null;
if (hasNext()) {
next = get(cursor);
cursor = getNextCursor();
}
return next;
}
/**
* Return the index of the next element that matches the selector.
*/
private int getNextCursor() {
try {
cursor++;
if (cursor != size()) {
Object next = get(cursor);
int size = size();
/**
* If next is not selected, keep going until a selected
* element is found or the end of the list is reached.
*/
while (!selector.select(next) && (cursor < size)) {
cursor++;
if (cursor < size) {
next = get(cursor);
}
}
}
return cursor;
}
catch(IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
/**
* Not implemented for simplicity.
*/
public void remove() {
throw new UnsupportedOperationException();
}
private void checkForComodification() {
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
}
}References
- Gamma, E., R. Helm, R. Johnson and J. Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software, Addison-Wesley, 1995.