Defining Iterators

 

Python

Java

 

By convention, the iter() method returns an iterator on an iterable object.  The user of an iterator can expect the method next() to return the next object in an iteration, until next raises a StopIteration exception.  At that point, one closes the iterator using the close() method.

 

Let us assume that the LinkedStack class now includes an iter method.  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

 

 

 

 

The iterator() method returns an iterator on an iterable object.  The user of an iterator can expect the method next() to return the next object in an iteration, while the method hasNext() returns True. 

 

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;

        }

    }

}

 

 

 

Previous

Index

Next