Java Tutorial: Iterators

Chapters

• Java Tutorial: Iterators
• Enumeration
• Ways of Getting Iterator
• iterator() Method
• descendingIterator() Method
• listIterator() Method
• spliterator() Method
• characteristics() Method
• hasCharacteristics() Method
• tryAdvance() Method
• trySplit() Method
• estimateSize() Method
• getExactSizeIfKnown() Method
• getComparator() Method
• OfDouble, OfInt, OfLong and OfPrimitive

Iterators

Java has different type of iterators. The very first iterator is the Enumeration. New iterators, like the Iterator Interface, differ from enumerations in two ways:

• Iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined semantics.
• Method names have been improved.

An Enumeration can be converted into an Iterator by using the Enumeration.asIterator() method. Iterators are often used for the Collections Framework.

Enumeration

An object that implements the Enumeration interface generates a series of elements, one at a time. Successive calls to the nextElement method return successive elements of the series. This iterator is mainly used for Vector, Stack and HashTable which are legacy collections.

This example demonstrates Enumeration.

import java.util.Enumeration;
import java.util.Vector;

public class SampleClass{

  public static void main(String[] args){
  
    Vector<String> vc =
    new Vector<>();
    
    vc.add("Apple");
    vc.add("Orange");
    vc.add("Melon");
    
    Enumeration<String> en =
    vc.elements();
    
    while(en.hasMoreElements())
      System.out.println(en.nextElement());
  }
}

Result
Apple
Orange
Mango

In the example above, we create a Vector object and add three strings to it. Then, we create an Enumeration for Vector by calling the elements() method. Then, we traverse Vector via Enumeration starting from the first index. hasMoreElements() returns true if the Enumeration's pointer is not past beyond the last index. nextElement() returns the next available element where the Enumeration's pointer is pointing.

Pointer is just like a cursor that is pointing at some index. In Enumeration, pointer starts at index 0. Then, after nextElement() is invoked, the pointer will move to the next index until it reaches the last index.

Ways of Getting Iterator

There are several methods that return an instance that is related to Iterator interface. Each method returns a particular iterator.

iterator() Method

This method returns an Iterator with a pointer that starts at first index and end at last index. This method is available to almost every collection that is a subclass of Collection interface.

import java.util.Iterator;
import java.util.ArrayList;

public class SampleClass{

  public static void main(String[] args){
  
    ArrayList<String> ar =
    new ArrayList<>();
    
    ar.add("Apple");
    ar.add("Orange");
    ar.add("Melon");
    
    Iterator<String> it =
    ar.iterator();
    
    while(it.hasNext())
      System.out.println(it.next());
  }
}

Result
Apple
Orange
Melon

hasNext() returns true if the ArrayList's point is not past beyond last index. next() returns the next available element where the pointer is pointing. We can use Iterator to remove elements by using the remove() method. We can also assign a lambda expression to our iterator by using the forEachRemaining() method.

descendingIterator() Method

This method is available from the Deque interface. LinkedList and ArrayDeque inherit this method. The Iterator that is returned by this method has a pointer that starts at last(tail) index and end at first(head) index.

import java.util.Iterator;
import java.util.LinkedList;

public class SampleClass{

  public static void main(String[] args){
  
    LinkedList<String> ar =
    new LinkedList<>();
    
    ar.add("Apple");
    ar.add("Orange");
    ar.add("Melon");
    
    Iterator<String> it =
    ar.descendingIterator();
    
    while(it.hasNext())
      System.out.println(it.next());
  }
}

Result
Melon
Orange
Apple

listIterator() Method

This method returns a ListIterator. ListIterator is an iterator for lists that allows the programmer to traverse the list in either direction, modify the list during iteration, and obtain the iterator's current position in the list.

A ListIterator has no current element; its cursor position always lies between the element that would be returned by a call to previous() and the element that would be returned by a call to next(). listIterator() is available from List and available to its subclasses. This iterator can get, remove and set an element from an index.

import java.util.ArrayList;
import java.util.ListIterator;

public class SampleClass{

