com.ibm.wala.util.graph.traverse
Class DFSDiscoverTimeIterator<T>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractList<E>
          java.util.Vector<E>
              java.util.Stack<T>
                  com.ibm.wala.util.graph.traverse.DFSDiscoverTimeIterator<T>

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<T>, java.util.Collection<T>, java.util.Iterator<T>, java.util.List<T>, java.util.RandomAccess

Direct Known Subclasses:

NumberedDFSDiscoverTimeIterator, SlowDFSDiscoverTimeIterator

public abstract class DFSDiscoverTimeIterator<T>
extends java.util.Stack<T>
implements java.util.Iterator<T>

This class implements depth-first search over a NumberedGraph, return an enumeration of the nodes of the graph in order of increasing discover time. This class follows the outNodes of the graph nodes to define the graph, but this behavior can be changed by overriding the getConnected method.

See Also:

Serialized Form

Field Summary

Fields inherited from class java.util.Vector

capacityIncrement, elementCount, elementData

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

DFSDiscoverTimeIterator()

Method Summary

protected abstract java.util.Iterator<? extends T>	getConnected(T n) get the out edges of a given node
protected abstract java.util.Iterator<? extends T>	getPendingChildren(T n) Method getPendingChildren.
boolean	hasNext() Return whether there are any more nodes left to enumerate.
protected void	init(java.util.Iterator<? extends T> nodes) subclass constructors must call this!
protected void	init(T N) subclass constructors must call this!
T	next() Find the next graph node in discover time order.
void	remove()
protected abstract void	setPendingChildren(T v, java.util.Iterator<? extends T> iterator) Method setPendingChildren.
protected void	visitEdge(T from, T to)

Methods inherited from class java.util.Stack

empty, peek, pop, push, search

Methods inherited from class java.util.Vector

add, add, addAll, addAll, addElement, capacity, clear, clone, contains, containsAll, copyInto, elementAt, elements, ensureCapacity, equals, firstElement, get, hashCode, indexOf, indexOf, insertElementAt, isEmpty, lastElement, lastIndexOf, lastIndexOf, remove, remove, removeAll, removeAllElements, removeElement, removeElementAt, removeRange, retainAll, set, setElementAt, setSize, size, subList, toArray, toArray, toString, trimToSize

Methods inherited from class java.util.AbstractList

iterator, listIterator, listIterator

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.List

iterator, listIterator, listIterator

Constructor Detail

DFSDiscoverTimeIterator

public DFSDiscoverTimeIterator()

Method Detail

init

protected void init(java.util.Iterator<? extends T> nodes)

subclass constructors must call this!

Parameters:

G -

nodes -

init

protected void init(T N)

subclass constructors must call this!

hasNext

public boolean hasNext()

Return whether there are any more nodes left to enumerate.

Specified by:

hasNext in interface java.util.Iterator<T>

Returns:

true if there nodes left to enumerate.

getPendingChildren

protected abstract java.util.Iterator<? extends T> getPendingChildren(T n)

Method getPendingChildren.

Returns:

Object

setPendingChildren

protected abstract void setPendingChildren(T v,
                                           java.util.Iterator<? extends T> iterator)

Method setPendingChildren.

Parameters:

v -

iterator -

next

public T next()
       throws java.util.NoSuchElementException

Find the next graph node in discover time order.

Specified by:

next in interface java.util.Iterator<T>

Returns:

the next graph node in discover time order.

Throws:

java.util.NoSuchElementException

getConnected

protected abstract java.util.Iterator<? extends T> getConnected(T n)

get the out edges of a given node

Parameters:

n - the node of which to get the out edges

Returns:

the out edges

remove

public void remove()
            throws UnimplementedError

Specified by:

remove in interface java.util.Iterator<T>

Throws:

UnimplementedError

See Also:

Iterator.remove()

visitEdge

protected void visitEdge(T from,
                         T to)