net.i2p.router.util
Class RandomIterator<E>

java.lang.Object
  extended by net.i2p.router.util.RandomIterator<E>
All Implemented Interfaces:
Iterator<E>

public class RandomIterator<E>
extends Object
implements Iterator<E>

This is some Java code I wrote for a school project to save some time when iterating in random order over a part of list (until some condition becomes true): Here is a sample on how to use the code:

        for(Iterator iter = new RandomIterator(myObjList); iter.hasNext();){
            Object o = iter.next();
            if(someCondition(o) )
                return o; // iteration stopped early
        }
    

 I wrote it to replace a Collection.shuffle call and this code gave us an overall increase in program execution speed of about 25%.
 As the javadoc description says, you are better off calling Collection.shuffle if you need to iterate over the entire list. But if you may stop early this class can save you some time, as it did in our case.

 Provides a random iteration over the given list.

 This effect can be achieved by using Collections.shuffle,
 which shuffles the entire collection in linear time.

 If the iteration process may end before all items
 are processed, this class may give a speed increase
 because the shuffling process is performed as items are requested
 rather than in the beginning.

 I2P changes:
   - Use BitSet instead of boolean[]
   - Use I2P RandomSource
   - Done check in next(), throw NSEE
   - Ensure lower and upper bounds are always clear
   - Replace unbounded loop in next(). It is now O(N) time, but now
     the iterator will tend to "clump" results and thus is not truly random.
     *** This class is not recommended for small Lists,
     *** or for iterating through a large portion of a List.
     *** Use Collections.shuffle() instead.
   - Add test code


Constructor Summary
RandomIterator(List<E> list)
           
 
Method Summary
 boolean hasNext()
           
 E next()
           
 void remove()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

RandomIterator

public RandomIterator(List<E> list)
Method Detail

hasNext

public boolean hasNext()
Specified by:
hasNext in interface Iterator<E>

next

public E next()
Specified by:
next in interface Iterator<E>

remove

public void remove()
Specified by:
remove in interface Iterator<E>
Throws:
UnsupportedOperationException - always