com.jrockit.mc.flightrecorder.util
Class PriorityIterator<Type>

java.lang.Object
  com.jrockit.mc.flightrecorder.util.PriorityIterator<Type>

All Implemented Interfaces:

java.util.Iterator<Type>

public final class PriorityIterator<Type>
extends java.lang.Object
implements java.util.Iterator<Type>

interface that takes an array of k iterators and iterates over them in a prioritized order.

The priority order for a given object returned from iterator.next() is determined by a PriorityProvider. Advantages compared to iterating through all iterators and putting the result in a large array and sort it is:

Less allocation and space requirements, O(k) instead of O(n), if merge sort(Arrays.sort()) is used.

Reduced time complexity, O(k) log(n) instead of O(n) log(n) for merge sort.

Better cache locality compared to sorting with radix sort even though it has better time complexity.

k = number of iterator to prioritize from
n = total number of elements

Uses a priority heap to keep track of what iterator has the current highest value for iterator.next().

Author:

Erik Gahlin

Constructor Summary

PriorityIterator(java.util.List<java.util.Iterator<Type>> iterators, IPriorityProvider<Type> provider)

PriorityIterator(java.util.List<java.util.Iterator<Type>> iterators, java.util.List<IPriorityProvider<Type>> provider)
Constructs a PrioriteryIterator

Method Summary

boolean	hasNext() Returns true if the iterator has another element.
Type	next() Returns the iterator.next() value from the iterator with the highest priority.
void	remove() Remove is not supported.

Methods inherited from class java.lang.Object

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

Constructor Detail

PriorityIterator

public PriorityIterator(java.util.List<java.util.Iterator<Type>> iterators,
                        java.util.List<IPriorityProvider<Type>> provider)

Constructs a PrioriteryIterator

Parameters:

iterators - the iterator to pick values from in a priority way

PriorityIterator

public PriorityIterator(java.util.List<java.util.Iterator<Type>> iterators,
                        IPriorityProvider<Type> provider)

Method Detail

remove

public void remove()

Remove is not supported.

Specified by:

remove in interface java.util.Iterator<Type>

hasNext

public boolean hasNext()

Returns true if the iterator has another element.

Specified by:

hasNext in interface java.util.Iterator<Type>

next

public Type next()

Returns the iterator.next() value from the iterator with the highest priority.

Specified by:

next in interface java.util.Iterator<Type>