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.
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.
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.
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
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.
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
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
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.
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.
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.
SelectionArrayList class is an example of a selection iterator.