  public static void main(String[] args){
  
    ArrayList<String> ar =
    new ArrayList<>();
    
    ar.add("Apple");
    ar.add("Orange");
    ar.add("Melon");
    ar.add("Melon");
    
    ListIterator<String> li =
    ar.listIterator();
    
    String next = "";
    String prev = "";
    
    int nextIndex = 0;
    int prevIndex = 0;
    System.out.println("Checking for nearest"
    +" duplicate...");
    while(li.hasNext()){
      nextIndex = li.nextIndex();
      next = li.next();
        
      if(next == prev){
        System.out.println(prev + " at index "
        +prevIndex+" is equal to " + next +
        " at index "+nextIndex);
        
        System.out.println("Setting "+prev+
        " at index " + prevIndex + " to "
        +"Watermelon...");
        
        if(li.hasPrevious()){
          prevIndex = li.previousIndex();
          
          while(prevIndex != 1){
            prev = li.previous();
            prevIndex = li.previousIndex();
          }
          
          li.set("Watermelon");
          continue;
        }
      }
      
      prev = next;
      prevIndex = nextIndex;
    }
    
    //We need to create another
    //listIterator to iterate
    //to the ArrayList again
    li = ar.listIterator();
    
    System.out.println("Elements...");
    while(li.hasNext())
      System.out.println(li.next());
    
  }
}

Result
Checking for nearest duplicate...
Melon at index 2 is equal to Melon at index 3
Setting Melon at index 2 to Watermelon...
Elements...
Apple
Orange
Watermelon
Melon

ListIterator's pointer doesn't directly point at elements. it points in-between elements. For example, next() returns "Orange" which is located at index 1. Now, the pointer points at the middle of index 1 and index 2.Now, If we call previousIndex(), it will return index 1. If we call nextIndex(), it will return index 2.

spliterator() Method

This method returns a Spliterator that performs traversing and partitioning elements of a source. The source of elements covered by a Spliterator could be, for example, an array, a Collection, an IO channel, or a generator function. A Spliterator may also partition off some of its elements (using trySplit()) as another Spliterator, to be used in possibly-parallel operations.

Operations using a Spliterator that cannot split, or does so in a highly imbalanced or inefficient manner, are unlikely to benefit from parallelism. Traversal and splitting exhaust elements; each Spliterator is useful for only a single bulk computation. Let's discuss Spliterator's methods. My explanation about methods here is simplifed. Refer to the documentation for more information.

Spliterator have different types of characteristics based on a collection or a stream. It's important to know the characteristics of a particular Spliterator because some characteristics may interfere with out operation or is needed in an operation. For example, if a Spliterator has CONCURRENT characteristic then multiple threads may safely concurrently modify this iterator. Spliterator is available from Collection and BaseStream.

characteristics() Method

Returns a set of characteristics of this Spliterator and its elements. The result is represented as ORed(Bit field) values from ORDERED, DISTINCT, SORTED, SIZED, NONNULL, IMMUTABLE, CONCURRENT, SUBSIZED. Repeated calls to characteristics() on a given spliterator, prior to or in-between calls to trySplit, should always return the same result.

If a Spliterator reports an inconsistent set of characteristics (either those returned from a single invocation or across multiple invocations), no guarantees can be made about any computation using this Spliterator.

import java.util.ArrayList;
import java.util.Spliterator;

public class SampleClass{

  public static void main(String[] args){
    
    ArrayList<String> ar =
    new ArrayList<>();
    
    ar.add("Apple");
    ar.add("Orange");
    ar.add("Melon");
    
    Spliterator<String> st =
    ar.spliterator();
    
    int arChars = Spliterator.ORDERED |
                  Spliterator.SIZED |
                  Spliterator.SUBSIZED;
                  
    if(arChars == st.characteristics())
      System.out.println("Spliterator of "
      +"ArrayList is\nSIZED, SUBSIZED and ORDERED.");
  }
}

Result
Spliterator of ArrayList is
SIZED, SUBSIZED and ORDERED.

hasCharacteristics() Method

Method form:default boolean hasCharacteristics(int characteristics)
Returns true if this Spliterator's characteristics() contain all of the given characteristics.

import java.util.HashSet;
import java.util.Spliterator;

public class SampleClass{

