Notes

Notes on modifying objects to make it possible to iterate over and through them.

Iterable vs Iterator

Iterable is a generic approach to getting an iterator. It enables an object to support for-each syntax. It is not concerned with how the iterator works, where it starts or stops, etc. It just returns the iterator. If you implement Iterable<E> you just need to be able to provide an Iterator<E>.

Java API Docs: Iterable: http://docs.oracle.com/javase/7/docs/api/java/lang/Iterable.html

Iterator<E> iterator()

An Iterator provides you with an actual object interface that makes it work like a scanner - hasNext(), next(), remove(). It is nicer but it takes more work - you gotta define your own class that extends the iterator class.

Java API Docs: Iterator: https://docs.oracle.com/javase/7/docs/api/java/util/Iterator.html

boolean hasNext()
E next()
void remove()

Implementation - Unsorted Table Map

See Maps/UnsortedTableMap for another example of iterables/iterators in action. This class requires defining three pairs of classes: Iterator and Iterable objects for keys, values, and key-value pairs.

Implementation - Tree Iterator

Overview

The implementation of a tree iterator will begin by defining a high-level abstract interface called Tree, which implements the Iterable interface.

The Tree accepts a generic type E of data. It utilizes a Position class internally to keep track of the organization of the elements of type E in the tree.

The Tree<E> class extends the Iterable<E> class, which means it is required to implement an iterator() method that returns an object of type Iterator<E>:

public interface Tree<E> extends Iterable<E> {
        public Iterator<E> iterator();
	public Iterable<Position<E>> positions();
}

As noted above, an Iterator is a full fledged wrapper object that works like a scanner - next, hasNext, remove, etc. The Iterable is a more dumbed down, straight-up iterable container. The whole iterable thing, all at once.

Here, we implement the iterator() second, and the positions() iterable container of Position objects first.

Positions iterable container

public class LinkedBinTree<E> implements Tree<E> {

	/** Define a method that returns an iterable Position pointer that 
	 * iterates through the tree in the specified order. */
	public Iterable<Position<E>> positions() { return preorder(); }


	/** Pre-order tree traversal. 
	 *
	 * This returns an iterable.
	 * Pre-order means the visit action is performed on the node
	 * before any of its children are visited. 
	 * This is a recursive method. */ 
	public Iterable<Position<E>> preorder() {
		List<Position<E>> snapshot = new LinkedList<Position<E>>();
		preorderSubtree(root(), snapshot);
		return snapshot;
	}

	/** Preorder traversal, with a specific subtree. */
	public Iterable<Position<E>> preorder(Position<E> p) {
		List<Position<E>> snapshot = new LinkedList<Position<E>>();
		preorderSubtree(p, snapshot);
		return snapshot;
	}

	/** Utility method for pre-order tree traversal. */
	private void preorderSubtree(Position<E> p, List<Position<E>> snapshot) { 
		// Base case is, no children, no loop.
		// Recursive case is, this will be called on child nodes.

		// 1. Perform visit action for Position p
		snapshot.add(p);

		// 2. Recurse through children
		for(Position<E> c : children(p)) {
			preorderSubtree(c,snapshot);
		}
	}

Element iterator class

Now that we have a way of obtaining each individual Position object representing positions in the tree, we can visit each position of the tree in whichever order we wish (preorder or postorder, see Trees and Trees/Preorder and Trees/Postorder for details). We can wrap that iterable container with a simple object that provides the Iterator interface, and runs the method to get the data stored at a particular position in the tree.

	// This uses the positions() method and traversals we defined above.

	/** Element iterator class for iterating over elements, rather than positions, in a tree. */
	private class ElementIterator implements Iterator<E> {
		Iterator<Position<E>> piter;
		public ElementIterator() { 
			piter = positions().iterator();
		}
		/** Returns true if there is a next position. */
		public boolean hasNext() { return piter.hasNext(); }
		/** Returns the element at the next node in the tree. */
		public E next() { return piter.next().getElement(); }
		/** Removes the selected position from the tree - yikes. */
		public void remove() { piter.remove(); }
	}

	/** Define the Linked Binary Tree iterator to be 
	 * an element iterator, not a position iterator. */
	public Iterator<E> iterator() { return new ElementIterator(); }

Java/Iterable

From charlesreid1

Contents