java.lang.Object
net.i2p.router.util.RandomIterator<E>
Type Parameters:
E - type of elements returned by this iterator
All Implemented Interfaces:
Iterator<E>
public class RandomIterator<E>extends Object implements Iterator<E>
Random iterator for efficient early-termination iteration over collections.

Provides random iteration over a list with the ability to stop iteration early when a condition is met. This can provide significant performance improvements over Collections.shuffle() when the iteration process may terminate before processing all elements.

Uses BitSet for tracking served items and I2P RandomSource for better randomness distribution. Includes Android compatibility workarounds and proper bounds checking to prevent infinite loops.

Performance characteristics:

  • O(N) time complexity for iteration setup
  • O(1) average time for next() calls
  • Memory efficient with minimal object allocation

Note: Not recommended for small lists or when iterating through a large portion of a collection. Use Collections.shuffle() for those cases instead.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private static final boolean
    HAS_ANDROID_BUG
    True on the Android versions whose bit operations are broken.
    private final List<E>
    list
    The list being traversed in random order.
    private final int
    LIST_SIZE
    Size of that list.
    private int
    lower
    Used to narrow the range to take random indexes from.
    private final Random
    rand
    The random number generator has a great influence on the running time of this iterator.
    private final BitSet
    served
    Mapping indicating which items were served (by index).
    private int
    servedCount
    The amount of items served so far.
    private int
    upper
    How many of the remaining elements may still be picked.

  • Constructor Summary

    Constructors
    Constructor
    Description
    RandomIterator(List<E> list)
    Fixes the index range from the list size and marks nothing as served yet.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    hasNext()
    Whether the next random element is present.
    E
    next()
    Return the next random element.
    private int
    nextClearBit(int n)
    Workaround for bug in Android (ICS only?) http://code.google.com/p/android/issues/detail?id=31036
    private int
    previousClearBit(int n)
    Finds the last unset bit at or below a position.
    void
    remove()
    Removal is not supported.
    private static void
    testAndroid()
    Test case from android ticket above.

    Methods inherited from class Object

    clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface Iterator

    forEachRemaining

  • Field Details

    • served

      private final BitSet served
      Mapping indicating which items were served (by index). if served[i] then the item with index i in the list has already been served.

      Note it is possible to save memory here by using BitSet rather than a boolean array, however it will increase the running time slightly.

    • servedCount

      private int servedCount
      The amount of items served so far.

    • list

      private final List<E> list
      The list being traversed in random order.

    • LIST_SIZE

      private final int LIST_SIZE
      Size of that list.

    • rand

      private final Random rand
      The random number generator has a great influence on the running time of this iterator.

      See, for instance, Michael Brundage's random number generation essay for some implementations, which are faster than java.util.Random. This is the shared Random; the JVM may substitute a faster implementation on this platform.

    • lower

      private int lower
      Used to narrow the range to take random indexes from.

    • upper

      private int upper
      How many of the remaining elements may still be picked.

    • HAS_ANDROID_BUG

      private static final boolean HAS_ANDROID_BUG
      True on the Android versions whose bit operations are broken.

  • Constructor Details

    • RandomIterator

      public RandomIterator(List<E> list)
      Fixes the index range from the list size and marks nothing as served yet.
      Parameters:
      list - the list to iterate over, whose size fixes the index range; it is not copied, so later changes to its size are not seen

  • Method Details

    • hasNext

      public boolean hasNext()
      Whether the next random element is present.
      Specified by:
      hasNext in interface Iterator<E>
      Returns:
      whether next is present

    • next

      public E next()
      Return the next random element.
      Specified by:
      next in interface Iterator<E>

    • previousClearBit

      private int previousClearBit(int n)
      Finds the last unset bit at or below a position.
      Parameters:
      n - the position to search down from
      Returns:
      the highest unset bit at or below n

    • nextClearBit

      private int nextClearBit(int n)
      Workaround for bug in Android (ICS only?) http://code.google.com/p/android/issues/detail?id=31036
      Parameters:
      n - the index to start searching from
      Returns:
      the first unserved index at or after n, -1 if there is none

    • remove

      public void remove()
      Removal is not supported.
      Specified by:
      remove in interface Iterator<E>
      Throws:
      UnsupportedOperationException - always, as this iterator is not mutable

    • testAndroid

      private static void testAndroid()
      Test case from android ticket above.