  public static void main(String[] args){
  
    HashSet<String> hs =
    new HashSet<>();
    
    hs.add("Apple");
    hs.add("Orange");
    hs.add("Melon");
    
    Spliterator<String> st =
    hs.spliterator();
    
    if(st.hasCharacteristics(Spliterator.ORDERED))
      System.out.println("st is ORDERED.");
      
    if(st.hasCharacteristics(Spliterator.DISTINCT))
      System.out.println("st is DISTINCT.");
      
    if(st.hasCharacteristics(Spliterator.SORTED))
      System.out.println("st is SORTED.");
      
    if(st.hasCharacteristics(Spliterator.SIZED))
      System.out.println("st is SIZED.");
      
    if(st.hasCharacteristics(Spliterator.NONNULL))
      System.out.println("st is NONNULL.");
      
    if(st.hasCharacteristics(Spliterator.IMMUTABLE))
      System.out.println("st is IMMUTABLE.");
      
    if(st.hasCharacteristics(Spliterator.CONCURRENT))
      System.out.println("st is CONCURRENT.");
      
    if(st.hasCharacteristics(Spliterator.SUBSIZED))
      System.out.println("st is SUBSIZED.");
  }
}

Result
st is DISTINCT.
st is SIZED.

We can put multiple characteristics as a single argument in hasCharacteristics().

import java.util.ArrayList;
import java.util.Spliterator;

public class SampleClass{

  public static void main(String[] args){
    
    ArrayList<String> ar =
    new ArrayList<>();
    
    ar.add("Apple");
    ar.add("Orange");
    ar.add("Melon");
    
    Spliterator<String> st =
    ar.spliterator();
    
    int arChars = Spliterator.ORDERED |
                  Spliterator.SIZED |
                  Spliterator.SUBSIZED;
                  
    if(st.hasCharacteristics(arChars))
      System.out.println("Spliterator of "
      +"ArrayList is\nSIZED, SUBSIZED and ORDERED.");
  }
}

Result
Spliterator of ArrayList is
SIZED, SUBSIZED and ORDERED.

tryAdvance() Method

Method form: boolean tryAdvance(Consumer<? super T> action)
If a remaining element exists, performs the given action on it, returning true; else returns false. If this Spliterator is ORDERED the action is performed on the next element in encounter order. Exceptions thrown by the action are relayed to the caller.

Subsequent behavior of a spliterator is unspecified if the action throws an exception.

import java.util.Spliterator;
import java.util.ArrayList;
import java.util.function.Consumer;

public class SampleClass{

  public static void main(String[] args){
  
    ArrayList<String> ar =
    new ArrayList<>();
    
    ar.add("Apple");
    ar.add("Orange");
    ar.add("Melon");
    
    Spliterator<String> st =
    ar.spliterator();
    
    Consumer<String> cons =
    (e) -> System.out.println("-"+e+"-");
    
    while(st.tryAdvance(cons));
  }
}

Result
-Apple-
-Orange-
-Melon-

trySplit() Method

If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator that called this method. If this Spliterator is ORDERED, the returned Spliterator must cover a strict prefix of the elements.

Unless this Spliterator covers an infinite number of elements, repeated calls to trySplit() must eventually return null. Upon non-null return:

• the value reported for estimateSize() before splitting, must, after splitting, be greater than or equal to estimateSize() for this and the returned Spliterator; and
• if this Spliterator is SUBSIZED, then estimateSize() for this spliterator before splitting must be equal to the sum of estimateSize() for this and the returned Spliterator after splitting.

This method may return null for any reason, including emptiness, inability to split after traversal has commenced, data structure constraints, and efficiency considerations.

import java.util.Spliterator;
import java.util.ArrayList;
import java.util.Collections;

public class SampleClass{

  public static void main(String[] args){
  
    ArrayList<Integer> ar =
    new ArrayList<>();
    
    Collections.addAll(ar,1,2,3,4,5,6,7,8
    ,9,10,11,12,13,14,15);
    
    Spliterator<Integer> st1 =
    ar.spliterator();
    
    Spliterator<Integer> st2 =
    st1.trySplit();
    
    Spliterator<Integer> st3 =
    st2.trySplit();
    
    st1.forEachRemaining(
	(e) -> System.out.println(e));
    
    System.out.println("----------");
    
    st2.forEachRemaining(
	(e) -> System.out.println(e));
    
    System.out.println("----------");
    
    st3.forEachRemaining(
	(e) -> System.out.println(e));
  }
}

Result
8
9
10
11
12
13
14
15
----------
4
5
6
7
----------
1
2
3

In the example above, we use Spliterator in sequential manner. We also use forEachRemaining() for traversing spliterators. If you want to run spliterators in parallel, Use Fork/Join framework or multithreading in conjunction with Spliterator.

estimateSize() Method

