Defining Iterators

Let us assume that the LinkedStack class now includes an itermethod.  Then one can visit the objects in a stack, from top to bottom, in either of the following ways:

stack = LinkedStack()
i = stack.iter()
while True:
    try:
        element = i.next()
        # process element
    except StopIteration:
        i.close()
        break
for element in stack:
    # process element

The iter method actually builds and returns a generator object.  The code for this object executes in a separate process running concurrently with the process that uses the iterator.  A generator object can maintain state, such as a current position pointer to the elements in the collection.  This reference in the current example is initially to the first node in the stack’s linked list.  The generator’s code also executes a while True loop.  If the current position equals None, then the last node has been passed and the generator raises a StopIteration exception.  Otherwise, the generator yields the element at the current node.  The yield statement pauses the execution of the process executing the generator’s code until the method next() is called.  This method returns the element just yielded.  When control returns to the generator object, the current pointer is set to the next field of the current node.  The generator’s process runs forever, unless the user calls its close() method.

Example:

class OneWayNode:

    def __init__(self, data, next):
        self.data = data
        self.next = next

class LinkedStack:

    def __init__(self):
        self.items = None
        self.size = 0

    def push(self, element):
        self.items = OneWayNode(element, self.items)
        self.size += 1

    def pop(self):
        element = self.items.data
        self.items = self.items.next
        self.size -= 1
        return element

    def peek(self):
        return self.items.data

    def isEmpty(self):
        return len(self) == 0

    def __len__(self):
        return self.size

    def __iter__(self):
        curPos = self.items
        while True:
            if curPos is None:
                raise StopIteration
            yield curPos.data
            curPos = curPos.next

Let us assume that the LinkedStack class now includes an iterator method. Then one can visit the objects in a stack, from top to bottom, in either of the following ways:

TrueStack<String> stack = new LinedStack<String>();
i = stack.iterator();
while (i.hasNext()){
    String element = i.next()
    // process element
}

for (String element : stack)
    # process element

The implementing class defines an iterator() method that returns an instance of an inner class.  This class implements the Iterator interface.  Its methods next() and hasNext() track a current position pointer to the elements in the collection.

Note that several iterators may be open concurrently on the same collection.  To maintain the consistency of each iterator with the collection’s data, collection-based modifications (push, pop) are not allowed during the operation of any iterator.  The collection now maintains a count of its modifications. When an iterator is instantiated, it sets its own count of modifications to the collection’s count.  On each call of the next() method, the iterator compares the two counts.  If they are not the same, a collection-based modification has occurred and an exception is thrown.

Example:

import java.util.iterator;

public class LinkedStack<E> implements TrueStack<E>{

    private OneWayNode<E> items;
    private int size;
    private int modCount;

    public LinkedStack(){
        this.items = null;
        this.size = 0;
        this.modCount = 0;
    }

    public void push(E element){
        this.items = new OneWayNode<E>(element, items);
        this.size += 1;
        this.modCount += 1;
    }
   
    public E pop(){
        E element = this.items.data;
        this.items = this.items.next;
        this.size -= 1;
        this.modCount += 1;
        return element;
    }

    public E peek(){
        return this.items.data;
    }

    public boolean isEmpty(){
        return this.size() == 0;
    }

    public int size(){
        return this.size;
    }

    public Iterator<E> iterator(){
        return new StackIterator<E>();                
    }

    private class StackIterator<E> implements Iterator<E>{

        private OneWayNode curPos;
        private int curModCount;

        private StackIterator(){
            this.curPos = items;
            this.curModCount = modCount;
        }

        public boolean hasNext(){
            return curPos != null;
        }

        public E next(){
            if (! this.hasNext()
                throw new IllegalStateException();
            if (this.curModCount != modCount)
                throw new ConcurrentModificationException()
            E data = this.curPos.data;
            this.curPos = this.curPos.next();
            return data;
        }

        public void remove(){
            throw new UnsupportedOperationException();
        }
    }                                

    private class OneWayNode<E>{

        private E data;
        private OneWayNode next;

        private OneWayNode(E data, OneWayNode next){
            this.data = data;
            This.next = next;
        }
    }
}