Returns an estimate of the number of elements that would be encountered by a forEachRemaining() traversal, or returns Long.MAX_VALUE if infinite, unknown, or too expensive to compute.

If this Spliterator is SIZED and has not yet been partially traversed or split, or this Spliterator is SUBSIZED and has not yet been partially traversed, this estimate must be an accurate count of elements that would be encountered by a complete traversal. Otherwise, this estimate may be arbitrarily inaccurate, but must decrease as specified across invocations of trySplit().

import java.util.Spliterator;
import java.util.HashSet;
import java.util.Collections;

public class SampleClass{

  public static void main(String[] args){
  
    HashSet<Integer> ar =
    new HashSet<>();
    
    Collections.addAll(ar,1,2,3,4,5,6,7,8
    ,9,10,11,12,13,14,15);
    
    Spliterator<Integer> st1 =
    ar.spliterator();
    
    if(!st1.hasCharacteristics
       (Spliterator.SUBSIZED))
       System.out.println("This spliterator is "
       +"not SUBSIZED.\nEstimate size may be"+
       " inacurrate after split.");
      
    
    System.out.println("st1 size before "+
    "split: " + st1.estimateSize());
    
    Spliterator<Integer> st2 =
    st1.trySplit();
    
    System.out.println("st1 size after "+
    "split: " + st1.estimateSize());
    
    st1.forEachRemaining(
	(e) -> System.out.println("st1: " + e + " "));
    
    st2.forEachRemaining(
	(e) -> System.out.println("st2: " + e + " "));
  }
}

Result(Result may vary)
This spliterator is not SUBSIZED.
Estimate size may be inaccurate after split.
st1 size before split: 15
st1 size after split: 7
st2: 1
st2: 2
st2: 3
st2: 4
st2: 5
st2: 6
st2: 7
st2: 8
st2: 9
st2: 10
st2: 11
st2: 12
st2: 13
st2: 14
st2: 15

In the example above, trySplit() didn't split st1 because the spliterator is not ORDERED. It means that st1 size after split was innacurate. st1 size after split was innacurate because the spliterator is not SUBSIZED. Take a look at this next example.

import java.util.Spliterator;
import java.util.ArrayList;
import java.util.Collections;

public class SampleClass{

  public static void main(String[] args){
  
    ArrayList<Integer> ar =
    new ArrayList<>();
    
    Collections.addAll(ar,1,2,3,4,5,6,7,8
    ,9,10,11,12,13,14,15);
    
    Spliterator<Integer> st1 =
    ar.spliterator();
    
    if(st1.hasCharacteristics
       (Spliterator.SUBSIZED))
       System.out.println("This spliterator is "
       +"SUBSIZED.");
      
    
    System.out.println("st1 size before "+
    "split: " + st1.estimateSize());
    
    Spliterator<Integer> st2 =
    st1.trySplit();
    
    System.out.println("st1 size after "+
    "split: " + st1.estimateSize());
    
    st1.forEachRemaining(
	(e) -> System.out.println("st1: " + e + " "));
    
    st2.forEachRemaining(
	(e) -> System.out.println("st2: " + e + " "));
  }
}

This spliterator is SUBSIZED.
st1 size before split: 15
st1 size after split: 8
st1: 8
st1: 9
st1: 10
st1: 11
st1: 12
st1: 13
st1: 14
st1: 15
st2: 1
st2: 2
st2: 3
st2: 4
st2: 5
st2: 6
st2: 7

In this example above, the spliterator is SUBSIZED. Thus, st1 size after the split is accurate.

getExactSizeIfKnown() Method

Convenience method that returns estimateSize() if this Spliterator is SIZED, else -1.

import java.util.Spliterator;
import java.util.HashSet;
import java.util.Collections;

public class SampleClass{

  public static void main(String[] args){
  
    HashSet<Integer> ar =
    new HashSet<>();
    
    Collections.addAll(ar,1,2,3,4,5,
                          6,7,8,9,10);
    
    Spliterator<Integer> st1 =
    ar.spliterator();
    
    if(!st1.hasCharacteristics
       (Spliterator.SUBSIZED))
       System.out.println("This spliterator is "
       +"not SUBSIZED.\nSplitted spliterators off"
       +"\nof this spliterator are not SIZED and SUBSIZED.");
    
    long result = st1.getExactSizeIfKnown();
    System.out.println("st1 size: " + result);
    
    Spliterator<Integer> st2 =
    st1.trySplit();
    
    result = st2.getExactSizeIfKnown();
    
    System.out.println("st2 size: " + result);
  }
}

Result
This spliterator is not SUBSIZED.
Splitted spliterators off
of this spliterator are not SIZED and SUBSIZED.
st1 size: 10
st2 size: -1

getComparator() Method

Method form: default Comparator<? super T> getComparator()
If this Spliterator's source is SORTED by a Comparator, returns that Comparator. If the source is SORTED in natural order, returns null. Otherwise, if the source is not SORTED, throws IllegalStateException.

import java.util.TreeSet;
import java.util.ArrayList;
import java.util.Spliterator;
import java.util.Collections;

public class SampleClass{

  public static void main(String[] args){
  
    TreeSet<Integer> ts =
    new TreeSet<>(Collections.reverseOrder());
    
    Collections.addAll(ts,1,2,3,4,5);
    
    Spliterator<Integer> st =
    ts.spliterator();
    
    ArrayList<Integer> ar =
    new ArrayList<>();
    
    Collections.addAll(ar,6,7,8,9,10);
    Collections.sort(ar, st.getComparator());
    
    System.out.println("TreeSet Elements...");
    while(st.tryAdvance((e) -> 
      System.out.print(e + " ")));
    
    System.out.println();
    
    System.out.println("ArrayList Elements...");
    for(Integer i : ar)
      System.out.print(i + " ");
  }
}

Result
Treeset Elements...
5 4 3 2 1

ArrayList Elements...
10 9 8 7 6

OfDouble, OfInt, OfLong and OfPrimitive

Spliterator.OfDouble, Spliterator.OfInt and Spliterator.OfLong are spliterators that specialize in double, int and long primitive types respectively. This spliterators improve performance for processing primitive types.

This example demonstrates Spliterator.OfInt

import java.util.Spliterator;
import java.util.Arrays;
import java.util.function.Consumer;

public class SampleClass{

  public static void main(String[] args){
  
    int[] ints = {1,2,3,4,5};
    
    Spliterator.OfInt so =
    Arrays.stream(ints).spliterator();
    
    Consumer<Integer> cons =
    (e) -> System.out.print((e*e) + " ");
    
    while(so.tryAdvance(cons));
  }
}

Result
1 4 9 16 25

In the example above, we use a Consumer functional interface. This interface wraps primitive types to their respective wrapper classes, which may undermine the performance boost of these specialized spliterators. If wrapper classes are not necessary in our program, we can drop them.

There are functional interfaces that don't wrap primitives into their respective wrapper classes. For int primitive, we can use the IntConsumer functional interface.

import java.util.Spliterator;
import java.util.Arrays;
import java.util.function.IntConsumer;

public class SampleClass{

  public static void main(String[] args){
  
    int[] ints = {1,2,3,4,5};
    
    Spliterator.OfInt so =
    Arrays.stream(ints).spliterator();
    
    IntConsumer ic =
    (e) -> System.out.print((e*e) + " ");
    
    while(so.tryAdvance(ic));
  }
}

Result
1 4 9 16 25

tryAdvance() of Spliterator.OfInt accepts Consumer and IntConsumer because in Spliterator.OfInt, tryAdvance() has this form:
tryAdvance(Consumer<? super Integer> action)

ALso, Spliterator.OfDouble, Spliterator.OfInt and Spliterator.OfLong extend OfPrimitive interface. OfPrimitive has this form of tryAdvance:
boolean tryAdvance(T_CONS action)
According to the documentation, T_CONS is the type of primitive consumer. The type must be a primitive specialization of Consumer , such as IntConsumer for Integer.

These two forms can create an ambiguity. Take a look at this example:

import java.util.Spliterator;
import java.util.Arrays;
import java.util.function.IntConsumer;

public class SampleClass{

  public static void main(String[] args){
  
    int[] ints = {1,2,3,4,5};
    
    Spliterator.OfInt so =
    Arrays.stream(ints).spliterator();
    
    while(so.tryAdvance((e) -> 
    System.out.print((e*e) + " ")));
  }
}

Result
error: reference to tryAdvance is ambiguous...

 both method tryAdvance(IntConsumer) in OfInt
 and method 
 tryAdvance(Consumer<? super Integer>)
 in OfInt match

forEachRemaining() is available to these specialized spliterators and forEachRemaining() of these specialized spliterators is also optimized for primitive types just like tryAdvance().